Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones

Rashid Alyassi; Majid Khonji; Areg Karapetyan; Sid Chi-Kin Chau; Khaled Elbassioni; Chien-Ming Tseng

Source-linked AI summary

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones

Rashid Alyassi, Majid Khonji, Areg Karapetyan, Sid Chi-Kin Chau, Khaled Elbassioni, Chien-Ming Tseng

arXiv:1703.10049v5Mar 29, 2017cs.ROcs.DS

TL;DR

Long-distance autonomous drone missions must jointly manage energy-constrained routing and recharging under battery, wind, and operational limitations. The paper combines a real-world multirotor energy model with an ATSP-based planner and approximation algorithm, then validates the system through simulations and experiments. The estimator matches ground-truth power within 0.4% in one experiment and energy within 5% in a complex recharging scenario.

Problem
Limited battery endurance and wind sensitivity make long-distance drone routing difficult, while existing planners largely focus on short-distance fleet missions without integrated recharging decisions.
Method
The paper models multirotor energy consumption, formulates flight and recharging planning as a multi-objective ATSP, and develops an approximation algorithm with performance guarantees.
Results
Estimated power consumption matched ground truth within 0.4%, while estimated energy consumption in a complex recharging scenario stayed within 5% of measurements.
Takeaways & Limitations
The resulting drone management system supports energy-feasible long-distance mission planning, real-time flight-path tracking, and recomputation in dynamic environments.

Abstract

from arXiv · show

Unmanned aerial vehicles (UAVs), commonly known as drones, are being increasingly deployed throughout the globe as a means to streamline monitoring, inspection, mapping, and logistic routines. When dispatched on autonomous missions, drones require an intelligent decision-making system for trajectory planning and tour optimization. Given the limited capacity of their onboard batteries, a key design challenge is to ensure the underlying algorithms can efficiently optimize the mission objectives along with recharging operations during long-haul flights. With this in view, the present work undertakes a comprehensive study on automated tour management systems for an energy-constrained drone: (1) We construct a machine learning model that estimates the energy expenditure of typical multi-rotor drones while accounting for real-world aspects and extrinsic meteorological factors. (2) Leveraging this model, the joint program of flight mission planning and recharging optimization is formulated as a multi-criteria Asymmetric Traveling Salesman Problem (ATSP), wherein a drone seeks for the time-optimal energy-feasible tour that visits all the target sites and refuels whenever necessary. (3) We devise an efficient approximation algorithm with provable worst-case performance guarantees and implement it in a drone management system, which supports real-time flight path tracking and re-computation in dynamic environments. (4) The effectiveness and practicality of the proposed approach are validated through extensive numerical simulations as well as real-world experiments.

I. INTRODUCTION

The paper addresses long-distance drone missions constrained by limited batteries, wind, and recharging decisions by combining energy modeling, tour optimization, approximation guarantees, and real-time management.

Motivation: Limited battery endurance and wind sensitivity restrict drones’ suitability for persistent, long-distance missions.Existing UAV planners mainly target short-distance, recurrent fleet tours and do not directly address distant fuel-constrained trips with recharging decisions.
Motivation: Frequent or poorly planned recharging can cause delays and excess energy use, while inaccurate battery estimates may disrupt missions or cause failure.
Contributions: A first-order regression model estimates multirotor energy use from wind, motion kinematics, and payload mass within 5% deviation across three drones.
Contributions: The energy-constrained tour problem is formulated as a multi-objective ATSP minimizing flight and recharging time while maintaining feasible battery state-of-charge.
Contributions: An approximation algorithm jointly plans flight missions and charging strategies with an asymptotic constant-factor guarantee and demonstrated scalability.
Contributions: The implemented management system supports real-time path tracking and recomputation, with simulations and real-world experiments used for validation.

IV. POWER CONSUMPTION MODEL

The paper develops a practical battery-endurance estimator using experiments on three commercial multirotor drones and models motion, weight, wind, and altitude as energy-consumption factors.

Model Development: A nine-term regression model is trained separately for each drone and evaluated through field experiments.
Experimental Setup and Scope: Battery-consumption data were collected from 3DR Solo, DJI Matrice 100, and DJI Matrice 600 Pro using developer kits and onboard flight sensors.
Model Factors: The endurance model examines motion type, total drone and payload weight, wind speed and direction, and flight altitude as compound energy-consumption factors.

B. Experimentation Results and Analysis

