Cooperative Informed Tree (CoIT*): Cooperative Bi-Directional Multi-Resolution Motion Planning with Adaptive Edge Screening

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 appropriate 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.