Shortest Path Planning Algorithm – A Particle Swarm Optimization (PSO) Approach

Abstract

Path planning for a mobile robot is a difficult task and has been widely studied in robotics. The objective of recent researches is not just to find feasible paths but to find paths that are optimal with respect to distance covered and safety of the robot. Techniques based on optimization have been proposed to solve this problem but some of them used techniques that may converge to local minimum. In this paper, we present a global path planning algorithm for a mobile robot in a known environment with static obstacles. This algorithm finds the optimal path with respect to distance covered. It uses particle swarm optimization (PSO) technique for convergence to global minimum and a customized algorithm which generates the coordinates of the search space. Our customized algorithm generates the coordinates of the search space and passes the result to the PSO algorithm which then uses the coordinate values to determine the optimal path from start to finish. We perform our experiments using four different environments with population size 100 each in a 10 x 10 grid terrain and our results are favorable.