Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs

1. Problem Definition

The paper addresses the Unlabeled Multi-Robot Motion Planning (MRMP) problem.

• Setting: A set of $m$ unit-disk robots operating within a polygonal workspace $W$ (which may contain obstacles).
• Goal: Move the robots from a set of starting positions $S$ to a set of target positions $T$ (where $|S|=|T|=m$) such that every target is occupied by exactly one robot at the end.
• Unlabeled Variant: Robots are indistinguishable; any robot can occupy any target, provided all targets are filled.
• Constraints: Robots must avoid collisions with obstacles and with each other (distance between centers must be $\ge 2$).
• Objective: Find a collision-free motion plan that minimizes the total path length (sum of lengths of all robot trajectories).

Key Challenge: The problem is generally PSPACE-hard. Previous polynomial-time solutions required strict "separation" assumptions to guarantee feasibility and optimality:

• Robots-Separation ($\rho$): Minimum distance between any two start/target positions.
• Obstacles-Separation ($\omega$): Minimum distance between any start/target position and any obstacle.

2. Methodology

The authors propose two distinct algorithmic strategies to relax the separation assumptions required for polynomial-time solutions while maintaining constant-factor approximation guarantees.

A. Generalized Weakly-Monotone Strategy (Algorithm 1)

This approach generalizes the work of Solovey et al. (RSS'15) by introducing a weakly-monotone strategy and an overlap parameter ($\epsilon$).

• Concept: Instead of requiring robots to stay strictly at their start/target points while others move (monotone), this strategy allows robots to move within a small "revolving area" (a disk of radius $1+\epsilon$) around their current position to clear paths.
• Mechanism:
  1. Optimal Assignment: Compute a set of geodesic paths $\Gamma$ matching starts to targets that minimizes total length (ignoring collisions).
  2. Target Selection: Identify an "$\epsilon$-interrupting target"—a target that does not strictly block any path in $\Gamma$, though it may slightly interrupt them.
  3. Path Switching: If a path is blocked, the algorithm performs a "switch," reassigning the blocking robot to a different target and finding a new path.
  4. Clearance Motion: Robots interrupting the active path move slightly within their revolving area to clear the way.
  5. Recursion: The process repeats, removing satisfied start/target pairs and shrinking the workspace.
• Trade-off: The algorithm uses a parameter $\epsilon \in [0, 1]$ to balance the required robots-separation ($\rho$) and obstacles-separation ($\omega$).

B. The Exodus Algorithm (Algorithm 2)

This is a completely different strategy designed to achieve the optimal robots-separation of $\rho = 2$ (the theoretical minimum for non-overlapping disks).

• Concept: A global "corridor-opening" strategy. Instead of local adjustments, all non-moving robots move synchronously to clear a path.
• Mechanism:
  1. Path Extension: Extend the geodesic path of the selected robot to the boundary of the free space.
  2. Partitioning: This extended path partitions the free space into "pockets," which are further subdivided into "Exodus cells" using angle bisectors of reflex vertices.
  3. Synchronized Movement: All robots not on the active path move exactly 2 units outward from the path, perpendicular to the path segment in their specific cell.
  4. Execution: The active robot moves along the path. Once it reaches the target, all other robots move back to their original positions.
• Requirement: This requires a larger obstacles-separation ($\omega = 3$) to ensure robots can move 2 units without hitting obstacles.

3. Key Contributions and Results

The paper significantly improves the state-of-the-art separation bounds for polynomial-time MRMP.

Improved Trade-offs (Theorem 10)

The generalized algorithm achieves constant-factor approximations ($O(OPT)$) for various combinations of $\rho$ and $\omega$:

1. Optimized Obstacles-Separation: $\rho \approx 3.291$ and $\omega \approx 1.354$.
2. Optimized Robots-Separation (Weakly-Monotone): $\rho = 2\frac{2}{3}$ and $\omega = 1\frac{2}{3}$.
3. Monotone Case: $\rho = 4$ and $\omega \approx 1.614$. (This resolves a conjecture from [18] that $\omega=1.614$ is sufficient for $\rho=4$).

The Exodus Algorithm Results (Theorem 12)

• Achieves the optimal robots-separation of $\rho = 2$ (monochromatic).
• Requires obstacles-separation of $\omega = 3$.
• Works for both labeled and unlabeled variants in simple polygons.
• Time Complexity: $\tilde{O}(m^3 + mn^2)$.
• Solution Length: $OPT + O(m^2)$.

Lower Bounds (Section 7)

The authors prove that their bounds are nearly tight:

• Unlabeled Case: If $\rho$ is not assumed (i.e., $\rho=2$), an obstacles-separation of at least 1.5 is sometimes necessary for a solution to exist.
• Labeled Case: An obstacles-separation of at least 2 is sometimes necessary.
• Monotone Plans: The paper proves that monotone plans may not exist if $\omega < 1.614$, and weakly-monotone plans may not exist if $\omega < 1.354$.

4. Significance and Impact

1. Relaxing Density Constraints: Previous algorithms required sparse robot configurations ($\rho \ge 4$) or large buffers around obstacles ($\omega \ge \sqrt{5} \approx 2.236$). This work demonstrates that dense environments can be handled with much tighter constraints ($\rho$ down to 2, $\omega$ down to 1.354).
2. Strategy Innovation: The introduction of the "Exodus" strategy provides a new paradigm for MRMP, moving away from purely local path-clearing to synchronized global movements, enabling the handling of the tightest possible robot separation ($\rho=2$).
3. Theoretical Limits: By establishing lower bounds on $\omega$ for both labeled and unlabeled cases, the paper defines the theoretical limits of what is possible without further assumptions, guiding future research.
4. Practical Applicability: The algorithms provide polynomial-time solutions with constant approximation guarantees, making them viable for real-world applications involving dense fleets of robots in cluttered environments.

Summary Table of Results

Algorithm Type	Robots-Separation ($\rho$)	Obstacles-Separation ($\omega$)	Approximation	Time Complexity
Previous (Solovey et al.)	4	$\sqrt{5} \approx 2.236$	$OPT + 4m$|$\tilde{O}(m^4 + n^2m^2)$
This Paper (Generalized)	$\approx 3.291$	$\approx 1.354$	$O(OPT)$|$\tilde{O}(m^4 + n^2m^2)$
This Paper (Generalized)	$2\frac{2}{3}$	$1\frac{2}{3}$	$O(OPT)$|$\tilde{O}(m^4 + n^2m^2)$
This Paper (Exodus)	2 (Optimal)	3	$OPT + O(m^2)$	$\tilde{O}(m^3 + mn^2)$
Lower Bound (Unlabeled)	2	1.5 (Necessary)	N/A	N/A

In conclusion, this paper fundamentally advances the understanding of multi-robot motion planning by proving that polynomial-time solutions with near-optimal path lengths are achievable in significantly denser environments than previously thought possible, provided appropriate trade-offs between robot spacing and obstacle clearance are made.