PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics

Jingjin Yu, Steven M. LaValle

arXiv:1507.03290v1cs.RO

TL;DR

Optimal multi-robot path planning on graphs involves four distinct, NP-hard objectives. The paper uses an MPP–network-flow equivalence and ILP-based complete algorithms, enhanced by heuristics, to compute near-optimal solutions for dense instances with hundreds of robots.

  • Problem

    The paper addresses optimal planning for distinguishable robots on connected graphs under four distinct objectives that prior work showed are NP-hard to optimize.

  • Method

    The paper establishes a one-to-one mapping between MPP and multi-commodity flow, then encodes the four objectives in integer linear programming models with performance-enhancing heuristics.

  • Results

    The algorithms compute near-optimal solutions for hundreds of densely populated robots, often in seconds, while minimum makespan is solved for up to 180 robots in reported experiments.

  • Takeaways & Limitations

    The framework provides complete optimization algorithms for four MPP objectives and practical near-optimal performance on highly populated graphs.

Abstract

from arXiv · show

We study the problem of optimal multi-robot path planning on graphs MPP over four distinct minimization objectives: the makespan (last arrival time), the maximum (single-robot traveled) distance, the total arrival time, and the total distance. In a related paper, we show that these objectives are distinct and NP-hard to optimize. In this work, we focus on efficiently algorithmic solutions for solving these optimal MPP problems. Toward this goal, we first establish a one-to-one solution mapping between MPP and network-flow. Based on this equivalence and integer linear programming (ILP), we design novel and complete algorithms for optimizing over each of the four objectives. In particular, our exact algorithm for computing optimal makespan solutions is a first such that is capable of solving extremely challenging problems with robot-vertex ratio as high as 100%. Then, we further improve the computational performance of these exact algorithms through the introduction of principled heuristics, at the expense of some optimality loss. The combination of ILP model based algorithms and the heuristics proves to be highly effective, allowing the computation of 1.x-optimal solutions for problems containing hundreds of robots, densely populated in the environment, often in just seconds.

I. INTRODUCTION

The paper studies optimal multi-robot path planning on connected graphs, including fully occupied-cycle rotations, and develops complete algorithms with effective heuristics.

  • Problem formulation: MPP plans paths for distinguishable robots on connected graphs while avoiding simultaneous vertex and head-on edge collisions.Robots may wait or move to adjacent vertices at discrete time steps.
  • Problem formulation: Unlike most discrete formulations, MPP permits synchronized rotations along fully occupied cycles, even when robots occupy every vertex.This formulation is intended to better suit multi-robot applications and remains feasible to test in polynomial time.
  • Motivation and related work: Prior work established that the four optimization objectives are distinct and NP-hard, motivating effective near-optimal algorithms.Earlier cycle-free methods often provide completeness guarantees without optimality guarantees.
  • Contributions: The paper maps MPP solutions one-to-one to multi-commodity flow solutions and encodes all four objectives in integer linear programming models.The framework yields complete algorithms for optimizing makespan, maximum distance, total arrival time, and total distance.
  • Contributions: Principled heuristics, including time-domain k-way splitting, improve performance with a slight loss of solution optimality.The paper reports that splitting can substantially improve computation while having limited negative impact on makespan path optimality.
  • Contributions: The resulting methods target challenging dense instances, including cases with robot-vertex ratio up to 100%.The introduction presents near-optimal solutions for hundreds of robots, often in seconds.

B. Optimal Formulations

The paper defines four global objectives for feasible MPP solutions: two minimize time and two minimize traveled distance. A four-step 9-puzzle solution illustrates minimum makespan.

  • Feasible solutions: A feasible path records each robot’s start, arrival time, goal-staying behavior, and collision-free movements.Path length increases by one whenever a robot traverses an edge, including repeated edge traversals.
  • Time objectives: Makespan minimizes the latest robot arrival time, max_i t_i.The illustrated 9-puzzle solution is optimal because robot 9 requires at least four steps to reach its goal.
  • Distance objectives: Maximum distance minimizes the longest individual path length, max_i len(p_i).The objective concerns the greatest distance traveled by any single robot.
  • Time objectives: Total arrival time minimizes the sum of robot arrival times, Σ_i t_i.This objective aggregates when all robots reach their goals.
  • Distance objectives: Total distance minimizes the sum of all robot path lengths, Σ_i len(p_i).Path length counts every edge traversal made by each robot.

