An Improved Sampling Dijkstra Approach for Robot Navigation and Path Planning

Abstract

The task of path planning is extremely investigated in mobile robotics to determine a suitable path for the robot from the source point to the target point. The intended path should satisfy purposes such as collision-free, shortest-path, or power-saving. In the case of a mobile robot, many constraints should be considered during the selection of path planning algorithms such as static or dynamic environment and holonomic or non-holonomic robot. There is a pool of path-planning algorithms in the literature. However, Dijkstra is still one of the effective algorithms due to its simplicity and capabilities to compute single-source shortest-path to every position in the workspace. Researchers propose several versions of the Dijkstra algorithm, especially in mobile robotics. In this paper, we propose an improved approach based on the Dijkstra algorithm with a simple sampling method to sample the workspace to avoid an exhaustive search of the Dijkstra algorithm which consumes time and resources. The goal is to identify the same optimal shortest path resulting from the Dijkstra algorithm with minimum time and number of turns i.e., a smoothed path. The simulation results show that the proposed method improves the Dijkstra algorithm with respect to the running time and the number of turns of the mobile robot and outperforms the RRT algorithm concerning the path length.