Anytime Lifelong Multi-Agent Pathfinding in Topological Maps
This study addresses a lifelong multi-agent path finding (lifelong MAPF) problem that continuously solves an MAPF instance online according to newly assigned goals. Specifically, we focus on lifelong MAPF in a topological map. This problem is challenging because the movement of the agent is restrict...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10054055/ |
| _version_ | 1827999972050599936 |
|---|---|
| author | Soohwan Song Ki-In Na Wonpil Yu |
| author_facet | Soohwan Song Ki-In Na Wonpil Yu |
| author_sort | Soohwan Song |
| collection | DOAJ |
| description | This study addresses a lifelong multi-agent path finding (lifelong MAPF) problem that continuously solves an MAPF instance online according to newly assigned goals. Specifically, we focus on lifelong MAPF in a topological map. This problem is challenging because the movement of the agent is restricted to narrow corridors in a topological map, rather than the entire map area. Bypasses may be limited or farther away in corridors, significantly complicating the computation of paths. Furthermore, low-quality solutions may cause traffic congestion or even deadlock in a corridor. Therefore, we propose a novel lifelong MAPF method that effectively resolves conflicts in corridors based on an anytime strategy. This method gradually improves the solution quality by updating sub-paths with heavy traffic congestion. Furthermore, we adopt several improvement steps to effectively resolve corridor conflicts in a conflict-based search (CBS). This method significantly reduces the search space and computation time of CBS. We conducted extensive experiments on various topological maps in warehouse and railway environments. The results show that the proposed method outperforms state-of-the-art methods in terms of throughput and success rate. In particular, the proposed method can resolve collisions with a longer time horizon than existing methods, considerably improving throughput on a topological map with long-range corridors and heavy traffic congestion. |
| first_indexed | 2024-04-10T06:06:47Z |
| format | Article |
| id | doaj.art-efde0c665b9844f092da37b02ffa2078 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-10T06:06:47Z |
| publishDate | 2023-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-efde0c665b9844f092da37b02ffa20782023-03-03T00:00:34ZengIEEEIEEE Access2169-35362023-01-0111203652038010.1109/ACCESS.2023.324947110054055Anytime Lifelong Multi-Agent Pathfinding in Topological MapsSoohwan Song0https://orcid.org/0000-0003-2145-1161Ki-In Na1https://orcid.org/0000-0002-4229-4786Wonpil Yu2https://orcid.org/0000-0001-5729-7931Intelligent Robotics Research Division, Electronics and Telecommunications Research Institute (ETRI), Daejeon, South KoreaIntelligent Robotics Research Division, Electronics and Telecommunications Research Institute (ETRI), Daejeon, South KoreaIntelligent Robotics Research Division, Electronics and Telecommunications Research Institute (ETRI), Daejeon, South KoreaThis study addresses a lifelong multi-agent path finding (lifelong MAPF) problem that continuously solves an MAPF instance online according to newly assigned goals. Specifically, we focus on lifelong MAPF in a topological map. This problem is challenging because the movement of the agent is restricted to narrow corridors in a topological map, rather than the entire map area. Bypasses may be limited or farther away in corridors, significantly complicating the computation of paths. Furthermore, low-quality solutions may cause traffic congestion or even deadlock in a corridor. Therefore, we propose a novel lifelong MAPF method that effectively resolves conflicts in corridors based on an anytime strategy. This method gradually improves the solution quality by updating sub-paths with heavy traffic congestion. Furthermore, we adopt several improvement steps to effectively resolve corridor conflicts in a conflict-based search (CBS). This method significantly reduces the search space and computation time of CBS. We conducted extensive experiments on various topological maps in warehouse and railway environments. The results show that the proposed method outperforms state-of-the-art methods in terms of throughput and success rate. In particular, the proposed method can resolve collisions with a longer time horizon than existing methods, considerably improving throughput on a topological map with long-range corridors and heavy traffic congestion.https://ieeexplore.ieee.org/document/10054055/Multi-agent pathfindingmobile robotslogistics automationpath planningmulti-robot systemtopological map |
| spellingShingle | Soohwan Song Ki-In Na Wonpil Yu Anytime Lifelong Multi-Agent Pathfinding in Topological Maps IEEE Access Multi-agent pathfinding mobile robots logistics automation path planning multi-robot system topological map |
| title | Anytime Lifelong Multi-Agent Pathfinding in Topological Maps |
| title_full | Anytime Lifelong Multi-Agent Pathfinding in Topological Maps |
| title_fullStr | Anytime Lifelong Multi-Agent Pathfinding in Topological Maps |
| title_full_unstemmed | Anytime Lifelong Multi-Agent Pathfinding in Topological Maps |
| title_short | Anytime Lifelong Multi-Agent Pathfinding in Topological Maps |
| title_sort | anytime lifelong multi agent pathfinding in topological maps |
| topic | Multi-agent pathfinding mobile robots logistics automation path planning multi-robot system topological map |
| url | https://ieeexplore.ieee.org/document/10054055/ |
| work_keys_str_mv | AT soohwansong anytimelifelongmultiagentpathfindingintopologicalmaps AT kiinna anytimelifelongmultiagentpathfindingintopologicalmaps AT wonpilyu anytimelifelongmultiagentpathfindingintopologicalmaps |