Cooperative Informed Tree (CoIT*): Cooperative Bi-Directional Multi-Resolution Motion Planning with Adaptive Edge Screening
Xiao Tan, Yaonan Wang, renjie Ding, min liu, Zhe Zhang, Xiaoqian Yu
AI summary
Problem
Balancing heuristic accuracy with computational efficiency in informed path planning remains difficult, as existing bidirectional methods suffer from limited reverse-side edge screening and underutilized forward-reverse heuristic cooperation.
Approach
CoIT* coordinates forward and reverse searches using a multi-heuristic, multi-resolution reverse queue that supplies accurate priors, enabling the forward search to defer expensive full-resolution collision checks via high-resolution pre-checks.
Key results
- Significantly lower planning time and higher accuracy than state-of-the-art planners on high-dimensional benchmarks
- Reduced collision-checking overhead through prior-guided lazy edge validation
- Successful validation in simulated and real-world surgical robot planning tasks
- Guaranteed probabilistic completeness and asymptotic optimality with dynamic local-global resolution adaptation
Why it matters
Provides a scalable, efficient planning framework for high-dimensional robotic applications like surgical robotics where speed and reliability are critical.
Abstract
In informed search-based path planning, heuristic functions that incorporate problem knowledge are essential for guiding the search and improving efficiency. The accuracy and computational cost of these heuristics are therefore critical to performance. However, accuracy and computational efficiency are often contradictory, making it difficult to select an appro- priate heuristic for a given problem. In this paper, we present CoIT* (Cooperative Informed Tree*), an almost-asymptotically optimal asymmetric bi-directional planning algorithm designed to address these challenges. CoIT* introduces a multi-resolution and multi-heuristic queue cooperation mechanism between forward and reverse searches: the forward search interacts with the reverse search to provide cooperative information exchange, which enhances both local and global edge screening. This cooperation improves the accuracy of the reverse search, while multi-resolution exploration enables lazy edge validation in the forward search, thereby reducing planning time. We validate CoIT* on high-dimensional benchmark problems as well as simulated and real surgical robot planning tasks. Experimental results demonstrate that CoIT* achieves higher accuracy and significantly lower planning time compared with state-of-the- art planners.