Source-linked AI summary
Planning Optimal Paths for Multiple Robots on Graphs
Jingjin Yu, Steven M. LaValle
TL;DR
The paper studies optimal collision-free path planning for multiple robots on graphs, where coupled paths make the problem difficult. It uses multiflow-based ILP models for time and distance optimality, and reports complete algorithms that solve substantial instances while allowing the time-optimal method to act as a heuristic.
Problem
Coupled robot paths create enormous state spaces and branching factors, making complete optimal planning difficult, especially for tightly coupled problems.
Method
The paper converts multi-robot path planning into multiflow-based ILP models for time-optimal and distance-optimal solutions.
Results
The resulting algorithms are complete, while TOMPP plans time-optimal paths for several dozen robots on graphs with hundreds of vertices within minutes.
Takeaways & Limitations
TOMPP is effective for tightly coupled and larger instances and can serve as a heuristic, while DOMPP combined with TOMPP often produces time-optimal solutions near distance optimality.
Abstract
from arXiv · showhide
In this paper, we study the problem of optimal multi-robot path planning (MPP) on graphs. We propose two multiflow based integer linear programming (ILP) models that computes minimum last arrival time and minimum total distance solutions for our MPP formulation, respectively. The resulting algorithms from these ILP models are complete and guaranteed to yield true optimal solutions. In addition, our flexible framework can easily accommodate other variants of the MPP problem. Focusing on the time optimal algorithm, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. Computational results confirm the effectiveness of our method.
I. INTRODUCTION
The paper addresses the computational difficulty of collision-free multi-robot path planning by formulating time- and distance-optimal variants as complete ILP-based methods. Experiments show that the time-optimal approach can solve sizeable instances and also serve as a heuristic.
- Motivation: Coupling between robots creates enormous state spaces and branching factors, limiting complete distance-optimal methods such as A∗ on tightly coupled problems.
- Evaluation: With Gurobi, the method plans time-optimal, collision-free paths for several dozen robots on graphs with hundreds of vertices within minutes.
- Motivation: The paper evaluates multi-robot path planning as a subroutine across applications including assembly, evacuation, formation control, transportation, and search and rescue.
- Motivation: Time-optimal planning is NP-hard for a closely related multi-robot path-planning formulation, so polynomial-time optimal performance should not generally be expected.
- Contributions: The paper develops complete ILP models for time-optimal and distance-optimal multi-robot path planning on graphs.
- Contributions: The models accommodate other MPP formulations, including the grid-world formulation discussed in prior work.
A. Problem Formulation
The formulation assigns each robot a path on a connected graph and forbids vertex-sharing and head-on edge collisions. It distinguishes makespan from total traveled distance, which can favor different solutions.
- Problem definition: Each robot moves at unit speed on a connected undirected graph from an individual initial vertex to an individual goal vertex.
- Collision model: Collisions occur when robots occupy the same vertex or traverse the same edge in opposite directions at a time step.
- Problem definition: A feasible MPP solution consists of one feasible path per robot with no pair of paths in collision.
- Objectives: Makespan is the number of time steps until the last robot reaches its goal.
- Objectives: Distance optimality counts the total number of edges traveled by all robots, and it need not coincide with time optimality.
- Motion model: The formulation permits multiple robots to move simultaneously when their moves do not create collisions, including rotations along graph cycles.
B. A Motivating Example
The motivating example is a highly constrained 9-puzzle in which numbered robots must reach a prescribed configuration. The paper connects its solution framework to network and multiflow formulations.
- A. Motivating example: The 9-puzzle asks numbered robots in one grid configuration to reach the row-major goal configuration shown in Fig. 2(b).
- A. Motivating example: The example is highly constrained, making a feasible solution non-trivial and an optimality guarantee more demanding.
- A. Motivating example: The time-optimal algorithm solves the presented 9-puzzle instance in under 0.1 second using a four-step solution.
- B. Network flow: The network-flow formulation represents edges with capacities and costs and imposes capacity and flow-conservation constraints.
- B. Network flow: MPP is modeled as a multiflow problem because robots are distinct commodities rather than interchangeable units of flow.
B. Equivalence between MPP and multiflow
The paper establishes a bijection between collision-free multi-robot paths and integer maximum multiflows in a time-expanded network. The construction encodes robot movements, vertex conflicts, and head-on edge collisions so multiflow solutions correspond exactly to MPP solutions.
- Time-expanded network: The construction creates 2T + 1 time-indexed copies of every graph vertex and connects successive time layers through edge gadgets.For each original edge and consecutive time steps, the gadget links the corresponding vertex copies.
- Collision encoding: Unit-capacity blue edges prevent multiple flows from sharing a vertex at the same time step.The surjectivity proof uses these capacities to show that distinct unit flows are vertex-disjoint.
- Collision encoding: The edge gadget prevents two robots from traversing an undirected edge in opposite directions during the same time step.Its edges have unit capacity; the horizontal middle edge has unit cost and the other four edges have zero cost.
- Equivalence theorem: Theorem 2 gives a bijection between MPP solutions using at most T time steps and integer maximum multiflows of value n.Each robot is represented as a single commodity, and the multiflow has one unit of flow per robot.
- Correctness correspondence: A feasible set of non-colliding robot paths maps to vertex-disjoint unit flows, while a feasible maximum multiflow converts back to paths without meet or head-on collisions.The reverse conversion deletes source, sink, gadget, and blue-edge tail vertices from each flow.
C. Accommodating other formulations
The network-flow encoding is flexible enough to represent alternative MPP collision rules. The paper illustrates this by adding a diagonal-crossing gadget or omitting the head-on-collision gadget.
- Diagonal crossings: A gadget can be added to the time-expanded network to permit a single diagonal crossing in grid-world formulations.The construction allows a robot to cross diagonally when the destination is unoccupied and the other diagonal is unused in that time step.
- Diagonal crossings: The diagonal-crossing gadget remains compatible with vertex-capacity constraints because no two robots can occupy one vertex at the same time step.The blue dotted edges in the time-expanded network enforce this restriction.
- Alternative collision rules: Head-on collisions can be allowed by omitting the undirected-edge gadget during construction of the time-expanded network.This models formulations such as two adjacent CPUs exchanging data in parallel without allowing multiple units at one CPU.
IV. ALGORITHMIC SOLUTIONS FOR OPTIMAL MULTI-ROBOT PATH PLANNING
The paper formulates time- and distance-optimal multi-robot path planning as ILP models over a time-expanded network. For time optimality, TOMPP increases the horizon until the first feasible solution, guaranteeing minimum makespan when a solution exists.
- Model objectives: The ILP framework encodes either makespan or total distance as the optimization objective in a time-expanded network.Makespan is the time when the last robot reaches its goal; distance optimality is the total distance traveled by all robots.
- Time optimality: For a fixed time horizon T, a maximum multiflow of value n indicates a feasible solution for all n robots.The algorithm tests successive horizons and extracts robot paths from the resulting flow.
- Time optimality: TOMPP starts at the maximum individual shortest-path length and increments T until the first feasible ILP model is found.The first feasible horizon is therefore the minimum feasible makespan.
- Guarantee: TOMPP is complete and returns a solution with minimum makespan to Problem 1 if one exists.Completeness follows from the finite state space and eventual testing of sufficiently large horizons.
B. Distance optimality
The distance-optimal model uses minimum-cost maximum multiflow to minimize the total path length of all robots. DOMPP is complete and returns a minimum-total-path-length solution when one exists, but its time-expanded formulation is slow for many robots.
- Distance optimality: Distance optimality is encoded with a minimum-cost maximum multiflow while retaining the core ILP constraints.Setting each loopback variable x_i,i to 1 forces maximum flow.
- Distance optimality: The feasible objective value equals the total distance of all robots’ paths.A distance-optimal solution can be sought in a time-expanded network with T = nT_t, where T_t is TOMPP’s optimal horizon.
- Guarantee: DOMPP is complete and returns a solution with minimum total path length to Problem 1 if one exists.This provides a true distance-optimality guarantee for the formulation.
- Limitation: DOMPP is not very fast for problems with many robots because its time-expanded network requires a large number of steps.The evaluation therefore focuses on TOMPP, while DOMPP remains useful for time-optimal and near-distance-optimal solutions.
V. PROPERTIES OF THE n2-PUZZLE
The n2-puzzle has highly coupled, synchronous robot motion and enormous state spaces and branching factors. Nevertheless, all states are connected for n ≥ 3, so every instance is solvable, though recursive constructions are not generally optimal.
- Puzzle structure: In the n2-puzzle, robots move synchronously on disjoint cycles, and no robot can move without at least three others moving.This coupling makes the puzzle substantially constrained.
- Connectivity: All states of a 9-puzzle are connected via legal moves.The proof uses movement of the center robot and a procedure for exchanging two border robots.
- Connectivity: For n ≥ 3, all states of an n2-puzzle are connected via legal moves.The construction solves larger puzzles recursively by fixing portions of the puzzle and reducing the remaining square.
- Solvability: All instances of the n2-puzzle with n ≥ 3 are solvable.The resulting recursive algorithms solve any instance but are not generally time- or distance-optimal.
- Computational difficulty: 16! > 10^13 and 25! > 10^25 illustrate the rapidly expanding state space of larger puzzles.The 25-puzzle also has a branching factor exceeding 10^4, while Manhattan distance is a poor heuristic in the illustrated instances.
VI. SOLUTIONS AND EVALUATION
TOMPP solves increasingly difficult n2-puzzle instances optimally, outperforming exhaustive search in the reported experiments. Its performance remains limited on the 36-puzzle, whose state space and branching factor are vastly larger.
- 9-puzzle: TOMPP solved all 100 randomly generated 9-puzzle instances with an average computation time of 1.36 seconds per instance.The experiment compared TOMPP with an optimized optimal BFS algorithm.
- 16-puzzle: TOMPP solved all 100 randomly generated 16-puzzle instances with an average computation time of 18.9 seconds.The competing BFS algorithm ran out of memory after a few minutes.
- 16-puzzle: A bidirectional search for the 16-puzzle also ran out of memory after about 10 minutes.Reaching depth 3 required storing about 3 × 10^7 states, exceeding the 4GB JavaVM capacity.
- 36-puzzle: TOMPP generally did not solve randomly generated 36-puzzle instances within 24 hours.The 36-puzzle has 3.7 × 10^41 states and a branching factor well over 10^6.
B. Time optimal solutions for grid graphs
On 20×15 and 32×32 grid graphs, TOMPP’s difficulty depends non-monotonically on obstacle percentage and robot count. Reduced graph size can simplify instances, while reduced connectivity can make them harder.
- 20% obstacles on a 20×15 grid with 30 start/goal pairs provides the representative evaluation setting.The grid contains removed vertices modeling obstacles, with starts and goals explicitly marked.
- Obstacle percentage affects computational difficulty non-monotonically because obstacles both shrink the graph and reduce its connectivity.The 20×15 setting becomes particularly hard at 30% obstacles, where reduced connectivity outweighs the smaller problem size.
- Longer optimal solution times indicate fewer alternative paths remain available in more constrained graphs.The experiments use average optimal time steps alongside computation time to reflect this reduced path availability.
- 32×32 grids with 20% obstacles showed difficulty similar to 20×15 grids with 25% obstacles, but substantially lower difficulty than with 30% obstacles.The larger-grid experiment used 10–50 robots, 10 random instances per robot count, and a 30-minute limit per instance.
C. Distance optimality of time optimal solutions
The paper combines TOMPP and DOMPP to address distance optimality after finding minimum-time solutions, while also using TOMPP to resolve conflicts in large instances. Results indicate practical heuristic performance and often near-distance-optimal solutions.
- Distance optimality: DOMPP computes distance-optimal solutions on a time-expanded network whose length T is fixed after TOMPP finds the minimum feasible time.DOMPP was evaluated with a 200-second per-instance cutoff and could still return feasible, sometimes near-optimal solutions when optimality was not reached.
- Heuristic use: TOMPP is used as a generic heuristic that locally resolves stalled path conflicts after independently planned robot paths stop making progress.The heuristic is not specialized to a particular robot or grid setting.
- Heuristic use: The heuristic’s computation time and completion rate appear comparable to state-of-the-art results, although no direct literature comparison was made.The authors attribute the lack of side-by-side comparison to important differences in problem formulations.
- Conclusion: TOMPP and DOMPP provide complete algorithms for time- and distance-optimal MPP, with DOMPP often yielding near-distance-optimal solutions when combined with TOMPP.The conclusion also reports TOMPP as feasible for tightly coupled and larger, more spacious instances, and effective as a large-instance heuristic.
- Open problems: ILP performance remains improvable through leaner models, solver-parameter tuning, and methods tailored to difficult puzzle-like MPP instances.The authors identify these as open problems rather than established performance results.