Real-Time LaCAM for Real-Time MAPF
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911078981566464 |
|---|---|
| author | Liang, Runzhe Veerapaneni, Rishi Harabor, Daniel Li, Jiaoyang Likhachev, Maxim |
| author_facet | Liang, Runzhe Veerapaneni, Rishi Harabor, Daniel Li, Jiaoyang Likhachev, Maxim |
| contents | The vast majority of Multi-Agent Path Finding (MAPF) methods with completeness guarantees require planning full-horizon paths. However, planning full-horizon paths can take too long and be impractical in real-world applications. Instead, real-time planning and execution, which only allows the planner a finite amount of time before executing and replanning, is more practical for real-world multi-agent systems. Several methods utilize real-time planning schemes but none are provably complete, which leads to livelock or deadlock. Our main contribution is Real-Time LaCAM, the first Real-Time MAPF method with provable completeness guarantees. We do this by leveraging LaCAM (Okumura 2023) in an incremental fashion. Our results show how we can iteratively plan for congested environments with a cutoff time of milliseconds while still maintaining the same success rate as full-horizon LaCAM. We also show how it can be used with a single-step learned MAPF policy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06091 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Real-Time LaCAM for Real-Time MAPF Liang, Runzhe Veerapaneni, Rishi Harabor, Daniel Li, Jiaoyang Likhachev, Maxim Multiagent Systems Artificial Intelligence Robotics The vast majority of Multi-Agent Path Finding (MAPF) methods with completeness guarantees require planning full-horizon paths. However, planning full-horizon paths can take too long and be impractical in real-world applications. Instead, real-time planning and execution, which only allows the planner a finite amount of time before executing and replanning, is more practical for real-world multi-agent systems. Several methods utilize real-time planning schemes but none are provably complete, which leads to livelock or deadlock. Our main contribution is Real-Time LaCAM, the first Real-Time MAPF method with provable completeness guarantees. We do this by leveraging LaCAM (Okumura 2023) in an incremental fashion. Our results show how we can iteratively plan for congested environments with a cutoff time of milliseconds while still maintaining the same success rate as full-horizon LaCAM. We also show how it can be used with a single-step learned MAPF policy. |
| title | Real-Time LaCAM for Real-Time MAPF |
| topic | Multiagent Systems Artificial Intelligence Robotics |
| url | https://arxiv.org/abs/2504.06091 |