Terrain-Aware Probabilistic Search Planning for Unmanned Aerial Vehicles
Nathan Schomer, Julie Adams
AI summary
Problem
Low-cost UAVs used in mountain search and rescue face severe battery and computational limits, yet existing planning tools fail to prioritize high-probability search areas early while ensuring complete terrain coverage.
Approach
The method decouples planning into viewpoint sampling for terrain coverage and path ordering using a clustered traveling salesperson problem with a relaxed priority parameter to trade off search urgency against flight efficiency.
Key results
- Terrain-aware viewpoint sampling guarantees minimum sensor coverage
- Relaxed priority TSP formulation balances search urgency and path efficiency
- Metaheuristic solver enables fast in-situ computation on portable devices
- Field tests confirm resilient UAV operation under adverse mountain conditions
Why it matters
Provides a practical, computationally lightweight autonomy solution for volunteer mountain search and rescue teams operating under strict budget and battery constraints.
Abstract
Mountain search and rescue is a form of emergency response to assist people in austere environments (e.g., extreme terrain, poor weather). Volunteer mountain search and rescue teams in the United States have begun adopting consumer-grade unmanned aerial vehicles to assist a variety of tasks (e.g., search, resource delivery); however, these tools lack the autonomy necessary for the mountain search and rescue teams to fully realize their potential for wide area, aerial search. The unique and tight constraints of mountain search and rescue (e.g., in situ computation, sensor limitations) greatly limit the applicability of recent robotics research. A two-step coverage path planning algorithm that leverages existing viewpoint and path planning approaches was developed to meet the unique needs of mountain search and rescue. Viewpoints were sampled to meet a minimum coverage ratio and assigned priority from a search probability map. The path planning problem was formulated as a clustered traveling salesperson problem, which is solved with a metaheuristic iterative solver. Simulation results inform parameter selection for a series of field experiments. The field experiments demonstrate how the new algorithm can provide resilience against the many compounding factors that make UAV-based mountain search and rescue challenging.