Tactical Game-Theoretic Decision-Making With Homotopy Class Constraints
- 26 September 2024
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Intelligent Vehicles
- Vol. 10 (7) , 3916-3930
Abstract
We propose a tactical homotopy-aware decisionmaking framework for game-theoretic motion planning in urban environments. We model urban driving as a generalized Nash equilibrium problem (GNEP) with mixed-integer constraints and employ homotopic class constraints to tame the combinatorial aspect of motion planning. More specifically, by utilizing homotopy classes, we partition the high-dimensional solution space into finite, well-defined subregions. Each subregion (homotopy) corresponds to a high-level tactical decision, such as the passing order between pairs of players. The proposed formulation allows finding global optimal Nash equilibria in a computationally tractable manner by solving a mixed-integer quadratic program (MIQP). Each homotopy decision is represented by a binary variable that activates different sets of linear collision avoidance constraints. By guiding the branch-and-bound solver, the introduction of homotopic constraints allows for a more efficient search, leading to faster solutions (on average, 5 times faster in roundabout scenarios). We experimentally validate the proposed approach on scenarios taken from the rounD dataset. Simulationbased testing in a Model Predictive Control (MPC) framework demonstrates the capability of the framework in achieving globally optimal solutions while yielding a 78% average decrease in the computational time with respect to an implementation without the homotopic constraintsKeywords
All Related Versions
This publication has 80 references indexed in Scilit:
- Tailored presolve techniques in branch‐and‐bound method for fast mixed‐integer optimal control applicationsOptimal Control Applications and Methods, 2023
- ALGAMES: a fast augmented Lagrangian solver for constrained dynamic gamesAutonomous Robots, 2021
- Trajectron++: Dynamically-Feasible Trajectory Forecasting with Heterogeneous Data2020
- Potential Games2016
- G1fitting with clothoidsMathematical Methods in the Applied Sciences, 2014
- Inter‐sample avoidance in trajectory optimizers using mixed‐integer linear programmingInternational Journal of Robust and Nonlinear Control, 2013
- Decomposition algorithms for generalized potential gamesComputational Optimization and Applications, 2010
- Generalized Nash Equilibrium ProblemsAnnals of Operations Research, 2009
- Numerical Optimization1999
- Potential GamesGames and Economic Behavior, 1996