Optimal Motion Planning for Two Square Robots in a Rectilinear Environment

Pankaj K. Agarwal, Mark de Berg, Benjamin Holmgren, Alex Steiger, Martijn StruijsSocg 2025 · DOI

TL;DR

This paper tackles the problem of finding optimal collision-free paths for two square robots moving in a rectilinear environment. They present an efficient algorithm for minimizing the total path length of both robots (MIN-SUM) and prove that minimizing the time taken for both robots to reach their destinations (MIN-MAKESPAN) is NP-hard.

What Problem Does This Paper Address?

Imagine a warehouse with two automated guided vehicles (AGVs), each shaped like a square, needing to navigate around obstacles to reach their designated spots. The challenge is to figure out the best way for them to move, not just to avoid crashing into each other or the walls, but also to optimize for certain goals. Two common optimization goals are:

  1. Minimizing total work: This means minimizing the sum of the distances each robot travels. Think of it as minimizing the total fuel consumed or wear and tear on the robots.
  2. Minimizing makespan: This means minimizing the time until the last robot reaches its destination. This is crucial for tasks where a synchronized completion is important, like in a manufacturing line.

While algorithms exist for simpler scenarios (like point robots or robots moving in free space), finding optimal plans for multiple robots with complex shapes (like squares) in environments with obstacles, especially under these specific optimization criteria, is a significant challenge. This paper focuses on these two specific optimization goals for two square robots in a rectilinear environment (environments made of only horizontal and vertical lines).

Methods

The paper presents two main contributions:

  • Optimal MIN-SUM Algorithm: The core of their approach for the MIN-SUM problem is to prove that an optimal plan can always be found on a special kind of grid, called a "canonical grid." This grid is derived from the environment's boundaries and the robots' start/end positions. They then construct a configuration graph on this grid and use a standard shortest path algorithm (Dijkstra's) to find the optimal plan. The key technical challenge was proving that such a canonical-grid plan exists and can be constructed without increasing the total path length. This involved intricate "pushing" operations to align robot paths with grid lines while ensuring feasibility and optimality.
  • NP-Hardness Proof for MIN-MAKESPAN: For the MIN-MAKESPAN problem, they demonstrate that it's computationally very difficult (NP-hard). They achieve this by reducing it to the well-known PARTITION problem. Essentially, they construct a specific workspace and robot movement scenario where solving the MIN-MAKESPAN problem for the robots is equivalent to solving the PARTITION problem, which is known to be NP-hard.

Datasets

Not discussed in the paper. The problem is theoretical and focuses on algorithmic design for a general rectilinear environment.

Key Insights and Ideas

  • Canonical Grid is Key: The most significant insight is the proof that for the MIN-SUM problem, an optimal plan for two square robots in a rectilinear environment can always be found on a specific, structured grid. This drastically simplifies the search space for optimal paths.
  • "Pushing" as a Core Operation: The technique of "pushing" one robot's path to align with grid lines, while carefully managing the other robot's movement to avoid collisions and maintain optimality, is a novel and complex approach to transforming arbitrary optimal paths into the desired canonical-grid paths.
  • The Dichotomy of Optimization: The paper highlights a fundamental difference in complexity between minimizing total work (solvable efficiently) and minimizing completion time (computationally hard) for this multi-robot planning problem. This suggests that different strategies are needed depending on the primary objective.
  • Rectilinear Environments Simplify: The focus on rectilinear environments, while restrictive, allows for more structured analysis and the development of grid-based algorithms, which is a common strategy in computational geometry.

Key Results

  • MIN-SUM: An O(n log n) time algorithm is presented to compute an optimal collision-free motion plan for two unit square robots in a rectilinear environment with n vertices, minimizing the sum of their path lengths (l₁-metric). This is the first polynomial-time algorithm for this specific problem.
  • MIN-MAKESPAN: The problem of computing an optimal motion plan that minimizes the makespan (maximum time) for two unit square robots in a rectilinear environment is proven to be NP-hard.

Limitations and Future Work

  • Rectilinear Environment: The algorithms and proofs are specific to rectilinear environments. Extending them to general polygonal environments or environments with curved obstacles would be a significant challenge.
  • Two Robots: The results are for exactly two robots. Generalizing to k robots with a runtime dependent on k (e.g., o(k)) is an open problem.
  • Unit Squares: The robots are modeled as unit squares. While the l₁-metric is used, extending to other metrics or different robot shapes would require new approaches.
  • Open Problems: The authors explicitly list several open problems:
  • Can the runtime of the MIN-SUM algorithm be improved?
  • Can the algorithm be extended to k robots with a better runtime?
  • Is the MIN-SUM problem for two squares in a general polygonal environment in P?
  • Is there a pseudo-polynomial-time algorithm for MIN-MAKESPAN in rectilinear environments?

Summary updated

BibTeX
@inproceedings{agarwal2025optimal,
  author = {Pankaj K. Agarwal and Mark de Berg and Benjamin Holmgren and Alex Steiger and Martijn Struijs},
  title = {{Optimal Motion Planning for Two Square Robots in a Rectilinear Environment}},
  booktitle = {Socg},
  year = {2025},
  doi = {10.4230/lipics.socg.2025.5},
}
Figure