Overcoming the Narrow Passage Bottleneck in Motion Planning

195 concepts160 papers1 proposal

Imagine trying to thread a needle. In our three-dimensional physical world, this is a test of fine motor control. But for a robotic arm with seven joints, the task is planned in a seven-dimensional mathematical space called the Configuration Space (C-space). In this high-dimensional space, the physical constraint of the needle's eye transforms into a notorious geometric challenge: the narrow passage problem.

Traditional motion planners rely on randomly sampling configurations to find a path from start to finish. While highly effective in open spaces, these algorithms fail catastrophically when forced through tight constraints. Understanding why this happens—and how modern research bypasses it—requires looking closely at the geometry of high-dimensional spaces.

The Geometry of the Bottleneck

To understand why narrow passages stall traditional planners, consider how volume behaves as dimensions increase. If you randomly sample points inside a 2D square containing a narrow hallway, your chance of hitting the hallway depends on its area relative to the square. If the hallway's width is halved, the probability drops linearly.

However, if a robot has $d$ degrees of freedom, its C-space is $d$-dimensional. Shrinking a clearance constraint across multiple joints causes the volume of the valid configuration space to shrink exponentially with the number of dimensions. As noted by Andreas Orthey et al. in Section Patterns: Efficiently Solving Narrow Passage Problems using Multilevel Motion Planning, the mathematical probability of uniformly sampling a valid configuration inside these tight corridors quickly approaches zero. The planner spends millions of iterations evaluating collisions in invalid regions, completely blind to the tiny opening that connects the space.

[ Open C-Space ] ---> ( Exponentially Shrinking Volume ) ---> [ Open C-Space ]
                                 |
                       [ Uniform Sampler Fails ]

The problem becomes even more severe during physical interactions like grasping an object or performing bimanual manipulation. To hold a rigid object with two hands, the distance between the robot's grippers must remain exactly constant. This strict kinematic constraint means that valid configurations no longer occupy a volumetric corridor; instead, they lie on a lower-dimensional surface called a manifold.

In the full C-space, a manifold has a volume of exactly zero (a property mathematicians call measure zero). Because a uniform random sampler has a 0% chance of hitting a zero-volume surface, standard exploration techniques cannot find valid states for contact-rich tasks.

Targeting the Manifold: Conditional and Sequenced Samplers

If uniform sampling cannot hit a zero-volume manifold, the most direct solution is to change how we sample. Rather than searching the entire space and rejecting failures, researchers design samplers that are mathematically constrained to the manifold from the start.

Leslie Pack Kaelbling et al. address this in Sampling-based methods for factored task and motion planning by exploiting "factoring." They observe that most robotic actions only alter a small subset of environmental variables at any given moment. By isolating these variables, the authors construct conditional samplers that generate configurations directly on the low-dimensional submanifolds where interactions occur.

Standard Sampling:  [ High-Dim Space ] --(Random Search)--> [ Misses Zero-Volume Manifold ]
Factored Sampling:  [ Isolated Subspace ] --(Conditional Sampler)--> [ Directly On Manifold ]

When a task involves a chain of different constraints—such as picking up a jug, moving it, and pouring—the robot must transition from one manifold to another. Péter Englert et al. formalized this in Sampling-Based Motion Planning on Sequenced Manifolds. Their framework, PSM*, treats the planning problem as a sequence of intersecting manifolds. Instead of searching blindly, the planner uses specialized steering strategies to navigate along these thin surfaces and cross the intersections explicitly, bridging the gaps that stall traditional algorithms.

Similarly, physical interactions can serve as a guide rather than an obstacle. In Contact Mode Guided Sampling-Based Planning for Quasistatic Dexterous Manipulation in 2D, Xianyi Cheng et al. use specific contact modes (such as sliding or fixed contact) to restrict the search space. By structuring the sampler around the physics of contact, the robot can discover complex manipulation strategies because the sampler is inherently biased toward valid physical boundaries.

Biasing Exploration and Local Connectivity

When a planner does manage to find a sample inside a narrow passage, it must exploit that discovery. Standard tree-based planners like Rapidly-exploring Random Trees (RRT) often fail here because they discard new samples if they cannot immediately link back to the main tree.

To fix this, Fabio Ramos et al. developed RRdT* in Balancing Global Exploration and Local-connectivity Exploitation with Rapidly-exploring Random disjointed-Trees. Instead of forcing every sample to connect to a single root, the algorithm allows disconnected trees to sprout within the narrow passages themselves. By combining directional sampling distributions with local random walks, the algorithm biases tree growth along the successful directions of previous iterations, effectively "threading" the search tree through the bottleneck.

Standard RRT:   [Root Tree] ----> [Obstacle Block] (Discarded Samples)
RRdT*:          [Root Tree] ----> [Local Disjointed Tree Inside Passage] ----> [Goal Tree]

Learning the Free Space: Generative Models and Projections

With the rise of deep learning, researchers have begun replacing hand-crafted heuristics with generative models that learn what valid paths look like from data. However, navigating ultra-tight spaces introduces a new problem: neural networks naturally output smooth approximations, meaning a generated path might still clip an obstacle or violate a strict kinematic constraint.

To enforce safety in highly dense environments, Jinhao Liang et al. introduced Simultaneous MRMP Diffusion (SMD) in Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models. Rather than relying on soft penalties or rejection sampling—which fail when the feasible space is a narrow manifold—the authors embed hard optimization constraints directly into the denoising steps of a diffusion model using an Augmented Lagrangian Method. The model generates trajectories while mathematically projecting them back onto the valid manifold at every step of the generation process.

Diffusion Step ---> Soft Guidance / Penalty ---> [May drift into obstacles]
Diffusion Step ---> Augmented Lagrangian Projection ---> [Guaranteed on Feasible Manifold]

This hybrid approach of pairing generative models with optimization is highly effective. In CppFlow: Generative Inverse Kinematics for Efficient and Robust Cartesian Path Planning, Jeremy Morgan et al. use a learned model to generate high-quality initial guesses for Cartesian paths. These guesses act as a macro-guidance system, placing the initial trajectory directly inside the narrow corridors so that classical optimizers can rapidly refine them without getting trapped in local minima.

Pre-Decomposing the Space

A final, powerful alternative to stochastic sampling is to analyze the geometry of the environment before planning begins. If the free space can be mapped out into simple, clean shapes, the planner can navigate narrow passages deterministically.

In Approximating Robot Configuration Spaces with few Convex Sets using Clique Covers of Visibility Graphs, P. Werner et al. introduce a method to decompose complex C-spaces into a small number of large convex polytopes. By constructing a visibility graph of sampled points and finding "cliques" (subgraphs where every point can see every other point), they can grow convex regions that perfectly capture the connectivity of the space, ensuring that narrow passages are explicitly mapped rather than left to chance.

For certain systems, this geometric reasoning can be translated entirely into symbolic logic. Shankara Narayanan Krishna demonstrates in The Reach-Avoid Problem for Constant-Rate Multi-Mode Systems that treating motion planning as a logical satisfaction problem via Bounded Model Checking allows planners to navigate highly constrained corridors. Because symbolic solvers reason about the boundaries mathematically rather than stochastically, they can penetrate narrow bottlenecks that random sampling algorithms might never find.

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 2, frozen text):

@misc{lacuna_narrow_passage_problem_7e8d8dd1_v2,
  title = {narrow passage problem},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/narrow-passage-problem/rdr_7e8d8dd157d6431299874f5464144ceb/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake