PaperlayerView exact revision on arXiv

Source-linked AI summary

Hierarchical Game-Theoretic Planning for Autonomous Vehicles

Jaime F. Fisac, Eli Bronstein, Elis Stefansson, Dorsa Sadigh, S. Shankar Sastry, Anca D. Dragan

arXiv:1810.05766v1cs.ROcs.AIcs.MAmath.OC

TL;DR

Autonomous-driving planners must account for mutual influence between the autonomous vehicle and human drivers, but exact dynamic games are too expensive for real-time use. The paper introduces a hierarchical decomposition using a long-horizon strategic game and short-horizon tactical planning, and reports richer, safer, and more effective behavior, including successful overtaking in a simulated scenario.

  • Problem

    Prediction-planning pipelines treat human trajectories as unalterable obstacles, while exact dynamic games are computationally demanding for real-time autonomous driving.

  • Method

    The framework solves a long-horizon dynamic game with simplified dynamics and uses its value to guide short-horizon tactical planning, while permitting probabilistic human models.

  • Results

    The hierarchical autonomous vehicle successfully completed a simulated overtaking maneuver, reaching a maximum speed of 39.94 m/s, 4.94 m/s above its target speed.

  • Takeaways & Limitations

    The framework is intended to enhance existing autonomous-driving planners by accounting for mutual influence with human drivers while remaining tractable.

Abstract

from arXiv · show

The actions of an autonomous vehicle on the road affect and are affected by those of other drivers, whether overtaking, negotiating a merge, or avoiding an accident. This mutual dependence, best captured by dynamic game theory, creates a strong coupling between the vehicle's planning and its predictions of other drivers' behavior, and constitutes an open problem with direct implications on the safety and viability of autonomous driving technology. Unfortunately, dynamic games are too computationally demanding to meet the real-time constraints of autonomous driving in its continuous state and action space. In this paper, we introduce a novel game-theoretic trajectory planning algorithm for autonomous driving, that enables real-time performance by hierarchically decomposing the underlying dynamic game into a long-horizon "strategic" game with simplified dynamics and full information structure, and a short-horizon "tactical" game with full dynamics and a simplified information structure. The value of the strategic game is used to guide the tactical planning, implicitly extending the planning horizon, pushing the local trajectory optimization closer to global solutions, and, most importantly, quantitatively accounting for the autonomous vehicle and the human driver's ability and incentives to influence each other. In addition, our approach admits non-deterministic models of human decision-making, rather than relying on perfectly rational predictions. Our results showcase richer, safer, and more effective autonomous behavior in comparison to existing techniques.

I. INTRODUCTION

The paper frames autonomous driving as a mutual-influence problem that standard prediction-planning pipelines handle inadequately. It introduces a hierarchical game-theoretic framework that preserves this interaction while maintaining computational tractability.

  • Motivation: Standard pipelines feed predicted human trajectories to planning as unalterable moving obstacles, producing excessively conservative and sometimes unsafe behavior.This separates prediction from planning instead of modeling their mutual influence.
  • Motivation: Recent game-theoretic approaches model humans as utility-driven followers, but assume they accommodate an autonomous vehicle’s future trajectory rather than influence it.The paper identifies this as an inversion of the roles in earlier pipeline approaches.
  • Contribution: The proposed framework addresses mutual influence through a long-horizon coupled interaction model while maintaining computational tractability.The strategic interaction spans multiple seconds and allows the drivers to affect each other through actions over time.
  • Contribution: The strategic planner uses simplified dynamics and full interaction, while the tactical planner uses high-fidelity dynamics and simplified interaction informed by strategic value.The high-level value is incorporated as a terminal component of short-horizon trajectory optimization, implicitly extending its planning horizon.
  • Contribution: The framework supports probabilistic human decision models, including noisy rationality, rather than requiring deterministic ideal-rational predictions.It is also agnostic to the tactical planner and can enhance alternative planning schemes through a strategic terminal cost.
  • Scope: The framework’s safety and efficiency depend on the designer’s optimization objective, which can encode comfort and safety for other road users.Solving the dynamic game does not inherently make the autonomous vehicle more aggressive.

II. DYNAMIC GAME FORMULATION

The formulation models an autonomous vehicle and human driver as strategically coupled agents whose joint actions determine cumulative objectives. Exact dynamic-game solutions are computationally prohibitive, motivating approximate models and a pairwise scope.

  • Game formulation: The formulation considers one human driver and one autonomous system controlling vehicles with fully observable joint state dynamics.Each player selects driving controls from a compact action set.
  • Game formulation: The autonomous vehicle maximizes a finite-horizon cumulative return over the evolution of both vehicles.Its reward may include fuel consumption, comfort, courteousness, time efficiency, and safety.
  • Game formulation: Because safety and other objectives can depend on the human’s actions, the autonomous vehicle must reason about both vehicles’ future actions.The reward can also penalize causing other vehicles to maneuver abruptly.
  • Game formulation: When the human is modeled as optimizing her own objective, the explicit coupling forms a dynamic game in which each player accounts for the other’s possible actions.Human actions are predicted as functions of currently available information, including the joint state and possibly the autonomous vehicle’s current action.
  • Tractability: Exact strategy derivation is computationally prohibitive because computation scales exponentially with the dimensionality of the joint state space.The paper argues that several-second traffic interactions can yield useful insights from approximate rather than full-fidelity vehicle dynamics.
  • Scope: The practical formulation is limited to pairwise interactions because extending computation to N vehicles scales exponentially in the number of vehicles.The extension is theoretically well-defined, while recent prediction approaches may enable viable extensions.

