Probabilistic Roadmap, A*, and GA for Proposed Decoupled Multi-Robot Path Planning

Abstract

In this paper, two main steps algorithm used to determine the optimal path planning for the multi-robot problem. Firstly, a probabilistic roadmap is developed in the free configuration space of the robots work space which avoids the static obstacles. Then by using the A* algorithm and the probabilistic roadmap created, the near-optimal path for each robot is determined which represents the shortest path between the starting point and the end point. Secondly, we used an improved genetic algorithm to make these paths more optimal to guarantee the shortest paths, which represents an intermediate process lie between roadmap creation and path following. Also, we used a new population production method in this algorithm, and new operators in addition to the selection and crossover in the genetic algorithm also used to ensure the feasibility of the results. The results of the simulation gained from the proposed method show that it is optimal by finding the shortest path for each robot with optimization rate average 18.25% from the original path, and it is fast enough to find the optimal paths in few generations.