Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912928706330624 |
|---|---|
| author | Zang, Hongzhi Zhang, Yulun Jiang, He Chen, Zhe Harabor, Daniel Stuckey, Peter J. Li, Jiaoyang |
| author_facet | Zang, Hongzhi Zhang, Yulun Jiang, He Chen, Zhe Harabor, Daniel Stuckey, Peter J. Li, Jiaoyang |
| contents | We study the problem of optimizing a guidance policy capable of dynamically guiding the agents for lifelong Multi-Agent Path Finding based on real-time traffic patterns. Multi-Agent Path Finding (MAPF) focuses on moving multiple agents from their starts to goals without collisions. Its lifelong variant, LMAPF, continuously assigns new goals to agents. In this work, we focus on improving the solution quality of PIBT, a state-of-the-art rule-based LMAPF algorithm, by optimizing a policy to generate adaptive guidance. We design two pipelines to incorporate guidance in PIBT in two different ways. We demonstrate the superiority of the optimized policy over both static guidance and human-designed policies. Additionally, we explore scenarios where task distribution changes over time, a challenging yet common situation in real-world applications that is rarely explored in the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_16506 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding Zang, Hongzhi Zhang, Yulun Jiang, He Chen, Zhe Harabor, Daniel Stuckey, Peter J. Li, Jiaoyang Multiagent Systems We study the problem of optimizing a guidance policy capable of dynamically guiding the agents for lifelong Multi-Agent Path Finding based on real-time traffic patterns. Multi-Agent Path Finding (MAPF) focuses on moving multiple agents from their starts to goals without collisions. Its lifelong variant, LMAPF, continuously assigns new goals to agents. In this work, we focus on improving the solution quality of PIBT, a state-of-the-art rule-based LMAPF algorithm, by optimizing a policy to generate adaptive guidance. We design two pipelines to incorporate guidance in PIBT in two different ways. We demonstrate the superiority of the optimized policy over both static guidance and human-designed policies. Additionally, we explore scenarios where task distribution changes over time, a challenging yet common situation in real-world applications that is rarely explored in the literature. |
| title | Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding |
| topic | Multiagent Systems |
| url | https://arxiv.org/abs/2411.16506 |