상세정보
학술지
Anytime Lifelong Multi-Agent Pathfinding in Topological Maps
- 발행일
- 202302
- 출처
- IEEE Access, v.11, pp.20365-20380
- ISSN
- 2169-3536
- 출판사
- IEEE
- 협약과제
- 22PS1700, 이종의 다중 모바일 물류 핸들링 로봇 통합 운영 시뮬레이터 및 실시간 플릿 매니지먼트 시스템 개발, 유원필
- 초록
- 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 제안 키워드
- Long-range, Railway environment, Search Space, Solution quality, Success rate, Time horizon, Traffic congestion, computation time, conflict-based, heavy traffic, multi-agent
본 저작물은 크리에이티브 커먼즈 저작자 표시 - 비영리 - 변경금지 (CC BY NC ND) 조건에 따라 이용할 수 있습니다.
