Multi-objective Evolutionary Path Planning with Neutrality

Abstract

One of the main challenges when developing mobile robots is path planning. Efficient and robust algorithms are needed to produce plans for the movements of the robot. Many classical path planning algorithms depend on geometrically simple environments to achieve good performance, otherwise the paths produced tend to be far from ideal - especially when the paths are to be optimized for multiple objectives. Evolutionary algorithms have proved to be able to optimize paths in complex environments in a way that is easily adapted to solving multiple objectives. However, the solution space in path planning problems is very complex, marred by infeasible regions and local optima. This makes finding true optimal solutions difficult. In the last decade or so, neutrality - the ability to generate the same solution in multiple ways - has gained attention in evolutionary computing. Some work indicate that neutrality improves optimization in problems with difficult solution spaces. In this thesis an evolutionary algorithm for path planning with a neutral chromosome encoding is proposed. The chromosomes are encoded as sets of points, which are translated into roadmap graphs, which are then traversed to find one or more optimal solutions within the graph. To best represent the various strenghts of each chromosome, selection methods are proposed that let a number of solutions compete collectively for their chromosome. The algorithm has been implemented and tested thoroughly on four different environments, first for single-objective optimization, and then for multi-objective optimization problems. A comparison has been done to a reference algorithm that is similar but without a neutral solution representation. The proposed algorithm is not very efficient when optimizing distance only, but shows promising performance in multi-objective problems where other objectives are involved. The performance is significantly more robust than the reference algorithm in an environment that has many routes that separate and cross multiple times, finding a near-optimal solution up to 27% of the time, while the reference algorithm finds solutions of the same quality only 7% of the time.