A Schema-Guided Constrained Multi-Objective Optimization Evolutionary Algorithm for Multiple Uncrewed Aerial Vehicle Path Planning

Multiple uncrewed aerial vehicles path planning (MUPP) has become increasingly critical in modern aerial operations, enabling coordinated fleet missions across diverse and complex scenarios. Recent research has increasingly modeled MUPP as a constrained multi-objective optimization problem (CMOP) to address the inherent complexity of balancing competing objectives such as energy consumption and safety margins while satisfying operational constraints including obstacle avoidance and inter-UAV collision prevention. Evolutionary algorithms (EAs) have emerged as the predominant solution approach for the CMOP due to their population-based nature and effectiveness in handling multi-objective optimization with complex constraints. However, existing EAs typically evaluate entire solutions containing multiple UAV paths as whole units, which can lead to the loss of valuable information when high-quality individual UAV paths are embedded within otherwise poor-performing solutions. To overcome this fundamental limitation, we propose a schema-guided constrained multi-objective optimization evolutionary algorithm (SGCMOEA) that operates at both solution and schema levels, where each schema represents an individual UAV path. SGCMOEA introduces two key innovations: an adaptive elite schema preservation strategy that maintains a dynamic repository of solutions with valuable schemata discovered during evolution, and a schema-guided solution reconstruction strategy that intelligently reconstructs new solutions by combining the schemata identified throughout the search process. Comprehensive experiments on six real-world MUPP benchmark instances demonstrate that SGCMOEA significantly outperforms state-of-the-art algorithms in solution quality, convergence speed, and constraint satisfaction, validating its effectiveness for complex MUPP scenarios.