Improved Dijkstra Algorithm for Mobile Robot Path Planning and Obstacle Avoidance

Optimal path planning avoiding obstacles is among the most attractive applications of mobile robots (MRs) in both research and education. In this paper, an optimal collision-free algorithm is designed and implemented practically based on an improved Dijkstra algorithm. To achieve this research objectives, first, the MR obstacle-free environment is modeled as a diagraph including nodes, edges and weights. Second, Dijkstra algorithm is used offline to generate the shortest path driving the MR from a starting point to a target point. During its movement, the robot should follow the previously obtained path and stop at each node to test if there is an obstacle between the current node and the immediately following node. For this aim, the MR was equipped with an ultrasonic sensor used as obstacle detector. If an obstacle is found, the MR updates its diagraph by excluding the corresponding node. Then, Dijkstra algorithm runs on the modified diagraph. This procedure is repeated until reaching the target point. To verify the efficiency of the proposed approach, a simulation was carried out on a hand-made MR and an environment including 9 nodes, 19 edges and 2 obstacles. The obtained optimal path avoiding obstacles has been transferred into motion control and implemented practically using line tracking sensors. This study has shown that the improved Dijkstra algorithm can efficiently solve optimal path planning in environments including obstacles and that STEAM-based MRs are efficient cost-effective tools to practically implement the designed algorithm.