Congestion-Aware Path Coordination Game With Markov Decision Process Dynamics
| Autor: | Sarah H. Q. Li, Daniel Calderone, Behcet Acikmese |
|---|---|
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
TheoryofComputation_MISCELLANEOUS Computer Science::Computer Science and Game Theory Control and Optimization Control and Systems Engineering ComputingMilieux_PERSONALCOMPUTING TheoryofComputation_GENERAL Computer Science - Multiagent Systems Multiagent Systems (cs.MA) |
| Zdroj: | IEEE Control Systems Letters. 7:431-436 |
| ISSN: | 2475-1456 |
| DOI: | 10.1109/lcsys.2022.3189323 |
| Popis: | Inspired by the path coordination problem arising from robo-taxis, warehouse management, and mixed-vehicle routing problems, we model a group of heterogeneous players responding to stochastic demands as a congestion game under Markov decision process dynamics. Players share a common state-action space but have unique transition dynamics, and each player's unique cost is a {function} of the joint state-action probability distribution. For a class of player cost functions, we formulate the player-specific optimization problem, prove the equivalence between the Nash equilibrium and the solution of a potential minimization problem, and derive dynamic programming approaches to solve the Nash equilibrium. We apply this game to model multi-agent path coordination and introduce congestion-based cost functions that enable players to complete individual tasks while avoiding congestion with their opponents. Finally, we present a learning algorithm for finding the Nash equilibrium that has linear complexity in the number of players. We demonstrate our game model on a multi-robot warehouse \change{path coordination problem}, in which robots autonomously retrieve and deliver packages while avoiding congested paths. 6 pages, 4 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|