Multi-Objective Memetic Algorithms For Path Planning

Path planning problem is the hotspot in many research areas, such as autonomous robotics, GPS navigation, vehicle scheduling in logistics, and routing problem in network communication. Solving path planning problem is of great application potentials and research values, where planning algorithms play a pivotal role. Real-world path planning problems often call for optimizing multiple objectives simultaneously which poses great challenges to path planning algorithm. The traditional path planning algorithms were mainly designed to solve single objective problem, and tend to be time-consuming and get trapped in local optimal especially in the complex environments. Multi-objective evolutionary algorithms(MOEAs) can complete with the traditional methods thanks to their robustness, extensibility and capability of solving multi-objective optimization problems; yet they could suffer from slow convergence in local region. Multi-objective memetic algorithms(MOMAs) combine MOEAs with meme operator(local search). The local search is introduced to fine-tune the individuals to accelerate the local convergence. MOMAs can improve the searching efficiency of multi-objective path planning by taking advantage of both global and local search.This dissertation focuses on the applications of MOMAs to real-world path planning problems. The main contributions of this work can be summarized as follows:(1) Two multi-objective memetic algorithms namely MOMA-E and MOMA-D are proposed to solve the global path planning problem of wheeled robots. Particularly, the two MOMAs are implemented based on MOEA with elitist non-dominated sorting and decomposition strategies respectively to optimize the path length and smoothness simultaneously. Novel path encoding scheme, path rectification, and specific evolutionary operators are designed and introduced to the MOMAs to enhance the search ability of the algorithms as well as guarantee the safety of the candidate paths obtained in complex environments. Experimental results on both simulated and real maps show that the proposed MOMAs are efficient in planning a set of valid tradeoff paths in complex environments.(2) A multi-objective memetic algorithm called LSH-MOMA is proposed to solve the one-to-many-to-one dynamic pickup-and delivery problem(1-M-1 DPDP). LSH-MOMA is a synergy of multi-objective evolutionary algorithm and locality-sensitive hashing based local search. Three objectives namely route length, response time, and workload are optimized simultaneously in an evolutionary framework. In each generation, LSH-based rectification and local search are imposed to repair and improve the individual solutions. LSH-MOMA is evaluated on four benchmark DPDPs and the experimental results show that LSH-MOMA is efficient in obtaining optimal tradeoff solutions of the three objectives.This dissertation presents three MOMAs to solve the global path planning problem of the wheeled robot and 1-M-1 DPDP respectively. The experimental results show that they are efficient in obtaining optimal tradeoff solutions of multiple objectives, which can provide some insights for later researcher facing similar path planning problems.