Planning a Shortest Path Based on Detour and Path Shortening

Abstract

This article aims to study path planning for autonomous unmanned vehicles, which includes the shortest path and the obstacle avoidance function. The path planning method in this article is based on a known environment for the robot in a point-to-point situation, thus it is different from the obstacle avoidance and path optimization method made by the probabilistic roadmap planners or the heuristic search method. The first task is to obtain a rough path, by avoiding obvious obstacles on the path using the concept of detour, and then apply the Constrained Delaunay triangulation to find the shortest path by applying the Dijkstra algorithm if the starting and/or destination points are in the concave obstacle. Finally, the Path Shortening method is used to obtain a suboptimal solution.