Solving Three-Dimensional Path Planning Problem Using a Visibility-Based Graphical Representation of the Design Space

Abstract

Planning the shortest collision-free path among scattered obstacles is an NP-complete problem. As reviewed in this paper, a variety of deterministic as well as heuristic methods have been developed to address different instances of the problem. The focus of the deterministic methods is primarily on the optimality of the final solution and has been applied exclusively to regular shapes such as spheres or cubes. Nevertheless, due to the problem's intrinsic complexities (especially in 3D), researchers mainly resort to heuristics that offer acceptable (yet possibly suboptimal) solutions with reasonable resources. Therefore, less attention has been given to further the state-of-the-art in deterministic methods, which for 3D problems primarily focuses on approximating the solution. However, with the advancements in high-performance computing, we believe it is time to focus on solution quality. As such, this study aims to further the efforts in deterministic optimization methods for 3D path planning by overcoming some challenges of the existing methods and improving the optimality of the solution. The proposed approach is rooted in visibility-based planning methods where the obstacle-free space is modeled as a connectivity graph to be searched for the shortest path. The advantage of the proposed method in constructing the representative graph is that it does not make approximations to identify the graph nodes, unlike the existing methods. Nor does it limit the objects’ geometries to specific shapes such as blocks or spheres. The capability of the method in finding the shortest collision-free paths in environments cluttered with convex polyhedra is demonstrated using sample test problems.