Optimizing Autonomous Multi-UAV Path Planning for Inspection Missions: A Comparative Study of Genetic and Stochastic Hill Climbing Algorithms

Efficient path planning is vital for multi-UAV inspection missions, yet the comparative effectiveness of different optimization strategies has not received much attention. This paper introduces the first application of the Genetic Algorithm (GA) and Hill Climbing (HC) to multi-UAV inspection of indoor pipelines, providing a unique comparative analysis. GA exemplifies the global search strategy, while HC illustrates an enhanced stochastic local search. This comparison is impactful as it highlights the trade-offs between exploration and exploitation—two key challenges in multi-UAV path optimization. It also addresses practical concerns such as workload balancing and energy efficiency, which are crucial for the successful implementation of UAV missions. To tackle common challenges in multi-UAV operations, we have developed a novel repair mechanism. This mechanism utilizes problem-specific repair heuristics to ensure feasible and valid solutions by resolving redundant or missed inspection points. Additionally, we have introduced a penalty-based approach in HC to balance UAV workloads. Using the Crazyswarm simulation platform, we evaluated GA and HC across key performance metrics: energy consumption, travel distance, running time, and maximum tour length. The results demonstrate that GA achieves a 22% reduction in travel distance and a 23% reduction in energy consumption compared to HC, which often converges to suboptimal solutions. Additionally, GA outperforms HC, Greedy, and Random strategies, delivering at least a 13% improvement in workload balancing and other metrics. These findings establish a novel and impactful benchmark for comparing global and local optimization strategies in multi-UAV tasks, offering researchers and practitioners critical insights for selecting efficient and sustainable approaches to UAV operations in complex inspection environments.