Efficient Motion Planning in Narrow Passages via Long-Short Edge Coupling and Stitching Sampling

Abstract Sampling-based motion planners often suffer from slow finite-time convergence in narrow passages and cluttered high-dimensional environments, where useful valid samples near critical bottlenecks are sparse and bidirectional search can become locally stagnant. Existing informed planners improve efficiency by restricting sampling to cost-relevant regions or by refining global graph approximations, but local collision-failure information and the structure of the current path are often underused when search progress stalls. This paper proposes Stitching Informed Trees (SIT*), an almost-surely asymptotically optimal informed bidirectional planner that augments the underlying informed bidirectional search framework with two local stitching mechanisms. Before an initial feasible solution is found, SIT* detects exhaustion of the current bidirectional search over the graph approximation, identifies a promising forward–reverse frontier pair, and constructs a local bridge-repair ellipsoid around the current search interface. After an initial feasible solution has been found, SIT* applies long-short edge coupling to partition the current path and construct chained local ellipsoids for path-aware refinement. These local regions concentrate sampling on crowded or detour-prone path segments where cost improvement is more likely, while the global informed bidirectional search process is preserved. Benchmark results on Narrow Passage and Random Rectangles problems from $$\mathbb {R}^{2}$$ R 2 to $$\mathbb {R}^{8}$$ R 8 show that SIT* improves finite-time success rate, initial-solution convergence, and final solution cost compared with competitive informed-planning baselines.

Authors

Institutions

Publication Details

Journal
Journal of Intelligent & Robotic Systems
Published
2026-11-13
DOI
https://doi.org/10.1007/s10846-026-02484-9
Primary Topic
Robotic Path Planning Algorithms
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Efficient Motion Planning in Narrow Passages via Long-Short Edge Coupling and Stitching Sampling

Kuanqi Cai, Zhonghua Miao, Zhenshan Bing, Liding Zhang et al.
3 links
Journal of Intelligent & Robotic Systems
Robotic Path Planning Algorithms
article

Efficient Motion Planning in Narrow Passages via Long-Short Edge Coupling and Stitching Sampling

Kuanqi Cai, Zhonghua Miao, Zhenshan Bing, Liding Zhang, Alois Knoll, Xucheng Guo, Fan Wu
article en

Abstract

Abstract Sampling-based motion planners often suffer from slow finite-time convergence in narrow passages and cluttered high-dimensional environments, where useful valid samples near critical bottlenecks are sparse and bidirectional search can become locally stagnant. Existing informed planners improve efficiency by restricting sampling to cost-relevant regions or by refining global graph approximations, but local collision-failure information and the structure of the current path are often underused when search progress stalls. This paper proposes Stitching Informed Trees (SIT*), an almost-surely asymptotically optimal informed bidirectional planner that augments the underlying informed bidirectional search framework with two local stitching mechanisms. Before an initial feasible solution is found, SIT* detects exhaustion of the current bidirectional search over the graph approximation, identifies a promising forward–reverse frontier pair, and constructs a local bridge-repair ellipsoid around the current search interface. After an initial feasible solution has been found, SIT* applies long-short edge coupling to partition the current path and construct chained local ellipsoids for path-aware refinement. These local regions concentrate sampling on crowded or detour-prone path segments where cost improvement is more likely, while the global informed bidirectional search process is preserved. Benchmark results on Narrow Passage and Random Rectangles problems from $$\mathbb {R}^{2}$$ R 2 to $$\mathbb {R}^{8}$$ R 8 show that SIT* improves finite-time success rate, initial-solution convergence, and final solution cost compared with competitive informed-planning baselines.

Journal of Intelligent & Robotic Systems
Shanghai University (CN), Italian Institute of Technology (IT), Suzhou University of Science and Technology (CN), École Polytechnique Fédérale de Lausanne (CH), Technical University of Munich (DE), Nanjing University (CN)
Technische Universität München
Robotic Path Planning Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon