Globally Optimal Motion Planning for Mobile Robots via Topology-Aware Divide-and-Conquer

TY - JOUR

T1 - Globally Optimal Motion Planning for Mobile Robots via Topology-Aware Divide-and-Conquer

AU - Zhang, Runda

AU - Ning, Wentao

AU - Chai, Runqi

AU - Chai, Senchun

AU - Xia, Yuanqing

N1 - Publisher Copyright: © 1996-2012 IEEE.

PY - 2026

Y1 - 2026

N2 - Sampling-based motion planning methods have become widely adopted for motion planning due to their effectiveness in high-dimensional and complex environments. However, existing methods often prioritize planning efficiency and tend to get trapped in local optima. To overcome this limitation, we propose a divide-and-conquer hybrid sampling planning framework (DCH-RRT*), which decomposes the overall planning problem into topology-constrained subspaces for parallel exploration under the guidance of topological structure. DCH-RRT* first constructs a Connectivity Roadmap (CRM) and explores diverse topologies based on CRM to perform topology-aware decomposition, enabling an effective partitioning of the entire configuration space. A hybrid sampling strategy is then introduced to guide efficient exploration and accelerate convergence within the topology-informed, nonuniform sampling space. Theoretical analysis confirms that the proposed framework retains asymptotic optimality, while extensive experiments demonstrate that it consistently achieves high-quality paths with competitive computational efficiency compared to existing methods.

AB - Sampling-based motion planning methods have become widely adopted for motion planning due to their effectiveness in high-dimensional and complex environments. However, existing methods often prioritize planning efficiency and tend to get trapped in local optima. To overcome this limitation, we propose a divide-and-conquer hybrid sampling planning framework (DCH-RRT*), which decomposes the overall planning problem into topology-constrained subspaces for parallel exploration under the guidance of topological structure. DCH-RRT* first constructs a Connectivity Roadmap (CRM) and explores diverse topologies based on CRM to perform topology-aware decomposition, enabling an effective partitioning of the entire configuration space. A hybrid sampling strategy is then introduced to guide efficient exploration and accelerate convergence within the topology-informed, nonuniform sampling space. Theoretical analysis confirms that the proposed framework retains asymptotic optimality, while extensive experiments demonstrate that it consistently achieves high-quality paths with competitive computational efficiency compared to existing methods.

KW - Optimal planning

KW - sampling-based motion planning

KW - topology-aware decomposition

UR - https://www.scopus.com/pages/publications/105031491422

U2 - 10.1109/TMECH.2026.3660348

DO - 10.1109/TMECH.2026.3660348

M3 - Article

AN - SCOPUS:105031491422

SN - 1083-4435

JO - IEEE/ASME Transactions on Mechatronics

JF - IEEE/ASME Transactions on Mechatronics

ER -