Planning the Shortest Path in Cluttered Environments: A Review and a Planar Convex Hull-Based Approach

Abstract

Routing or path-planning is the problem of finding a collision-free and preferably shortest path in an environment usually scattered with polygonal or polyhedral obstacles. The geometric algorithms oftentimes tackle the problem by modeling the environment as a collision-free graph. Search algorithms such as Dijkstra’s can then be applied to find an optimal path on the created graph. Previously developed methods to construct the collision-free graph, without loss of generality, explore the entire workspace of the problem. For the single-source single-destination planning problems, this results in generating some unnecessary information that has little value and could increase the time complexity of the algorithm. In this paper, first a comprehensive review of the previous studies on the path-planning subject is presented. Next, an approach to address the planar problem based on the notion of convex hulls is introduced and its efficiency is tested on sample planar problems. The proposed algorithm focuses only on a portion of the workspace interacting with the straight line connecting the start and goal points. Hence, we are able to reduce the size of the roadmap while generating the exact globally optimal solution. Considering the worst case that all the obstacles in a planar workspace are intersecting, the algorithm yields a time complexity of O(n log(n/f)), with n being the total number of vertices and f being the number of obstacles. The computational complexity of the algorithm outperforms the previous attempts in reducing the size of the graph yet generates the exact solution.