CGA: Corridor Generating Algorithm for Multi-Agent Environments

In this work, we consider path planning for a team of mobile agents where one agent must reach a given target as soon as possible and the others must accommodate to avoid collisions. We call this practical problem the Single-Agent Corridor Generating (SACG) problem and explore several algorithms for solving it. We propose two baseline algorithms based on existing Multi-Agent Path Finding (MAPF) algorithms and outline their limitations. Then, we present the Corridor Generating Algorithm (CGA), a fast and complete algorithm for solving SACG. CGA performs well compared to the baseline approaches. In addition, we show how CGA can be generalized to address the lifelong version of MAPF, where new goals appear over time.

Authors

• Arseniy Pertzovsky
• Roni Stern
• Roie Zivan

Keywords

• Mobile agents
• Path planning
• Intelligent robots
• Pathfinding
• Complete Algorithm
• Baseline Algorithms
• Time Step
• Action Plan
• Single Agent
• Current Position
• Contributions Of This Work
• Shortest Path
• Number Of Agents
• Main Agent
• Vertices
• Current Goals
• Pair Of Vertices
• Breadth-first Search
• Start Location
• Rule-based Algorithm
• Outline Of The Proof