Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910577870241792 |
|---|---|
| author | Lehoux-Lebacque, Vassilissa Silander, Tomi Loiodice, Christelle Lee, Seungjoon Wang, Albert Michel, Sofia |
| author_facet | Lehoux-Lebacque, Vassilissa Silander, Tomi Loiodice, Christelle Lee, Seungjoon Wang, Albert Michel, Sofia |
| contents | Multi-Agent Path Finding (MAPF) is an important optimization problem underlying the deployment of robots in automated warehouses and factories. Despite the large body of work on this topic, most approaches make heavy simplifications, both on the environment and the agents, which make the resulting algorithms impractical for real-life scenarios. In this paper, we consider a realistic problem of online order delivery in a warehouse, where a fleet of robots bring the products belonging to each order from shelves to workstations. This creates a stream of inter-dependent pickup and delivery tasks and the associated MAPF problem consists of computing realistic collision-free robot trajectories fulfilling these tasks. To solve this MAPF problem, we propose an extension of the standard Prioritized Planning algorithm to deal with the inter-dependent tasks (Interleaved Prioritized Planning) and a novel Via-Point Star (VP*) algorithm to compute an optimal dynamics-compliant robot trajectory to visit a sequence of goal locations while avoiding moving obstacles. We prove the completeness of our approach and evaluate it in simulation as well as in a real warehouse. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_14527 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses Lehoux-Lebacque, Vassilissa Silander, Tomi Loiodice, Christelle Lee, Seungjoon Wang, Albert Michel, Sofia Robotics Artificial Intelligence Multiagent Systems Multi-Agent Path Finding (MAPF) is an important optimization problem underlying the deployment of robots in automated warehouses and factories. Despite the large body of work on this topic, most approaches make heavy simplifications, both on the environment and the agents, which make the resulting algorithms impractical for real-life scenarios. In this paper, we consider a realistic problem of online order delivery in a warehouse, where a fleet of robots bring the products belonging to each order from shelves to workstations. This creates a stream of inter-dependent pickup and delivery tasks and the associated MAPF problem consists of computing realistic collision-free robot trajectories fulfilling these tasks. To solve this MAPF problem, we propose an extension of the standard Prioritized Planning algorithm to deal with the inter-dependent tasks (Interleaved Prioritized Planning) and a novel Via-Point Star (VP*) algorithm to compute an optimal dynamics-compliant robot trajectory to visit a sequence of goal locations while avoiding moving obstacles. We prove the completeness of our approach and evaluate it in simulation as well as in a real warehouse. |
| title | Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses |
| topic | Robotics Artificial Intelligence Multiagent Systems |
| url | https://arxiv.org/abs/2408.14527 |