A Simple, but NP-Hard, Motion Planning Problem

Lawrence H. Erickson, Steven M. LaValleAAAI 2013 · DOI

Abstract

While finding a collision-free path in a 2D environment with convex obstacles is computationally efficient, the Minimum Constraint Removal (MCR) problem—finding a path that intersects the minimum number of obstacles—is NP-hard. This paper demonstrates that even in simple geometric settings with convex polygons, deciding which "soft" obstacles to breach is a fundamentally difficult optimization problem.

Introduction

In classical motion planning, the objective is typically binary: find a collision-free path from a start point $q_s$ to a goal $q_g$. However, many real-world scenarios involve "soft" constraints where obstacles are not strictly impassable but should be avoided if possible. Examples include a robot navigating a building with forceable doors or an outdoor rover crossing damaging terrain. The Minimum Constraint Removal (MCR) problem seeks the path that minimizes the number of intersected obstacles.

Figure 1: A path from $q_s$ to $q_g$ intersecting a subset of convex obstacles $O_1, \dots, O_7$. The MCR problem aims to find a path that minimizes this intersection count.

While previous research established the hardness of MCR in complex 3D environments or discrete graphs, this work focuses on the simplest case: a 2D plane with convex polygonal obstacles. Surprisingly, while checking for the existence of any path is trivial ($O(n \log n)$), finding the optimal path is NP-hard.

Methodology: Logic via Geometry

The authors prove NP-hardness through a reduction from MAX2HORNSAT (Maximum Binary Horn Clause Satisfiability). The reduction involves constructing geometric "gadgets" that encode logical variables and clauses into the 2D plane.

Variable Gadgets

To represent a boolean variable $x_i$, the authors design a gadget where the robot must choose between two paths representing the values True ($T$) or False ($F$). This choice forces the robot to commit to a truth assignment that will affect its interactions with subsequent clause gadgets.

Figure 5: A variable gadget where the robot's choice of path corresponds to a truth assignment for variable $x_i$.

Clause Gadgets and Weighting

Clause gadgets are geometric structures that intersect the variable loops. If the chosen path "satisfies" the clause's logic, the robot can pass without additional cost. Otherwise, it must intersect a "penalty" obstacle. To enforce these paths, the authors use Obstacle Weighting by stacking multiple identical obstacles. This creates high-cost boundaries that act as "walls," forcing the robot into specific corridors and allowing the standard MCR definition (which counts obstacles) to represent a weighted optimization problem.

Key Results

The paper successfully proves that MCR is NP-hard for navigation among convex polygons in a 2D plane. The reduction establishes a specific formula relating the minimum number of intersected obstacles ($z$) to the maximum number of satisfied logical clauses:

$$\text{Max Satisfied Clauses} = (a + 1)\ell + 3c - z$$

where $a$ is the number of low-weight obstacles, $\ell$ is the number of variables, and $c$ is the number of clauses.

Discussion and Future Work

This result highlights a significant complexity gap between path existence and path optimization. While finding a path is easy, finding the best path is computationally daunting.

The authors identify several open questions regarding specific obstacle geometries. For instance, if obstacles are restricted to unit circles, the problem might become tractable. Conversely, axis-aligned rectangles are conjectured to remain NP-hard. Furthermore, the proof relies on specific intersection patterns; if obstacles only intersect in pairs, the complexity might decrease. These findings have significant implications for higher-dimensional configuration spaces common in robotic arm planning, where MCR is likely to be even more difficult.

Summary updated

BibTeX
@inproceedings{erickson2013simple,
  author = {Lawrence H. Erickson and Steven M. LaValle},
  title = {{A Simple, but NP-Hard, Motion Planning Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8545},
}
Figure