Efficient planning for drone and ground vehicle teams with energy limits
Robust and Scalable UAV-UGV Planning for Aerial Monitoring under Energy and Precedence Constraints
RoboticsMultiagent Systems
Summary
Planning routes for teams of drones (UAVs) and ground vehicles (UGVs) is tricky when drones need to visit spots in a certain order and have limited battery life. The authors designed a method that figures out how these vehicles should move and when so drones can recharge on ground vehicles and still complete missions quickly. Their approach can handle unexpected travel delays and ensures the order of visits is respected by allowing teams to adjust their speed. They tested their method using computer simulations and showed it works efficiently, even though the problem is very complex.
What this means in practice
- •For drone delivery operators: Schedule drone and ground vehicle routes to maintain delivery order and ensure drones recharge without delaying shipments.
- •For disaster response teams: Coordinate UAV and UGV teams to monitor affected areas in sequence efficiently while managing drone battery limits and unexpected delays.
Authors
Cahit Ikbal Er, Yasin Yazicioglu
Abstract
We consider planning for unmanned aerial vehicle (UAV) and unmanned ground vehicle (UGV) teams in aerial monitoring missions with ordering requirements on the monitoring points to be visited by the UAV. The system consists of multiple UAV-UGV teams, each comprising one UAV and one UGV. UAV energy limitations are modeled through endurance, defined as the maximum flight time on a full battery. The UGVs serve as mobile charging stations and transport the UAVs between consecutive aerial tours. Given a set of monitoring points subject to ordering constraints and the teams' initial and terminal positions, the objective is to minimize mission completion time while satisfying UAV energy limits and the required visit order under bounded travel-time disturbances that may arise during execution. Unlike prior work, the plan jointly determines vehicle routes and their timing, allowing teams to slow down as needed to satisfy the ordering constraints. We develop a polynomial-time algorithm that generates efficient solutions to the underlying NP-hard planning problem. We establish feasibility guarantees, characterize the algorithm's computational complexity, and evaluate its performance via numerical comparisons.