Experiments characterize how motion, payload, wind, and altitude affect drone power consumption, supporting a multivariate model that estimates battery use under varied flight conditions. The model closely matches measurements, with errors of 0.4% in one validation and within 5% in a complex scenario.

Motion, Wind, and Payload Experiments: 3DR Solo power consumption increases almost linearly with payload weight during hovering, within its 500 g maximum loading capacity.The experiments also examine the joint effects of payload and horizontal motion on DJI Matrice 600.
Motion, Wind, and Payload Experiments: Power consumption decreases during headwind flight at maximum ground speed in the tested 3DR Solo setting, although aerodynamic drag may reverse this benefit beyond a threshold.The observed reduction is attributed to translational lift increasing relative airflow over the propellers.
Altitude Experiments: Altitude changed observed hovering power consumption by merely 1% between 50 and 110 meters for DJI Matrice 600.Under the adopted FAA altitude limit, the study therefore treats the altitude effect as constant, while noting it might be larger at higher altitudes.
Regression Model of Power Consumption for Drones: The model expresses estimated power as a linear combination of three composite forces parameterized by mass, acceleration, velocity, and wind attributes.It assumes uniform conditions over a time interval, so energy consumption is estimated as power multiplied by elapsed time.
Model Evaluation: Predicted and measured power records match within 0.4% for 3DR Solo and DJI Matrice 100, while a complex DJI Matrice 600 scenario remains within 5% deviation.The complex scenario includes multiple target locations and a recharging station.

V. SOLUTION METHODOLOGY

The methodology reduces energy-constrained drone mission planning to distance optimization under battery and charging constraints, then constructs a feasible tour through graph-based approximation procedures.

A. Case with Uniform Speed and Steady Wind: Under uniform speed and steady wind, flight time is proportional to path length, while energy consumption and charging time are modeled linearly.The model permits edge-dependent flight-cost coefficients to represent non-uniform environmental effects and directional wind asymmetry.
A. Case with Uniform Speed and Steady Wind: The formulation simplifies total-trip-time minimization to minimizing a modified travel distance while retaining a constant-factor relationship to the original problem.The reduction uses bounds relating charging time and flight time, and the simplified problem is later connected back to DFP.
A. Case with Uniform Speed and Steady Wind: The modified distance between two sites is the shortest feasible path that may pass through charging stations, assuming full charge at the origin.The simplified formulation assumes maximum state of charge at charging stations and later restores minimal charging requirements using Lemma 2.
A. Case with Uniform Speed and Steady Wind: The method assumes reachable charging access, accounts for asymmetric distances, and returns a near-optimal plan with a provable constant-factor guarantee.The reachability assumption requires each target to be accessible from some charging station within the available battery range.
A. Case with Uniform Speed and Steady Wind: Find-plan applies a Hungarian-algorithm tour construction, converts sub-tours into a feasible flight plan, and then minimizes its charging requirements.The implementation computes pairwise distances and paths before applying Fix-plan and Fix-charge.

B. Practical Adaptations

The proposed algorithms are extended heuristically to handle uncertain wind and variable drone speed in practical missions.

B. Practical Adaptations: Wind uncertainty is handled conservatively by replacing each flight-cost coefficient with its maximum over the anticipated wind domain.The uncertain domain can encode ranges of wind speed and orientation.
B. Practical Adaptations: Variable speed is handled by solving multiple rounds at increasing speeds and selecting the feasible plan with the lowest total flight time.The process stops when higher speed makes the problem infeasible because some sites can no longer be reached on battery.

VI. EXPERIMENTAL VALIDATION AND CASE STUDIES

The approach is evaluated through a real-world experiment and extensive numerical simulations examining flight-plan feasibility, charging strategies, average-case performance, and scalability.

VI. EXPERIMENTAL VALIDATION AND CASE STUDIES: A real-world experiment verifies the produced flight mission plans and recharging strategies in an automated drone management system.The experiment complements the analytic results developed for the basic setting.
VI. EXPERIMENTAL VALIDATION AND CASE STUDIES: Numerical simulations and diverse case studies examine the planner’s average-case performance and scalability.

A. Drone Management System

The drone management system lets users specify goals, obtain computed flight plans through a cloud server, and monitor missions using continuously fetched onboard-sensor data.

A. Drone Management System: The interface accepts user goals and visualizes the computed flight mission plan, with cloud computation based on supplied location data.The drone is then programmed to follow the pre-computed plan.
A. Drone Management System: Continuous GPS, video-feed, and state-of-charge data support real-time monitoring of the drone’s flight status.

B. Field Experiment

