PaperlayerView exact revision on arXiv

Source-linked AI summary

Combining Planning and Deep Reinforcement Learning in Tactical Decision Making for Autonomous Driving

Carl-Johan Hoel, Katherine Driggs-Campbell, Krister Wolff, Leo Laine, Mykel J. Kochenderfer

arXiv:1905.02680v1cs.ROcs.AIcs.LG

TL;DR

Autonomous-driving tactical decisions must handle diverse environments, uncertain sensing, and interactions with other road users. The paper combines neural-network-guided Monte Carlo tree search with reinforcement learning, extending AlphaGo Zero to continuous, partially observable driving without self-play. In two highway cases, the framework outperformed baseline and individually used planning or learning methods, while requiring an order of magnitude fewer training samples than a comparable DQN agent.

  • Problem

    Tactical decision making requires safe and effective behavior under diverse environments, uncertain sensor information, and complex interactions with other road users.

  • Method

    The framework combines Monte Carlo tree search and reinforcement learning, extending AlphaGo Zero to continuous, partially observable autonomous-driving states without self-play.

  • Results

    The framework outperformed baseline methods and individually used MCTS or the trained neural network across two conceptually different highway cases.

  • Takeaways & Limitations

    The combined planning-and-learning framework is flexible across driving cases and required one order of magnitude fewer training samples than a DQN agent on a similar case.

Abstract

from arXiv · show

Tactical decision making for autonomous driving is challenging due to the diversity of environments, the uncertainty in the sensor information, and the complex interaction with other road users. This paper introduces a general framework for tactical decision making, which combines the concepts of planning and learning, in the form of Monte Carlo tree search and deep reinforcement learning. The method is based on the AlphaGo Zero algorithm, which is extended to a domain with a continuous state space where self-play cannot be used. The framework is applied to two different highway driving cases in a simulated environment and it is shown to perform better than a commonly used baseline method. The strength of combining planning and learning is also illustrated by a comparison to using the Monte Carlo tree search or the neural network policy separately.

I. INTRODUCTION

The paper addresses tactical decision making under diverse environments, uncertain sensing, and interaction with traffic participants by combining planning and reinforcement learning in a general framework.

  • Tactical decision making must produce safe, effective behavior across diverse and complex environments with uncertain sensor information and interacting traffic participants.
  • Handcrafted rule-based methods and sequential motion-planning approaches struggle to generalize or capture the full complexity of real-world driving.
  • POMDP formulations represent uncertainty and interaction, but finding an optimal policy is difficult and offline policies are hard to precompute for the many possible real-world scenarios.
  • Reinforcement learning can learn tactical decisions, but commonly requires many training samples and may struggle with long temporal correlations through credit assignment.
  • The paper extends AlphaGo Zero into a general autonomous-driving framework that combines Monte Carlo tree search with deep reinforcement learning.
  • The framework is evaluated in two highway cases and uses action restrictions to ensure collision-free behavior while operating with continuous, partially observable states.

B. Monte Carlo Tree Search

Monte Carlo tree search approximately selects actions in partially observable decision problems by exploring a generative-model search tree, with progressive widening addressing continuous state spaces.

  • MCTS builds alternating state and action layers to estimate state-action values and approximately select actions in POMDPs.
  • A generative model samples the next state while the upper confidence bound balances estimated return against exploration of less-tried actions.
  • Continuous state spaces can make every sampled state unique, producing an excessively wide shallow tree under standard MCTS.
  • Progressive widening limits children to kN(s, a)^α, adding sampled states only while the child count remains below that limit.
  • The paper combines MCTS with reinforcement learning by training a neural network to guide tree sampling while the search improves the network’s training process.

A. Tree search

