Open Access

ARTICLE

Improved Dijkstra Algorithm for Mobile Robot Path Planning and Obstacle Avoidance

Shaher Alshammrei¹, Sahbi Boubaker^2,*, Lioua Kolsi^1,3

1 Department of Mechanical Engineering, College of Engineering, University of Ha’il, Ha’il, 2440, Saudi Arabia
2 Department of Computer and Network Engineering, College of Computer Science and Engineering, University of Jeddah, Jeddah, 21959, Saudi Arabia
3 Research Laboratory of Metrology and Energy Systems, National Engineering School, Energy Engineering Department, University of Monastir, Monastir, 5000, Tunisia

* Corresponding Author: Sahbi Boubaker. Email:

Computers, Materials & Continua 2022, 72(3), 5939-5954. https://doi.org/10.32604/cmc.2022.028165

Received 04 February 2022; Accepted 22 March 2022; Issue published 21 April 2022

Abstract

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.

---

Keywords

---