A new sampling-based motion planning algorithm known as Stitching Informed Trees demonstrates improved finite-time success rates, faster initial-solution convergence, and lower final trajectory costs across complex environments, according to research published in the Journal of Intelligent and Robotic Systems. Developed by an engineering team including Liding Zhang, Xucheng Guo, and Alois Knoll, the method addresses critical performance bottlenecks that typically impede autonomous robotic navigation through narrow passages and cluttered high-dimensional spaces.
Sampling-based motion planners frequently encounter severe computational difficulties in constrained geometric environments. In both narrow passages and cluttered multidimensional configurations, the availability of useful, valid configuration samples near critical bottlenecks is exceptionally sparse. Under these challenging conditions, traditional bidirectional search algorithms often experience local stagnation, failing to achieve acceptable finite-time convergence as the search interface struggles to bridge tight gaps between obstacles.
While existing informed planners attempt to mitigate these computational delays, their current operational designs exhibit distinct limitations when search progress stalls. Existing approaches typically enhance algorithmic efficiency by restricting random sampling to cost-relevant regions or by systematically refining global graph approximations. However, when bidirectional search progress halts, conventional methods frequently underutilize vital local collision-failure information as well as the underlying structural characteristics of the current navigation path.
To overcome these limitations, the authors developed Stitching Informed Trees, designated as SIT*, which augments standard informed bidirectional search frameworks with two distinct local stitching mechanisms. The resulting algorithm maintains almost-sure asymptotic optimality, ensuring that solution paths converge toward the theoretical optimum over time while preserving the underlying global informed bidirectional search architecture.
The algorithm deploys its first local stitching mechanism before establishing an initial feasible trajectory. During this early planning stage, SIT* actively monitors the graph approximation to detect the exhaustion of the current bidirectional search. Upon identifying search exhaustion, the planner isolates a promising forward-and-reverse frontier pair and constructs a localized bridge-repair ellipsoid around the active search interface, concentrating sampling efforts directly across the problematic bottleneck.
Once an initial feasible solution is successfully established, SIT* initiates its second mechanism by applying long-short edge coupling to partition the existing trajectory. The planner constructs a sequence of chained local ellipsoids specifically configured for path-aware refinement. These chained ellipsoidal regions focus ongoing sampling on crowded or detour-prone path segments where cost reductions are most probable, all while maintaining the integrity of the overarching global bidirectional search.
The research team evaluated the performance of SIT* across standard simulation benchmarks, testing both Narrow Passage and Random Rectangles problem sets spanning from two-dimensional space to eight-dimensional space. Across these configurations, comparative benchmark results confirmed that SIT* consistently outperforms competitive informed-planning baselines in finite-time success rate, initial-solution convergence speed, and final path cost.
Subject of Research: Sampling-based robotic motion planning in narrow passages
Article Title: Efficient Motion Planning in Narrow Passages via Long-Short Edge Coupling and Stitching Sampling
Article References: Zhang, L., Guo, X., Cai, K., Wu, F., Miao, Z., Bing, Z., & Knoll, A. (2026). Efficient Motion Planning in Narrow Passages via Long-Short Edge Coupling and Stitching Sampling. Journal of Intelligent & Robotic Systems. https://doi.org/10.1007/s10846-026-02484-9
Image Credits: AI Generated
DOI: 10.1007/s10846-026-02484-9
Keywords: motion planning, sampling-based planners, narrow passages, Stitching Informed Trees, SIT*, bidirectional search, long-short edge coupling, stitching sampling, bridge-repair ellipsoid, chained local ellipsoids, path-aware refinement, asymptotic optimality, finite-time convergence, high-dimensional planning, Random Rectangles benchmark, robotics
News Source: Denise Maddox. (November 16, 2026). Stitching Informed Trees Improve Motion Planning in Narrow High-Dimensional Passages. Scienmag.