III. HIERARCHICAL GAME-THEORETIC PLANNING

The hierarchical planner separates long-horizon strategic interaction from short-horizon trajectory execution. It solves the strategic game with approximate dynamics and uses its value to guide tactical planning, while allowing probabilistic human responses.

  • Strategic planner: The high-level planner solves a long-horizon dynamic game through approximate dynamics, producing a value function that estimates achievable long-term outcomes from each state.The approximation reduces state and action dimensionality to improve tractability.
  • Tactical planner: The low-level planner incorporates the strategic value as a guiding terminal reward while optimizing short-horizon trajectories with the full planning model.The value is used for guidance rather than executing actions from the simplified dynamics directly.
  • Information structure: The strategic game uses feedback closed-loop information, allowing the human’s action to depend on the autonomous vehicle’s current action at each time step.This produces a Stackelberg dynamic game in which the autonomous vehicle is the leader.
  • Human model: The human follower can use a probability distribution over actions, enabling noisy rationality and models learned through inverse optimal control.Probabilistic responses also provide a way to account for inevitable departures from modeling assumptions.
  • Dynamic programming: The framework generalizes feedback Stackelberg dynamic programming to a noisy follower whose decision rule depends on the follower’s own state-action values.The leader therefore solves a nested optimization involving the human’s decision rule and Q values.
  • Computation: The discretized strategic computation has complexity O(|Ŝ| · |Â_A| · |Â_H| · K) but is highly parallelizable, theoretically permitting time complexity O(K).The authors expect advances in autonomous-driving hardware to support online computation of strategic value.

B. Tactical planner: Open-loop trajectory optimization

The tactical planner performs short-horizon, receding-horizon trajectory optimization while using the strategic value as a terminal guide to account for longer-term outcomes.

  • B. Tactical planner: Open-loop trajectory optimization: The strategic value estimates optimal reward-to-go beyond the tactical planning window and guides the optimizer toward states with desirable long-term performance.This extends the effective planning horizon beyond a single short trajectory-optimization window.
  • B. Tactical planner: Open-loop trajectory optimization: The tactical planner optimizes short-term vehicle trajectories with a horizon M much shorter than the strategic horizon N.It uses a high-fidelity vehicle model and a short-term predictive model of human decisions.
  • B. Tactical planner: Open-loop trajectory optimization: The tactical objective differs from standard receding-horizon optimization only by adding the strategic value as a terminal term.The strategic value can be implemented as a grid-based look-up table providing values and numerically approximated gradients.
  • B. Tactical planner: Open-loop trajectory optimization: The low-level optimization runs online using a trajectory optimizer that estimates the human’s best response to each candidate autonomous-vehicle plan.The demonstrated implementation uses a quasi-Newton scheme with nested optimization.

IV. RESULTS

The results section compares the hierarchical planner with tactical-only planning and examines which components of the hierarchy improve performance.

  • IV. RESULTS: The evaluation compares the hierarchical approach with a tactical planner alone, following state-of-the-art approaches.The comparison is designed to assess the benefit of solving the dynamic game hierarchically.
  • IV. RESULTS: Additional analysis studies which aspects of the hierarchical method contribute to better performance.The experiments specifically highlight the role of reasoning with the fully coupled information structure of the dynamic game.

1) Environment:

The case studies use a simulated two-lane highway with one autonomous car and one human-driven vehicle, modeled with safety and efficiency objectives.

  • 1) Environment:: The environment contains an autonomous car and a human-driven vehicle on a simulated two-lane highway.Both vehicles’ rewards include safety, efficiency or progress, and a preference for the left lane.
  • 1) Environment:: The autonomous car additionally prefers a target speed slightly above the human’s and prefers being ahead of the human.These preferences are included in the autonomous car’s reward for the case studies.
  • 1) Environment:: Each vehicle uses a dynamic bicycle model with a discrete time step of ∆t = 0.1 s, while the planner uses M = 5 time steps.The tactical planning horizon therefore covers 0.5 s.

3) Strategic-Level Dynamics:

