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 goal state. The efficiency of an informed algorithm is contingent upon how quickly the planner can find the initial solution and the associated overhead involved in collision detection. Existing informed planners do not fully exploit the information contained in historical collision detection results, resulting in additional unnecessary collision detections. Furthermore, they optimize paths through rewiring before discovering an initial solution. This approach not only hampers the planner’s space exploration, but also generates a superfluous amount of unproductive overhead. In this paper, an Obstacle-Sensitive and Initial-Solution-first path planning algorithm (OSIS) is proposed. OSIS leverages historical collision detection 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.