Optimization of waypoint-guided potential field navigation using evolutionary algorithms

Abstract

This paper describes a method for optimization of waypoint selection for potential field navigation in autonomous robots. In the method presented here, a genetic algorithm (GA) is used for optimizing the potential field. The chromosome of each individual encodes parametrizations for the potential field generated by waypoints, obstacles, and goals. The waypoints themselves are obtained through a Voronoi tessellation of the environment in which the robot is operating. It is demonstrated that the algorithm allows a robot to navigate safely and efficiently through spaces with many obstacles, even in cases where these are placed in a strongly unfavorable way. Furthermore, the results from simulations were implemented successfully in an actual Khepera robot. Using a slightly simplified navigation procedure, in which the robot comes to a standstill between successive steps in the navigation, the Khepera robot managed to navigate through one of the most difficult environments used in the simulations. Finally, the paper briefly describes a different implementation of potential field navigation, in the path planning adaptation submodule of a more advanced simulated mobile robot (VirBot).