Multi-Robot Coordination Induced in an Adversarial Graph-Traversal Game
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913521678155776 |
|---|---|
| author | Berneburg, James Wang, Xuan Xiao, Xuesu Shishika, Daigo |
| author_facet | Berneburg, James Wang, Xuan Xiao, Xuesu Shishika, Daigo |
| contents | This paper presents a game theoretic formulation of a graph traversal problem, with applications to robots moving through hazardous environments in the presence of an adversary, as in military and security scenarios. The blue team of robots moves in an environment modeled by a time-varying graph, attempting to reach some goal with minimum cost, while the red team controls how the graph changes to maximize the cost. The problem is formulated as a stochastic game, so that Nash equilibrium strategies can be computed numerically. Bounds are provided for the game value, with a guarantee that it solves the original problem. Numerical simulations demonstrate the results and the effectiveness of this method, particularly showing the benefit of mixing actions for both players, as well as beneficial coordinated behavior, where blue robots split up and/or synchronize to traverse risky edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_08222 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Multi-Robot Coordination Induced in an Adversarial Graph-Traversal Game Berneburg, James Wang, Xuan Xiao, Xuesu Shishika, Daigo Computer Science and Game Theory Robotics This paper presents a game theoretic formulation of a graph traversal problem, with applications to robots moving through hazardous environments in the presence of an adversary, as in military and security scenarios. The blue team of robots moves in an environment modeled by a time-varying graph, attempting to reach some goal with minimum cost, while the red team controls how the graph changes to maximize the cost. The problem is formulated as a stochastic game, so that Nash equilibrium strategies can be computed numerically. Bounds are provided for the game value, with a guarantee that it solves the original problem. Numerical simulations demonstrate the results and the effectiveness of this method, particularly showing the benefit of mixing actions for both players, as well as beneficial coordinated behavior, where blue robots split up and/or synchronize to traverse risky edges. |
| title | Multi-Robot Coordination Induced in an Adversarial Graph-Traversal Game |
| topic | Computer Science and Game Theory Robotics |
| url | https://arxiv.org/abs/2409.08222 |