ETRI-Knowledge Sharing Plaform

KOREAN
논문 검색
Type SCI
Year ~ Keyword

Detail

Journal Article Anytime Lifelong Multi-Agent Pathfinding in Topological Maps
Cited 0 time in scopus Download 91 time Share share facebook twitter linkedin kakaostory
Authors
Soohwan Song, Ki-In Na, Wonpil Yu
Issue Date
2023-02
Citation
IEEE Access, v.11, pp.20365-20380
ISSN
2169-3536
Publisher
IEEE
Language
English
Type
Journal Article
DOI
https://dx.doi.org/10.1109/ACCESS.2023.3249471
Project Code
22PS1700, Development of integrated robot operating simulator and real-time fleet management system for heterogeneous, multiple logistics robots, Wonpil Yu
Abstract
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.
KSP Keywords
Long-range, Railway environment, Search Space, Solution quality, Success rate, Time horizon, Traffic congestion, computation time, conflict-based, heavy traffic, multi-agent
This work is distributed under the term of Creative Commons License (CCL)
(CC BY NC ND)
CC BY NC ND