MARPF: Multi-Agent and Multi-Rack 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_ | 1866915637644754944 |
|---|---|
| author | Makino, Hiroya Ohama, Yoshihiro Ito, Seigo |
| author_facet | Makino, Hiroya Ohama, Yoshihiro Ito, Seigo |
| contents | In environments where many automated guided vehicles (AGVs) operate, planning efficient, collision-free paths is essential. Related research has mainly focused on environments with pre-defined passages, resulting in space inefficiency. We attempt to relax this assumption. In this study, we define multi-agent and multi-rack path finding (MARPF) as the problem of planning paths for AGVs to convey target racks to their designated locations in environments without passages. In such environments, an AGV without a rack can pass under racks, whereas one with a rack cannot pass under racks to avoid collisions. MARPF entails conveying the target racks without collisions, while the obstacle racks are relocated to prevent any interference with the target racks. We formulated MARPF as an integer linear programming problem in a network flow. To distinguish situations in which an AGV is or is not loading a rack, the proposed method introduces two virtual layers into the network. We optimized the AGVs' movements to move obstacle racks and convey the target racks. The formulation and applicability of the algorithm were validated through numerical experiments. The results indicated that the proposed algorithm addressed issues in environments with dense racks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_12376 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | MARPF: Multi-Agent and Multi-Rack Path Finding Makino, Hiroya Ohama, Yoshihiro Ito, Seigo Multiagent Systems In environments where many automated guided vehicles (AGVs) operate, planning efficient, collision-free paths is essential. Related research has mainly focused on environments with pre-defined passages, resulting in space inefficiency. We attempt to relax this assumption. In this study, we define multi-agent and multi-rack path finding (MARPF) as the problem of planning paths for AGVs to convey target racks to their designated locations in environments without passages. In such environments, an AGV without a rack can pass under racks, whereas one with a rack cannot pass under racks to avoid collisions. MARPF entails conveying the target racks without collisions, while the obstacle racks are relocated to prevent any interference with the target racks. We formulated MARPF as an integer linear programming problem in a network flow. To distinguish situations in which an AGV is or is not loading a rack, the proposed method introduces two virtual layers into the network. We optimized the AGVs' movements to move obstacle racks and convey the target racks. The formulation and applicability of the algorithm were validated through numerical experiments. The results indicated that the proposed algorithm addressed issues in environments with dense racks. |
| title | MARPF: Multi-Agent and Multi-Rack Path Finding |
| topic | Multiagent Systems |
| url | https://arxiv.org/abs/2403.12376 |