Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913216508985344 |
|---|---|
| author | Chen, Zhe Harabor, Daniel Li, Jiaoyang Stuckey, Peter J. |
| author_facet | Chen, Zhe Harabor, Daniel Li, Jiaoyang Stuckey, Peter J. |
| contents | Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics that asks us to compute collision-free paths for a team of agents, all moving across a shared map. Although many works appear on this topic, all current algorithms struggle as the number of agents grows. The principal reason is that existing approaches typically plan free-flow optimal paths, which creates congestion. To tackle this issue, we propose a new approach for MAPF where agents are guided to their destination by following congestion-avoiding paths. We evaluate the idea in two large-scale settings: one-shot MAPF, where each agent has a single destination, and lifelong MAPF, where agents are continuously assigned new destinations. Empirically, we report large improvements in solution quality for one-short MAPF and in overall throughput for lifelong MAPF. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_11234 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding Chen, Zhe Harabor, Daniel Li, Jiaoyang Stuckey, Peter J. Artificial Intelligence Multiagent Systems Robotics Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics that asks us to compute collision-free paths for a team of agents, all moving across a shared map. Although many works appear on this topic, all current algorithms struggle as the number of agents grows. The principal reason is that existing approaches typically plan free-flow optimal paths, which creates congestion. To tackle this issue, we propose a new approach for MAPF where agents are guided to their destination by following congestion-avoiding paths. We evaluate the idea in two large-scale settings: one-shot MAPF, where each agent has a single destination, and lifelong MAPF, where agents are continuously assigned new destinations. Empirically, we report large improvements in solution quality for one-short MAPF and in overall throughput for lifelong MAPF. |
| title | Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding |
| topic | Artificial Intelligence Multiagent Systems Robotics |
| url | https://arxiv.org/abs/2308.11234 |