Multi-Target Robot Path Planning Using Enhanced Genetic Algorithms and Probabilistic Roadmaps

Abstract

Path planning receives considerable attention over the last two decades. This study proposes a hybrid approach that combines the probabilistic roadmap with an enhanced genetic algorithm (EGA), enabling path planning for both single and multiple targets. Compared with existing genetic algorithm (GA) methods, the proposed approach offers three main advantages: (1) it employs an environment representation based on image processing and morphological operations; (2) it introduces a new strategy for creating the initial population of the GA; and (3) it incorporates a novel operator to increase the quality of the generated paths. To demonstrate the effectiveness of the probabilistic roadmap and enhanced genetic algorithm (PRMEGA), multiple simulation experiments are performed, with results compared against the GA, artificial bee colony, and particle swarm optimization. The proposed approach outperforms existing methods by 25.5%, achieving near-optimal paths for both single and multiple targets in fewer generations while also reducing computation time by 14.1%.