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 indo...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-12-01
|
| Series: | Energies |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1996-1073/18/1/50 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841549280495534080 |
|---|---|
| author | Faten Aljalaud Yousef Alohali |
| author_facet | Faten Aljalaud Yousef Alohali |
| author_sort | Faten Aljalaud |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-81622f5c3ad44d02a389b9e76d7be126 |
| institution | Kabale University |
| issn | 1996-1073 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Energies |
| spelling | doaj-art-81622f5c3ad44d02a389b9e76d7be1262025-01-10T13:16:56ZengMDPI AGEnergies1996-10732024-12-011815010.3390/en18010050Optimizing Autonomous Multi-UAV Path Planning for Inspection Missions: A Comparative Study of Genetic and Stochastic Hill Climbing AlgorithmsFaten Aljalaud0Yousef Alohali1Computer Science Department, Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh 11564, Saudi ArabiaComputer Science Department, College of Computer and Information Sciences, King Saud University, Riyadh 11451, Saudi ArabiaEfficient 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.https://www.mdpi.com/1996-1073/18/1/50autonomousmulti-UAVpath planninginspectiongenetic algorithm |
| spellingShingle | Faten Aljalaud Yousef Alohali Optimizing Autonomous Multi-UAV Path Planning for Inspection Missions: A Comparative Study of Genetic and Stochastic Hill Climbing Algorithms Energies autonomous multi-UAV path planning inspection genetic algorithm |
| title | Optimizing Autonomous Multi-UAV Path Planning for Inspection Missions: A Comparative Study of Genetic and Stochastic Hill Climbing Algorithms |
| title_full | Optimizing Autonomous Multi-UAV Path Planning for Inspection Missions: A Comparative Study of Genetic and Stochastic Hill Climbing Algorithms |
| title_fullStr | Optimizing Autonomous Multi-UAV Path Planning for Inspection Missions: A Comparative Study of Genetic and Stochastic Hill Climbing Algorithms |
| title_full_unstemmed | Optimizing Autonomous Multi-UAV Path Planning for Inspection Missions: A Comparative Study of Genetic and Stochastic Hill Climbing Algorithms |
| title_short | Optimizing Autonomous Multi-UAV Path Planning for Inspection Missions: A Comparative Study of Genetic and Stochastic Hill Climbing Algorithms |
| title_sort | optimizing autonomous multi uav path planning for inspection missions a comparative study of genetic and stochastic hill climbing algorithms |
| topic | autonomous multi-UAV path planning inspection genetic algorithm |
| url | https://www.mdpi.com/1996-1073/18/1/50 |
| work_keys_str_mv | AT fatenaljalaud optimizingautonomousmultiuavpathplanningforinspectionmissionsacomparativestudyofgeneticandstochastichillclimbingalgorithms AT yousefalohali optimizingautonomousmultiuavpathplanningforinspectionmissionsacomparativestudyofgeneticandstochastichillclimbingalgorithms |