The strategic level reduces the vehicle-interaction model to make long-horizon dynamic programming tractable, using coarse time discretization, reduced state representations, and approximate dynamics.

  • 3) Strategic-Level Dynamics:: The strategic model uses ∆k = 0.5 s and K = 10, representing a 5 s horizon on the straight highway.It retains relative longitudinal position while assuming nominal human speed and aligned headings.
  • 3) Strategic-Level Dynamics:: One high-level model assumes the human remains in the left lane, reducing the state to [xrel, yA, vrel].Its approximate dynamics use relative velocity, autonomous lateral velocity, vehicle accelerations, and friction.
  • 3) Strategic-Level Dynamics:: A second model allows dynamic human lateral position, augmenting the state with yH and solving the resulting game on a 75 × 12 × 12 × 21 grid.The feedback Stackelberg solution is computed with Algorithm 1.
  • 3) Strategic-Level Dynamics:: The constant-human-lateral-position model supports computation on a 101 × 17 × 43 grid for the feedback Stackelberg solution.The model uses a friction parameter and autonomous lateral velocity alongside longitudinal accelerations.
  • 3) Strategic-Level Dynamics:: The simulated human driver uses a low-level trajectory optimizer and accurately predicts the autonomous vehicle’s imminent 0.5 s state trajectory.This setup produced sufficiently realistic behavior for the simple maneuvers considered.

B. Main Case Studies

Across three driving scenarios, hierarchical planners completed maneuvers that the tactical planner only partially completed or failed to complete. The experiments also show how strategic value and human-response modeling shape overtaking behavior.

  • B. Main Case Studies: The case studies compare tactical short-horizon planning with hierarchical planners using constant or dynamic human lateral position across three scenarios.A successful maneuver is defined as overtaking and merging in front of the human-driven car.
  • B. Main Case Studies: The tactical optimization omits the local human-response estimate and uses iterated local best response between candidate plans and predicted human trajectories.The stated approximation makes the reward easier to optimize and empirically produces less aggressive behavior.
  • 1) Easy Merge: In the typical merge, both hierarchical planners merged quickly in front of the human, whereas the tactical planner merged slowly.The hierarchical planners received the larger left-lane reward sooner.
  • 2) Hard Merge: In the hard merge, the tactical planner overtook without entering the left lane, while both hierarchical planners overtook and merged in front of the human.This comparison is depicted in Fig. 2.
  • 3) Overtaking: In complete overtaking, the tactical planner accelerated then braked and remained behind, while the constant-position hierarchical planner completed both lane changes and overtook.It reached 39.94 m/s, 4.94 m/s above its target speed.
  • 3) Overtaking: The dynamic-position hierarchical planner used strategic value to consider tailgating and lane-change alternatives depending on whether the human changed lanes.If tailgating succeeds, the autonomous vehicle overtakes from the left; otherwise, it can execute the lane-change strategy.

C. In-depth Analysis

The analysis shows that hierarchical planning’s advantage comes from modeling the interaction’s information structure, not merely from extending the tactical horizon. Incorrect assumptions about human anticipation or influence can produce poor or unsafe behavior.

  • C. In-depth Analysis: The results support fully coupled information modeling as a key benefit of hierarchical planning, beyond its longer implicit horizon or escape from local optima.The strategic value guides optimization toward globally preferable states, but the experiments identify information structure as the differentiating factor.
  • 1) Hierarchical vs. long-horizon and more global tactical planning:: A 2 s tactical horizon with diverse initializations still failed to complete overtaking, showing that longer-horizon optimization alone did not resolve the problem.The planner remained behind the human and was not real-time; horizons beyond 2 s were not tractable.
  • 1) Hierarchical vs. long-horizon and more global tactical planning:: The stronger tactical planner assumed that the human knew the autonomous vehicle’s future trajectory, causing poor performance when the human did not adapt in advance.Against a slow human driver, the autonomous car braked abruptly to avoid collision and remained behind.
  • 2) Differentiating through human response:: Including the influence term made some hierarchical behaviors more aggressive, producing collisions in the hard merge scenario and aggressive overtaking behavior in one case.Because the term was substantially more expensive and sometimes had no behavioral effect, the authors favored omitting it for these scenarios.
  • 2) Differentiating through human response:: Assuming a human as a pure open-loop follower may encourage overconfident actions that become unsafe when the human fails to preemptively make way.The paper connects this assumption to undesirably aggressive behavior and unsafe situations.

3) Confidence in Strategic Human Model:

The framework can vary confidence in a probabilistic human model through an inverse-temperature parameter. Lower confidence discourages overtaking because the human is modeled as more unpredictable and collision-prone.

  • 3) Confidence in Strategic Human Model:: With inverse temperature 1, the autonomous car successfully overtook the human, whereas values below 0.3 left it behind.These values correspond to different strategic values computed from varying confidence in the Boltzmann noisily rational human model.
  • 3) Confidence in Strategic Human Model:: The framework uses a lower-order approximate dynamical model to solve a closed-loop, nonzero-sum game whose value informs low-level trajectory planning.This decomposition is intended to make reasoning about mutual influence tractable.
  • 3) Confidence in Strategic Human Model:: The high-level computation has favorable online characteristics because all states on the discretized grid may be updated simultaneously.The paper relates this massive parallelism to high-performance parallel computing hardware developed for real-time perception.
  • 3) Confidence in Strategic Human Model:: The authors propose that the framework can enhance existing planners to support safer and more efficient interaction with human drivers.This is presented as a supported application of combining strategic values with existing autonomous-driving planners.
Loading 1810.05766v1…