Deep Reinforcement Learning for Autonomous Collision Avoidance

Bachelor’s degree thesis Deep Reinforcement Learning for Autonomous Collision Avoidance Jon Liberal Huarte Work advised by: Ming Liu (HKUST) Vicen¸c Puig Cayuela (UPC) In partial fulfillment of the requirements for the Bachelor’s degree in Mathematics Bachelor’s degree in Industrial Engineering Technologies May 2020 ii Abstract Deep Reinforcement Learning for Autonomous Collision Avoidance by Jon Liberal Huarte Collision avoidance is a complicated task for autonomous vehicle control. Most traditional methods in this area consist on model-based solutions, where an understanding of vehicle dynamics and an accurate model of vehicle behavior is required, in order to predict the trajectory of the controlled car and the surrounding vehicles. Such solutions struggle to anticipate and explicitly model surrounding car driving behavior. This work investigates a model-free Deep Reinforcement Learning based method for collision avoidance, where the agent processes the distances to the closest entities and outputs the steering angle and acceleration required to avoid collisions. A traffic simulator is used to generate a wide range of roads and vehicles, which will interact - not always compliantly - with the learning agent allowing it to collect learning experience. After being trained on such conditions, the agent shows intelligent driving behavior, avoiding areas with high traffic density, adapting its speed to avoid rear or front crashes, and steering when necessary to avoid lateral crashes. Keywords: Autonomous driving, Deep Reinforcement Learning, Neural Networks, Robot Control, Collision Avoidance, Deep Deterministic Policy Gradients. MSC code: 93C85 iii Resumen Prevenci´on de colisiones en coches aut´onomos mediante aprendizaje por refuerzo por Jon Liberal Huarte La prevenci´on de colisiones es una tarea compleja en el control de veh´ıculos aut´onomos. Los m´etodos tradicionales utilizan modelos expl´ıcitos para predecir la din´amica de los veh´ıculos e intentar anticipar las decisiones de control de los conductores en el entorno. Estos modelos no siempre consiguen predecir con ´exito la trayectoria de los objectos din´amicos en el entorno del veh´ıculo controlado. Esta tesis investiga un m´etodo de control basado en el aprendizaje profundo por refuerzo. El agente procesa las distancias detectadas desde el veh´ıculo controlado a los objectos m´as cercanos, y mediante redes neuronales estima la acci´on de control ´optima para evitar colisiones. Para el aprendizaje, se dise˜na un simulador de tr´afico que genera un amplio rango de carreteras y veh´ıculos, que interact´uan - no siempre siguiendo las normas de circulaci´on - con el veh´ıculo de control, lo que permite al agente recabar informaci´on diversa y asociar a cada estado una acci´on de control que minimice el riesgo de colisi´on. Tras el entrenamiento, el agente demuestra haber aprendido a evitar circular en ´areas con alta densidad de tr´afico, a adaptar su velocidad para evitar colisiones frontales y traseras, y a realizar giros que eviten choques con veh´ıculos que se aproximan por los laterales. Palabras clave: Conducci´on Aut´onoma, Aprendizaje por Refuerzo Profundo, Redes Neuronales, Control Autom´atico, Prevenci´on de Colisiones, Deep Deterministic Policy Gradients. C´odigo MSC: 93C85 iv Acknowledgements First, I would like to thank my HKUST supervisor Ming Liu for inviting me to the Robotics and Multi-Perception Lab and for the opportunity to research a diverse range of robotics topics. I would also like to thank Jianhao Jiao for his help in the beginning of my stay, for providing me interesting research topics and supporting my research initiatives. I woud like to express my gratitude for Xiaodong Mei, who has advised me in discovering the field of Reinforcement Learning. Second, I am grateful for the support received from Prof. Vicen¸c Puig at UPC, who has offered his generous guidance during my stay at HKUST, and his feedback for this thesis. I would like to direct a heartfelt acknowledgement to CFIS. I sincerely value the trust that Fundaci´o Privada Cellex has placed in me and my fellow students during my studies at CFIS. Special thanks to Miguel ´ Angel Barja, for his eager willingness to help the students not only during our studies but also in our future endeavors. Furthermore, many thanks to Toni Pascual, who has followed with empathy and caring interest our stay in Hong Kong during these trying times. Lastly, I would like to thank my family for their cheerful support all these years. Jon Liberal Huarte Navarra, May 4, 2020 v Preface The work for this thesis has been conducting at the Robotics and Multi-Perception Lab at Hong Kong University of Science and Technology (HKUST). I have been able to investigate a wide range of Machine Learning and Robotics research areas: 1. Image stitching. The Waymo Open Dataset provides images recorded by its fleet of autonomous cars. For each timestep, a set of 5 images provides visual information from different angles, and Image Stitching methods provide a complete panorama image of the car surroundings. This was my work for the first month of my stay. 2. Reinforcement Learning for Robot Control. A novel learning by trial and error approach to the Collision Avoidance problem. It is the work presented in this thesis. For this project a new traffic simulator was created, which was the open sourced at [17]. My studies at UPC have proved to be essential to tackle the challenges that arised during the project. Specifically, the Mechanics, System Dynamics, Automatic Control, Machine Mechanisms Theory and Informatics courses in the Degree in Industrial Technology Engineering; and also the Statistics, Probability, Algorithmics, Calculus, Differential Geometry, Ordinary Differential Equations courses in the Degree in Mathematics. vi Contents List of Figures viii List of Acronyms ix 1 Introduction 1 1.1 Motivation for Deep Reinforcement Learning .................. 1 1.2 Application to Autonomous Driving ....................... 3 1.3 Document overview ................................ 4 2 Related work 5 2.1 Collision Avoidance for Mobile Robots ..................... 5 2.1.1 Virtual Force Field ............................ 5 2.1.2 Vector Field Histogram .......................... 6 2.1.3 Line Following ............................... 8 2.1.4 Conformal Lattice Planner ........................ 9 2.2 Deep Reinforcement Learning .......................... 10 2.2.1 Challenges in modern RL ........................ 10 2.2.2 State-of-the-art overview ......................... 11 3 Reinforcement Learning: essential concepts 14 3.1 Mathematical foundations ............................ 14 3.1.1 Markov Decision Process ......................... 14 3.1.2 Policies and rewards ........................... 16 3.2 Estimating the optimal policy .......................... 17 3.2.1 Q-learning ................................. 17 3.2.2 Policy gradients .............................. 20 4 Simulation 22 4.1 Kinematic Bycicle Model ............................. 22 4.1.1 Simplification hypothesis ......................... 22 4.1.2 Model description ............................ 23 4.1.3 Control variables and restrictions .................... 24 4.1.4 Simulation step .............................. 24 4.2 Simulated surrounding vehicle behaviour .................... 25 4.2.1 Behaviour planner ............................ 25 4.2.2 Low level control ............................. 26 4.3 Road generation and vehicle spawning ..................... 27 4.4 Agent-Environment Interaction ......................... 27 4.4.1 Interaction standards ........................... 27 4.4.2 State .................................... 28 4.4.3 Action ................................... 28 4.4.4 Reward .................................. 29 5 RL Implementation 31 5.1 Baseline for performance comparison ...................... 31 5.1.1 Problem formulation ........................... 31 5.1.2 Implementation .............................. 34 5.1.3 Baseline Performance ........................... 35 5.2 DRL for Collision Avoidance ........................... 37 5.2.1 Algorithm selection ............................ 37 5.2.2 System input and output ......................... 37 5.2.3 Problem Adaptation ........................... 38 5.3 Algorithm implementation and performance .................. 39 5.3.1 SAC .................................... 40 5.3.2 DDPG ................................... 42 6 Conclusions and future work 45 Bibliography 46 viii List of Figures 1.1 Moore’s Law. ................................... 2 2.1 Artificial Potential Field for air navigation ................... 6 2.2 Visual Representation of Vector Field Histogram ................ 7 2.3 Polar histogram generation ............................ 8 2.4 Line following obstacle avoidance ........................ 8 2.5 Conformal Lattice Planner ............................ 9 2.6 OpenAI Hide-and-Seek .............................. 11 2.7 Sample efficiency for Humanoid Locomotion Learning ............. 12 3.1 Agent-Environment Interaction in a Markov decision process. ......... 15 3.2 Pseudocode for Q-learning ............................ 19 4.1 Kinematic Bycicle Model ............................. 23 4.2 Examples of random road generation for simulation. .............. 27 4.3 Laser readings illustration ............................ 29 5.1 Trajectory collision checking ........................... 33 5.2 Conformal Lattice Planner impementation ................... 35 5.3 Conformal Lattice Planner maneauver example ................ 36 5.4 Conformal Lattice Planner failure example ................... 36 5.5 Soft Actor Critic (SAC) pseudocode ....................... 40 5.6 SAC performance with respect to training stage ................ 41 5.7 Deep Deterministic Policy Gradients (DDPG) pseudocode .......... 42 5.8 DDPG performance with respect to training stage ............... 43 5.9 DDPG sharp turn example ............................ 44 5.10 DDPG lane change example ........................... 44 5.11 DDPG traffic opening identification example .................. 44 ix List of Acronyms APF Artificial Potential Field CLP Conformal Lattice Planner DDPG Deep Deterministic Policy Gradients DNN Deep Neural Network DRL Deep Reinforcement Learning DL Deep Learning KBM Kinematic Bicycle Model MDP Markov Decision Process NN Neural Network PPO Proximal Policy Optimization RL Reinforcement Learning SAC Soft Actor Critic TRPO Trust Region Policy Optimization VFF Virtual Force Field VFH Vector Field Histogram 2.1. Collision Avoidance for Mobile Robots 7 Figure 2.2: Visual Representation of Vector Field Histogram, reprinted from [5] Visual Representation of Vector Field Histogram, reprinted from [5]. Directions facing obstacles A, B and C represent higher obstacle density in the histogram. VFH+ Presented in [30] as an improvement on VFH [5]. VFH+ is different from VFH mainly in the sense that it considers robot dynamics. This is important for our case as cars are non-holonomic vehicles. The histogram generated in VFH is modified to represent the obstacle density of each possible trajectory arc that the robot can perform. This modified histogram is restricted therefore by robot motion kinematics. The optimal steering direction is then selected by choosing the valley in the modified histogram (see histogram (c) in 2.3) that lays closest to the goal angle. This alternative fails to predict the motion of dynamic obstacles. 2.1. Collision Avoidance for Mobile Robots 8 (a) Example robot layout. (b) The 3 stages of polar histograms for VFH+ steering angle selection. Figure 2.3: Polar histogram generation from an example obstacle layout, reprinted from [30]. 2.1.3 Line Following These solutions [9,19,31] are more recent and more specific for autonomous driving vehicles. Reliable solutions have been proposed for road detection and line following in autonomous cars. Collision avoidance is then performed by identifying obstacles that obstruct the desired trajectory. (a) Laser sensor distribution. (b) Sequence of line following based obstacle avoidance Figure 2.4: Line following obstacle avoidance presented in Almasri et al, reprinted from [19]. In Almasri et a [19], a line following technique is presented for holonomic robots; line following 2.1. Collision Avoidance for Mobile Robots 9 is performed until front laser sensors detect an obstacle. In that case, the robot turns until laser sensor readings reach a safe threshold, and navigates around the object until returning to the reference line is possible. A careful tuning of each sensor threshold is required to achieve satisfactory obstacle avoidance. These line following based methods are design for static environments and also fail to anticipate dynamic obstacle motion. 2.1.4 Conformal Lattice Planner Perhaps a more driving specific method is the Conformal Lattice Planner [20]. Applied to the autonomous driving problem, this approach consists first on picking goal points that are laterally offset further down the road. Figure 2.5: Conformal Lattice Planner, reprinted from [32]. Then, a spline trajectory is computed from the car to each of the points (green points in Figure 2.5). A cost function evaluates the goodness of each of these trajectories, according to criteria such as collision with obstacles, minimizing curvature, reducing drastic speed changes and distance to the reference line. Once the optimal trajectory is selected, the control action that corresponds to that trajectory is considered the optimal control input. Conformal Lattice Planner has been the main technique for planning these recent years, and can be considered state-of-the-art. However, it still requires dynamic object behavior modelling to anticipate obstacle motion in order to avoid collisions. As this is the approach that best relates to the task tackled in this work, Conformal Lattice Planner is the baseline used for performance comparison. 2.2. Deep Reinforcement Learning 10 2.2 Deep Reinforcement Learning The field of Deep Reinforcement Learning has become a considerable branch of Deep Learning research in recent years. The progress in supervised learning (image classification, object detection, medical diagnosis, Natural Language Processing, pose estimation, etc.) has outpaced the progress in Deep Reinforcement Learning. The idea that an initially clueless entity can learn the structure of a complex process just by interacting with such process is promising, yet challenging to implement, as many practical difficulties arise. 2.2.1 Challenges in modern RL The credit assignment problem It is not straightforward to attribute merit to the actions executed by the agent. Some actions might yield a reward long after they are executed. After performing a sequence of actions, the reward received cannot be certainly attributed to any action in particular. Standard Deep Reinforcement Learning (DRL) techniques tend to be error prone in environments with delayed rewards (like Go, or chess). Estimating which actions to reinforce therefore requires more sophisticated methods. The exploration-exploitation trade off This trade-off is not only specific to RL tasks. The exploration-exploitation trade-off is studied in human cognitive psychology [27,4], and arises whenever a subject needs to choose between acquiring new information, or settling for the best-so-far option. As a relatable example, the exploration-exploitation trade-off arises whenever a person is at a restaurant and doubts between the dish that she likes best so far, and a dish she has never tried before. In RL, if the agent is only driven by maximizing environment rewards, it might settle for suboptimal actions early in the training process, renouncing to explore better actions that are incorrectly estimated to be less profitable. On the other hand, strongly motivating it to explore might lead to failed training convergence, as the actions executed might be too random to extract useful information about the environment. For complex environments, the state space is just too broad. It is not computationally feasible to explore the whole state and action space, the agent must restrict itself to a relatively small set of spaces. Balancing how much the agent should explore is key to satisfactory training. 2.2. Deep Reinforcement Learning 11 Reward shaping Each DRL application consists of a human goal. Transferring this goal from words to a consistent reward is challenging. If the reward is not aligned with the original human goal, the agent might find alternative ways to maximize the reward without actually fulfilling its original task. For example, it might find inconsistencies in the training simulators (such as in OpenAI Hide and Seek [3]), or glitches in the reward systems. Figure 2.6: In OpenAI Hide-and-Seek [3], the seekers exploit a bug in the physics engine that enables them to surf boxes to jump into the hiders’ shelter. Automatic reward shaping has been studied [11], but so far it is not considered to be applicable for most approaches. For most DRL problems, rewards are specifically designed by researchers. For this thesis, this is also the case. Sample inefficiency Training experience is needed for any Reinforcement Learning training task. Such experience is usually obtained by simulation. Some off-policy algorithms theoretically allow to reuse training samples, but even so, DRL algorithms reuse samples dramatically less than other Deep Learning methods, where the training runs through the complete dataset at each epoch. Improving sample efficiency has been a major goal for recent research, some DRL algorithms (such as Soft Actor Critic (SAC)) show outstanding efficiency improvements. 2.2.2 State-of-the-art overview A variety of techniques have succeeded to solve a diverse range of problems. The following methods are considered the current state-of-the-art DRL techniques: 2.2. Deep Reinforcement Learning 12 Figure 2.7: Sample efficiency of several DRL algorithms for Humanoid Locomotion Learning, reprinted from [28]. Soft Actor Critic Actor-Critic methods consist of two separate models; the Actor, that decides on the optimal action, and the Critic, which evaluates how good that action is . Haarnoja et al [28] published a variant of Actor-Critic methods that motivate action space exploration. First, SAC is similar to Deep Deterministic Policy Gradients (DDPG) in the sense that both are designed for continous action spaces (which is our case). Therefore, the set of possible actions is no longer finite and discrete. The soft term in Soft Actor Critic refers to a tweak in the objective reward function: instead of greedily maximizing the expected reward, an entropy term is added to motivate action randomness when possible. The optimal action is no longer the one with the highest traditional Q-value, and actions that yield similar rewards but allow for greater variance in the action command are prioritised over actions that yield good results only in a narrow action range. This method is considered state-of-the-art for Reinforcement Learning application, specially when the action space is large, as in the Humanoid Locomotion problem, where there are 21 action dimensions. 2.2. Deep Reinforcement Learning 13 Proximal Policy Optimization Presented in Schulman et al[15], Proximal Policy Optimization (PPO) is based on Trust Region Policy Optimization (TRPO) theory [16]. The motivation is the following. When training Policy Gradients methods, it is common to see the performance of the agent collapse suddenly. This is attributed to the fact that weights in the policy network are repeatedly pushed out of the safe region where numerical stability is guaranteed, until network outputs reach a singularity and start outputting nonsense. TRPO is a Policy Gradients method that solves this stability issue by restricting weight updates to a trust region that can be computed for each sample. PPO is an approximation of TRPO that shares the idea of restricting weight update magnitude, while simplifying the implementation and keeping performance. Deep Deterministic Policy Gradients DDPG was presented in [29], as an adaptation of Q-learning methods to continous action spaces. The idea behind this approach is based on gradient ascent. As the action space is continuous, the Q function can be assumed to be differentiable with respect to the action space. Therefore, the gradient of the Q function with respect to the action at;∇atQ, can be used to estimate the direction from attowards the optimal action a∗ t. The policy network is therefore updated to progressively predict actions that lay closer to the optimal action a∗ tat each sample. 14 Chapter 3 Reinforcement Learning: essential concepts This chapter presents the most important elements of the RL framework. We first present a mathematical model of the general RL problem, then we go through the main elements in the RL framework. The last section explains the two main approaches for training policies towards optimal performance. 3.1 Mathematical foundations For the sake of mathematical tractability, it is useful to model the RL problem as a mathematically idealized form of such problem, for which precise theoretical statements can be made. We need a mathematical object that captures the set of states that can take place, the nature of the transitions between such states, and the rewards associated with such transitions. 3.1.1 Markov Decision Process A Markov Decision Process (Markov Decision Process (MDP)) is a discrete time stochastic control process, and provides a mathematical framework for modelling decision making, in situations where outcomes depend partially on the decision taken. First, an MDP consists of an Agent - Environment interface: •Agent: the learner and decision maker. 3.1. Mathematical foundations 15 •Environment: Everything outside the agent, everything that the agent interacts with. Figure 3.1: Agent-Environment Interaction in a Markov decision process. The interaction between the agent and its environment can be defined more specifically. At each time step, the agent receives a representation of its environment’s state, St∈ S. Based on that state, the agent selects an action At∈ A(St), where A(St) is the set of feasible actions at state St. As a result of the action selected, one time step later, the agent receives a numerical reward Rt+1 ∈ R, and finds itself in a new state St+1. Concatenating such interactions gives rise to a trajectory comprised of states, actions and rewards: S0, A0, R1, S1, A1, R2, ..., ST, AT, RT+1 This trajectory is not completely random. Performing a particular action at a particular state usually has an influence on the reward and new state that arise. Rtand Stare therefore random variables whose probability distributions depend on the preceding state and action. For any preceding state s∈ S and action a∈ A(s), the probability of reaching state s0∈ S and obtaining a reward r∈ R at the next time step is given by the probability distribution function p: p:S × R × S × A −→ R (s0, r, s, a)7→ P r(St=s0, Rt=r|St−1=s, At−1=a) It is worth noting that this function pcompletely defines the dynamics of the MDP. The RL training task therefore consists on estimating pby interacting with the environment 3.1. Mathematical foundations 16 and observing the transitions that take place. From p, we can also compute useful functions for our RL task. For example, we can compute an estimate of how good an action ais at a specific state s, by computing the expected immediate reward r(s, a): S × A −→ R, r(s, a):=E[Rt|St−1=s, At−1=a] = X r∈R rX s0∈S p(s0, r|s, a) 3.1.2 Policies and rewards Now that we have defined our MDP, it makes sense to define the decision taking function: the policy. A policy πis a function that evaluates the current state of the environment, and outputs the action that the agent should take. More formally, π:S −→ A. The RL agent needs to learn the optimal policy, the policy that, broadly speaking, maximizes some measure of the expected total reward. There are several options to define this measure. For example, we might aim to maximize only the immediate reward Rt+1, but this objective would result in a short-sighted greedy policy that prioritizes short term rewards at the cost of long term losses. A more sensible choice would be to aim to maximize the sum of rewards Gt, Gt:=Rt+1 +Rt+2 +Rt+3 +... However, Gtstill has some inconvenients. Firstly, in the case of infinite episodes, Gtmight fail to converge. Furthermore, it does not seem logical to consider that all rewards are equally important, regardless of how far down the road they are. The farther in the future a reward is, the more uncertain it is. Discounting the sum of rewards solves both issues, and gives place to a new discounted cumulative sum of rewards Gt Gt:=Rt+1 +γRt+2 +γ2Rt+3 +... = ∞ X k=0 γkRt+k+1 where γis the discount factor and is usually 0.9< γ < 0.999. The optimal policy is therefore π∗:= argmax π∈Π Eπ[Gt|St=s]∀s∈ S 4.1. Kinematic Bycicle Model 23 focusing only on kinematic restrictions. 4.1.2 Model description The continuous-time equations that describe vehicle motion are: ˙x=vcos(ψ+β) ˙y=vsin(ψ+β) ˙ ψ=v lr sin(β) ˙v=a β=tan−1lr lf+lr tan (δf) where vand aare the velocity and acceleration of the considered centre of the vehicle, respectively. Spatial and angular variables x, y, ψ, β, δfdescribe the position and configuration of the vehicle and are graphically explained in Figure 4.1. Lengths lfand lrare model identification parameters denoting the distance from vehicle center to front and rear axis, respectively. Figure 4.1: The Kinematic Bycicle Model, reprinted from [14] It is worth noting that the Kinematic Bycicle Model requires just 2 parameters (lfand lr) for model identification, which is typically an error prone stage of vehicle simulation. 4.1. Kinematic Bycicle Model 24 4.1.3 Control variables and restrictions Typically, u:= (δf, a) denotes the set of control input variables, as they determine vehicle motion. The steering angle δfis limited by the maximum steering angle restriction δmax such that −δmax < δf< δmax The increment of δfis also limited by δrate such that −δrate <∆δf< δrate Similarly for a, the Tire Force-Ellipse of the vehicle tires (see [25]) provides an acceptable range of accelerations amin, amax and hence amin < a < amax Excessive increments in acceleration can lead to mechanical damage and discomfort and is therefore limited by arate such that −arate <∆a<arate These restrictions are implemented in the simulator, limiting the control actions of the driving agent accordingly. 4.1.4 Simulation step The state of the vehicle is defined as: x:= (x, y, ψ, v) A simulation step consists of calculating the state of the vehicle xt+∆tgiven the state xtand control input ut.xt+∆tis computed using the Euler Method, which approximates f(xt+∆t)≈f(x) + f0(x)∆t 4.2. Simulated surrounding vehicle behaviour 25 Using the equations described in Section 4.1.2 and the Euler method lead to the following discrete-time model: xt+∆t≈xt+vcos(ψt+βt)∆t yt+∆t≈yt+vsin(ψt+βt)∆t ψt+∆t≈ψt+vt lr sin(βt)∆t vt+∆t≈vt+at∆t βt=tan−1lr lf+lr tan (δft) At each time step, the simulator will update the position of each simulated car according to the equations above. 4.2 Simulated surrounding vehicle behaviour In order to provide challenging traffic interactions to the RL agent, it is necessary to create a control method that directs surrounding cars along thoughout the driving environment. From now on, the term surrounding vehicle applies to any simulated vehicle that is not the ego vehicle, which is the vehicle controlled by the RL agent. 4.2.1 Behaviour planner We begin by defining the high-level control. The behaviour planner is in charge of assigning a lane to the surrounding vehicle. The low-level control will then be in charge of changing lanes or following the current lane. The behaviour planner is designed to perform unexpected lane-changes and driving maneauvers, in order to challenge the RLagent collision avoiding capacity. At each time step, the behaviour planner reevaluates the assigned lane of the controlled surrounding vehicle. Most of the times, the planner will decide to stay on the current lane. However, with relatively low probability , the vehicle will decide to execute an unexpected maneauver. This can be: •Lane-change: The planner will change the assigned lane to an adjacent lane, after checking that no other surrounding vehicles obstruct such change (note that it does not 4.2. Simulated surrounding vehicle behaviour 26 take into account the ego vehicle). •Speed update: Updating the desired update, either suddenly increasing, or decreasing it, to test the RL agent capacity. •Sudden stop: Unexpectedly braking and staying stopped until the episode ends. Such maneauvers will motivate the agent to develop collision avoidance capacity that can be extrapolated to other situations. 4.2.2 Low level control Executing high level behaviour planner commands requires a low level control that compares the current vehicle state xtto the reference and outputs concrete control commands. For such purpose, a line following PID control is considered to be sufficient. PID steering controller In order to describe the PID controller, one needs to define the Process Variable (PV), Controlled Variable (CV), and PID parameters: •Process Variable: The PV will be the distance to lane centerline of the controlled surrounding vehicle center. •Controlled Variable: The CV will be the steering angle δfof the controlled surrounding vehicle. •PID parameters: Arange of values for each parameter has been studied and has empirically proved to suffice to control the surrounding vehicle successfully. To favour experience randomization, each vehicle is created with a randomly sampled set of PID parameters from such range. The result is a line following steering controller that robustly performs turns and lane changes. PI cruise control Controlling vehicle speed is far more simple and a simple PI control is enough to attain the desired speed at each timestep. 4.3. Road generation and vehicle spawning 27 4.3 Road generation and vehicle spawning A richer range of roads, turns, lane number and turning angles is important to ensure that the agent is exposed to a wide variety of challenges. Each episode needs its own randomized environment. For each episode, A ∼200 m road track is created, with a random turn of angle ±80. The road will have a random number of lanes, from 1 to 4. The number of lanes random variable is more heavily shifted towards 2 lane roads, in order to match frequent real traffic environments. Figure 4.2: Examples of random road generation for simulation. The ego vehicle is generated at the start of the generated road, in a random lane. Afterwards, the surrounding vehicles are generated, collision free with each other and with the ego vehicle. While the episode lasts new surrounding vehicles are generated in the beginning of the road track to simulate real traffic flow. 4.4 Agent-Environment Interaction In this section we describe how the DRL agent interacts with the simulation environment. The simulator is designed following the OpenAI Gym standards (see [22]). 4.4.1 Interaction standards According to the industry DRL standards proposed by OpenAI, the agent-environment interaction can be conducted using an env Python objects that conforms to the standards specified in [22]. Such standards allow agile interchange of DRL training algorithms by abstracting the particular characteristics of our environment. More specifically, an example Python implementation of such interaction is detailed below: 1# reset environment to start a new episode 2s=env.reset() 4.4. Agent-Environment Interaction 28 3terminal =False 4# start 5while not terminal: 6# optional: visualize the simulation 7env.render() 8# Ask the RL Agent to select an action based on state s 9a=RL_Agent.select_action(s) 10 # run simulation step executing action a 11 s, reward, terminal, info =env.step(a) 12 13 env.close() The step() method provides the new state s, the transition reward reward, the Boolean terminal that specifies whether the episode has finished, an extra information info, which is irrelevant in our case. 4.4.2 State The state is the representation of the environment that the agent perceives. In our case, the states consists of nlaser distance readings, which measure the distance from the ego vehicle to the closest obstacle in each of the nequidistributed directions. An example for 8 lasers is shown in Figure 4.3. Formally, at time t, we can define the environment state stas the n-dimensional vector of distances measured by the nlasers in the ego vehicle. This state stwill be the environment representation provided in the env.step(action) method described in Section 4.4. 4.4.3 Action At each timestep, the environment asks the RL agent which action to execute. In our case, this is a control action. As described in Section 4.1.3, this action utcomprises the steering angle and motor acceleration to be executed. Formally, utis a 2-dimensional vector containing the desired (δf, a). The simulation environment will restrict the action suggested by the RL agent to the limits in value and change rate described in Section 4.1.3. 4.4. Agent-Environment Interaction 29 Figure 4.3: The case of 8 lasers (n= 8). In red, the laser readings that measure the distance from the ego vehicle (blue) to surrounding vehicles (green). 4.4.4 Reward The reward provided by the environment guides the RL agent training. Effective reward shaping is critical to align the learning goal of the RL agent with the human task accomplishment metric. For collision avoidance, the main goal is not to crash, and therefore it is straightforward to punish crashes with a strong negative reward. But this alone is not enough to achieve satisfactory driving behaviour. It is necessary to motivate the agent to advance towards the end of the road segment to complete the navigation task, otherwise, it might find spots on the road where it is relatively safe to stay stopped, avoiding collisions. As a result of this two simple goals (avoid collisions and complete the navigation task), the proposed reward metric is: rt=   Rcrash,if crashed at time t Rnavigate∆d, else where ∆drepresents the distance towards the end of the segment that the ego vehicle has advanced in the last time step. 4.4. Agent-Environment Interaction 30 Balancing Rcrash and Rnavigate is important to achieve a system that avoids collisions while still completing the navigation task successfully. For our implementation:    Rcrash =−4 Rnavigate = 0.01 31 Chapter 5 RL Implementation This chapter presents the proposed implementation for the RL agent training. First a DRL training algorithm is selected by evaluating which state-of-the-art algorithm is more suitable for the control task. Then, we describe an overview of the problems that arised during training, and workarounds around such problems. 5.1 Baseline for performance comparison In Chapter 2, the Conformal Lattice Planner method was described, presented as state-ofthe-art for autonomous driving planning. In this section, an implementation of this technique is implemented for our simulator. This will be useful to estimate the performance gain of the proposed RL technique with respect to the current Collision Avoidance techniques in the field. 5.1.1 Problem formulation Formally, Conformal Lattice Planner (CLP) is composed of several mathematical objects that are outlined below: 1. Ego-vehicle position x := (x, y, ψ, v) defined in Section 4.1. 2. Set of candidate goal points G. These points are considered at different road longitudes and are laterally offset to cover the range of future ego-vehicle positions. 3. Set of cubic splines S. A cubic spline is a parameterized curve s(u) = (x(u), y(u)) 5.1. Baseline for performance comparison 32 such that x(u) = a3u3+a2u2+a1u+a0 y(u) = b3u3+b2u2+b1u+b0 This set is associated to Gin the sense that for each goal point g,Scontains a spline sthat defines a smooth trajectory from current ego-vehicle position xto goal point g. Formally, ∀g∈ G,∃s∈ S |    s(0) = x s(1) = g   Each spline is computed by imposing boundary conditions at u= 0 and u= 1 such that the spline not only matches starting and ending point positions, but also such that the derivative of such spline matches the non-holonomic car motion restriction. Formally,                s(0) = (xego, yego) s0(0) = ~vego s(1) = g s0(0) = ~vroad                where ~vego is the ego-vehicle orientation vector and ~ vroad(g) is the vector parallel to the road at point g. 4. The objective function J(s) : S −→ R. This function aims to evaluate how satisfactory each possible trajectory. Common goals for standard autonomous driving control systems are minimizing collision risk, maximizing passenger comfort, minimizing travelled distance, reassuring stable car motion and dynamics. These can be quantitatively measured by several indicators such as trajectory curvature computation and collision checking. Specifically, the set of quantitative measures considered for the objective functions are: •Collisions in trajectory. For each trajectory spline, collision checking is essential to discard trajectories that lead to crashing with high probability. For that, trajectories that lie too close to dynamic obstacles or road edges are identified. 5.3. Algorithm implementation and performance 39 The implication of this property is that the discount factor γshould be lowered for our problem, as this parameter intends to account for long term action-effect dependence. Whereas in standard DRL training γ= 0.99, for our case the appropriate value is considered to be lower, specifically γ= 0.92. 2. Few action dimensions. Latest general DRL techniques have focused on high dimensional action spaces. For example, locomotion tasks require controlling many articulations simultaneously, and it is only the correct synchronicity at the set of articulation commands that provides useful locomotion progress data for training. In such cases, exploration of the broad action space is essential, and it is in these environments that soft entropy based algorithms like SAC thrive. However, the action space for autonomous driving is only 2-dimensional (steering angle and motor acceleration), and it is likely that exploration of the action space does not need to be artificially favoured. In this case, SAC algorithm’s main strength - exploration - might prove inefficient. 3. Imperfect environment information. Whereas many of the RL benchmark problems in the field rely on perfect information - that is, the complete set of useful information is accessible to the agent -, in the collision avoidance case the agent relies on a limited low resolution laser reading of its environment. It cannot sense whether each laser reading corresponds to a static obstacle (road limit) or a dynamic one (vehicle). Its readings are also local and fail to obtain a complete map of the driving situation. 5.3 Algorithm implementation and performance For this work, SAC and DDPG have been implemented according to papers [28] and [29] respectively. Both algorithms were trained on the simulator until convergence. The results are analysed in the pages that follow. 5.3. Algorithm implementation and performance 40 5.3.1 SAC Pseudocode Figure 5.5: SAC pseudocode, reprinted from [28] 5.3. Algorithm implementation and performance 41 Hyperparameters This subsection presents the set of hyperparameters used for training. SAC hyperparameter values Description Discount Factor Polyak constant Q learning rate πlearning rate Entropy term Symbol γ ρ lrQlrπα Value 0.92 0.995 0.001 0.001 0.2 Performance analysis Figure 5.6 shows how SAC performance evolved during training on the simulated environment detailed in 4for 100 epochs of 4000 steps each. Figure 5.6: SAC performance during training. It can be seen that SAC performs significantly worse than the CLP baseline. The reason for this might be the one explained in Section 5.2.3.SAC algorithm is designed to broadly explore a more extensive action space. Its strength might not be applicable to the Autonomous Driving task as the action space is only 2-dimensional. 5.3. Algorithm implementation and performance 42 5.3.2 DDPG Pseudocode Figure 5.7: DDPG pseudocode, reprinted from [29]. 5.3. Algorithm implementation and performance 43 Hyperparameters This subsection presents the set of hyperparameters used for training. DDPG hyperparameter values Description Discount Factor Polyak constant Q learning rate πlearning rate Action noise std Symbol γ ρ lrQlrπ Value 0.92 0.995 0.001 0.001 0.1 Performance analysis Figure 5.8 shows how DDPG performance evolved during training. Starting with a random policy, the agent progressively learns a policy that outperforms the CLP baseline. Figure 5.8: DDPG performance during training. After 100 epochs (roughly 0.4 million steps) the policy performance converges. Evaluating the learned policy for 300 episodes yielded an average episode return of r=−0.59 , significantly outperforming the CLP average episode return r=−1.42. A more visual analysis of the resultant DDPG control performance can be done by going through several driving situations and analysing how the agent faced each challenge. The following page shows a set of episodes in the simulated environment. 5.3. Algorithm implementation and performance 44 Figure 5.9: The agent performs successfully a sharp turn, in high traffic density. The agent correctly adapts its speed to traffic conditions. Figure 5.10: Lane change autonomously executed by the DDPG policy. Figure 5.11: The agent identifies an opening in the front and uses it to safely navigate to a less traffic dense area. 45 Chapter 6 Conclusions and future work As said in the thesis introduction, it is not the main goal of this thesis to provide a full autonomous driving pipeline. This algorithm could be used instead as an assistant, providing a reference when the main control system identifies sensor failure or uncertainty. It is worth noting that during training the agent constantly faces driving situations that are far more challenging than regular driving conditions. In simulation, surrounding vehicles are not compliant with the ego vehicle and might invade the ego vehicle’s lane unexpectedly. This chaotic environment trains the agent for extreme situations for which the main control pipeline might not be specifically tailored. Based on the performance presented in Section 5.3, it is safe to conclude that the DDPG algorithm achieves significant collision avoidance capacity. The algorithm shows intelligent driving behaviour. More specifically, the agent performs lane changes and overtakes successfully, aiming for areas with less traffic density which minimize crash risk. Furthermore, the agent steers to the side whenever an adjacent vehicle approaches it laterally, in order to avoid lateral crashes. The algorithm shows ability to adapt its speed to traffic conditions, to avoid front and rear crashes. However, there is still room for improving the developed technique, mostly in terms of safety. Autonomous Driving requires almost perfect performance, as mistakes can have serious dramatic consequences. Regarding future work that might spin off this thesis, an interesting possibility might be to implement collaborative driving, where the AI not only controls a single vehicle, but a set of vehicles. This task should give rise to coordination between driving entities, likely reducing 46 crash risk. Another technical possibility might be to use a more complex model for vehicle motion, such as a Dynamic Bicycle Model instead of a Kinematic Bicycle Model (KBM). This would make sense as it is in extreme situations that tire forces are strong and vehicle motion is unstable. On the personal side, the author understands that the research conducted not only aims to explore alternative possibilities in the Autonomous Collision Avoidance field. As a Final Degree Thesis, it is also intended to educate the author, prompting him to work independently and acquire the broad set of skills required for technical endeavors that might arise in his professional future. In that sense, the author has investigated profoundly interesting topics like Deep Learning and Reinforcement Learning, implementing RL techniques for a broad set of tasks. The author has as well implemented a traffic simulator from scratch, comprising vehicle motion models, vehicle control systems, and behaviour planning techniques. 47 Bibliography [1] J. S. A. Winkler. Dynamic collision avoidance of industrial cooperating robots using virtual force fields. 2012. [2] J. L. A. R. T. F. Andy Zeng, Shuran Song. Tossingbot: Learning to throw arbitrary objects with residual physics. 2019. [3] B. Baker, I. Kanitscheider, T. Markov, Y. Wu, G. Powell, B. McGrew, and I. Mordatch. Emergent tool use from multi-agent autocurricula, 2019. [4] M. E. S. D. Berger-Tal O, Nathan J. The exploration-exploitation dilemma: A multidisciplinary framework. 2014. [5] K. Borenstein. The vector field histogram - fast obstacle avoidance for mobile robots. 1991. [6] N. T. T. K. M. G. B. S. Byungsoo Kim, Vinicius C. Azevedo. Deep fluids: A generative network for parameterized fluid simulations. 2018. [7] A. Elfes. Using occupancy grids for mobile robot perception and navigation. Computer, 22(6):46–57, 1989. [8] D. N. N. et al. Virtual force field algorithm for a behaviour-based autonomous robot in unknown environments. 2011. [9] H. et al. Implementation of autonomous line follower robot. 2012. [10] M. et al. Playing atari with deep reinforcement learning. 2013. [11] Z. et al. Reward shaping via meta-learning. 2019. [12] F. Fan, J. Xiong, and G. Wang. On interpretability of artificial neural networks, 2020. [13] C. Huang, W. Li, C. Xiao, B. Liang, and S. Han. Potential field method for persistent surveillance of multiple unmanned aerial vehicle sensors. International Jour- Bibliography 48 nal of Distributed Sensor Networks, 14:155014771875506, 01 2018. doi: 10.1177/ 1550147718755069. [14] G. S. F. B. Jason Kong, Mark Pfeiffer. Kinematic and dynamic vehicle models for autonomous driving control design. 2015. [15] P. D. A. R. O. K. John Schulman, Filip Wolski. Proximal policy optimization algorithms. 2017. [16] P. M. M. I. J. P. A. John Schulman, Sergey Levine. Trust region policy optimization. 2015. [17] Jon Liberal. Python Traffic Simulator [Online]. URL here. [18] O. Khatib. Real-time obstacle avoidance for manipulators ans mobile robots. 1985. [19] K. E. M. M. Almasri, A. Alajlan. Trajectory planning and collision avoidance algorithm for mobile robotics system. 2016. [20] M. McNaughton, C. Urmson, J. M. Dolan, and J. Lee. Motion planning for autonomous driving with a conformal spatiotemporal lattice. In 2011 IEEE International Conference on Robotics and Automation, pages 4889–4895, 2011. [21] H. Moravec. Certainty grids for sensor fusion in mobile robots. Sensor Devices and Systems for Robotics, pages 243–276, January 1989. [22] OpenAI. OpenAI Gym [Online]. URL here. [23] S. W. P.J. Antsaklis, K.M. Passino. An introduction to autonomous control systems. 1991. [24] B. W. Z. K. Po-Wei Wang, Priya L. Donti. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. 2019. [25] M. B. R. Brach. The tire-force ellipse (friction ellipse) and tire characteristics. 2011. [26] M. Roser and H. Ritchie. Technological progress. Our World in Data, 2020. https://ourworldindata.org/technological-progress. [27] W. T. V. N. H. L. P. M. e. a. Stafford T, Thirkettle M. A novel task for the investigation of action acquisition. 2012.