Integer-Programming-Based Narrow-Passage Multi-Robot Path Planning with Effective Heuristics
This work addresses path planning for multi-robot systems in warehouse-like settings, representing an incremental improvement with domain-specific applications.
The paper tackles optimal multi-robot path planning in warehouse-like environments by proposing an integer programming-based algorithm with one-way constraints and heuristics, achieving improved efficiency as demonstrated through simulations.
We study optimal Multi-robot Path Planning (MPP) on graphs, in order to improve the efficiency of multi-robot system (MRS) in the warehouse-like environment. We propose a novel algorithm, OMRPP (One-way Multi-robot Path Planning) based on Integer programming (IP) method. We focus on reducing the cost caused by a set of robots moving from their initial configuration to goal configuration in the warehouse-like environment. The novelty of this work includes: (1) proposing a topological map extraction based on the property of warehouse-like environment to reduce the scale of constructed IP model; (2) proposing one-way passage constraint to prevent the robots from having unsolvable collisions in the passage. (3) developing a heuristic architecture that IP model can always have feasible initial solution to ensure its solvability. Numerous simulations demonstrate the efficiency and performance of the proposed algorithm.