OSIS: Obstacle-Sensitive and Initial-Solution-first path planning

Abstract

Informed path planning is a type of algorithm that uses problem-specific knowledge, expressed as heuristics, to efficiently discover an optimal path between a start and a goal state. The primary challenge in optimizing informed planning algorithms lies in quickly finding the initial solution while minimizing collision checking costs. In this paper, an Obstacle-Sensitive and Initial-Solution-first path planning algorithm (OSIS) is proposed. OSIS leverages historical collision check results to construct an asymptotically accurate distribution of obstacles in space. Based on this distribution, OSIS employs a reusable, inadmissible, yet more accurate heuristic that applies to the entire problem domain. Additionally, an initial-solution-first path optimization strategy is proposed to eliminate unnecessary path optimization. It ensures that OSIS prioritizes exploring uncharted spaces, leading to faster initial solution discovery. Experiments have demonstrated that OSIS outperforms existing algorithms in navigating around obstacles, and achieving convergence in solution cost. Experimental data show that OSIS can even improve the success rate of collision checking to more than 90% in the planning problems studied in this paper, which far exceeds the performance of other algorithms.