C. Network Flow Review

The paper reviews multiflow and constructs a time-expanded network that represents labeled multi-robot paths while enforcing collision constraints. A bijection then connects feasible MPP solutions with integer maximum multiflow solutions.

  • Network-flow background: Multiflow assigns a separate integer flow function to each robot commodity rather than treating all robots as interchangeable.The formulation uses one flow function f_i for each commodity i.
  • Network-flow background: Optimal MPP becomes difficult when robots are distinguishable, paralleling the contrast between single-commodity flow and maximum multiflow.The paper relates this difficulty to the NP-hardness of maximum multiflow and to optimal MPP with multiple robot groups.
  • Time-expanded network: The merge-split gadget splits each undirected edge through time steps to enforce the head-on collision constraint.The gadget assigns unit capacity to its edges and unit cost to the horizontal middle edge.
  • Time-expanded network: The reduction jointly expands graph space and time, using a fixed horizon T to represent robot interactions across time steps.The construction creates 2T + 1 vertex copies and inserts merge-split gadgets between successive time layers.
  • Time-expanded network: Green edges permit waiting, while blue unit-capacity edges ensure that each vertex holds at most one robot.These edges enforce the meet-collision constraint in the time-expanded network.
  • Solution correspondence: Theorem 1 establishes a bijection between MPP solutions with at most T time steps and integer maximum multiflows of value n.The proof maps each robot path to one unit flow and reconstructs paths from vertex-disjoint unit flows.

IV. COMPLETE, INTEGER LINEAR PROGRAMMING-BASED ALGORITHMS FOR OPTIMAL MPP PROBLEMS

Because the four optimal MPP objectives are computationally intractable, the paper uses a network-flow formulation to build ILP models solvable by linear programming packages.

  • ILP framework: Network-flow formulations enable ILP models for optimal MPP objectives despite the underlying computational intractability.The models can be solved with powerful linear programming packages.

A. Minimizing the Makespan

The makespan algorithm searches increasing time horizons with an ILP multiflow model, while related models optimize maximum single-robot distance. MINMAKESPAN is complete.

  • Minimizing the Makespan: The minimum-makespan model adds loopback edges from each robot’s goal to its start, with unit capacity and zero cost.These edges support a maximum multiflow formulation over a time-expanded network.
  • Minimizing the Makespan: For a fixed horizon T, binary variables represent each robot’s flow through every network edge.The objective and constraints are imposed on these edge-flow variables.
  • Minimizing the Makespan: The algorithm starts at the maximum individual shortest-path length and increases T until the ILP admits a flow of value n.The first feasible horizon is the optimal makespan.
  • Minimizing the Makespan: MINMAKESPAN is complete for finding minimum-makespan MPP solutions.A sufficiently large finite horizon guarantees either a feasible solution or a declaration that none exists.
  • Maximum single-robot distance: MINMAXDIST reuses the makespan network and variables while adding an integer xmax to minimize the largest robot distance.For each robot, a constraint bounds its traveled distance by xmax.
  • Maximum single-robot distance: After computing minimum makespan tmin, setting T = n tmin is sufficient for finding the minimum maximum distance.The bound follows because no robot travels more than the minimum maximum distance and total movement is at most n times that value.

C. Minimizing the Total Arrival Time

