Narrow Passage Problem

• Also called: narrow passages
• Category: Planning & manipulation › Motion planning
• Tags: motion-planning, sampling-based-planning, configuration-space, planner-failure-modes

The difficulty sampling-based planners have with thin corridors in free space: random samples rarely land inside them, so planning slows or settles on a long detour.

Definition

The narrow passage problem is the best-known weakness of sampling-based motion planners such as probabilistic roadmaps and rapidly-exploring random trees. These planners explore the configuration space by drawing random samples and connecting them with short collision-free motions. If the only route, or the shortest one, passes through a region of free space that is thin in one or more directions, the chance that a uniform sample falls inside it is proportional to its volume, which is tiny. Even a sample that lands inside may not connect to neighbors on both sides. The planner then needs very many samples to find the passage, or it finds a longer route first.

The effect grows with dimension. A gap that is a little wider than the robot in a 2D map is easy to sample, but for a 7-joint arm reaching into a shelf, inserting a peg into a hole or moving a part through a fixture, the valid configurations can form a thin sliver in a space with many dimensions, and its volume fraction becomes extremely small. Theoretical analyses of sampling-based planners, such as expansiveness and the ε-goodness of free space, make this dependence explicit: convergence guarantees still hold, but the number of samples needed rises sharply as passages narrow.

Many remedies bias sampling toward the boundaries and gaps of free space. Gaussian sampling keeps samples near obstacle surfaces, the bridge test keeps midpoints of short segments whose ends are both in collision, obstacle-based and medial-axis samplers push samples toward the boundary or the middle of corridors, and learned samplers predict where useful configurations lie. Other methods temporarily widen free space by shrinking obstacles or relaxing constraints, plan in the easier problem and then repair the path. Choosing well-placed intermediate waypoints or goal regions often works in engineering practice.

Why it matters

Many real tasks are narrow-passage problems: insertion, reaching into cluttered shelves and bins, and moving through doors or tight fixtures. Recognizing the problem explains planner time-outs and detours, and points to fixes in the sampler rather than simply raising the time limit.

Key applications

• Peg-in-hole insertion and assembly into fixtures
• Arm motion into shelves, cabinets and bins
• Mobile robots and vehicles passing through doors and tight corridors
• Disassembly and maintainability analysis of mechanical parts
• Benchmarking and designing sampling strategies for motion planners

In practice

An arm must place a part into a fixture with a few millimeters of clearance on each side. With a uniform sampler the planner often times out, or returns paths that swing far around the fixture. The team confirms the cause by shrinking the collision meshes slightly and seeing that planning becomes fast. They then add a pre-insertion pose above the fixture as an intermediate goal, switch the final approach to a straight-line Cartesian move checked for collisions, and add a sampler that concentrates samples near obstacle surfaces for the remaining free motion. Planning time drops and the detours disappear.

Common misconceptions

• A narrow passage is a physically narrow gap — it is narrow in configuration space; a wide doorway can still be a narrow passage for a long object that must be rotated precisely
• More time always solves it — sample counts needed can grow sharply with dimension and narrowness, so better sampling or decomposition usually helps more
• Probabilistic completeness means the planner will find the passage quickly — completeness only promises success eventually
• Only sampling-based planners suffer from it — grid search and optimization also struggle with thin free-space regions, through resolution limits or poor initial guesses

Who should know this

• Motion planning engineers using OMPL, MoveIt or similar libraries
• Manipulation engineers working on insertion and assembly
• Researchers developing sampling strategies for planners
• Students studying sampling-based planning

Related technologies

• Gaussian sampling
• Bridge test sampling
• Obstacle-based PRM
• Medial-axis PRM
• Learned sampling distributions
• OMPL

Related terms

• Probabilistic Roadmap
• Rapidly-exploring random tree
• Configuration Space
• RRT*
• Homotopy Class
• Peg-in-hole insertion

Related projects

• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms
• Ruckig: Real-time jerk-constrained time-optimal trajectory generation for robots and machines
• NeuPAN: Real-time end-to-end planner that maps raw lidar points directly to robot actions