Fast control method improves multi-agent game planning with constraints
Game-Theoretic Control with Constrained Potential Surgery
Robotics
Summary
Planning actions for many agents that interact and have limits is very hard and slow. The authors present a new fast solver that helps agents find good strategies quickly, even when there are limits on their actions. They also add a correction that helps avoid getting stuck in bad solutions. They tested their approach on computer simulations and real small race cars driving together.
What this means in practice
- •For autonomous vehicle teams: Coordinate actions of multiple self-driving cars in dynamic tasks while obeying safety and operational constraints.$Commercial implications: Enables development of real-time multi-vehicle control software for autonomous racing or urban driving fleets with constraints.
- •For robotics control engineers: Design efficient controllers for groups of robots to perform interactive tasks that involve physical or operational limits.
Authors
Zhiyuan Zhang, Panagiotis Tsiotras
Abstract
Constrained general-sum dynamic games are a popular formulation for highly interactive multi-agent planning problems. In recent years, Generalized Nash Equilibrium (GNE) solvers have achieved real-time performance for small dynamic games. However, solution speed still remains a bottleneck, and controlling even a small number of agents (e.g., more than four) in a dynamic task remains elusive. In addition, Newton solvers that focus on the first-order conditions are vulnerable to non-Nash saddle points, limiting the usefulness of the provided solution. In this work, we propose a fast and versatile interior point solver for constrained dynamic games, along with a computationally efficient second-order correction that increases the probability of converging to a local GNE solution in constrained dynamic games. The performance of the proposed method is evaluated on numerical benchmarks and a physical experiment involving scaled race cars.