In this paper, we propose a decision making algorithm intended for automatedvehicles that negotiate with other possibly non-automated vehicles inintersections. The decision algorithm is separated into two parts: a high-leveldecision module based on reinforcement learning, and a low-level planningmodule based on model predictive control. Traffic is simulated with numerouspredefined driver behaviors and intentions, and the performance of the proposeddecision algorithm was evaluated against another controller. The results showthat the proposed decision algorithm yields shorter training episodes and anincreased performance in success rate compared to the other controller.
Quick Read (beta)
Learning When to Drive in Intersections by Combining Reinforcement Learning and Model Predictive Control
In this paper, we propose a decision making algorithm intended for automated vehicles that negotiate with other possibly non-automated vehicles in intersections. The decision algorithm is separated into two parts: a high-level decision module based on reinforcement learning, and a low-level planning module based on model predictive control. Traffic is simulated with numerous predefined driver behaviors and intentions, and the performance of the proposed decision algorithm was evaluated against another controller. The results show that the proposed decision algorithm yields shorter training episodes and an increased performance in success rate compared to the other controller.
How can a self-driving vehicle interact and drive safely through intersections with other road users? Interactions between road users in intersections is a complex problem to solve, making it difficult to address using conventional rule based systems. Many advancements aim to solve this problem by trying to imitate human drivers  or predicting what other drivers in traffic are planning to do . In , the authors show that by modeling the decision process as a partially observable Markov decision process, the model can account for uncertainty in sensing the environment and  showed some probabilistic guarantees when solving the problem using reinforcement learning (RL).
Previous research  showed that reinforcement learning can be used to learn a negotiation behavior between vehicles without vehicle to vehicle communication when driving in an intersection. The method found a policy that could avoid collisions in an intersection with crossing traffic, where other vehicles have different intentions. Since the previous work separates the framework in a high-level decision maker and a low-level controller, the high-level decision making algorithm can focus on the task when to drive, while the low level controller handles the comfort of passengers in the car by generating a smooth acceleration profile. We showed how this worked for intersections with a single crossing point, where Short Term Goal (STG) actions could choose one car to follow. This architecture, similar to Fig. 1, gives the decision algorithm, the RL policy, the flexibility to choose actions that can safely drive through the intersection by switching between numerous STG. A solution with a simple controller holds well when the distance between intersection are far away from each other, but when there are several crossing points in close succession, the system would have a hard time avoiding collisions due to the increased complexity of multiple points and timeing where a collision can occur.
In this paper, we instead propose to combine the high-level decision maker from  with a Model Predictive Controller (MPC) in a framework presented in Fig. 1. The performance of the MPC controller is benchmarked against a Sliding Mode controller that was used in . The benefit of the MPC is that it can consider multiple vehicles at the same time and generate an optimal trajectory, which instantly gives feedback on performance and feasibility, i.e. predicting collisions, to the high-level decision maker. In contrast to , where the authors prove stability and recursive feasibility using an MPC approach and assuming that agents can cooperate, we restrict ourselves to non-cooperative scenarios.
Applying MPC directly to the problem could lead to a growing complexity with the number of vehicles in the intersection, e.g., the vehicle needs to decide based on multiple options which vehicle to yield for, and which to drive in front of. Therefore, we propose to separate the problem into two parts: the first being a high-level decision maker, which structures the problem, and the second being a low level planner, which optimizes a trajectory given the traffic configuration.
For the high-level decision maker, RL is used to find a policy for how the vehicle should drive through the intersection, and MPC is used as a low-level planner to optimize a safe trajectory. Compared to [7, 8] where all vehicles are controlled using MPC to stay in safe sets, based on models of other vehicles’ future trajectory, this could possibly be perceived as too conservative for a passenger. By combining RL and MPC, the decision policy will learn which action is optimal by using feedback from the MPC controller in the reward function. Since MPC uses predefined models, e.g. vehicle models and other obstacle prediction models, the performance relies on their accuracy and assumptions. To mitigate this, we use Q-learning, a model-free RL approach, to maximize the expected future reward based on the experience gained during an entire episode. This approach is able to compensate, to some extent, for model errors and is explained more in Section IV-A.
In this work, we focus on the integration between policy and actuation, by having an MPC controller directly giving feedback to the decision maker through immediate reward, allowing the policy to know how comfortably the controller can handle an action and give feedback sooner if the predicted outcome may be good or bad.
This paper is structured as follows. Section II introduces the problem formulation along with the two-layers of the decision algorithm. Section III presents three agents used for simulation and validation. Implementation details are presented in Section IV, and the results are shown in Section V followed by discussion in Section VI. Finally, we draw conclusions in Section VII.
II Problem formulation
The goal of the ego-vehicle is to drive along a predefined route that has one or two intersections with crossing traffic, where the intent of other road users is unknown. Therefore, the ego-vehicle needs to assess the driving situation and drive comfortably, while avoiding collisions with any vehicle11 1 Although our approach can be extended to other road users, for convenience of exposition we’ll refer to vehicles. that may cross. In this section, we define the underlying Partially Observable Markov Decision Process (POMDP) and present how the problem is decomposed using RL for decision making and MPC for planning and control.
II-A Partially Observable Markov Decision Process
A POMDP  is defined by the 7-tuple , where is the state space, an action space that is defined in section III-A, the transition function, the reward function is defined in IV-D, an observation space, the probability of being in state given the observation , and the discount factor.
A POMDP is a generalization of the Markov Decision Process (MDP)  and therefore works in the same way in most aspects. At each time instant , an action, , is taken, which will change the environment state to a new state . Each transition to a state with an action has a reward given by a reward function . The key difference from a regular MDP is that the environment state is not entirely observable, e.g., the intention of other vehicles is not known. In order to find the optimal solution for our problem, we need to know the future intention of other drivers. Instead, we can only partially perceive the state though observations .
In the reinforcement learning problem, an agent observes the state of the environment, takes an action , and receives a reward at every time step . Through experience, the agent learns a policy in a way that maximizes the accumulated reward in order to find the optimal policy . In Q-learning, the policy is represented by a state action value function . The optimal policy is given by the action that gives the highest Q-value.
Following the Bellman equation, the optimal Q-function is given by
The action space is made out of six actions. The first two actions: take way, and give way, have the simple goal of crossing the intersection and stopping before the intersection, respectively. The actions has the goal of following a vehicle .
In the following, we explain the two agents used for control of the ego vehicle and how they apply each action and how the surrounding traffic is modeled with varying intentions.
III-A MPC agent
We model the vehicle motion with states and control , defined as
where we denote the position along the driving path in a Frenet frame as , the velocity as , the acceleration as , and the jerk as , see Fig. 1(a). In addition, we assume that measurements of other vehicles are provided through an observation . We limit the scope of the problem to consider at most four vehicles, and define the observations as
where we denote the position along its path as , the velocity as , and for , as the distance to the ego-vehicle from the intersection point, see Fig. 1(a). Note that we distinguish between , since vehicles can cross at different points, see Fig. 4.
We assume that there exists a lateral controller that stabilizes the vehicle along the driving path. To that end, we only focus on the longitudinal control. Given the state representation, the dynamics of the vehicle is then modeled using a triple integrator with jerk as control input.
The objective of the agent is to safely track a reference, i.e. follow a path with a target speed, acceleration, and jerk profile, while driving comfortably and satisfying constraints that arise from physical limitations and other road users, e.g. not colliding in intersections with crossing vehicles. Hence, we formulate the problem as a finite horizon, constrained optimal control problem
where is the prediction time index, is the prediction horizon, , , and are the stage costs, is the terminal cost, and are the predicted state and control inputs, and are the state and control input references, denotes the predicted state of vehicles in the environment which need to be avoided, and is the action from the high-level decision maker in Sec. II-B. Constraint (5b) enforces that the prediction starts at the current state estimate , (5c) enforces the system dynamics, and (5d) enforces constraints on the states, control inputs, and obstacle avoidance.
The reference points, , are assumed to be set-points of a constant velocity trajectory, e.g. following the legal speed-limit of the road. Therefore, we set the velocity reference according to the speed limit, and the acceleration and jerk to zero.
III-A1 Obstacle prediction
In order for the vehicle planner in (5) to be able to properly avoid collisions, it is necessary to provide information about the surrounding vehicles in the environment. Therefore, similarly to , we assume that a sensor system provides information about the environment, and that there exists a prediction layer which generates future motions of other vehicles in the environment. The accuracy of the prediction layer does indeed affect the performance of the planner, however, since the high-level decision maker is separated from the low level control, the decisions can still be made robust to handle model errors and prediction errors.
In this paper, for simplicity the future motion of other agents is estimated by a constant velocity prediction model. The motion is predicted at every time instant for prediction times , and is used to form the collision avoidance constraints, which we describe in the next section. Even though more accurate prediction methods do exist, e.g. [12, 13], we use this simple model to show the potential of the overall framework.
III-A2 Collision avoidance
We denote a vehicle with the following notation , and an associated crossing point at position in its own vehicle frame, which translated into the ego-vehicle frame is denoted as . For clarity, see Fig. 1(a). With a predefined road topology, we assume that the vehicles will travel along the assigned paths, and that collisions may only occur at the intersection points between an obstacle and the ego vehicle. Hence, for collision avoidance, we use the predictions of the future obstacle states for times , provided by the prediction layer outside of the MPC framework. Given the obstacle measurements, the prediction layer will generate future states throughout the prediction horizon. With this information, it is possible to identify the time slots when a vehicle enters and exits the intersection.
Whenever an obstacle is predicted to be within a threshold of , e.g. the width of the intersecting area, the ego vehicle faces a constraint of the following form
where ensures sufficient padding from the crossing point that does not cause a collision. The choice of must be at least such that together with the dimensions of the ego-vehicle does not overlap with the intersecting area.
III-A3 Take way and give way constraint
Since the constraints from the surrounding obstacles become non-convex, we rely on the high-level policy maker to decide through action how to construct constraint (5d) for Problem (5). The take-way action implies that the ego-vehicle drives first through the intersection, i.e., it needs to pass the intersection before all other vehicles. This implies that for any vehicle that reaches the intersection during prediction times , the generated constraint needs to lower bound the state according to
Similarly, if the action is to give way, then the position needs to be upper bounded by the closest intersection point so that
for all times that the vehicle is predicted to be in the intersection.
III-A4 Following an obstacle
If action is not chosen to give way, or to take way, the remaining options are to follow one of the vehicles. For such choices on the ego-vehicle position is upper bounded by . For other vehicles , we construct the following constraints
if then , which implies that the ego-vehicle should drive ahead of all vehicles that are approaching the intersection;
if then , which implies that the ego-vehicle should wait to pass vehicle and other vehicles ;
if then the constraints generated for vehicle becomes an upper or lower bound depending on if vehicle is ahead or behind vehicle into the intersection.
III-B Sliding mode agent
To benchmark the performance of using MPC, we introduce a Sliding Mode (SM) controller that was used in  and given by the following
The SM controller aims to keep a minimum distance to a target vehicle with a velocity of , by controlling the acceleration . The tuning parameters , , and are used to tune the comfort of the controller. In case no target vehicle exists, the controller maintains a target velocity with a proportional control law from (8d) with the proportional constant . The final acceleration is given by (8e). For more details about the SM agent see .
III-C Surrounding traffic agents
There are three intentions for agents in surrounding traffic. Examples of some velocity profiles are shown in Fig. 1(b). The intention of all agents is implemented with a SM controller with various target values. The take way intention does not yield for the crossing traffic and simply aim to keep its target reference speed. The give way intention, however, slows down to a complete stop at the start of the intersection, until crossing traffic has passed. The third intention is cautious, i.e. slowing down but not to a full stop.
IV-A Deep Q-Network
The deep Q-network is structured as a three layer neural network with shared weights and a Long Short-Term Memory (LSTM) layer based on previous work  and shown in Fig. 3. A similar study for lane changes on a highway confirmed the importance of having equal weights for inputs that describe the state of interchangeable objects . The input features are composed of observations , introduced in section II-A and shown in Fig. 1(a), with up to four observed vehicles
Normalization of the input features is done by scaling the features down to values between using the maximum speed , maximum acceleration and a car’s sight range . Empty observations of other vehicles has a default value of . The input vectors are sent though two hidden layers and with shared weights and respectively
The output of each sub-network is then sent through a fully connected layer
that is then connected to an LSTM  layer that can store and use previous features
The output from the LSTM is then sent through a final layer
where the operator denotes pointwise multiplication, is a masking vector described in the next section, and are the weights and biases for the final layers, respectively. The optimal policy is then given by maximizing the optimal action value function as
Q-masking  helps the learning process by reducing the exploration space by disabling actions the agent does not need to explore. If there are less than cars, it would then be meaningless to choose to follow a car that does not exist. Which motivates masking off cars that do not exist. In previous work , a high negative reward was given when an action to follow a car that did not exist was chosen, while the algorithm continued with a default action take way. The agent quickly learned to not choose cars that did not exist, but with Q-masking, the agent does not have to explore these options. For further details about the training see .
IV-C Simulation environment
All agents are spawned with a random intention, initial speed m/s, and position m. The vehicle dimensions are m wide and m long. The ego car operates within comfort bounds and therefore has a limited maximum acceleration and deceleration of m/s.
Two main types of crossing were investigated. One and two crossing points as shown in Fig. 4, where the distance between crossing points vary between m with each scenarios.
The MPC agent was discretized at Hz, with a prediction horizon of and cost tuning of
IV-D Reward function tuning
There are three states that terminates an episode: success, failure, and timeout. Success is when the ego agent reaches the end of the road defined by the scenario. Failure is when the frame of the ego agent overlaps with another road users’ frame, e.g., in a collision, this frame can be the size of the vehicle or a safety boundary around a vehicle. The final terminating state is timeout, which is simply when the agent can not reach the two previous terminating states before the elapsed time reaches the timeout time .
According to , the values and gradient can grow to be very large if the total reward values are too large. All rewards are therefore scaled with the episode timeout time , which is set to 25, to keep the total reward . The reward function is defined as follows:
where consists of
with , being weight parameters, and . The first term corresponds to a feasibility check of Problem (5), which to a large extent depends on the validity of the accuracy of the prediction layer. The high-level decision from the policy-maker affects how the constraints are constructed, and may turn the control problem infeasible, e.g. if the decided action is to take way, while not being able to pass the intersection before all other obstacles. Therefore, whenever the MPC problem becomes infeasible we set , otherwise , to indicate that the selected action most likely will result in a collision with the surrounding environment. Because usually only triggers close to a potential collision, is set to the first time a crash prediction is triggered, to scale the negative reward relatively higher the later it is predicted.
The second term relates to the comfort of the planned trajectory, which is estimated by computing and weighting the acceleration and jerk profiles as
where , and are the acceleration component of the state and jerk component of the control, respectively, and are the corresponding weights, and is a normalizing factor which ensures that . For the simulation we used and .
The timeout reward 0.5 was set to be higher than the average accumulated reward from , so that the total accumulated reward would be positive in case of timeouts.
For evaluation we compared the success rate of the decision-policy together with a collision to timeout ratio (CTR). The success rate is defined as the number of times the agent is able to cross the intersections without colliding with other obstacles or exceeding the time limit to cross. Since we define a time-out to be a failure, we use the CTR to separate potential collisions from the agent being too conservative.
Fig. 5 shows a comparison in success rate between the proposed MPC architecture and the previous SM agent for scenarios with only one intersection. In this scenario, the MPC agent converges after training episodes, while the previous SM agent converges after training episodes. In addition, comparing the CTR metric, Tabel. I shows that the MPC agent has CTR of , while the SM agent has a CTR of . Evidently, it is apparent that the MPC is able to leverage future information into its planning horizon in order to achieve faster training, higher success rates, and also avoiding more collisions as a result.
We evaluate the performance of the MPC and SM agents for the more difficult double intersection problem, where we vary the distance between the intersection points. Table I shows the performance of the MPC and SM agent for both the single and double scenarios. The performance decreases for both agents in the double crossing scenario. However, it is evident that the MPC agent suffers less performance degradation compared to the SM agent. The CTR more than doubles for the MPC agent for the double crossing, while the already high CTR rate for the SM agent increases above rates of . Still, the MPC agent manages to outperform the SM agent.
The benefit of being able to use a prediction horizon for the MPC is shown to mostly impact the training time for the traffic scenarios compared to the SM agent. This allows the RL decision-policy to get feedback early in the training process to see whether an action most likely will lead to a collisions. In addition, the lower CTR also implies that the use of a prediction horizon also makes the decision-policy more conservative, since it rather times out than risk collisions.
It is important to note that only little effort was put into tuning the MPC agent, and that we used very primitive prediction methods that do not hold very well in crossing scenarios, e.g. the simulated agents did not keep constant speed profiles while approaching the intersections. However, under these circumstances, the decision algorithm still managed to obtain a success rate above for the double crossings.
In practice, a full decision architecture system would include a safety layer that limits which acceleration values the system can actuate in order to stay safe, followed by the decisions algorithm from this work that generates an acceleration request. The environment state, together with the new acceleration request, could be sent through a collision avoidance system that checks if the current path has a collision risk, and avoiding collision by allowing higher acceleration limits. This way, a failure would correspond to a intervention by the collision avoidance system instead of a crash.
In this paper, we proposed a decision making algorithm for intersections which consists of two components: a high-level decision maker that uses Deep Q-learning to generate decisions for how the vehicle should drive through the intersection, and a low-level planner that uses MPC to optimize safe trajectories. We tested the framework in a traffic simulation with randomized intent of other road users for both single and double crossings. Results showed that the proposed MPC agent outperforms the previous SM agent with success rate in scenarios with double crossings compared to for the SM agent. Results also showed that the crash timeout ratio was also significantly lower at for the MPC agent compared to for the SM agent in single crossings. Meaning, the proposed method is better at handling scenarios with multiple intersections and vehicles.
-  M. Bansal, A. Krizhevsky, and A. Ogale, “ChauffeurNet: Learning to Drive by Imitating the Best and Synthesizing the Worst,” 2018.
-  A. Zyner, S. Worrall, J. Ward, and E. Nebot, “Long short term memory for driver intent prediction,” in IEEE Intelligent Vehicles Symposium, Proceedings, 2017.
-  S. Brechtel, T. Gindele, and R. Dillmann, “Probabilistic decision-making under uncertainty for autonomous driving using continuous pomdps,” in 17th International IEEE Conference on Intelligent Transportation Systems (ITSC). IEEE, 2014, pp. 392–399.
-  M. Bouton, J. Karlsson, A. Nakhaei, K. Fujimura, M. J. Kochenderfer, and J. Tumova, “Reinforcement learning with probabilistic guarantees for autonomous driving,” in Workshop on Safety Risk and Uncertainty in Reinforcement Learning, Conference on Uncertainty in Artificial Intelligence (UAI), 2017.
-  T. Tram, A. Jansson, R. Grönberg, M. Ali, and J. Sjöberg, “Learning negotiating behavior between cars in intersections using deep q-learning,” in 2018 21st International Conference on Intelligent Transportation Systems (ITSC), Nov 2018, pp. 3169–3174.
-  R. Hult, M. Zanon, S. Gros, and P. Falcone, “Optimal coordination of automated vehicles at intersections: Theory and experiments,” IEEE Transactions on Control Systems Technology, pp. 1–16, 2018.
-  X. Qian, J. Gregoire, A. de La Fortelle, and F. Moutarde, “Decentralized model predictive control for smooth coordination of automated vehicles at intersection,” in 2015 European Control Conference (ECC), July 2015, pp. 3452–3458.
-  G. R. de Campos, P. Falcone, and J. Sjöberg, “Autonomous cooperative driving: a velocity-based negotiation approach for intersection crossing,” in 16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013). IEEE, 2013, pp. 1456–1461.
-  M. J. Kochenderfer et al., ”Decision Making Under Uncertainty: Theory and Application”. The MIT Press, 2015.
-  R. Bellman, “A markovian decision process,” Journal of Mathematics and Mechanics, vol. 6, no. 5, pp. 679–684, 1957.
-  I. Batkovic, M. Zanon, M. Ali, and P. Falcone, “Real-time constrained trajectory planning and vehicle control for proactive autonomous driving with road users,” in European Control Conference (ECC) 2019, 2019.
-  S. Lefèvre, D. Vasquez, and C. Laugier, “A survey on motion prediction and risk assessment for intelligent vehicles,” ROBOMECH journal, vol. 1, no. 1, p. 1, 2014.
-  I. Batkovic, M. Zanon, N. Lubbe, and P. Falcone, “A computationally efficient model for pedestrian motion prediction,” in 2018 European Control Conference (ECC), June 2018, pp. 374–379.
-  C. Hoel, K. Wolff, and L. Laine, “Automated speed and lane change decision making using deep reinforcement learning,” in 2018 21st International Conference on Intelligent Transportation Systems (ITSC), Nov 2018, pp. 2148–2155.
-  S. Hochreiter and J. Urgen Schmidhuber, “Long short-term memory,” Neural Computation, vol. 9, no. 8, pp. 1735–1780, 1997. [Online]. Available: http://www7.informatik.tu-muenchen.de/ hochreit http://www.idsia.ch/ juergen
-  M. Mukadam, A. Cosgun, A. Nakhaei, and K. Fujimura, “Tactical decision making for lane changing with deep reinforcement learning,” in NIPS Workshop on Machine Learning for Intelligent Transportation Systems, 2017.
-  H. P. van Hasselt, A. Guez, M. Hessel, V. Mnih, and D. Silver, “Learning values across many orders of magnitude,” in NIPS, 2016.