Potential-dominant solver speeds up multi-agent equilibrium problems
PDO-Split: A Real-Time Solver for Constrained Potential-Dominant Games
Computer Science and Game Theory
Summary
Solving planning problems where multiple decision-makers act simultaneously can be very slow, especially when many agents are involved. The authors present PDO-Split, a method that breaks down these complex problems by focusing on parts where agents cooperate more than compete. This approach allows faster and more reliable solutions for tasks like coordinating cars in traffic or races. They also tested their method on small autonomous race cars, showing it works in real time.
What this means in practice
- •For autonomous vehicle developers: Coordinate multiple autonomous cars in real time for tasks like racing or traffic merging using faster multi-agent equilibrium solvers.$Commercial implications: Enables production-level multi-agent control systems for autonomous cars with improved speed and reliability.
- •For robotics control engineers: Implement real-time multi-agent game-theoretic control in robotic fleets requiring constrained coordination under competitive and cooperative influences.
Authors
Zhiyuan Zhang, Yue Guan, Panagiotis Tsiotras
Abstract
We present Potential-Dominant Operator Splitting (PDO-Split), a real-time generalized Nash equilibrium solver for constrained dynamic multi-agent problems with potential-dominant structure. PDO-Split targets the computational bottleneck in game-theoretic model predictive control, where repeatedly solving the equilibrium KKT system becomes costly as the number of agents increases. We introduce a class of gamma-potential-dominant games, in which the potential (or cooperative) structure dominates the competitive interactions between the agents. We show that this structure allows PDO-Split to use the potential component as a preconditioner while incorporating the competitive component through iterative refinement. We establish convergence guarantees and exploit the symmetry of the potential component through a reusable LDL^T factorization to accelerate the linear solvers. We evaluate PDO-Split across several practical multi-agent planning problems, including eight-car racing and six-vehicle ramp merging, achieving substantially improved runtime and convergence rate over existing DDP-based and Newton-based methods, especially with a larger number of agents. The algorithm is also experimentally validated on miniature autonomous race car platforms, demonstrating the approach's real-time capability.