Who Plays First? Optimizing the Order of Play in Stackelberg Games with Many Robots
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916299088592896 |
|---|---|
| author | Hu, Haimin Dragotto, Gabriele Zhang, Zixu Liang, Kaiqu Stellato, Bartolomeo Fisac, Jaime F. |
| author_facet | Hu, Haimin Dragotto, Gabriele Zhang, Zixu Liang, Kaiqu Stellato, Bartolomeo Fisac, Jaime F. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_09246 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Who Plays First? Optimizing the Order of Play in Stackelberg Games with Many Robots Hu, Haimin Dragotto, Gabriele Zhang, Zixu Liang, Kaiqu Stellato, Bartolomeo Fisac, Jaime F. Robotics Artificial Intelligence Systems and Control Optimization and Control 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. |
| title | Who Plays First? Optimizing the Order of Play in Stackelberg Games with Many Robots |
| topic | Robotics Artificial Intelligence Systems and Control Optimization and Control |
| url | https://arxiv.org/abs/2402.09246 |