@InProceedings{HPlan2021paper1,
  author           = {Han Zhang and Mingze Yao and Ziang Liu and Jiaoyang Li and Lucas Terr and Shao-Hung Chan and T. K. Satish Kumar and Sven Koenig},
  title            = {A Hierarchical Approach to Multi-Agent Path Finding},
  booktitle        = {Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021)},
  year             = {2021},
  pages            = {1--7},
  abstract         = {The Multi-Agent Path Finding (MAPF) problem arises in many real-world applications, ranging from automated warehousing to multi-drone delivery. Solving the MAPF problem optimally is NP-hard, and existing optimal and bounded-suboptimal MAPF solvers thus usually do not scale to large MAPF instances. Greedy MAPF solvers scale to large MAPF instances, but their solution qualities are often bad. In this paper, we therefore propose a novel MAPF solver, Hierarchical Multi-Agent Path Planner (HMAPP), which creates a spatial hierarchy by partitioning the environment into multiple regions and decomposes a MAPF instance into smaller MAPF sub-instances for each region. For each sub-instance, it uses a bounded-suboptimal MAPF solver to solve it with good solution quality. Our experimental results show that HMAPP solves as large MAPF instances as greedy MAPF solvers while achieving better solution qualities on various maps.},
  url_paper        = {https://hierarchical-task.net/publications/hplan/2021/HPlan2021-paper1.pdf},
  url_presentation = {https://www.youtube.com/watch?v=eBZALSeZpXU&t=3s}
}

{"_id":"5Jq4ppD8NsWbeKssQ","bibbaseid":"zhang-yao-liu-li-terr-chan-kumar-koenig-ahierarchicalapproachtomultiagentpathfinding-2021","author_short":["Zhang, H.","Yao, M.","Liu, Z.","Li, J.","Terr, L.","Chan, S.","Kumar, T. K. S.","Koenig, S."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Han"],"propositions":[],"lastnames":["Zhang"],"suffixes":[]},{"firstnames":["Mingze"],"propositions":[],"lastnames":["Yao"],"suffixes":[]},{"firstnames":["Ziang"],"propositions":[],"lastnames":["Liu"],"suffixes":[]},{"firstnames":["Jiaoyang"],"propositions":[],"lastnames":["Li"],"suffixes":[]},{"firstnames":["Lucas"],"propositions":[],"lastnames":["Terr"],"suffixes":[]},{"firstnames":["Shao-Hung"],"propositions":[],"lastnames":["Chan"],"suffixes":[]},{"firstnames":["T.","K.","Satish"],"propositions":[],"lastnames":["Kumar"],"suffixes":[]},{"firstnames":["Sven"],"propositions":[],"lastnames":["Koenig"],"suffixes":[]}],"title":"A Hierarchical Approach to Multi-Agent Path Finding","booktitle":"Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021)","year":"2021","pages":"1–7","abstract":"The Multi-Agent Path Finding (MAPF) problem arises in many real-world applications, ranging from automated warehousing to multi-drone delivery. Solving the MAPF problem optimally is NP-hard, and existing optimal and bounded-suboptimal MAPF solvers thus usually do not scale to large MAPF instances. Greedy MAPF solvers scale to large MAPF instances, but their solution qualities are often bad. In this paper, we therefore propose a novel MAPF solver, Hierarchical Multi-Agent Path Planner (HMAPP), which creates a spatial hierarchy by partitioning the environment into multiple regions and decomposes a MAPF instance into smaller MAPF sub-instances for each region. For each sub-instance, it uses a bounded-suboptimal MAPF solver to solve it with good solution quality. Our experimental results show that HMAPP solves as large MAPF instances as greedy MAPF solvers while achieving better solution qualities on various maps.","url_paper":"https://hierarchical-task.net/publications/hplan/2021/HPlan2021-paper1.pdf","url_presentation":"https://www.youtube.com/watch?v=eBZALSeZpXU&t=3s","bibtex":"@InProceedings{HPlan2021paper1,\n author = {Han Zhang and Mingze Yao and Ziang Liu and Jiaoyang Li and Lucas Terr and Shao-Hung Chan and T. K. Satish Kumar and Sven Koenig},\n title = {A Hierarchical Approach to Multi-Agent Path Finding},\n booktitle = {Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021)},\n year = {2021},\n pages = {1--7},\n abstract = {The Multi-Agent Path Finding (MAPF) problem arises in many real-world applications, ranging from automated warehousing to multi-drone delivery. Solving the MAPF problem optimally is NP-hard, and existing optimal and bounded-suboptimal MAPF solvers thus usually do not scale to large MAPF instances. Greedy MAPF solvers scale to large MAPF instances, but their solution qualities are often bad. In this paper, we therefore propose a novel MAPF solver, Hierarchical Multi-Agent Path Planner (HMAPP), which creates a spatial hierarchy by partitioning the environment into multiple regions and decomposes a MAPF instance into smaller MAPF sub-instances for each region. For each sub-instance, it uses a bounded-suboptimal MAPF solver to solve it with good solution quality. Our experimental results show that HMAPP solves as large MAPF instances as greedy MAPF solvers while achieving better solution qualities on various maps.},\n url_paper = {https://hierarchical-task.net/publications/hplan/2021/HPlan2021-paper1.pdf},\n url_presentation = {https://www.youtube.com/watch?v=eBZALSeZpXU&t=3s}\n}\n\n","author_short":["Zhang, H.","Yao, M.","Liu, Z.","Li, J.","Terr, L.","Chan, S.","Kumar, T. K. S.","Koenig, S."],"key":"HPlan2021paper1","id":"HPlan2021paper1","bibbaseid":"zhang-yao-liu-li-terr-chan-kumar-koenig-ahierarchicalapproachtomultiagentpathfinding-2021","role":"author","urls":{" paper":"https://hierarchical-task.net/publications/hplan/2021/HPlan2021-paper1.pdf"," presentation":"https://www.youtube.com/watch?v=eBZALSeZpXU&t=3s"},"metadata":{"authorlinks":{}},"downloads":6},"bibtype":"inproceedings","biburl":"hierarchical-task.net/bibtex/hplan-publications.bib","dataSources":["T9LQLt3D2MDhrCfjh"],"keywords":[],"search_terms":["hierarchical","approach","multi","agent","path","finding","zhang","yao","liu","li","terr","chan","kumar","koenig"],"title":"A Hierarchical Approach to Multi-Agent Path Finding","year":2021,"downloads":7}