Lasse Peters

Contingency Games

Contingency Games for Multi-Agent Interaction

@inproceedings{peters2023arXiv,
    title     = {Contingency Games for Multi-Agent Interaction},
    author    = {Peters, Lasse and Bajcsy, Andrea and Chiu, Chih-Yuan, and Fridovich-Keil, David and Laine, Forrest, and Ferranti, Laura and Alonso-Mora, Javier},
    booktitle = {arXiv e-prints},
    year      = {2023},
    url       = {https://arxiv.org/abs/2304.05483}
}

News

Abstract

Contingency planning, wherein an agent generates a set of possible plans conditioned on the outcome of an uncertain event, is an increasingly popular way for robots to act under uncertainty. In this work, we take a game-theoretic perspective on contingency planning which is tailored to multi-agent scenarios in which a robot’s actions impact the decisions of other agents and vice versa. The resulting contingency game allows the robot to efficiently coordinate with other agents by generating strategic motion plans conditioned on multiple possible intents for other actors in the scene. Contingency games are parameterized via a scalar variable which represents a future time at which intent uncertainty will be resolved. Varying this parameter enables a designer to easily adjust how conservatively the robot behaves in the game. Interestingly, we also find that existing variants of game-theoretic planning under uncertainty are readily obtained as special cases of contingency games. Lastly, we offer an efficient method for solving N-player contingency games with nonlinear dynamics and non-convex costs and constraints. Through a series of simulated autonomous driving scenarios, we demonstrate that plans generated via contingency games provide quantitative performance gains over game-theoretic motion plans that do not account for future uncertainty reduction.

The Key Idea of Contingency Games

Contingency games are best understood through an example. The figure below shows an autonomous vehicle (the ego-agent) encountering a jay-walking pedestrian. In this scenario, the ego-agent is uncertain about the pedestrian’s goal position.

By solving a contingency game, the ego-agent yields a strategic motion plan that accounts for initial intent uncertainty while capturing future uncertainty reduction. The key idea enabling a tractable solution of contingency games is the introduction of simplified belief dynamics. Rather than capturing the changes of the belief at every time-step, contingency games consider two phases which are separated by the so-called branching time:

  • Before the branching time, the ego-agent cannot discern the pedestrian’s intent; thus it must generate a single motion plan that trades off between all possible hypotheses weighted by their likelihood
  • After the branching time, the ego-agent is certain about the pedestrian’s intent; thus it can generate a distinct motion plan for each intent hypothesis.

The resulting contingency plan consists of multiple branches; each of which is optimized against a distinct intent hypothesis of the opponent.

You can build intuition for this planning framework by playing with the interactive demo below.

Here are a few observations that we encourage you to explore::

  • As you vary the belief of the ego-agent, observe how the robot balances the cost of each branch according to their likelihood. For example, when you set the belief to be “almost certain” that the opponent will go to the right, about one hypothesis, observe how the robot plans to pass on the right while generating a backup plan that allows to still swerve over to the right.

  • As you vary the branching time, observe how different information gain dynamics affect the aggressiveness of the plan. If the robot can reach certainty about its opponent’s intent early, it can commit to a branch earlier and thus be more aggressive in its motion plan. If the robot cannot reach certainty about its opponent’s intent early, it must be more conservative.

  • For extreme values of the branching time, you can find two interesting special case:

    • For immediate branching, the robot generates a certainty-equivalent plan
    • When the branching time is set to the length of the planning horizon, the plan never branches and the ego-agent generates a single plan that minimizes the expected cost of all possible hypotheses.

Code

This project has produced a range of software packages which we will link here as they become available:

  • ParametricMCPs.jl: The mixed-complementary problem backend for our contingency game solver.

Supplementary Material

Slides

Short Summary

Talks

2023-05-13 at Nuro


Last Updated: 2023-05-13