The tree-search procedure uses a neural network’s action priors and value estimate to guide progressive-widening MCTS, then generates actions and training data from repeated simulations.

  • The neural network maps state s to action priors and a value estimate, providing guidance for MCTS selection and evaluation.
  • Each search iteration traverses from the root through selected actions to a leaf, where progressive widening either expands a sampled child or reuses an existing one.
  • The selected action maximizes a neural-network-guided UCB condition that combines state-action value, prior probability, and visit counts.
  • After expansion or simulation, visit counts and Q-values are updated through a backward pass, and the root action is sampled from exponentiated visit counts.
  • Training data are generated by repeatedly selecting actions with MCTS while the neural network parameters are optimized from stored samples.

B. Training process

Training data are generated through simulated episodes and used to jointly train the neural network’s value and policy outputs. Terminal handling determines the return target, while stored experience tuples support gradient-based optimization.

  • B. Training process: Each training episode starts from a random initial state and runs until termination, with actions selected by Algorithm 1.The resulting episode contains the states, actions, and rewards used to construct training samples.
  • B. Training process: Discounted returns are computed for every episode step by summing future rewards and incorporating a terminal-state value estimate when needed.The terminal value is zero for terminal final states; otherwise it is estimated by the neural network.
  • B. Training process: Search-tree action distributions and discounted returns are stored with each state as targets for neural-network training.The experience memory stores tuples of the form (s_i, π_i, z_i).
  • B. Training process: The neural network is optimized with a loss combining mean-squared value error, policy cross-entropy, and L2 weight regularization.Parameters c1, c2, and c3 balance the three loss components.

IV. IMPLEMENTATION

The implementation models highway traffic and vehicle behavior for two test cases, using IDM and MOBIL-based dynamics with stochastic acceleration for surrounding vehicles. The framework is evaluated in continuous driving and highway-exit scenarios.

  • IV. IMPLEMENTATION: The framework is applied to continuous highway driving and off-ramp exiting, using the modeled environment as both a generative model and simulation setting.The two cases differ in whether the objective is efficient traffic navigation or reaching an exit.
  • A. Driver Modeling: The Intelligent Driver Model governs longitudinal motion through speed, headway, and approach-rate dependent acceleration.Its parameters include desired speed, time gap, minimum distance, maximum acceleration, and desired deceleration.
  • A. Driver Modeling: Acceleration noise is applied independently to surrounding vehicles, while the ego vehicle receives no acceleration noise.The noise is normally distributed with zero mean and unit standard deviation before scaling by σ_vel and the simulation time step.
  • A. Driver Modeling: Surrounding-vehicle lane changes follow MOBIL, which evaluates acceleration gains for involved vehicles subject to a safety criterion.The politeness factor weights the effects on neighboring vehicles, and a threshold determines whether the lane change is performed.
  • A. Driver Modeling: Figure 1 depicts the green ego truck and surrounding vehicles colored by driver aggressiveness, from red aggressive to blue timid.The panels show continuous highway driving and an approach to a right-side exit.

B. Physical Modeling

The physical model uses constant longitudinal acceleration and constant lateral speed to update vehicle motion on a four-lane, straight, one-way highway. Braking is bounded by a maximum deceleration.

  • B. Physical Modeling: Both test cases use a straight, one-way highway with four lanes and constant-acceleration longitudinal dynamics.Longitudinal position and speed are updated from each vehicle’s motion state under the constant-acceleration assumption.
  • B. Physical Modeling: Braking acceleration is limited to bmax.This imposes an explicit bound on the vehicle’s longitudinal deceleration.
  • B. Physical Modeling: Lateral motion assumes a constant lateral speed vy during lane changes.The lateral position is updated according to that speed and the intended lane-change direction.
  • B. Physical Modeling: Outside a lane change, lateral speed is set to zero; lane-change direction determines the sign of the lateral update.The model uses the parameter values listed in Table IV.

C. POMDP Formulation

