Introducing Delays in Multi-Agent Path Finding
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910415380807680 |
|---|---|
| author | Kottinger, Justin Geft, Tzvika Almagor, Shaull Salzman, Oren Lahijanian, Morteza |
| author_facet | Kottinger, Justin Geft, Tzvika Almagor, Shaull Salzman, Oren Lahijanian, Morteza |
| contents | We consider a Multi-Agent Path Finding (MAPF) setting where agents have been assigned a plan, but during its execution some agents are delayed. Instead of replanning from scratch when such a delay occurs, we propose delay introduction, whereby we delay some additional agents so that the remainder of the plan can be executed safely. We show that finding the minimum number of additional delays is APX-Hard, i.e., it is NP-Hard to find a $(1+\varepsilon)$-approximation for some $\varepsilon>0$. However, in practice we can find optimal delay-introductions using Conflict-Based Search for very large numbers of agents, and both planning time and the resulting length of the plan are comparable, and sometimes outperform the state-of-the-art heuristics for replanning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_11252 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Introducing Delays in Multi-Agent Path Finding Kottinger, Justin Geft, Tzvika Almagor, Shaull Salzman, Oren Lahijanian, Morteza Robotics Multiagent Systems We consider a Multi-Agent Path Finding (MAPF) setting where agents have been assigned a plan, but during its execution some agents are delayed. Instead of replanning from scratch when such a delay occurs, we propose delay introduction, whereby we delay some additional agents so that the remainder of the plan can be executed safely. We show that finding the minimum number of additional delays is APX-Hard, i.e., it is NP-Hard to find a $(1+\varepsilon)$-approximation for some $\varepsilon>0$. However, in practice we can find optimal delay-introductions using Conflict-Based Search for very large numbers of agents, and both planning time and the resulting length of the plan are comparable, and sometimes outperform the state-of-the-art heuristics for replanning. |
| title | Introducing Delays in Multi-Agent Path Finding |
| topic | Robotics Multiagent Systems |
| url | https://arxiv.org/abs/2307.11252 |