BiAIT*: Symmetrical Bidirectional Optimal Path Planning with Adaptive Heuristic

Adaptively Informed Trees (AIT^∗) develops the problem-specific heuristic under the current topological abstraction of the state space with a lazy-reverse tree that is constructed without collision checking. AIT^∗can avoid unnecessary searching with the heuristic, which significantly improves the algorithm performance, especially when collision checking is expensive. However, the heuristic estimation in AIT^∗consumes lots of computation resources, and its asymmetric bidirectional searching strategy cannot fully exploit the potential of the bidirectional method. In this article, we extend AIT^∗from the asymmetric bidirectional search to the symmetrical bidirectional search, namely BiAIT^∗. Both the heuristic and space searching in BiAIT^∗are calculated bidirectionally. The path planner can find the initial solution faster with our proposed method. In addition, when a collision happens, BiAIT^∗can update the heuristic with less computation. Simulations are carried out to evaluate the performance of the proposed algorithm, and the results show that our algorithm can find the solution faster than the state of the arts. We also analyze the reason for different performances between BiAIT^∗and AIT^∗. Furthermore, we discuss two simple but effective modifications to fully exploit the potential of the adaptively heuristic method. Note to Practitioners-This work is inspired by the adaptively heuristic method and the symmetrical bidirectional searching method. This article introduces a novel algorithm using the symmetrical bidirectional method to calculate the heuristic and search the state space efficiently. The problem-specific heuristic in BiAIT^∗derives from a lazy-forward tree and a lazy-reverse tree, which are constructed without collision checking. In BiAIT^∗, the lazy-forward and lazy-reverse trees share heuristic information and jointly guide the growth of the forward and reverse trees, which conduct collision checking and guarantee that their edges are feasible. Compared with state-of-the-art methods, BiAIT^∗finds the initial heuristic and updates the heuristic more quickly. In the future, we will refine our design to avoid the suboptimal heuristic problem. The proposed algorithm can be extended to apply to industrial robots, medical robots, or service robots to realize efficient path planning. The OMPL implementation of BiAIT^∗is available at https://github.com/Licmjy-CU/BiAITstar.