The driving problem is formulated as a POMDP with continuous physical and driver states, a compact tactical action space, collision-free action pruning, and rewards for efficient progress toward the desired objective.

  • C. POMDP Formulation: The POMDP formulation represents physical states, driver-model states, surrounding vehicles, and a terminal-state indicator.Physical state includes each vehicle’s longitudinal and lateral position and speed; driver state contains model parameters.
  • C. POMDP Formulation: Each driver state is represented by set speed, time gap, minimum distance, acceleration, deceleration, politeness, threshold, and safety parameters.These parameters define the modeled driver behavior for the vehicles in the scene.
  • C. POMDP Formulation: The tactical action space contains five choices: maintain the driver state, adjust the ACC setpoint upward or downward, or change lanes left or right.A lower-level operational layer executes the selected tactical action.
  • C. POMDP Formulation: ACC setpoint adjustments change requested speed or time-gap behavior, while lane-change actions start, continue, or abort lateral motion.The operational layer uses IDM for ACC behavior and sets lateral speed for lane changes.
  • 2) Action space, A:: Actions that could lead to collisions are pruned, and ACC increases are excluded when the setpoint already equals the minimum time-gap setting.The action rules require braking consequences to remain above the collision-avoidance threshold.
  • 3) Reward model, R:: The reward model combines speed-tracking reward with a penalty for initiating lane changes and a terminal reward for reaching the exit.Safety is handled through the crash-free action set rather than the reward function.
  • 3) Reward model, R:: Table I summarizes the agent’s available tactical actions.The table is associated with the action-space description rather than the reward definition.

4) State transition model, T:

The transition model generates future states from the current state and action, while observations combine nearby vehicles’ physical states with the ego vehicle’s physical and driver states. Unobserved driver states are estimated with particle filtering and represented by the highest-weight particle for tree search.

  • Transition generation: The IDM/MOBIL and physical models form a generative model G that samples the next state from the current state and action.The same generative model is used during Monte Carlo tree search.
  • Observations: Observations include surrounding vehicles’ physical states and the ego vehicle’s physical and driver states, but exclude surrounding vehicles’ driver states.
  • Sensor model: Vehicles within the sensor range are assumed to be observed exactly, while more distant vehicles are not detected.
  • Driver-state estimation: A particle filter estimates each surrounding vehicle’s driver-model parameters from its physical-state history.Particles represent the belief over driver parameters and are resampled after actions using weights based on new observations.
  • Tree-search input: The tree search uses the observed state together with the highest-weight particle as the estimated most likely driver state.

D. Neural Network Architecture and Training Process

The network processes normalized ego and surrounding-vehicle inputs with shared convolutional structure, then estimates action priors and state value. Training uses replayed episode samples and stochastic gradient optimization.

  • Input representation: The network normalizes states and represents surrounding vehicles relative to the ego vehicle before inference.Its inputs describe the ego vehicle and each surrounding vehicle.
  • Vehicle encoding: Shared convolutional layers and max pooling process interchangeable surrounding vehicles, making their ordering and number irrelevant.This architecture applies identical weights across vehicles and creates translational invariance.
  • Network architecture: Two convolutional layers and max pooling are concatenated with ego-state inputs, followed by fully connected layers and separate action-distribution and value heads.The heads estimate p(s, θ) and V(s, θ).
  • Training process: Completed-episode samples are stored in replay memory, and training begins after the configured initial sample collection.Mini-batches are drawn uniformly from memory for optimization.

E. Episode Implementation

