Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.07779 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910938915930112 |
|---|---|
| author | Li, Jiarui Zanardi, Alessandro Zardini, Gioele |
| author_facet | Li, Jiarui Zanardi, Alessandro Zardini, Gioele |
| contents | We present a novel algorithm for large-scale Multi-Agent Path Finding (MAPF) that enables fast, scalable planning in dynamic environments such as automated warehouses. Our approach introduces finite-horizon hierarchical factorization, a framework that plans one step at a time in a receding-horizon fashion. Robots first compute individual plans in parallel, and then dynamically group based on spatio-temporal conflicts and reachability. The framework accounts for conflict resolution, and for immediate execution and concurrent planning, significantly reducing response time compared to offline algorithms. Experimental results on benchmark maps demonstrate that our method achieves up to 60% reduction in time-to-first-action while consistently delivering high-quality solutions, outperforming state-of-the-art offline baselines across a range of problem sizes and planning horizons. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_07779 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multi-Agent Path Finding via Finite-Horizon Hierarchical Factorization Li, Jiarui Zanardi, Alessandro Zardini, Gioele Robotics We present a novel algorithm for large-scale Multi-Agent Path Finding (MAPF) that enables fast, scalable planning in dynamic environments such as automated warehouses. Our approach introduces finite-horizon hierarchical factorization, a framework that plans one step at a time in a receding-horizon fashion. Robots first compute individual plans in parallel, and then dynamically group based on spatio-temporal conflicts and reachability. The framework accounts for conflict resolution, and for immediate execution and concurrent planning, significantly reducing response time compared to offline algorithms. Experimental results on benchmark maps demonstrate that our method achieves up to 60% reduction in time-to-first-action while consistently delivering high-quality solutions, outperforming state-of-the-art offline baselines across a range of problem sizes and planning horizons. |
| title | Multi-Agent Path Finding via Finite-Horizon Hierarchical Factorization |
| topic | Robotics |
| url | https://arxiv.org/abs/2505.07779 |