Hierarchical heuristic search using a Gaussian mixture model for UAV coverage planning.

Area of Science:

• Robotics and Control Systems
• Artificial Intelligence
• Search and Rescue Operations

Background:

• Optimizing unmanned aerial vehicle (UAV) flight paths is crucial for maximizing search mission success.
• Environmental factors like vegetation and lighting create variable detection probabilities, complicating pathfinding.
• The optimal search path problem is NP-Hard, especially with partial detection considerations.

Purpose of the Study:

• To develop novel algorithms for generating efficient UAV flight paths that incorporate partial detection.
• To address the complexity introduced by varying detection probabilities in different search areas.
• To produce flight paths that approximate optimal solutions for search missions.

Main Methods:

• Introduction of a new class of algorithms utilizing a task difficulty map to model partial detection.
• Employment of the mode goodness ratio heuristic with a Gaussian mixture model for prioritizing search subregions.
• Exploration of the parameter space at multiple resolution levels to find effective paths.

Main Results:

• The proposed algorithms significantly outperform two established methods (Bourgault's and LHC-GW-CONV) in simulated scenarios.
• Demonstrated ability to generate efficient paths that achieve near-optimal payoffs.
• Validated performance across three distinct real-world search and rescue scenarios.

Conclusions:

• The developed algorithms offer a significant advancement in UAV search mission efficiency and effectiveness.
• Accounting for partial detection through task difficulty maps is a viable strategy for complex search problems.
• These algorithms provide a practical solution for optimizing UAV search paths in challenging environments.