Sampling Strategies for High Dimensional Narrow Passages

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2164 papers189 conceptsfrozen 2026-10-04

In robot motion planning, the "curse of dimensionality" is not just a mathematical abstract—it is a physical wall. As a robot gains more joints or coordinates (Degrees of Freedom, or DoF), the space of all possible positions it can take, known as the Configuration Space (C-space), grows exponentially. Within this vast space, the "valid" regions—where the robot isn't hitting a wall or itself—often shrink into incredibly thin, winding corridors.

This is the Narrow Passage Problem. Traditional planners rely on random sampling: they throw "darts" at the C-space and check if they land in a valid spot. But in a high-dimensional room with a tiny doorway, the mathematical probability of a random dart landing exactly in that doorway is effectively zero.

Researchers are moving away from blind "dart-throwing" toward strategies that understand the geometry of the void.

The Geometry of Free Space

The earliest intuition for solving narrow passages was to stop looking at the obstacles and start looking at the "emptiness." In a foundational approach, Rodney A. Brooks proposed representing free space as a union of generalized cones (Solving the Find-Path Problem by Good Representation of Free Space). By modeling the "freeways" between obstacles, the planner can stay safely in the center of a passage rather than grazing the edges.

Modern geometric approaches have evolved this into "bubbles" and "cliques." Ki Myung Brian Lee and colleagues developed a Safe Bubble Cover (Safe Bubble Cover for Motion Planning on Distance Fields), which represents the environment as overlapping spheres of guaranteed free space. This allows a planner to "hop" from bubble to bubble, bypassing the need for expensive collision checks at every single point. Similarly, P. Werner and Daniela Rus use Visibility Clique Covers (Approximating Robot Configuration Spaces with few Convex Sets using Clique Covers of Visibility Graphs) to decompose complex C-spaces into a small number of large convex polytopes, making the "needle" of a narrow passage much easier to find.

Learning Where to Look

If the valid space is a thin manifold, why not learn its shape? A major thrust of recent research uses generative models to "bias" the sampler. Instead of sampling uniformly, these models learn a learned sampling distribution from past successful plans.

Multilevel Lifting and Tree Grafting

Sometimes, the best way to solve a 7-dimensional problem is to solve a 2-dimensional one first. Andreas Orthey pioneered the use of Section Patterns (Section Patterns: Efficiently Solving Narrow Passage Problems in Multilevel Motion Planning). This method solves a simplified version of the task (e.g., moving a point through a maze) and then "lifts" that solution into the robot's full high-dimensional space using reactive strategies.

When these paths inevitably hit a dead end due to a narrow constraint, researchers use "salvage" operations. Liding Zhang and Alois Knoll proposed Tree Grafting (Tree Based Grafting Approach for Bidirectional Motion Planning With Local Subsets Optimization), which identifies "failed" edges that almost made it through a passage and re-processes them with greedy local sampling to bridge the gap.

From Hallucination to Reality

In extreme cases, like the BARN Challenge (Autonomous Ground Navigation in Highly Constrained Spaces), robots must navigate gaps with only centimeters of clearance. Here, Xuesu Xiao and Peter Stone suggest Learning from Hallucination (Toward Agile Maneuvers in Highly Constrained Spaces: Learning from Hallucination). By taking a robot's successful path in an open field and "hallucinating" the tightest possible obstacles around it, they create a synthetic training set of perfect narrow-passage traversals.

By combining these facets—geometric decomposition, learned priors, and hierarchical lifting—modern motion planning is transforming the "narrow passage" from a statistical impossibility into a navigable map.

Papers in this version

Showing 60 of 164 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 147 papers
  2. Version 1 · 2026-10-04 · 164 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_narrow_passage_problem_7e8d8dd1,
  title = {narrow passage problem},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/narrow-passage-problem/rdr_7e8d8dd157d6431299874f5464144ceb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_sampling_strategies_for_high_dimensional_7e8d8dd1_v1,
  title = {Sampling Strategies for High Dimensional Narrow Passages},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sampling-strategies-for-high-dimensional-narrow-passages/rdr_7e8d8dd157d6431299874f5464144ceb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}