The total-arrival-time ILP extends the minimum-makespan model with variables that identify when each robot reaches its goal, then minimizes the resulting arrival times. MINTOTALTIME is complete.

  • The model inherits the network, variables, and constraints from the minimum-makespan ILP.
  • Binary variables yt_i identify the time robot r_i reaches and stops at its goal.The construction assigns a time-indexed variable for each robot and time step.
  • Constraint (14) implements a logical AND between edge-use variables and stores the result in yt_i.
  • The robot's arrival time is represented through the number of steps remaining after it reaches its goal.T − PT_i denotes the time spent by robot r_i.
  • MINTOTALTIME is a complete algorithm for finding minimum total-arrival-time solutions.

D. Minimizing the Total Distance

The minimum-total-distance ILP reuses the maximum-distance model while replacing its objective, yielding a complete algorithm for minimum total-distance MPP solutions.

  • The total-distance model changes only the objective function of the minimum-maximum-distance ILP.The variable xmax is unnecessary for this objective.
  • MINTOTALDIST is a complete algorithm for finding minimum total-distance solutions for MPP.
  • T = ntmin is sufficient to build a network containing a minimum-total-distance solution, if one exists.

V. HEURISTICS FOR EFFECTIVE COMPUTATION OF NEAR-OPTIMAL SOLUTIONS

The heuristics reduce ILP model size while preserving the general network-flow framework, improving computational practicality at the expense of some optimality.

  • V. HEURISTICS FOR EFFECTIVE COMPUTATION OF NEAR-OPTIMAL SOLUTIONS: The exact ILP algorithms are complete and optimal in principle but become harder to use as graph and problem size grow.
  • A. Building More Compact Models: The heuristics target leaner ILP models by compacting the representations of collision constraints (8) and (9).They apply across all four optimality objectives.
  • A. Building More Compact Models: The compact structure simplifies the merge-split gadget and removes extra blue edges used in the original network-flow representation.
  • A. Building More Compact Models: Each simplified merge-split gadget uses two edges instead of five and only two variables per robot.
  • A. Building More Compact Models: The updated ILP model is roughly half the size of the original model.
  • A. Building More Compact Models: Reachability analysis removes binary variables that cannot be true because relevant edges are unreachable for a robot.Variables are deleted based on reachability from each robot's start and to its goal.

B. Divide-and-Conquer Over Time Domain

The k-way split divides MPP over time into independent subproblems whose solutions can be concatenated, substantially reducing computation time with limited makespan optimality loss. Experiments show exact and heuristic MINMAKESPAN performance across dense, obstructed grids, while comparisons expose differing scalability among methods.

  • Divide-and-Conquer Over Time Domain: The k-way split divides a planning problem into time-separated subproblems and concatenates their solutions.The heuristic first splits robot paths into pieces with intermediate goals; because division occurs over time, child instances do not interact.
  • Divide-and-Conquer Over Time Domain: The heuristic suits makespan because the objective is additive across split subproblems, but it does not directly apply to total time.It also applies to distance objectives when their required time horizon is close to the minimum-makespan horizon.
  • k-way Split Performance: The 4-way split computes minimum-makespan solutions for up to 180 robots, with most cases solved in under 10 seconds and all but one ratio below 1.1.With 25% obstacles, problems up to 60 robots were solved consistently in about 40 seconds; the reported ratio is conservatively underestimated.
  • k-way Split Performance: Increasing the split count generally reduces computation time at the expense of optimality, with 16-split solving 300-robot instances at a 69% robot-vertex ratio.The evaluation used a 24 × 18 grid and averaged data points over 10 randomly generated instances under a 600-second limit.
  • Comparison: Compared with alternatives, ID performs well up to 60 robots but does not scale well beyond 100, while OD+ID and WHCA* stop beyond 40 robots in the tested setup.The comparisons include OD+ID, ID, WHCA*, and COBOPT, with differing support for cycles and optimization objectives.

B. Minimum Makespan Solution to N 2-puzzles

