Multi Graph Search for High-Dimensional Robot Motion Planning
This work addresses motion planning for high-dimensional robots like manipulators, offering a solution to issues of unpredictability and high computational costs, though it appears incremental as it builds on existing search methods.
The paper tackles the problem of efficient motion planning for high-dimensional robotic systems by introducing Multi-Graph Search (MGS), a search-based algorithm that generalizes classical unidirectional and bidirectional search to a multi-graph setting, resulting in improved performance on manipulation and mobile manipulation tasks.
Efficient motion planning for high-dimensional robotic systems, such as manipulators and mobile manipulators, is critical for real-time operation and reliable deployment. Although advances in planning algorithms have enhanced scalability to high-dimensional state spaces, these improvements often come at the cost of generating unpredictable, inconsistent motions or requiring excessive computational resources and memory. In this work, we introduce Multi-Graph Search (MGS), a search-based motion planning algorithm that generalizes classical unidirectional and bidirectional search to a multi-graph setting. MGS maintains and incrementally expands multiple implicit graphs over the state space, focusing exploration on high-potential regions while allowing initially disconnected subgraphs to be merged through feasible transitions as the search progresses. We prove that MGS is complete and bounded-suboptimal, and empirically demonstrate its effectiveness on a range of manipulation and mobile manipulation tasks. Demonstrations, benchmarks and code are available at https://multi-graph-search.github.io/.