Analyzing the Performance of Real-Coded Genetic Algorithm with Control Locations for Multi-Robot Path Planning

The problem of navigating multi-robot systems through environments in a collision-free manner is becoming ever more important in the healthcare industry. An increasing interesting can be observed in optimization-based methods for path planning in multi robot systems. This study analyzes the performance of a Real-Coded Genetic Algorithm when planning paths for multi-robot systems with up to five robots. Our approach uses the control location method extended to multiple robot systems. The entire path-planning task was contained within the objective function, which meant that no custom modifications to the optimization algorithm were required, furthermore no constraints were placed on the robot displacements—the collision space was continuous. In total 625 simulations were performed over five custom collision maps and including five reruns of the procedure to minimize the effects of random number generator. Our findings indicated that the methods was viable in cases up to five robots, where the average success rate for path planning was more than 37% with a low number of generations and population size. Depending on the map the success rate could be as high as 80% for systems with 4 robots. Interestingly, avoiding robot-to-environment collisions was more difficult than robot-to-robot collisions, while the number of control locations proved to be more costly for the algorithm than the number of the robots. This might suggest that the algorithm is more suited to simpler collision spaces with higher number of robots.