MINMAKESPAN is evaluated on highly constrained N^2-puzzles with 100% robot-vertex ratio. It solves 16- and 25-puzzles consistently, but generally cannot solve randomly generated 36-puzzles within 24 hours.

  • Puzzle Evaluation: N^2-puzzles have a 100% robot-vertex ratio, making them highly constrained and extremely challenging.The evaluation used 100 randomly generated instances for n = 3, 4, and 5, with all states connected in the search space for n ≥ 3.
  • 16-puzzle: MINMAKESPAN solved all 100 randomly generated 16-puzzle instances in an average of 4.2 seconds.A BFS algorithm that handled the 9-puzzle ran out of memory after a few minutes.
  • 16-puzzle: Bidirectional search required over 5 × 10^8 stored states and more than 8GB of working memory for typical 16-puzzle completion.The memory requirement exceeded what the JavaVM could handle, and the search generally ran out of memory after about 10 minutes.
  • 25-puzzle: MINMAKESPAN consistently solved the 25-puzzle in an average of 391.6 seconds over 100 randomly generated problems.One solution required 7 steps, which is the least possible because one robot needs at least 7 steps to reach its goal.
  • 36-puzzle: MINMAKESPAN generally does not solve randomly generated 36-puzzles within 24 hours.The 36-puzzle state space contains 3.7 × 10^41 states and has a branching factor well over 10^6.
  • Comparison: WHCA* cannot solve the 9-puzzle, while OD+ID and ID solve 9-puzzles consistently but cannot solve 16-puzzles within 600 seconds.These comparisons use the reported experimental outcomes for the respective methods.

C. Minimum Makespan on 8 × 8, 16 × 16, and 32 × 32 Grids

The experiments evaluate MINMAKESPAN and related algorithms across increasingly large and obstacle-populated grids, showing strong scalability with controlled optimality loss. MINMAKESPAN substantially outperforms comparison methods on dense instances, while total-time and total-distance variants provide practical anytime behavior.

  • 50 robots are solved to almost true-optimal makespan in 10 seconds on the 8 × 8 grid with the 2-way split heuristic.
  • 60 robots are handled on the 8 × 8 grid with 4-way split at solutions within 1.7-optimal, while ID handles up to 30 robots.
  • 190 robots are handled on the 16 × 16 grid with 8-way split at always less than 1.4-optimal, while 4-way split reaches 160 robots at no more than 1.03-optimal.
  • 100× speedups over COBOPT are generally observed across the 8 × 8 and 16 × 16 grids, alongside much smaller solution makespans.
  • The 32 × 32 grid with 20% removed vertices exhibits a pattern consistent with the 8 × 8, 16 × 16, and 24 × 18 experiments.
  • MINTOTALTIME and MINTOTALDIST use branch-and-bound’s improving feasible solutions to support anytime behavior and user-specified sub-optimality thresholds.

VII. CONCLUSION

The paper presents a general ILP-based framework for optimal or near-optimal multi-robot path planning across four objectives. Combined with heuristics, it computes near-optimal solutions for hundreds of robots in seconds, including highly populated environments and preliminary continuous-domain settings.

  • The framework uses the MPP–network-flow equivalence to build ILP algorithms for makespan, maximum distance, total arrival time, and total distance.
  • Heuristics combined with the ILP algorithms compute near-optimal solutions for hundreds of robots in seconds at very high robot-vertex ratios.
  • Preliminary extensions produce solutions for around a hundred disc robots in 2D environments with holes.

APPENDIX

The appendix establishes solvability and structural properties for N^2-puzzles, where legal cyclic robot movements connect all configurations. It also highlights the rapidly growing state space and branching factor that make time-optimal search difficult.

  • All states of the 9-puzzle are connected via legal moves, using a procedure that exchanges border robots without affecting others.
  • The 16-puzzle solution scheme recursively fixes robot locations and uses coordinated cycle rotations for remaining pairs.
  • All states of an N^2-puzzle for N ≥3 are connected via legal moves, so every such instance is solvable.
  • The N^2-puzzle state space contains N^2 factorial states, including 16! > 10^13 and 25! > 10^25.
  • The branching factor grows from 26 for the 9-puzzle to around 500 for the 16-puzzle and over 10^4 for the 25-puzzle.
Loading 1507.03290v1…