Who Plays First? Optimizing the Order of Play in Stackelberg Games with Many Robots
This addresses coordination challenges in multi-robot systems like traffic and swarms, though it is an incremental improvement on existing Stackelberg game methods.
The paper tackles the problem of determining the optimal sequence for agents to commit to decisions in multi-agent Stackelberg games, introducing the Branch and Play algorithm that provably converges to a socially optimal order of play and equilibrium. It demonstrates practical utility in air traffic control, swarm formation, and delivery fleets, outperforming baselines.
We consider the multi-agent spatial navigation problem of computing the socially optimal order of play, i.e., the sequence in which the agents commit to their decisions, and its associated equilibrium in an N-player Stackelberg trajectory game. We model this problem as a mixed-integer optimization problem over the space of all possible Stackelberg games associated with the order of play's permutations. To solve the problem, we introduce Branch and Play (B&P), an efficient and exact algorithm that provably converges to a socially optimal order of play and its Stackelberg equilibrium. As a subroutine for B&P, we employ and extend sequential trajectory planning, i.e., a popular multi-agent control approach, to scalably compute valid local Stackelberg equilibria for any given order of play. We demonstrate the practical utility of B&P to coordinate air traffic control, swarm formation, and delivery vehicle fleets. We find that B&P consistently outperforms various baselines, and computes the socially optimal equilibrium.