The experiments evaluate tactical driving on a four-lane highway using simulated traffic, defined episode objectives, and baseline controllers. In continuous driving, the proposed agent benefits from planning and training and solves a situation requiring sequential overtaking.

  • Environment: Both test cases use a straight, one-way, four-lane highway where overtaking is allowed on either side.
  • Episode termination: The continuous case lasts 200 time steps, whereas the exit case ends when the ego vehicle reaches the exit longitudinally.The exit case additionally requires the ego vehicle to be in the rightmost lane.
  • Traffic generation: Surrounding vehicles follow IDM and MOBIL models with parameters sampled between aggressive and timid driver types.The reduced politeness factor makes slow drivers less likely to move out of the way.
  • Initialization: The initial simulation state is generated by running 200 IDM-controlled steps and inserting vehicles with random parameters when gap constraints permit.
  • Baselines and evaluation: The proposed MCTS/NN agent is compared with standard MCTS and IDM/MOBIL baselines under matched evaluation episodes.The continuous case also uses an IDM baseline that remains in its original lane.
  • Overall result: The proposed agents outperformed the baseline methods in both the continuous-driving and highway-exit cases.
  • Continuous driving results: The agent’s average reward improved substantially after 20,000 training steps, following relatively good pre-training performance from its planning component.Further training produced a smaller additional increase.
  • Planning behavior: Planning enabled the MCTS/NN agent to solve a scenario requiring two lane changes to overtake adjacent slow vehicles, unlike IDM/MOBIL.Standard MCTS also solved the illustrated situation.

B. Highway Exit Case

The highway-exit case measures whether the agent reaches the exit and how efficiently it does so. Training produced reliable success, while sufficient MCTS iterations were necessary for the agent to plan far enough in difficult scenarios.

  • Objective: The exit case prioritizes reaching the exit, with time efficiency as a secondary objective.
  • Success results: After around 120,000 training steps, the MCTS/NN agent solved all evaluation episodes; standard MCTS succeeded in 70% and modified IDM/MOBIL in 54%.
  • Long-horizon planning: The exit scenario can require planning over a long horizon when the ego vehicle starts 300 m away in the leftmost lane among six vehicles.
  • Baseline behavior: Standard MCTS stayed in its original lane after failing to find an exit route, while IDM/MOBIL changed rightward without reaching the exit.
  • Iteration ablation: With one iteration, the MCTS/NN agent succeeded in 14% of episodes; with 2,000 iterations, it solved all evaluation episodes.Ten iterations matched standard MCTS using 2,000 iterations.

VI. DISCUSSION

The framework combines planning and reinforcement learning to improve tactical decision making across two highway cases, while retaining anytime operation and adaptability. Its benefits include stronger performance, longer-horizon planning, and substantially lower training-sample requirements than a comparable DQN approach, but safety, reward design, and training coverage remain bounded.

  • Performance: The proposed agents outperformed baseline methods in both highway test cases, with a more significant advantage in the highway exit case.The exit case is more complex and has a pass/fail outcome, making policy quality more decisive.
  • Planning and learning: The MCTS/NN agent used learned action priors and value estimates to search deeper and plan over longer horizons than standard MCTS with the same iterations.This advantage was especially relevant when standard MCTS could not reach the exit within its search depth.
  • Anytime operation: Full performance was reached at around n = 1,000 searches in the studied cases, while the agent could return a neural-network action after any number of iterations.The required number of searches depends on environmental complexity and the traffic situation.
  • Limitations: The reward model promoted desired speed and penalized lane changes, but other cases may require more careful objectives incorporating fuel efficiency or effects on surrounding traffic.Inverse reinforcement learning is suggested as one way to model human preferences.
  • Sample efficiency: The framework required around one order of magnitude fewer training samples than a DQN agent on a similar case, although each sample was more computationally expensive to obtain.This trade-off matters differently for simulated data and expensive real-world driving data.
  • Generality: The same tree-search and training processes can support conceptually different driving cases after defining the state, action, reward, generative, and belief-state components.The study covered continuous highway driving and highway exit scenarios.
  • Limitations: Training episodes must cover intended situations, and functional safety of machine-learning-based decisions is difficult to guarantee.The agent can solve only the types of situations encountered during training.
  • Method adaptation: The AlphaGo Zero extension addresses continuous states, partial observability, and the absence of self-play through progressive widening, state estimation, and a generative model.The method also adapts the neural-network architecture and tree-expansion rule for autonomous driving.
Loading 1905.02680v1…