Tactical Game-theoretic Decision-making with Homotopy Class Constraints

We propose a tactical homotopy-aware decision-making 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...