Anytime Single-Step MAPF Planning with Anytime PIBT
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_ | 1866915235989815296 |
|---|---|
| author | Gandotra, Nayesha Veerapaneni, Rishi Saleem, Muhammad Suhail Harabor, Daniel Li, Jiaoyang Likhachev, Maxim |
| author_facet | Gandotra, Nayesha Veerapaneni, Rishi Saleem, Muhammad Suhail Harabor, Daniel Li, Jiaoyang Likhachev, Maxim |
| contents | PIBT is a popular Multi-Agent Path Finding (MAPF) method at the core of many state-of-the-art MAPF methods including LaCAM, CS-PIBT, and WPPL. The main utility of PIBT is that it is a very fast and effective single-step MAPF solver and can return a collision-free single-step solution for hundreds of agents in less than a millisecond. However, the main drawback of PIBT is that it is extremely greedy in respect to its priorities and thus leads to poor solution quality. Additionally, PIBT cannot use all the planning time that might be available to it and returns the first solution it finds. We thus develop Anytime PIBT, which quickly finds a one-step solution identically to PIBT but then continuously improves the solution in an anytime manner. We prove that Anytime PIBT converges to the optimal solution given sufficient time. We experimentally validate that Anytime PIBT can rapidly improve single-step solution quality within milliseconds and even find the optimal single-step action. However, we interestingly find that improving the single-step solution quality does not have a significant effect on full-horizon solution costs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_07841 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Anytime Single-Step MAPF Planning with Anytime PIBT Gandotra, Nayesha Veerapaneni, Rishi Saleem, Muhammad Suhail Harabor, Daniel Li, Jiaoyang Likhachev, Maxim Artificial Intelligence Multiagent Systems PIBT is a popular Multi-Agent Path Finding (MAPF) method at the core of many state-of-the-art MAPF methods including LaCAM, CS-PIBT, and WPPL. The main utility of PIBT is that it is a very fast and effective single-step MAPF solver and can return a collision-free single-step solution for hundreds of agents in less than a millisecond. However, the main drawback of PIBT is that it is extremely greedy in respect to its priorities and thus leads to poor solution quality. Additionally, PIBT cannot use all the planning time that might be available to it and returns the first solution it finds. We thus develop Anytime PIBT, which quickly finds a one-step solution identically to PIBT but then continuously improves the solution in an anytime manner. We prove that Anytime PIBT converges to the optimal solution given sufficient time. We experimentally validate that Anytime PIBT can rapidly improve single-step solution quality within milliseconds and even find the optimal single-step action. However, we interestingly find that improving the single-step solution quality does not have a significant effect on full-horizon solution costs. |
| title | Anytime Single-Step MAPF Planning with Anytime PIBT |
| topic | Artificial Intelligence Multiagent Systems |
| url | https://arxiv.org/abs/2504.07841 |