Layered MAPF Outperforms Raw Methods In Time And Memory Benchmarks

Table Of Links

ABSTRACT

I. INTRODUCTION

II. RELATED WORKS

III. PRELIMINARIES

IV. METHODOLOGY

V. RESULTS OF DECOMPOSITION

VI. RESULTS OF DECOMPOSITION’S APPLICATION

VII. CONCLUSION, ACKNOWLEDGMENTS AND REFERENCES

VII. CONCLUSION

Motivated by the exponential growth in the cost of solving MAPF instances (in terms of time and memory usage) as the number of agents increases, we proposed layered MAPF as a solution to reduce the computational burden. This approach decomposes a MAPF instance into multiple smaller subproblems without compromising solvability.

Each subproblem is solved in isolation, with consideration given to other subproblems’ solutions as dynamic obstacles. Our methodology involves a progressive decomposition of MAPF instances, ensuring that each step preserves solvability. In the results of our decomposition of MAPF instances (Section V), we observed that our method is highly effective for MAPF instances with free grids exceeding twice the number of agents. On average, the time cost is around 1s and never exceeds 3s, even for dense instances with 800 to 1000 agents. Memory usage remains below 1MB, with fewer computations and memory space required for maps with more free grids than agents.

When applied to the state-of-the-art methods (EECBS, PBS, LNS, HCA*, Push and Swap, PIBT+, LaCAM), layered MAPF significantly reduces memory usage and time cost, particularly for serial MAPF methods. Consequently, layered MAPF methods achieve higher success rates than raw MAPF methods, especially for serial MAPF. And the quality of solution for the layered version of serial MAPF methods is similar to the raw version, while the layered version of parallel MAPF methods produces inferior solutions due to the introduction of numerous wait actions during solution merging.

In conclusion, decomposition of MAPF instances is most beneficial for serial MAPF methods, resulting in reduced time cost and memory usage without sacrificing solution quality significantly. However, for parallel MAPF methods, decomposition may reduce memory usage but often worsens the solution without notable improvements in time cost.

Despite its effectiveness, layered MAPF has limitations: it becomes less effective as the number of agents increases in dense instances, and its application to parallel MAPF methods introduces numerous wait actions during solution merging.

In the future, we plan to propose new merging solution techniques for parallel methods without compromising solution quality. Additionally, we aim to generalize the idea of decomposing MAPF instances to address extensions of MAPF problems, such as considering the shape of agents.

ACKNOWLEDGMENTS

The first author thanks Lu Zhu for her encouragement and support during the consummation of Layered MAPF.

REFERENCES

[1] Eli Boyarski et al. “Don’t split, try to work it out: Bypassing conflicts in multi-agent pathfinding”. In: Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 25. 2015, pp. 47–51.

[2] Shao-Hung Chan et al. “Greedy priority-based search for suboptimal multi-agent path finding”. In: Proceedings of the International Symposium on Combinatorial Search. Vol. 16. 1. 2023, pp. 11–19.

[3] Matthew Hatem, Roni Stern, and Wheeler Ruml. “Bounded suboptimal heuristic search in linear space”. In: Proceedings of the International Symposium on Combinatorial Search. Vol. 4. 1. 2013, pp. 98–104.

[4] Jiaoyang Li, Wheeler Ruml, and Sven Koenig. “Eecbs: A bounded-suboptimal search for multi-agent path finding”. In: Proceedings of the AAAI conference on artificial intelligence. Vol. 35. 14. 2021, pp. 12353–12362.

[5] Jiaoyang Li et al. “Anytime multi-agent path finding via large neighborhood search”. In: International Joint Conference on Artificial Intelligence 2021. Association for the Advancement of Artificial Intelligence (AAAI). 2021, pp. 4127–4135.

[6] Jiaoyang Li et al. “Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search.” In: IJCAI. Vol. 2019. 2019, pp. 442–449.

[7] Jiaoyang Li et al. “MAPF-LNS2: Fast repairing for multi-agent path finding via large neighborhood search”. In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. 9. 2022, pp. 10256–10265.

[8] Jiaoyang Li et al. “New techniques for pairwise symmetry breaking in multi-agent path finding”. In: Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 30. 2020, pp. 193–201.

[9] Jiaoyang Li et al. “Symmetry-breaking constraints for grid-based multi-agent path finding”. In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. 01. 2019, pp. 6087–6095.

[10] Ryan Luna and Kostas E Bekris. “Push and swap: Fast cooperative path-finding with completeness guarantees”. In: IJCAI. Vol. 11. 2011, pp. 294–300.

[11] Hang Ma et al. “Searching with consistent prioritization for multi-agent path finding”. In: Proceedings of the AAAI conference on artificial intelligence. Vol. 33. 01. 2019, pp. 7643–7650.

[12] Keisuke Okumura. “Improving lacam for scalable eventually optimal multi-agent pathfinding”. In: arXiv preprint arXiv:2305.03632 (2023). [13] Keisuke Okumura. “Lacam: Search-based algorithm for quick multi-agent pathfinding”. In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. 10. 2023, pp. 11655–11662.

[14] Keisuke Okumura et al. “Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding”. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19. International Joint Conferences on Artificial Intelligence Organization, July 2019, pp. 535–542. DOI: 10.24963/ ijcai.2019/76. URL: https://doi.org/10.24963/ijcai.2019/ 76.

[15] Keisuke Okumura et al. “Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding”. In: Artificial Intelligence (2022), p. 103752. ISSN: 0004- 3702. DOI: https://doi.org/10.1016/j.artint.2022.103752.

[16] Guni Sharon et al. “Conflict-based search for optimal multi-agent pathfinding”. In: Artificial intelligence 219 (2015), pp. 40–66.

[17] David Silver. “Cooperative pathfinding”. In: Proceedings of the aaai conference on artificial intelligence and interactive digital entertainment. Vol. 1. 1. 2005, pp. 117–122.

[18] Roni Stern et al. “Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks”. In: Symposium on Combinatorial Search (SoCS) (2019), pp. 151–158.

[19] Robert Tarjan. “Depth-first search and linear graph algorithms”. In: SIAM journal on computing 1.2 (1972), pp. 146–160.

[20] Jordan Tyler Thayer and Wheeler Ruml. “Bounded suboptimal search: A direct approach using inadmissible estimates”. In: IJCAI. Vol. 2011. 2011, pp. 674–679.

:::info
Authors: