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
- Kuanqi Cai (ORCID: https://orcid.org/0000-0002-3655-8116)
- Zhonghua Miao (ORCID: https://orcid.org/0000-0001-7203-0901)
- Zhenshan Bing (ORCID: https://orcid.org/0000-0002-0896-2517)
- Liding Zhang (ORCID: https://orcid.org/0009-0007-0119-706X)
- Alois Knoll (ORCID: https://orcid.org/0000-0003-4840-076X)
- Xucheng Guo
- Fan Wu
Institutions
- 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)
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
- Technische Universität München