The field experiment tested the planner on a DJI Matrice 600 patrolling four sites with a charging station, while the case studies evaluated routing under varied wind, payload, battery, and uncertainty conditions.

Field experiment: The planner produced route [S, 1, 2, 3, C, 4, S], covering 9.47 km with one recharge stop in the DJI Matrice 600 experiment.The charging detour followed the selected minimum battery SoC limit of 40%.
Field experiment: The field experiment showed around 5% discrepancy between measured battery levels and regression-model estimates, primarily attributed to wind measurements from one location.
Case studies: In Study 1, north-east wind increased energy consumption and charging-related trip time relative to south wind.
Case studies: Doubling 3DR Solo’s battery capacity did not reduce total travel time because the added battery weight increased charging time.
Case studies: In Study 2, energy consumption increased with uncertainty, while the proposed approach’s advantage over the benchmark diminished at high uncertainty because the benchmark recharged more frequently.

D. Numerical Analyses

Numerical simulations assessed approximation quality, computational scalability, recharging-energy savings, and extensions to multiple UAVs and mobile charging stations.

Scalability and approximation: As the number of vertices increased, Alg. 3’s empirical approximation ratio improved toward near-optimality and exceeded its theoretical worst-case guarantee in average-case simulations.Fig. 14a reports results over 10 runs at a 95% confidence interval.
Scalability and approximation: For instances with up to 200 vertices, measured planner running time remained under 30 seconds.The implementation used Python 3 on an Intel i9-9900k CPU, and the authors note that C++ could reduce runtime further.
Recharging optimization: Recharging optimization produced more substantial energy savings on small-scale instances, where partial recharges were relatively more prominent.
Extensions: For multiple UAVs with non-shared charging stations, the extended MILP can handle sufficiently large instances but may produce arbitrarily worse objective values because it lacks time representation and allows each station to be used only once.
Extensions: The paper identifies mobile charging stations as a future extension requiring optimization of rover quantity and routing.The proposed mobile platform uses an autonomous tethered rover with a robotic arm carrying an inductive charging pad.

A. Details of Test Drones

The formulation represents drone tours, charging, energy, and flow constraints through a mixed-integer linear program, with an extension for multiple UAVs and non-shared charging stations.

Mixed-integer formulation: The SDFP formulation uses integer edge variables, energy levels, flow variables, and battery-capacity parameters to represent feasible drone tours.The graph includes target sites, charging stations, and the base.
Mixed-integer formulation: Constraints balance vertex degrees, enforce one visit per site, conserve flow, and capture flight-energy requirements using a sufficiently large constant M.
Multiple-UAV extension: The multiple-UAV extension assumes non-shared charging stations and restricts each charging station to a single use, producing disjoint tours.
Multiple-UAV extension: The scalability simulation varied the number of UAVs and total vertices from 20 to 100, and average tour cost per UAV decreased as fleet size grew.
Multiple-UAV extension: In the two-drone illustration, the solution assigned routes [S,1,2,3,S] and [S,4,S], left the charging station unused, and maintained the 40% minimum permissible SoC.

D. Proofs

The proof section states a bound relating optimal mission duration to flight distance and charging time.

Proofs: Lemma 1 bounds the optimal mission duration between expressions involving flight distance d(F), charging contribution c′, and constants c and c′.

where either

This section develops feasibility and optimality arguments for flight plans, including charging adjustments, algorithmic guarantees, and a multi-UAV simulation and performance evaluation.

where either: The multi-UAV evaluation reports computational time across 30 runs at a 99% confidence interval and average tour cost per UAV as the number of vertices grows.A separate two-drone simulation traces the UAV trajectories in the real-world experiment scenario.
where either: The charging proof analyzes station visits sequentially and shows that feasibility requires B_k ≥ B for each intervening segment.It considers whether the final charging constraint is tight and reduces charging variables when slack remains.
where either: The objective analysis separates plans with zero charging variables from plans requiring charging, yielding distinct objective expressions for the two cases.The proof identifies the zero-charging case as τ(F) = c_a d(F) before treating the charging case separately.
where either: The analysis shows that a feasible flight mission plan can be transformed into another feasible plan in O(|V|) time using charging adjustments.Lemma 2 and its proof connect this transformation to the Fix-charge procedure and Lemma 1.
where either: Theorem 1 establishes a guarantee for the flight plan returned by Find-plan by comparing it with an optimal plan and combining several lemmas.The proof relates DFP and SDFP solutions and invokes Lemmas 2 and 3 together with the definition of bd(·, ·).