Source-linked AI summary
Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
Shai Shalev-Shwartz, Shaked Shammah, Amnon Shashua
TL;DR
Autonomous driving needs long-term strategies that handle unpredictable multi-agent behavior while preserving functional safety and normal traffic flow. The paper applies deep reinforcement learning without Markov assumptions, separates learned desires from hard-constrained trajectory planning, and introduces an Option Graph that reduces the effective horizon and gradient-estimation variance.
Problem
Autonomous driving requires policies that balance unexpected behavior by other road users with normal traffic flow, while expected-reward learning makes functional safety difficult and MDP assumptions may fail.
Method
The paper combines non-Markovian policy-gradient learning with a learned Policy for Desires, hard-constrained trajectory planning, and a gated hierarchical Option Graph.
Results
The Option Graph significantly reduces the effective horizon and thereby reduces gradient-estimation variance.
Takeaways & Limitations
The framework separates driving comfort from safety guarantees while using temporal abstraction to reduce the learning problem’s effective horizon and output space.
Takeaways & Limitations
The experimental section is a demonstration using proprietary software and data, without a reproducible experiment or comparison to other approaches.
Abstract
from arXiv · showhide
Autonomous driving is a multi-agent setting where the host vehicle must apply sophisticated negotiation skills with other road users when overtaking, giving way, merging, taking left and right turns and while pushing ahead in unstructured urban roadways. Since there are many possible scenarios, manually tackling all possible cases will likely yield a too simplistic policy. Moreover, one must balance between unexpected behavior of other drivers/pedestrians and at the same time not to be too defensive so that normal traffic flow is maintained. In this paper we apply deep reinforcement learning to the problem of forming long term driving strategies. We note that there are two major challenges that make autonomous driving different from other robotic tasks. First, is the necessity for ensuring functional safety - something that machine learning has difficulty with given that performance is optimized at the level of an expectation over many instances. Second, the Markov Decision Process model often used in robotics is problematic in our case because of unpredictable behavior of other agents in this multi-agent scenario. We make three contributions in our work. First, we show how policy gradient iterations can be used without Markovian assumptions. Second, we decompose the problem into a composition of a Policy for Desires (which is to be learned) and trajectory planning with hard constraints (which is not learned). The goal of Desires is to enable comfort of driving, while hard constraints guarantees the safety of driving. Third, we introduce a hierarchical temporal abstraction we call an "Option Graph" with a gating mechanism that significantly reduces the effective horizon and thereby reducing the variance of the gradient estimation even further.
1 Introduction
Autonomous driving requires long-term policies that balance unexpected behavior by other road users with maintaining normal traffic flow. The paper addresses functional-safety and non-Markovian challenges by combining policy-gradient learning, hard safety constraints, and hierarchical temporal abstraction.
- Motivation: Manually enumerating the many driving scenarios would likely produce an overly simplistic policy.The policy must handle overtaking, yielding, merging, turning, and unstructured urban driving.
- Challenges: Autonomous driving differs from standard robotic settings because functional safety is difficult to guarantee when learning optimizes expected performance.Rare accidents may be underweighted by expectation-based optimization.
- Challenges: MDP assumptions are problematic because other vehicles, pedestrians, and cyclists can make the next state depend on non-Markovian behavior.The vehicle’s own dynamics may be Markovian while other road users’ behavior is not.
- Contributions: Policy-gradient learning can be used without assuming that the environment is Markovian.The paper proposes initializing with imitation and then iteratively updating the policy with policy gradients.
- Contributions: The paper separates learned driving desires from trajectory planning with hard safety constraints.Desires target driving comfort, while the non-learned planner guarantees safety; an Option Graph further reduces the effective horizon and gradient variance.
2 Reinforcement Learning without Markovian Assumption
The paper formulates policy-gradient learning over trajectories without Markov assumptions and analyzes the resulting variance. It reduces that variance through baselines, hard safety constraints, and temporal abstraction via an Option Graph.
- Formulation: The policy-gradient formulation treats the state as an agnostic collection of current environmental information rather than a necessarily Markovian state.The policy is differentiable in its parameters and can be implemented as a deep layered network.
- Formulation: Trajectories are sequences of state-action pairs with an arbitrary total reward function over the trajectory.The framework permits discounted immediate rewards but does not require that specific reward form.
- Policy Gradient: The gradient policy theorem gives an unbiased estimate of the expected total-reward gradient without Markov assumptions.The estimate can train a deep-network policy through stochastic gradient ascent or descent.
- Variance: Gradient-estimator variance increases with the time horizon and with very large penalties needed for rare accident events.These effects motivate separate variance-reduction mechanisms for long horizons and safety-critical corner cases.
- Variance Reduction: The proposed variance reductions combine baseline subtraction, a non-learned hard-safety component, and an Option Graph with gating.The Option Graph addresses horizon-related variance, while decomposition addresses variance from rare safety-critical events.
3 Variance Reduction
The paper extends policy-gradient variance-reduction techniques to the non-Markovian setting, using baselines and non-Markovian analogues of Q and value functions. Baselines can be estimated through a linear system or updated online.
- Baseline subtraction: Policy gradients can use baseline subtraction without requiring the baseline to depend on the current action or future trajectory.The baseline may depend on prior states, the current state, and policy parameters, but not on the current action or future states.
- Baseline subtraction: The optimal baseline is obtained by solving Xb = y, where X captures score-function correlations and y correlates returns with those scores.The paper proposes estimating X and y from episode mini-batches, or updating the baseline through online linear regression.
- Non-Markovian value estimates: Non-Markovian policy-gradient variants can replace the return with an analogue of the Q-function defined over trajectory histories.An unbiased estimator may use a random-variable approximation whose expectation equals the history-dependent Q-function.
- Non-Markovian value estimates: The corresponding advantage function is history-dependent and harder to estimate, so the experiments use return-minus-baseline estimators.The advantage is expressed as Qθ(trajectory history) minus a value estimate conditioned on the preceding history and current state.
4 Safe Reinforcement Learning
The paper addresses functional-safety problems in expected-reward reinforcement learning by separating learned driving desires from non-learned trajectory planning with hard safety constraints. In the double-merge setting, desires encode speed, lateral position, and negotiation choices, while the planner selects a safe trajectory.
- Safety problem: Rare accidents require extremely large negative rewards under expected-reward learning, creating variance that can make even the objective difficult to estimate.For accident probability p = 10^-9, the paper states that the penalty r must be extremely large; Var[R] is approximately pr^2 when r ≥ 1/p.
- Safety architecture: The paper injects hard safety constraints outside learning by composing a learnable Desires policy with a non-learned trajectory planner.The learned policy maps states to Desires, while the planner maps Desires to trajectories through constrained optimization.
- Safety architecture: The trajectory planner preserves functional safety while using learned Desires to support comfortable strategic decisions.The learned component selects goals such as overtaking or giving way; the planner enforces constraints such as staying on the roadway and avoiding nearby vehicles.
- Double-merge policy: The double-merge maneuver requires negotiation because vehicles approach from both sides and may either continue or merge across, making trajectory enumeration difficult.Dense traffic requires vehicles to negotiate right of way while avoiding failure to merge in time.
- Double-merge policy: In the double-merge scenario, Desires combine target speed, lateral position, and per-vehicle labels for giving way, taking way, or maintaining an offset.The lateral-position set includes lane centers and boundaries, while vehicle labels are drawn from {g, t, o}.
- Double-merge policy: The planner translates Desires into trajectory costs for speed, lateral position, and interactions with other vehicles, then minimizes their weighted sum subject to hard constraints.Interaction costs encode desired arrival-time ordering at trajectory intersections, including a 0.5-second separation preference.
5 Temporal Abstraction
The paper introduces an options graph that organizes driving decisions hierarchically as a traversal through a directed acyclic graph. This temporal abstraction reduces the effective decision horizon and the policy-gradient variance while narrowing the output choices at each node.
- Motivation: The options graph addresses the large or continuous Desires space and the high variance caused by long decision horizons.In the double-merge example, the episode horizon is roughly T = 250 steps.
- Options graph: An options graph is a hierarchical DAG traversed from a root node to a leaf, with each internal node selecting a child through its policy.The policy parameters are organized by node, and the resulting Desires are defined by the root-to-leaf traversal.
- Double-merge graph: The double-merge graph first selects merge-area preparation, lane-change behavior, and maneuver feasibility before choosing speed and per-vehicle semantic labels.The vehicle-label chain assigns each other vehicle a meaning such as give way, take way, or offset, with shared parameters across the chain.
- Variance reduction: Lower-frequency decisions or option termination reduce the effective horizon from roughly 250 steps to an order of magnitude smaller value.The paper describes decisions every second or gradient updates after option termination instead of decisions every 0.1 seconds.
- Benefits: The options graph reduces variance and sample complexity by decomposing decisions into smaller sequences and reducing the output space at each node.The paper also identifies interpretability as an immediate benefit of the graph structure.
6 Experimental Demonstration
The paper demonstrates its framework on a challenging double-merge negotiation scenario, using proprietary modules and data. The learner must achieve a smooth merge while preserving other vehicles’ comfort and driving patterns.
- Experimental Demonstration: The experiment is a demonstration rather than a reproducible comparison because it relies on proprietary software modules and data.A reproducible experiment with comparisons to other approaches is left for future work.
- Experimental Demonstration: The demonstration evaluates a challenging double-merge task in which vehicles from both sides are strongly motivated to merge.Failure to merge in time results in ending on the wrong side of the intersection.
- Experimental Demonstration: The reward accounts for merge success or failure, smoothness of trajectory control, and the comfort of other vehicles.The objective therefore includes both maneuver completion and traffic-compatible behavior.
- Experimental Demonstration: The sensing state represents lane geometry and free space, nearby vehicles’ locations, velocities, and headings, plus the required post-merge side.Other vehicles within 100 meters are observed, and the desired side is provided 300 meters before the merging area.
A.1 Proof of Theorem 1
Theorem 1 establishes a policy-gradient derivation for trajectory distributions without assuming that the environment is Markovian. The derivation relies on actions depending only on the current state and eliminates environment-transition terms because they do not depend on policy parameters.
- A.1 Proof of Theorem 1: The policy induces a probability distribution over state-action sequences for trajectories of length T.The proof begins by representing sequences as ordered state-action pairs.
- A.1 Proof of Theorem 1: The derivation makes no assumptions about the conditional distribution of the next state given the prior history.This distinguishes the result from MDP formulations requiring conditional independence from earlier history.
- A.1 Proof of Theorem 1: The sole stated behavioral assumption is that each random action choice depends only on the current state.This restriction comes from the chosen policy-function hypothesis space.
- A.1 Proof of Theorem 1: The likelihood-ratio derivation removes environment-transition probabilities from the policy gradient because they do not depend on θ.The proof invokes the standard likelihood-ratio trick after applying this parameter-independence observation.
A.2 Proof of Lemma 1
The proof of Lemma 1 is completed by applying Lemma 4, which makes the parenthesized term equal to zero.
- A.2 Proof of Lemma 1: Lemma 4 sets the term in parentheses to zero, completing the proof of Lemma 1.The supplied proof passage states that the claim follows from this result.
A.3 Proof of Lemma 2
The proof of Lemma 2 follows directly from Theorem 1.
- A.3 Proof of Lemma 2: The proof concludes that the claim follows from Theorem 1.No further proof steps are supplied in the passage.
A.4 Proof of Lemma 3
The proof bounds E[R(¯s)] within an interval and uses that bound to constrain its square.
- E[R(¯s)] lies in [−pr − (1 − p), −pr + (1 − p)].
- The interval bound implies E[R(¯s)]2 ≤ (pr + (1 − p))2.
- The squared expectation is therefore bounded by the square of pr + (1 − p).
A.5 Technical Lemmas
Lemma 4 begins by imposing a condition on the policy πθ for every parameter θ and state s.
- Lemma 4 assumes that πθ is a function satisfying a condition for every θ and s.
- The stated assumption applies uniformly across policy parameters θ.
- The stated assumption also applies for every state s.