Factorization of Dynamic Games over Spatio-Temporal Resources
OPEN ACCESS
Loading...
Author / Producer
Date
2022
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Dynamic games feature a state-space complexity that scales superlinearly with the number of players. This makes this class of games often intractable even for a handful of players. We introduce the factorization process of dynamic games as a transformation leveraging the independence of players at equilibrium to build a leaner game graph. When applicable, it yields fewer nodes, fewer players per game node, hence much faster solutions. While for the general case checking for independence of players requires to solve the game itself, we observe that for dynamic games in the robotic domain there exist exact heuristics based on the spatio-temporal occupancy of the individual players. We validate our findings in realistic autonomous driving scenarios showing that already for a 4-player intersection we have a reduction of game nodes and solving time close to 99%.
Permanent link
Publication status
published
Editor
Book title
2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
Journal / series
Volume
Pages / Article No.
13159 - 13166
Publisher
IEEE
Event
35th IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2022)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Games; Dynamic scheduling; Complexity theory; Intelligent robots; Autonomous vehicles
Organisational unit
09478 - Dörfler, Florian / Dörfler, Florian
09574 - Frazzoli, Emilio / Frazzoli, Emilio
Notes
Funding
180545 - NCCR Automation (phase I) (SNF)