Lasse Peters
Contingency Games
@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}
}
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.
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:
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:
This project has produced a range of software packages which we will link here as they become available: