Anytime Lifelong Multi-Agent Pathfinding in Topological Maps

Soohwan Song, Ki In Na, Wonpil Yu

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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.

Original languageEnglish
Pages (from-to)20365-20380
Number of pages16
JournalIEEE Access
Volume11
DOIs
StatePublished - 2023

Keywords

  • logistics automation
  • mobile robots
  • Multi-agent pathfinding
  • multi-robot system
  • path planning
  • topological map

Fingerprint

Dive into the research topics of 'Anytime Lifelong Multi-Agent Pathfinding in Topological Maps'. Together they form a unique fingerprint.

Cite this