ホモトピー類制約を用いた戦術的ゲーム理論的意思決定
Tactical Game-theoretic Decision-making with Homotopy Class Constraints
都市運転を一般化ナッシュ均衡問題として定式化し、ホモトピー類で解空間を分割して混合整数二次計画を解くことで、計算効率よく大域的最適な戦術的判断を導く手法を提案した。
著者: Michael Khayyat, Alessandro Zanardi, Stefano Arrigoni, Francesco Braghin
分類: cs.MA, cs.RO
原文アブストラクト
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 and employ a mixed-integer approach 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 to find global optimal Nash equilibria in a computationally tractable manner by solving a mixed-integer quadratic program. Each homotopy decision is represented by a binary variable that activates different sets of linear collision avoidance constraints. This extra homotopic constraint allows to find solutions in a more efficient way (on a roundabout scenario on average 5-times faster). We experimentally validate the proposed approach on scenarios taken from the rounD dataset. Simulation-based testing in receding horizon fashion 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 constraints.
