Bi-Level Route Optimization and Path Planning with Hazard Exploration
Authors:
- Jimin ChoiJCJimin Choi
- Grant StaggGSGrant Stagg
- Cameron K. PetersonCPCameron K. Peterson
- Max Z. LiMax Z. Li
Preprint
Abstract
Effective risk monitoring in dynamic environments such as disaster zones requires an adaptive exploration strategy to detect hidden threats. We propose a bi-level unmanned aerial vehicle (UAV) monitoring strategy that efficiently integrates high-level route optimization with low-level path planning for known and unknown hazards. At the high level, we formulate the route optimization as a vehicle routing problem (VRP) to determine the optimal sequence for visiting known hazard locations. To strategically incorporate exploration efficiency, we introduce an edge-based centroidal Voronoi tessellation (CVT), which refines baseline routes using pseudo-nodes and allocates path budgets based on the UAV's battery capacity using a line segment Voronoi diagram. At the low level, path planning maximizes information gain within the allocated path budget by generating kinematically feasible B-spline trajectories. Bayesian inference is applied to dynamically update hazard probabilities, enabling the UAVs to prioritize unexplored regions. Simulation results demonstrate that edge-based CVT improves spatial coverage and route uniformity compared to the node-based method. Additionally, our optimized path planning consistently outperforms baselines in hazard discovery rates across a diverse set of scenarios.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- PyVRP: A High-Performance VRP Solver PackageINFORMS Journal on Computing, 2024
- Management of a post-disaster emergency scenario through unmanned aerial vehicles: Multi-Depot Multi-Trip Vehicle Routing with Total Completion Time MinimizationExpert Systems with Applications, 2024
- The Evolution of the Vehicle Routing Problem—A Survey of VRP Research and Practice from 2005 to 20222023
- Applications of drone in disaster management: A scoping reviewScience & Justice, 2022
- Drone-surveillance for search and rescue in natural disasterComputer Communications, 2020
- Wireless Sensor Networks and Multi-UAV systems for natural disaster managementComputer Networks, 2017
- Experimental Results in Multi-UAV Coordination for Disaster Management and Civil Security ApplicationsJournal of Intelligent & Robotic Systems, 2010
- Centroidal Voronoi Tessellations: Applications and AlgorithmsSIAM Review, 1999