1

arXiv:1703.10049v2 [cs.RO] 12 Sep 2017

Autonomous Recharging and Flight Mission Planning for
Battery-operated Autonomous Drones
CHIEN-MING TSENG, Masdar Institute
CHI-KIN CHAU, Masdar Institute
KHALED ELBASSIONI, Masdar Institute
MAJID KHONJI, Masdar Institute
Autonomous drones (also known as unmanned aerial vehicles) are increasingly popular for diverse
applications of light-weight delivery and as substitutions of manned operations in remote locations. The
computing systems for drones are becoming a new venue for research in cyber-physical systems. Autonomous
drones require integrated intelligent decision systems to control and manage their flight missions in the
absence of human operators. One of the most crucial aspects of drone mission control and management is
related to the optimization of battery lifetime. Typical drones are powered by on-board batteries, with limited
capacity. But drones are expected to carry out long missions. Thus, a fully automated management system that
can optimize the operations of battery-operated autonomous drones to extend their operation time is highly
desirable. This paper presents several contributions to automated management systems for battery-operated
drones: (1) We conduct empirical studies to model the battery performance of drones, considering various
flight scenarios. (2) We study a joint problem of flight mission planning and recharging optimization for drones
with an objective to complete a tour mission for a set of sites of interest in the shortest time. This problem
captures diverse applications of delivery and remote operations by drones. (3) We present algorithms for
solving the problem of flight mission planning and recharging optimization. We implemented our algorithms
in a drone management system, which supports real-time flight path tracking and re-computation in dynamic
environments. We evaluated the results of our algorithms using data from empirical studies. (4) To allow fully
autonomous recharging of drones, we also develop a robotic charging system prototype that can recharge
drones autonomously by our drone management system. Overall, we present a comprehensive study on flight
mission planning of battery-operated autonomous drones, considering autonomous recharging.
CCS Concepts: •Computer systems organization →Embedded and cyber-physical systems; •Computing
methodologies →Robotic planning; •Theory of computation →Dynamic graph algorithms;
Additional Key Words and Phrases: Autonomous Drones, Flight Mission Planning, Recharging Optimization,
Automated Drone Management
ACM Reference format:
Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji. 2017. Autonomous Recharging and
Flight Mission Planning for Battery-operated Autonomous Drones. 1, 1, Article 1 (January 2017), 25 pages.
DOI: xx.xxxx/xxxxxxx.xxxxxxx

1

INTRODUCTION

Aerial vehicles are becoming a novel means of logistics. Often referred as drones in popular
terminology, or unmanned aerial vehicles in technical terminology, they have several advantages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee
provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and
the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored.
Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires
prior specific permission and/or a fee. Request permissions from permissions@acm.org.
© 2017 ACM. XXXX-XXXX/2017/1-ART1 $15.00
DOI: xx.xxxx/xxxxxxx.xxxxxxx

, Vol. 1, No. 1, Article 1. Publication date: January 2017.

1:2

Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji

over ground based transportations. (1) Agility: There is little restriction in the sky, unlike on
the ground with obstacles. Drones can travel across space in straight paths. They are usually
small in size, with nimble navigating ability. (2) Swiftness: Aerial transportation is usually not
hampered by traffic congestions. The time to arrival is mostly reflected by the travelled distance.
Drones can also be rapidly launched by catapults, and drop off payloads by parachutes with short
response time. (3) Energy-efficiency: Drones are typically light-weight, which consume less energy.
They are particularly energy-efficient for transporting light-weight items in short trips, whereas
ground vehicles are useful for carrying heavier objects in long distance. (4) Safeness: There is no
on-board human operator or driver. Drones can keep a safe distance from human users. Unmanned
transportation missions are specially desirable in hazardous environments.
These advantages of drones enable diverse applications for light-weight goods transportation and
as substitutions of manned operations in remote locations. There are several notable applications of
drones. (1) Remote Surveillance: Aerial transportation can access far-away remote regions, and geographically dispersed offshore locations. Particularly, oil and gas companies and utility providers,
which rely on extensive surveillance, measurements, mapping and surveying, maintenance operations for dispersed facilities, will be major users of drones. (2) Search and Rescue: Drones can be
deployed in ad hoc manner. In emergency with damaged or unreliable infrastructure, drones can
overcome the difficulty of accessing in isolated regions, enabling fast transportation with great
convenience and flexibility. (3) Hazardous Missions: Drones are excellent solutions for unmanned
missions in risky or hazardous areas, in particular, for taking measurements in high-altitude, or
bio/chemical harmful environments. Human supervisors can remotely control the drones to carry
out dangerous operations. (4) Light-weight Items Delivery: Parcels, medical items, and mail require
speedy delivery. Drones are effective in solving the last-leg problem of the distribution chain from
depots to homes of end-users. A recent study by Amazon [13] reports that 44% of the US population
are within 20 miles from its depot facility. Hence, it is practical to employ drones for delivery.
Therefore, in the near future, fully autonomous drones are expected for extensive deployment,
giving rise to a new class of intelligent systems for logistics. Hence, the computing systems for
drones are becoming an exciting new venue for research in cyber-physical systems. Autonomous
drones require integrated intelligent decision systems to control and manage their flight missions
in the absence of human operators. Despite increasingly popular applications of drones in diverse
sectors, the operations of drones are plagued with several challenges:
• Limited Battery Lifetime: Typical drones are electric vehicles, powered by on-board batteries.
Hence, the performance of drones is critically constrained by limited battery lifetime. Many
drones are only suitable for short-range trips, which considerably limit their applicability.
To optimize the battery performance of drones, there requires an intelligent management
system to track the real-time state-of-charge, and optimize the operations accordingly.
• Dynamic Operating Environments: Drones are expected to travel in certain high altitude,
and hence are significantly susceptible by wind and weather conditions. These conditions
are highly dynamic, and should be accounted for in a real-time manner. Also, drones are
light-weight, and the impact by wind is even more substantial. Drone management system
should take explicit consideration of the dynamic uncertain operating environments.
These challenges present unique problems for battery-operated autonomous drones. Since drones
are expected to carry out long missions in dynamic environments, a fully automated management
system that can optimize the operations of battery-operated autonomous drones to extend their
operation time is highly desirable.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
1:3
1.1

Our Contributions

To improve the practical usefulness of autonomous drones, this paper presents several contributions
to automated management systems for battery-operated drones:
(1) We conduct empirical studies to model the power consumption of drones, considering
various flight scenarios. Accurate model of battery performance in different scenarios
allows further flight mission planning and recharging optimization for drones.
(2) We study a joint problem of flight mission planning and recharging optimization for drones,
using the calibrated power consumption model of a drone, with an objective to complete a
tour mission for a set of sites of interest in the shortest time. We also consider uncertainty in
dynamic environments, such as wind conditions. This problem captures diverse applications
of delivery and remote operations by drones.
(3) We present algorithms for solving the problem of flight mission planning and recharging
optimization. We implemented our algorithms in a drone management system, which
supports real-time flight path tracking and re-computation in dynamic environments. We
evaluated the results of our algorithms using data from empirical studies.
(4) To allow fully autonomous recharging of drones, we also develop a robotic charging station
prototype that can recharge drones autonomously by our drone management system.
Autonomous recharging can significantly extend the battery lifetime of drones for longdistance missions.
2

RELATED WORK

There are diverse applications for drones, including delivery (e.g., for light-weight parcels, medical
items, mail) and remote operations (e.g., wildlife surveillance, environmental surveying, search and
rescue operations). Drones had been often studied for their flight and landing control mechanisms.
For example, see the books [18, 19] for a good overview of the recent results. There are two
aspects of literature about drones: 1) low-level transient control of flight operations, for example,
controlling propellers and balance using PID controllers [3, 4], and 2) high-level planning and
management of drone missions, for example, obstacle avoidance, localization and mapping and
path planning [20]. However, the high-level studies typically focus on a single short-distance flight
paths. Long-distance flight mission planning involving multiple trips and recharging optimization
has been considered to a lesser extent, to the best of our knowledge. Moreover, there is a lack of
prior work on flight mission optimization particularly considering battery-operated drones.
Most drones are aerial electric vehicles. The prior studies of logistic optimization mainly focus
on ground electric vehicles, not on aerial electric vehicles. Nonetheless, drones exhibit different
characteristics that create some unique challenges. For example, the impact of wind is more
substantial for drone flight. In [12], graph signal sampling and recovery techniques are used to plan
routes for autonomous aerial vehicles, and a method is proposed to plan an energy-efficient flight
trajectory by considering the influences of wind. Further, there appears limited empirical studies of
battery performance of drones, although the empirical studies of ground electric vehicles have been
explored in the literature. Modelling and predicting electric vehicle power consumption has been
the subject of a number of research papers. One method is the model-based whitebox approach,
based on specific vehicle dynamics model to understand the consumption behavior of electric
vehicles [16]. The power consumption estimation can also be obtained by a blackbox approach. For
example, a general statistical approach using regression model, without vehicle dynamics model,
can estimate the power consumption of vehicles [5]. Blackbox model is more tractable and more
convenient for trip optimization. Hence, we will employ a similar blackbox model for aerial electric
vehicles, but taking into account the flight conditions.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

1:4

Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji

This work is related to the trip planning problem of electric vehicles [17]. There are recent
results for path planning of electric vehicles considering recharging operations [6]. We adopt the
solution proposed in [15] for the so-called tour gas station problem, for which efficient algorithms
are designed for obtaining a near-optimal solution under certain assumptions. A variant of the
classical algorithm [7] for the travelling salesman problem (TSP) was proposed in [15] for the
tour gas station problem. In this work, we extend those methods to solve the problem for drone
management by incorporating extensions to the settings of drone operations.
For fully autonomous drone management, drones should also be able to recharge themselves
without manual intervention. Inductive charging for drones has been proposed that can flexibly
recharge drones in an autonomous manner [2]. However, this work relies on a different solution,
with a combination of a robotic arm that can accommodate drone recharging in arbitrary positions.
To enable autonomous recharging of drones, an autonomous inductive charging system is initially
proposed in [14], which is integrated with the management system of this paper.
3

EMPIRICAL STUDIES OF BATTERY PERFORMANCE OF DRONES

In order to accurately optimize the power consumption and flight missions of drones, we first
conducted a series of empirical studies to determine the battery performance of drones, considering
various flight scenarios. In particular, we evaluate the power consumption using two commercial
drone models, 3DR Solo [1] and DJI Matrice 100 [8] (see Fig. 1 and their specifications in Table 1).
Both drones support developer kits, which allow us to extract data and program the flight paths.
After gathering sufficient measurement data, we can apply regression models to capture the power
consumption behavior of the drones.

Fig. 1. Left: 3DR Solo. Right: DJI Matrice 100.

Weight
Dimensions
Battery
Battery Weight
Motors
Max Speed
Max Altitude
Charging Duration
Software

3DR Solo
2 kg
25cm × 46cm
5200 mAh 14.8V
500 g
880 kV (×4)
20 km/h
122 ft (FAA Regulation)
90 mins
Python Developer Kit

DJI Matrice 100
2.8 kg
46cm × 46cm
5700 mAh 22.8V
600 g
350 kV (×4)
60 km/h
122 ft (FAA Regulation)
180 mins
DJI SDK & ROS

Table 1. Specifications of 3DR Solo and DJI Matrice 100 drones.

, Vol. 1, No. 1, Article 1. Publication date: January 2017.

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
1:5
3.1

Settings of Empirical Studies

A typical drone is equipped with a number of sensors for two main purposes: (1) for self-stabilizing
the drone in the air, and (2) for remotely tracking the drone status (e.g., the battery state-ofcharge (SoC)). The stability of a drone is controlled by three essential sensors (i.e., gyroscopes,
accelerometers and barometers), with which it can maneuver itself in the air. The SoC is measured
by the voltage and current sensors. A major part of power consumption of a drone is due to
the powering of motors to lift itself in the air. Additional power consumption is required for the
movements of the drone. The movements can be decomposed into vertical and horizontal directions.
The barometer and GPS sensors can measure the 3-dimensional movements of a drone. The speed
and position of a drone can be tracked by GPS and IMU modules, which also enable automatic
navigation. The altitude of a drone can be tracked by barometer and GPS modules.
To understand the factors that determine the power consumption of a drone, we carried out the
following experiments for obtaining empirical data in the rural areas, where the drone can fly in a
straight path without obstacles:
(1) Impact of Motion: The motions of a drone can be divided into three types: hovering,
horizontal moving and vertical moving. We study the power consumption of a test drone
in each motion type.
(2) Impact of Weight: Typical drones can carry extra payloads, such as camera equipment or
parcels. We study the impact of different weights of payloads attached to a test drone.
(3) Impact of Wind: The major environmental factor that affects the drone is wind, including
wind direction and speed. Wind may benefit the power consumption in some cases, as well
as incurring resistance to the movement in other cases. We study the power consumption
of a test drone in various wind conditions.
The experimental results are described as follows.

12
10
8
6
4
2
00

Experiment 1

Experiment 2

Altitude
Speed

50

Experiment 3

Power

480
400
320
240
160
80
4500

Power(W)

Speed (km/h)
Altitude (m)

3.1.1 Impact of Motion. To study the power consumption of motions of a drone, we conducted
three experiments. The battery power, barometer and GPS location, and speed data were collected
in each experiment to analyze the performance of test drone 3DR Solo.

100

150

200
250
Time (sec)

300

350

400

Fig. 2. Motion and battery power consumption of test drone 3DR Solo.

Fig. 2 depicts the recorded data traces of the three experiments of test drone 3DR Solo. We
discuss several observations as follows:
• Experiment 1: The test drone hovered in the air without any movement in this experiment.
Note that the drone may slightly drift around the takeoff location due to deviation error of
GPS modules. We filter the speed data that is smaller than 0.5 m/s. This experiment shows
the baseline power consumption of a flying drone. From the recorded data, we observe that
the drone can maintain a sufficiently steady flying altitude with steady power consumption.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

1:6

Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji
• Experiment 2: The test drone ascended and descended repeatedly in this experiment. The
barometer data shows the altitude of the drone. The time series data allow us to compute
the vertical acceleration and speed of the drone. We observe larger power fluctuations due
to repeatedly vertical movements. Power consumption increases slightly, when the drone
ascends steady.
• Experiment 3: The test drone moved horizontally without altering its altitude in this experiment. The GPS data comprises of speed and course angle of the drone. We also gathered
average wind speed and direction using a wind speed meter during the experiment. We
observe smaller power fluctuations due to horizontal movements. We also measure idle
power consumption of the drone between the two experiments.

25
20
15
10
5
00

Weight: 0g
Altitude

50

Weight: 250g
Speed

100

Weight: 500g

150
200
Time (sec)

500
400
300
200
100
0

Power(W)

Speed (km/h)
Altitude (m)

3.1.2 Impact of Weights. One of the practical purposes of drones is to deliver payloads, and
hence, the total weight of a drone varies as the payload it carries. We carried out several experiments
with different weights of payloads on the test drone 3DR Solo to obtain empirical data. Three
different weights were tested on the drone. The drone was set to hover in the air without any
movement to obtain the corresponding baseline power consumption.

250

300

Fig. 3. Battery power consumption of test drone 3DR Solo with different payload weights.

Fig. 3 depicts the battery power consumption of the test drone carrying three different weights.
We observe that power consumption increases almost linearly when the weight of payload increases.
The weight limit of payload depends on the thrusts that the motors can produce. Note that the
maximum payload weight is 500g for 3DR Solo.
3.1.3 Impact of Wind. Wind condition is a major environmental factor to affect the power
consumption of test drone 3DR Solo. We conducted several experiments under different wind
conditions: headwind by flying against the direction of wind, and tailwind by flying along the
direction of wind. The experiments were carried out at the same location but on different days with
different wind conditions. The wind directions and average speeds were measured using a wind
speed meter for each experiment. Once the wind direction was determined, the drone was set to fly
into a headwind or tailwind at maximum speed (18 km/h).
Fig. 4 depicts the battery power consumption of the drone under different wind conditions. We
observe smaller power consumption when flying into headwind, which is due to the increasing
thrust by translational lift, when the drone moves from hovering to forward flight. When flying
into a headwind, translational lift increases due to the relative airflow over the propellers increases,
resulting in less power consumption to hover the drone [11]. However, when the wind speed
exceeds a certain limit, the aerodynamic drag may outweigh the benefit of translational lift. In our
setting, the drone speed is relatively slow, even at maximum speed. Hence, flying into a headwind
is likely more energy-efficient.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
1:7

Power (W)

300

Headwind

Tailwind

250
200
1500

10

20

30
Time (sec)

40

Wind: 14.4 km/h
Wind: 18.7 km/h
Wind: 22.0 km/h
Wind: 28.8 km/h
50

60

Fig. 4. Battery power consumption of test drone 3DR Solo under different wind conditions.

3.2

Regression Model of Power Consumption for Drone

Since drones are aerial electric vehicles, we can apply the methodology from the literature of
general electric vehicles to model the power consumption of a drone. There are two main types of
power consumption models of a drone:
• White-box Model: A straightforward approach is to employ a white-box microscopic
behavior model for each drone that comprehensively characterizes the motor performance,
aerodynamic environment, and battery systems. However, such a white-box model requires
a large amount of data for calibration and detailed knowledge specific to a particular drone.
For example, the aerodynamic parameters such as propeller efficiencies, motor efficiencies
and drag coefficients are difficult to obtain accurately without resorting to sophisticated
experimental setups like wind tunnel.
• Blackbox Model: A blackbox approach is more desirable, because it requires minimal
knowledge of vehicle model with only a small set of measurable variables and parameters of
the drone. In the subsequent sections, a blackbox model of power consumption of a drone
will be utilized for flight mission planning and recharging optimization. The advantage of
blackbox model is that it is obtained from simple data measurements without relying on
sophisticated experimental setups.
This section describes a general multivariate blackbox model of power consumption for a drone
that has been used extensively in the literature of electric vehicles [5, 9, 10, 21, 22], which will be
verified in the later empirical studies.
Let the estimated battery power consumption of a drone be P̂, which is estimated by a number
of measurement parameters in the following linear equation:
β 1  T
 
P̂ = β 2 
β 3 
 

 kv®xy k  β 4  T

  
 ka®xy k  + β 5 

  
 kv®xy k ka®xy k  β 6 

  

 kv®z k  β 7  T

  
 ka®z k  + β 8 

  
 kv®z k ka®z k  β 9 

  

 m



v®xy · w® xy 




1



(1)

where
• v®xy and a®xy are the speed and acceleration vectors describing the horizontal movement of
the drone.
• v®z and a®z are the speed and acceleration vectors describing the vertical movement of the
drone.
• m is the weight of payload.
• w® xy is the vector of wind movement in the horizontal surface.
• β 1 , ..., β 9 are the coefficients, and kv®k denotes the magnitude of a vector.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

1:8

Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji

The coefficients β 1 , ..., β 9 can be estimated by the standard regression method, if sufficient measurement data is collected.
Assuming the uniform conditions (e.g., speed, wind) within a period of duration D, the total
energy consumption of the drone in duration D is estimated by P̂ · D.
3.3

Evaluation of Power Consumption Model

To evaluate the accuracy of the power consumption model, we conducted experiments to collect
extensive empirical data to estimate the corresponding coefficients. Two test drones (3DR Solo and
DJI Matrice 100) were used in two sets of experiments. A test drone was programmed to first fly
vertical movements, then flying into a headwind and a tailwind with different weights of payloads.
The drone maintained its altitude during the horizontal flight. We conducted experiments under
simple conditions, where the drone ascended from the source until reaching the desired altitude
and then flied directly to the destination without changing its altitude. But the experiments are
sufficiently representative of other conditions.
The following are the estimated coefficients of power consumption models for 3DR Solo and DJI
Matrice 100:
• 3DR Solo:
P̂solo

−1.526 T


=  3.934 
 0.968 



 kv®xy k   18.125  T

 

 ka®xy k  +  96.613 

 

 kv®xy k ka®xy k  −1.085

 


 kv®z k  0.220 T

 

 ka®z k  + 1.332

 

 kv®z k ka®z k  433.9

 


 m



v®xy · w® xy 




1



(2)

• DJI Matrice 100:

P̂ dji

−2.595 T


=  0.116 
 0.824 



 kv®xy k  18.321 T

 

 ka®xy k  + 31.745

 

 kv®xy k ka®xy k  13.282

 


 kv®z k  0.197 T

 

 ka®z k  +  1.43 

 

 kv®z k ka®z k  251.7

 


 m



v®xy · w® xy 




1



(3)

We discussed the evaluation results of the test two drones using ground truth power consumption
data. Fig. 5-7 present the results for 3DR Solo, whereas Fig. 8-10 present the results for DJI Matrice
100. Fig. 5 and Fig. 8 depict the collected sensor data of our experiments for 3DR Solo and DJI
Matrice 100, respectively. We tested 3 different weights of payloads under similar flight paths
operations in each set of experiments. We obtain the estimated power consumption using the
respective regression model, and compare it to the ground truth power consumption data shown
in Fig. 6 and Fig. 9. We observe that the estimation is close to the actual measurement data. We
integrate power over time to obtain the power consumption of the drone in Fig. 7 and Fig. 10. The
errors of estimation of power consumption in the experiments are within 0.4%, showing relatively
good accuracy of our power consumption models for both test drones.
4

FLIGHT MISSION PLANNING AND RECHARGING OPTIMIZATION

In this section, we utilize the calibrated power consumption model of a drone from the last section
to study a joint problem of flight mission planning and recharging optimization for battery-operated
autonomous drones. The objective is to complete a flight tour mission for a set of sites of interest
in the shortest time. We consider a variable number of charging stations to allow recharging of
drones intermediately. This problem naturally captures diverse applications of delivery and remote
operations by drones. We provide efficient algorithms to determine the solutions, and implemented
our algorithms in an automated drone management system.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

25
20
15
10
5
00

Weight: 0
Altitude

Weight: 250g
Speed

Weight: 500g

500
400
300
200
100
6000

Power(W)

Speed (km/h)
Altitude (m)

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
1:9

100

200

300

400

500

Power (W)

Fig. 5. Sensor data for the evaluation experiment of test drone 3DR Solo.

500
400
300
200
100
00

Measurement

100

Estimation

200

300

400

500

600

Energy
consumption (Wh)

Fig. 6. Measured and estimated power consumption of test drone 3DR Solo.

40
30
20
10
00

Measurement

100

Estimation

200

300

Time (sec)

400

500

600

25
20
15
10
5
00

Weight: 0
Altitude

Weight: 300g
Speed

Weight: 600g

800
600
400
200
6000

Power(W)

Speed (km/h)
Altitude (m)

Fig. 7. Measured and estimated energy consumption of test drone 3DR Solo.

100

200

300

400

500

Power (W)

Fig. 8. Sensor data for the evaluation experiment of test drone DJI Matrice 100.

800
700
600
500
400
300
200
100
00

Measurement

100

Estimation

200

300

400

500

600

Energy
consumption (Wh)

Fig. 9. Measured and estimated power consumption of test drone DJI Matrice 100.

80
60
40
20
00

Measurement

100

Estimation

200

300
Time (sec)

400

500

600

Fig. 10. Measured and estimated energy consumption of test drone DJI Matrice 100.

, Vol. 1, No. 1, Article 1. Publication date: January 2017.

1:10
4.1

Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji
Model and Formulation

We denote a set of sites of interest by S that a drone needs to visit (e.g., drop-off locations of
parcels, or sites for measurements), and a set of charging station locations by C where a drone
can receive recharging. The base location of a drone is denoted by v 0 . Let V , S ∪ C ∪ {v 0 }. The
problem of drone flight mission planning with recharging is to find a flight mission plan (which is
a tour consisting of locations in S and C), such that the drone can visit all the sites in S, starting
and terminating at v 0 , with an objective of minimizing the total trip time, while maintaining the
state-of-charge (SoC) within the operational range. See an illustration of a flight mission plan with
recharging for a drone in Fig. 11.

Fig. 11. A flight mission plan with recharging for a drone.

Given a pair of locations (u, v), we denote the designated flight path by `(u, v), and the flight time
by τ (u, v). In this paper, we consider a simple flight path, such that the drone first ascends vertically
to a desired altitude, and then travels in a straight path, and finally descends to the destination
vertically. The model can
 be generalized to consider non-straight paths.
Let E `(u, v), τ (u, v) be the required energy consumption for the drone flying along `(u, v)
within flight time τ (u, v). E(·, ·) is an increasing function that maps the combination of flight path
`(u, v) and flight time τ (u, v) to the required amount of energy. E(·, ·) can be estimated by a power
consumption model of a drone. We represent the charging strategy by a function b(·) : C 7→ R that
maps a charging station to an amount energy to be recharged. When recharging its battery at u,
let the incurred charging time be τc (b(u)). Let η c ≤ 1 and η d ≥ 1 be the charging and discharging
efficiency coefficients. If the drone flies to a charging station u ∈ C, it recharges its battery by an
amount of energy denoted by η cb(u). If the drone flies between two sites
 u, v ∈ V , then it consumes
an amount of energy from the battery denoted by η d E `(u, v), τ (u, v) .
We denote a flight mission plan by F , which is a tour starting and terminating at v 0 , consisting
of a sequence of locations in S ∪ C ∪ {v 0 }. Denote k-th location by Fk . We require F1 = F| F | = v 0 .
The objective of flight mission planning is to find a flight mission plan F together with a charging
strategy b(·) that minimizes the total trip time, consisting of the flight time plus the charging time.
Let x k be the SoC when reaching the k-th location Fk in the flight mission plan. We require the
SoC to stay within feasible range [B, B]. The lower bound of SoC, B, ensures sufficient residual
energy for the drone to return to the base, in case of emergency. We set the initial SoC x 0 = B.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
1:11
With the above notations, the drone flight mission planning with recharging problem (DFP) is
mathematically formulated as follows.
(DFP)

min
F,b(·),x

|Õ
F |−1

τ (Fk , Fk +1 ) +

k =1

|F|
Õ

τc (b(Fk ))

(4)

k=1:Fk ∈ C

subject to
F1 = F| F | = v 0

(5)

S ⊆ F ⊆ S ∪ C ∪ {v 0 }




x k−1 − η d E `(Fk , Fk +1 ), τ (Fk , Fk +1 ) , if Fk ∈ S



xk =

x k−1 + η cb(Fk+1 ) − η d E `(Fk , Fk +1 ), τ (Fk , Fk +1 ) , if Fk ∈ C

B ≤ x k ≤ B, x 0 = B

(6)
(7)
(8)

The difficulty of DFP is to balance the flight decisions and charging decisions. On one hand, a
flight mission plan needs to consider the requirement of completing the mission in minimal total
trip time. On the other hand, it needs to be able to reach a charging station, in case of insufficient
battery, as well as minimizing the charging time.
The formulation of DFP can be extended to incorporate a variety of further factors for practical
flight mission plan optimization, such as restrictions of no-fly zones and attitude, and wind speed
forecast information. Users can also specify further goals, such as deadline of completion and
maximum payload weight. An efficient optimization algorithm is required to compute an optimal
flight mission plan to meet the users’ specified goals.
4.2

Case with Uniform Drone Speed and Steady Wind Condition

To provide efficient algorithms for DFP, we first consider a basic setting under some realistic
assumptions. Suppose that the horizontal speed of the drone is a uniform constant under steady
wind condition, which will be relaxed in Sec. 4.3. Then, the flight time τ (u, v) between two sites
u, v ∈ v is proportional to the length of flight path `(u, v), denoted by d(u, v). Our regression
model

of energy consumption for drone in Sec. 3 implies that the function E `(u, v), τ (u, v) is linear in
the distance d(u, v), and the charging time τc (b(u)) is linear in the amount of recharged energy
b(u). Thus, we assume the following linear objective functions:
τ (u, v) = c a d(u, v),
τc (b(u)) = cb b(u),

E `(u, v), τ (u, v) = c f (u, v) · d(u, v),

(9)
(10)

for some constants c a , cb , c f (u, v) > 0. Note that we allow c f (u, v) to be edge-dependent. This can
model non-uniform environment for each `(u, v), for instance, a path experiencing stronger wind
is expected to have a larger constant c f (u, v).
Denote the lower and upper bounds of c f by c f , min(u,v) c f (u, v) and c f , max(u,v) c f (u, v).
In this paper, we consider mostly long-distance trips (e.g., 2-3 km), for which the vertical landing
and take-off operations usually constitute a small part of the whole flight, and consume only a
small percentage of the total energy (e.g., < 1%). For clarity of presentation, we assume that the
energy consumption of landing and take-off operations is implicitly captured by c f (u, v) · d(u, v),
though our results can be easily extended to consider that explicitly.
Í
For convenience of notation, for a flight mission plan (F , b(·)), we write τ (F ) , k| F=1|−1 τ (Fk , Fk +1 )
Í|F |
Í | F |−1
and b(F ) , k =1:F ∈ C τc (b(Fk )). Also, define d(F ) , k=1 d(Fk , Fk +1 ).
k

, Vol. 1, No. 1, Article 1. Publication date: January 2017.

1:12

Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji

Under the aforementioned assumptions, the total charging time τc (b(F )), in an optimal flight
mission plan F , is proportional to the total flight time τ (F ), by the following lemma.
Lemma 4.1. In an optimal flight mission plan (F , b(·)), we have
c · d(F ) + c 0 ≤ τ (F ) + τc (b(F )) ≤ c · d(F ) + c 0
where either
1) c = c = c a and c 0 = 0, or
η
η
2) c = c a + c f cb ηdc , c = c a + c f cb ηdc , and c 0 =

cb
η c (B

− x 0 ).


Proof. See the Appendix.

Lemma 4.2. Given any feasible flight mission plan (F , b(·)), there is another feasible flight mission
plan (F , b 0(·)) such that
B − x0 c f ηd
τc (b(F )) ≤
+
· d(F )
ηc
ηc
Such a plan (F , b 0(·)) can be found in O(|V |) time.


Proof. See the Appendix.

Both Lemma 4.1 and Lemma 4.2 allow us to focus on minimizing the distance d(F ) instead of
total trip time. Hence, we simplify the problem DFP as a simplified formulation (SDFP), such that
its optimal solution is later shown to be within a constant factor with an optimal solution of DFP.
Simplified formulation (SDFP) is defined as follows.
(SDFP)

min
F,x

|Õ
F |−1

db Fk , Fk +1



(11)

k =1

subject to F1 = F| F | = v 0
S ⊆ F ⊆ S ∪ C ∪ {v 0 }

b k , Fk+1 ),
x
− η dd(F
x k = k −1
B, if Fk ∈ C
B ≤ x k ≤ B, x 0 = B

(12)
(13)
if Fk ∈ S

(14)
(15)

b ·), which is defined as follows. Recall
In SDFP, we consider a modified distance function d(·,

that V , S ∪ C ∪ {v 0 }. Consider a weighted undirected graph G 0 = (V , V2 ), whose edge lengths
b v)}u,v , which are the pairwise shortest
are defined by {c f (u, v) · d(u, v)}u,v . Then, obtain {d(u,
distances of each pair of nodes in G 0 . SDFP is related to the tour gas station problem in [15], which
optimizes a tour trip of a vehicle in minimal fuel cost, with options of refilling at given gas stations.
Note that we assume in the formulation of SDFP that the SoC is brought to its maximum at
each charging station. Once we obtain a tour under this assumption, it can be turned into a flight
mission plan with the minimal charging requirements using Lemma 4.2.
b v) be the distance to the nearest charging station from v, and
For u ∈ V , let dbu , minv ∈ C d(u,
b
su , argminv ∈ C d(u, v) be the nearest charging station from v.
B−B

Define U , ηd . Following [15], we make a mild assumption that for every u ∈ S \ {v 0 } there
is v ∈ C such that d(u, v) ≤ α U2 , where α ∈ [0, 1). This assumption can be justified (for α = 1) as
follows. For a location u ∈ S \ {v 0 }, if every v ∈ C is at distance greater than U2 , then it is infeasible
to visit u without incurring the battery level below B (as the SoC drops below B − η dU = B).
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
1:13
In the following,
we present an algorithm to SDFP and then DFP. The main algorithm is


Find-plan V , d , which is a variant of Christofides Algorithm [7] for finding a tour for travelling salesman problem, based on the results in [15]. It finds a minimum spanning tree T , and then
a minimum weight perfect matching M on the odd vertices of T . The edges of T and M define an
Eulerian graph, from which an Eulerian tour F0 can be obtained in linear time. The Eulerian tour
is passed to the procedure Fix-plan for converting it to a feasible flight mission plan F , which
might use a non-optimal charging function b(·). Then, the resulting plan (F , b(·)) is further passed
to procedure Fix-charge for finding the minimal charging requirements

 with respect to the flight
mission plan F . Specifically, the three procedures in Find-plan V , d are:


b u, v : This provides a lower bound for an optimal solution. Namely,
• Init-distances V , d,
e v), and the
it finds for every pair of locations u, v ∈ V , the minimum possible distance d(u,
corresponding shortest path P(u, v) to go from u to v without going out of the operational
b v) ≤ U − dbu − dbv then the drone can always go directly
range of the battery. Note that if d(u,
1
from u to v . Otherwise, at best (in an optimal solution), the drone can reach u with SoC
at most B − η ddbu , then it can visits a sequence of charging stations (only if the distance
db between two successive such stations is at most U ), then, form the last station, it has
to reach v such that the SoC at v is at least B + η ddbv (so that there is sufficient battery to
reach sv ). In particular, the distance from u to the first charging station on this path should
be at most U − dbu . Similarly, the distance from the last station on the path to v should be
at most U − dbv . This explains the definition of the graph G in line 5 of the procedure.
• Fix-plan G, F0 : starting from the flight mission plan F0 obtained using the (modified)
e this procedure reconstructs a feasible
Christofides algorithm with respect to the weights d,
flight mission plan F for problem (SDFP). It first replaces each edge (u, v) in the flight
mission plan by the corresponding path P(u, v). Since the resulting flight mission plan
maybe still infeasible, the procedure adds to every site a round trip to the closest charging
station. Finally, the added stations are dropped one by one in a greedy way as long as
feasibility ismaintained.

• Fix-charge F , b(·) : Starting from the flight mission plan (F , b(·)) constructed after calling


procedure Fix-plan G, F0 , this procedure finds a minimal amount of recharging energy,
according to Lemma 4.2.
Let OPTDFP and OPTSDFP be the optimal solutions of problems (DFP) and (SDFP), respectively.

Lemma 4.3 ([15]). The flight mission plan F returned by algorithm Find-plan V , d] has cost

b ) ≤ 3 1+α OPTSDFP .
d(F
2 1−α

The following theorem establishes that algorithm Find-plan V , d] has an asymptotic constantfactor approximation guarantee for DFP.

Theorem 4.4. The flight mission plan (F , b 0(·)) returned by algorithm Find-plan V , d] has cost
τ (F ) + τc (b(F )) = O(OPTDFP ) + O(1).
Proof. See the Appendix.



is, starting with SoC= B at su , then the drone reaches u with SoC B − η d dbu , and then it flies directly from u to v
causing the SoC to drop to B − η d (dbu + db(u, v)) = B + η d (U − dbu − db(u, v)) ≥ B + η d dbv at v. Thus, there is sufficient
battery at v to reach sv .

1 That

, Vol. 1, No. 1, Article 1. Publication date: January 2017.

1:14

Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji



Algorithm 1 Find-plan V , d
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

b v)}u,v on weighted undirected graph G 0 = (V ,
Compute pairwise shortest distances {d(u,
for each u, v ∈ V do


e v), P(u, v)) ← Init-distances V , d,
b u, v
(d(u,
end for

e where E = V
Consider the weighted undirected graph G = (V , E; d)
2
Find a minimum spanning tree T = (V , ET ) in G
V0 ← find the set of odd degree vertices in T
e
Find a minimum-weight perfect matching M = (V0 , E M ) in the graph (V0 , E; d)
F0 ← find an Eulerian tour in the graph (V , ET ∪ E M )
F ← Fix-plan[G, F0 ]
b 0(·) ← Fix-charge[F , b(·)]
return (F , b 0(·))

V
2 )



b u, v
Algorithm 2 Init-distances V , d,
1:
2:
3:
4:
5:

6:
7:
8:
9:

b v) ≤ U − dbu − dbv then
if d(u,
e v) ← d(u,
b v), P(u, v) ← {(u, v)}
d(u,
e v), P(u, v))
return (d(u,
else
Construct a weighted undirected graph G = (C ∪ {u, v}, E; w) where


b z) ≤ U − dbu Ð {v, z} : z ∈ C, d(v,
b z) ≤ U − dv0 Ð
E , {u, z} : z ∈ C, d(u,

b z 0) ≤ U
{z, z 0 } : z, z 0 ∈ C, d(z,
0
0
b z ) for all z, z 0 ∈ C ∪ {u, v}
and w(z, z ) , d(z,
P(u, v) ← shortest path between u and v in G (with a set of edge lengths {w(u, v)}u,v )
e v) ← length of P(u, v)
d(u,
e v), P(u, v))
return (d(u,
end if



Algorithm 3 Fix-plan G, F0
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

F ←∅
for each (u, v) in F0 do
Add P(u, v) to F
end for
Add to F a set of sub-tours {{(u, su ), (su , u) : u ∈ V }
for u ∈ V do
if F \ {(u, su ), (su , u) is feasible then
F ← F \ {(u, su ), (su , u)}
end if
end for
return F

, Vol. 1, No. 1, Article 1. Publication date: January 2017.

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
1:15


Algorithm 4 Fix-charge F , b(·)
Let Fi 1 , . . . , Fi r be the charging stations, in the order they appear on F
for j = 0, 1, . . . , r do
i j+1
Õ−1
3:
D j = ηd
c f (Fk , Fk +1 )d(Fk , Fk +1 )

1:
2:

k =i j

4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

4.3

end for
for j = 1, . . . , r do
Íj
B j , η c k=1
b(Fi k )
end for
for j = r downto 1 do
j−1
r
Õ
Õ
1
Dk −
Bk )}
b 0(Fi j ) = max{0, (B − x 0 +
ηc
k =0
k =1
if b 0(Fi j ) > 0 then
exit
end if
end for
return b 0(·)

Extensions

The preceding section presents a basic setting of DFP and its efficient algorithms. In reality, an
automated drone management system requires more sophisticated options. In this section, we
present two extensions to the preceding algorithms to obtain heuristics for more practical scenarios.
4.3.1 Wind Uncertainty. Under steady wind condition, we assume in the preceding algorithms
that c f (u, v) is a constant that depends on the designated path between sites u and v. In practice,
there is sometimes uncertainty in the wind condition. Often, the wind varies as the drone flies.
This also depends on the expected wind condition on this path. Thus, it should be more precisely
represented by c f (u, v, w), where w is the wind vector whose value is in an uncertain domain
w ∈ W . For example, W is defined by the predicted speed range [|w |, |w |] and the predicted
orientation range [θ w , θ w ]. We can modify the algorithms to account for the uncertainty of
W . We proceed conservatively in our algorithm by taking the worst-case, replacing c f (u, v) by
c f (u, v) = maxw ∈W c f (u, v, w).
4.3.2 Variable Drone Speed. We consider another scenario, in which the drone can vary its
speed uniformly at all designated paths in V . In this case, we run our algorithms sequentially in
multiple rounds, with an increasing drone speed at each round, until the algorithms can not return
a feasible solution (because that higher drone speed may result in insufficient battery to reach some
sites). Then we will enumerate all the optimal solutions in all the rounds to find the best solution
with the lowest total flight time. By enumerating the possibilities of different drone speeds, the
algorithms can identify an optimal flight mission plan.
5

CASE STUDIES

We implemented the algorithms in an automated drone management system. In particular, we
evaluated the results of flight mission planning and recharging optimization for the test drones in
several case studies, based on the data from empirical studies.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

1:16
5.1

Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji
Setup

We consider a scenario with four sites of interest, and four charging stations. The drones are
programmed to begin its mission from the base. Fig. 12 depicts the geographical locations of the
sites (as black points), charging stations (as blue squares) and the base (as magenta triangle). The
choices of geographical locations and distances are based on some real locations of a suburban
community.

3.83

Case
1
2
3
2.3
8
4
5
6
3.40
Charging stations 7
8

1.7

1

Uint: km

Base

Sites

9

2.60

2.3

2.78

2.62

Fig. 12. Geographical locations of the sites, charging stations and base.

Drone Battery (Wh) kw® xy k (20 km/h)
Solo
70
South
Solo
70
North-East
Solo
140
South
Solo
140
North-East
DJI
130
South
DJI
130
North-East
DJI
260
South
DJI
260
North-East

m (g)
0
0
500
500
0
0
600
600

Fig. 13. Parameters of setup.

There are two major sets of studies conducted as follows.
(1) Study 1: We study eight sub-cases using the power consumption models of 3DR Solo and
DJI Matrice 100 under different wind and payload conditions. For each drone, we study
4 sub-cases as follows. We consider using one battery in the first two sub-cases of each
drone. Different wind conditions with average wind speed of 18 km/h are studied in the
sub-cases. Then we double the battery capacity with the same wind condition in another
two sub-cases. Since the battery capacity is doubled, extra weight is added to the drone.
The parameters of all the sub-cases are summarized in Table 13.
(2) Study 2: We consider uncertainty of wind conditions. The wind speed and orientation vary
within a certain range. The wind speed varies from 0 to 21 km/h in four discrete scales,
while the wind orientation varies from 0◦ to 360◦ in four discrete scales.
In Study 1, the cases of 3DR Solo are denoted by S1 C1 to S1 C4 , and the cases of DJI Matrice 100 are
denoted by S1 C5 to S1 C8 . Similarly, in Study 2, the cases of 3DR Solo are denoted by S2 C1 to S2 C4 ,
and the cases of DJI Matrice 100 are denoted by S2 C5 to S2 C8 .
5.2

Results and Discussion

For comparison, we also consider a benchmark algorithm, by which a drone flies to the nearest
unvisited site, or the SoC drops below a preset threshold, then the drone flies to a charging station
instead. We set the preset threshold to be the minimum SoC that can fly to a nearest charging
station from any site.
5.2.1 Study 1. The results of flight missions of Study 1 are visualized in Figs. 16-19. The numbers
indicate the path order of the drone. The colors represent the SoC of battery. The wind orientations
are displayed on the upper-left corners. We plot the trip time and energy consumption of Study 1
in Figs. 14-15. There are several interesting observations as follows:
• Our algorithm significantly outperforms the benchmark algorithm, in terms of trip time
and energy consumption. Hence, our algorithms are superior for flight mission planning.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
1:17
• In the case study, the north-east wind affects flight missions to a larger extent, which causes
a higher energy consumption than that by south wind. Besides, there is a longer trip time
due to longer charging time.
• We observe that even the trip times in S1 C7 and S1 C8 are shorter, it consumes more energy
since the drone carrying extra battery, which results in heavier loads.
• Attaching one more battery does not help to reduce the trip time for 3DR Solo, while
attaching more battery helps to reduce trip time for DJI Matrice 100. The reason is because
attaching more battery enables DJI Matrice 100 to fly longer without recharging. The total
trip time is significantly decreased due to much shorter charging time (as the blue bars of
S1 C7 and S1 C8 are shorter). But the same path is not feasible for 3DR Solo. 3DR Solo will
require to charge at the left most charging station, and hence, the trip time increases. If we
slightly increase the battery capacity to 75 Wh, the results of 3DR Solo will be the same as
that of DJI Matrice 100.

400

300

300

200

200

100
0

100
S1 C1

S1 C2

S1 C3

S1 C4

0

Flight time
Benchmark time
Benchmark energy consumption

600

600

500

500

400

400

300

300

200

200

100

100

0

S1 C5

S1 C6

S1 C7

S1 C8

0

Energy consumption (Wh)

Trip time (mins)

400

Charging time
Energy consumption

Trip time (mins)

Flight time
Benchmark time
Benchmark energy consumption
Energy consumption (Wh)

Charging time
Energy consumption

Fig. 14. Trip time and energy consumption of Study 1 Fig. 15. Trip time and energy consumption of Study 1
using 3DR Solo.
using DJI Matrice 100.

5.2.2 Study 2. We study the results of flight mission planning considering uncertainty of wind
condition. We consider two sub-cases with the shortest trip time of two different drones from Study
1 (i.e., S1 C1 and S1 C7 ) and then increase uncertainty level for each case.
The results of flight missions of Study 2 are visualized in Figs. 20-21. We represent the ranges of
wind speeds and orientations as the shaded areas on the upper-left circles. We plot the trip time
and energy consumption of Study 2 in Figs. 22-23. There are several observations as follows:
• Recall that the energy consumption of S1 C1 does not have uncertain wind condition for 3DR
Solo with 70 Wh battery. In Study 2, we investigate if a feasible solution can be obtained in
the presence of uncertainty of wind condition. We gradually increase the uncertainty from
S2 C1 to S2 C4 . For example, in S2 C1 the wind speed varies from 9 to 12 km/h and orientation
varies from -45◦ to 45◦ . In this case, our algorithms always consider the worst-case setting
in the given range of wind conditions.
• We observe that the energy consumption in general increases as the uncertainty of wind
condition increases in Fig. 22. In partcular, the energy consumption of the worst uncertainty
is in S2 C4 , in which the drone may always fly into a tailwind. Thus, S2 C4 provides the most
conservative result.
• Similarly, recall that the energy consumption of S1 C7 does not have uncertain wind condition
for DJI Matrice 100 with 260 Wh battery (two batteries). We also observe similar trends when
the wind uncertainty is increased. In general, when uncertainty increases, the difference
of trip time/energy consumption between our approach and benchmark becomes smaller.
This is because of more frequent recharging when the uncertainty becomes larger.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

1:18

Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji

1

Wind orientation

SoC Wind orientation
100

2

SoC
100

10

11

1
5

3

50

9

6

6

5

4

2

7

7
4

3

8

Base
Sites

10

9

0

Charging stations

0

(a) Case 1.

(b) Case 2.

Wind orientation

SoC Wind orientation
100

1
3

SoC
100

9

1
3

2

4

50

8

5

9

2

4

8

5

7

6

50

8

7

6

0

(c) Case 3.

50

0

(d) Case 4.

Fig. 16. Visualized flight missions for Study 1 using 3DR Solo by our algorithm.
Wind orientation

SoC Wind orientation
100

3

2

SoC
100

1

1

2
3
4

10

4
6

5

50

11

5

9

7

7

6

8

50

10

8

9

0

0

(a) Case 1 benchmark.
Wind orientation

(b) Case 2 benchmark.
SoC Wind orientation
100

3

2

10

4

5

6

7

SoC
100

3

1

50

9

4

9
5

8

1

2

6

50

8
7

0

(c) Case 3 benchmark.

0

(d) Case 4 benchmark.

Fig. 17. Visualized flight missions for Study 1 using 3DR Solo by benchmark algorithm.

, Vol. 1, No. 1, Article 1. Publication date: January 2017.

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
1:19

1

Wind orientation

SoC Wind orientation
100

2

SoC
100

10

11

1
5

3

9

6

50

6

5

4

2

7

7

10

50

8

4

3

8

9

0

0

(a) Case 5.

(b) Case 6.

Wind orientation

SoC Wind orientation
100

SoC
100

1

1

2

2

7
50

3

4

50

4

6

5

7

3

6

5

0

(c) Case 7.

0

(d) Case 8.

Fig. 18. Visualized flight missions for Study 1 using DJI Matrice 100 by our algorithm.
Wind orientation

SoC Wind orientation
100

3

2

SoC
100

1

1

2
3
4

10

4

5

6

50

11

5

9

7

7

6

8

50

10

8

9

0

0

(a) Case 5 benchmark.
Wind orientation

(b) Case 6 benchmark.
SoC Wind orientation
100

SoC
100

3

1

1

2

8

6

50

7
2
5

9

4

3

4

5

6

50

8
7

0

(c) Case 7 benchmark.

0

(d) Case 8 benchmark.

Fig. 19. Visualized flight missions for Study 1 using Matrice 100 by benchmark algorithm.

, Vol. 1, No. 1, Article 1. Publication date: January 2017.

1:20

Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji

Wind uncertainty

SoC Wind uncertainty
100

2
4

1

10
2

50

3

5

4

6

8

7

7

11
50

10
8

9

0

0

(a) Case 1.

(b) Case 2.

Wind uncertainty

SoC Wind uncertainty
100

3

4

2

1

2

1

12
50

5
6

11
9

3

4

50

5

8

SoC
100

12

6

7

1

3

5

9

6

SoC
100

11

7

10

8

9

10

0

0

(c) Case 3.

(d) Case 4.

Fig. 20. Visualized flight missions for Study 2 using 3DR Solo.
Wind uncertainty

SoC Wind uncertainty
100

9

1
3

3

0

(b) Case 6.

Wind uncertainty

SoC Wind uncertainty
100

2
4

7

6

0

(a) Case 5.

1

7

2

50

0

1

10
50

3

9

6

8

(c) Case 7.

4
5

9

6

SoC
100

10

3

5

8

5

7

6

50

2

4

8

5

9

1
50

2

4

SoC
100

7

8

(d) Case 8.

Fig. 21. Visualized flight missions for Study 2 using DJI Matrice 100.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

0

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
1:21

400

300

300

200

200

100
0

100
S1 C1

S2 C1

S2 C2

S2 C3

S2 C4

0

Flight time
Benchmark time
Benchmark energy consumption

800

800

700

700

600

600

500

500

400

400

300

300

200

200

100
0

100
S1 C7

S2 C5

S2 C6

S2 C7

S2 C8

0

Energy consumption (Wh)

Trip time (mins)

400

Charging time
Energy consumption

Trip time (mins)

Flight time
Benchmark time
Benchmark energy consumption
Energy consumption (Wh)

Charging time
Energy consumption

Fig. 22. Trip time and energy consumption of Study Fig. 23. Trip time and energy consumption of Study
2 using 3DR Solo.
2 using DJI Matrice 100.

6

AUTOMATED DRONE MANAGEMENT SYSTEM

We implemented our algorithms in an automated drone management system. The user interface is
depicted in Fig 24. The user interface allows the users to specify individual goals and to visualize
the computed flight mission plan. The system connects to a cloud computing server, which uses
the input locations from the user and computes the optimal flight mission plan. Then the drone is
programmed to follow the flight mission plan computed by the server.
Furthermore, a dynamic tracking system of drone using on-board sensors, including GPS location,
video feed, SoC, and flight status, is utilized to monitor the real-time flight status of the drone. If
abnormal measurements are detected, for example, the reported sensor measurements deviate from
estimated value by flight mission planning, then real-time re-computation will be performed to
find the minimum adjustment to the previously computed flight mission plan. The user can abort
the mission anytime by clicking the button on the system. We remark that multiple drones can
also be tracked simultaneously.

Fig. 24. Interface of automated drone management
system.

7

Fig. 25. Robotic charging system.

AUTONOMOUS ROBOTIC CHARGING SYSTEM PROTOTYPE

In this section, we present a robotic charging system prototype that can recharge drones autonomously by our drone management system. More technical details can be found in [14].
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

1:22

Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji

There is a tethered rover capable of autonomous navigation, equipped with a robotic arm carrying
a charging pad that can adapt to different drone sizes and landing positions (see Fig. 25). Our
robotic rover uses 2D Light Detection and Ranging (LIDAR) sensors to navigate and detect a drone.
LIDAR sensors are more robust to environmental uncertainties and external lighting conditions
than computer vision sensors. The robotic charging system is comprised of three main components:
• Charging system: Since the goal of the charging system is to recharge drones in remote
areas, disconnected from the grid, it is vital to provide self-generating charging system, as
well as to protect the robotic rover from harsh environment conditions (i.e., rain, the wind,
etc.) when idle. So, our prototype can be powered by a solar panel. A landing zone with an
area of at least 3 × 3 m2 is designated for drone landing in front of the charging system.
• Robotic rover: To enable flexible deployment, a tethered rover is equipped with a robotic
arm that mounts a wireless inductive transmitter. Using autonomous drone detection and
navigation, the rover can cater for arbitrary landing position and orientation of a drone,
which is the case for most commercial drones that solely rely on inaccurate GPS and Inertial
Measurement Unit (IMU) for landing.
• Drones: Each drone is equipped with an inductive wireless receiver, compatible with that
of the robotic rover. In order to recharge a drone, the drone management system will send
a signal to the charging system to initiate the charging procedure.
We use Hokuyo UTM-30LX Scanning Laser Rangefinder to obtain 2D point cloud. The laser
rangefinder provides 30 meters detection range which allows the rover to detect far objects such as
drones or obstacles. The detection angle is 270◦ with 0.25◦ angular resolution. The rover odometry
is obtained based on wheel rotation using quadrature encoders.
A retractable arm is used to conduct inductive charging for the drones, which can flexibly
recharge drones in arbitrary positions. The inductive charging technology is based on resonant
inductive coupling, which can transfer energy without physical contact. It has been widely used
in wireless charging for smart phones. The use of inductive charging technology facilitates a
fully automated drone management system, without manually plugging to an external charger.
The current prototype uses six coils for inductive charging, giving a maximum charging speed of
6 × 700 = 3500 mA. We mounted six current sensors, on the robotic arm, to measure individual
coil charging rate. Our test drone is DJI Matrice 100 which is powered by two 5700 mA on-board
Li-Poly battery.
7.1

Recharging Process

We next describe the operations of recharging process. Once a drone is landed and a recharging
command is initiated, the robotic rover proceeds as follows:
(1) Finding the drone: From raw 2D LIDAR point cloud, we use a clustering technique to
separate the points of the drone from the background points.
(2) Classifying the drone and detecting its orientation: Based on supervised learning, drone
information (e.g., type, size, orientation, etc.) can be extracted from point cloud data. We
consider a single drone, and its orientation is detected using a rectangle boundary model.
The orientation of the drone is needed to instruct the rover to navigate to a position that
supports a better alignment for the charging pad with the receiver on the drone. This allows
more flexibility in the charging pad design (e.g., rectangular inductive charging pad instead
of a circular pad) to fit more inductive coils on the drone.
(3) Autonomously navigating towards the drone: the exact position of the navigation goal is
determined based on the allowable charging position.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
1:23
(4) Recharging: Position the charging pad on the drone and adjust the positioning using current
sensors readings.
Once a drone is fully charged, a termination command is initiated to the charging system. Then
the rover returns to the charging system to resume its idle state. Also, the drone management
system actively communicates with the robotic charging system to track the charging status.
8

CONCLUSION

Automated drone management system is important for practical applications of drones. This paper
provides multiple contributions to automated management systems for battery-operated drones,
including empirical studies to model the battery performance of drones considering various flight
scenarios, a study of flight mission planning and recharging optimization for drones that captures
diverse applications of delivery and remote operations by drones, and a management system
implementation with a robotic charging station to support autonomous recharging of drones.
In future work, we will incorporate a variety of further features in our automated drone management system, such as restrictions of no-fly zones and attitude, and wind speed forecast. Users may
also be able to specify further goals, such as deadline of completion and maximum payload weight.
A

PROOFS
Lemma 4.1. In an optimal flight mission plan (F , b(·)), we have
c · d(F ) + c 0 ≤ τ (F ) + τc (b(F )) ≤ c · d(F ) + c 0

where either
1) c = c = c a and c 0 = 0, or
η
η
2) c = c a + c f cb ηdc , c = c a + c f cb ηdc , and c 0 =

cb
η c (B

− x 0 ).

Proof. Consider an optimal flight plan (F , b(·)) and assume that the charging stations, in the
order they appear on F , is Fi 1 , . . . , Fi r , where without loss of generality, we assume Fi 1 , v 0 .
For completeness, let i 0 , 1 and i r +1 , |F |. For j = 0, 1, . . . , r , let
D j , ηd

i jÕ
+1 −1

c f (Fk , Fk +1 ) · d(Fk , Fk +1 ),

k =i j

and for j = 1, . . . , r , let B j , η cb(Fi j ).
Then, the feasibility of the flight mission plan F implies
x0 −

j
Õ
k =0

Dk +

j
Õ

Bk ≥ B, for j = 0, . . . , r

(16)

k=1

Let us refer to Ineq. (16) for a particular j as I (j) ≥ B. Particularly, consider I (r ) ≥ B. Suppose
that this inequality is not tight, that is, the left-hand side is strictly larger than the right-hand
side. Note that the variable b(Fi r ) = Bηrc appears only in this inequality. Since b(Fi r ) appears in the
objective function τc (b(F )) with a positive coefficient (i.e., τc (b(u)) = cb b(u)), there are two cases:
(i) b(Fi r ) = 0 at optimality, if I (r ) > B, or (ii) b(Fi r ) > 0 at optimality, if I (r ) = B. Otherwise, it
will contradict to the optimality of b(Fi r ), by reducing the value of b(Fi r ). If it is case (i), then the
inequality I (r − 1) ≥ B becomes redundant (as I (r − 1) ≥ I (r ) > 0). Removing I (r − 1) ≥ B, we obtain
that the variable b(Fi r −1 ) appears only in I (r ) ≥ B. Similarly, we can conclude that b(Fi r −1 ) = 0 and
remove the (now) redundant inequality I (r − 2) ≥ B.
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

1:24

Chien-Ming Tseng, Chi-Kin Chau, Khaled Elbassioni, and Majid Khonji

Continuing this argument, we conclude that there are two cases: (1) either all variables b(Fi j )
are set to zero in which case the value of the objective is τ (F ) = c a d(F ), or (2) we have
r
r
Õ
Õ
x0 −
Dk +
Bk = B,
k =0

k =1

In case (2), the value of the objective is
r
r
Õ
cb
cb Õ
Bk = τ (F ) + (B − x 0 +
Dk )
τ (F ) +
ηc
ηc
k =1

r
cb Õ
cb
= τ (F ) +
D k + (B − x 0 )
ηc
ηc

k =0

k =0

Therefore,


r
ηd
cb
cb Õ
cb
d(F ) + (B − x 0 ) ≤τ (F ) +
D k + (B − x 0 )
c a + c f cb
ηc
ηc
ηc
ηc
k =0


ηd
cb
≤ c a + c f cb
d(F ) + (B − x 0 ).
ηc
ηc

Lemma 4.2. Given any feasible flight mission plan (F , b(·)), there is another feasible flight mission
plan (F , b 0(·)) such that
B − x0 c f ηd
τc (b(F )) ≤
+
· d(F )
ηc
ηc
Such a plan (F , b 0(·)) can be found in O(|V |) time.
Proof. The proof follows from Lemma 4.1, which uses algorithm Fix-charge to implement the
argument used in Lemma 4.1 to find a feasible fight mission plan.


0
Theorem 4.4. The flight plan (F , b (·)) returned by algorithm Find-plan V , d] has cost
τ (F ) + τc (b(F )) = O(OPTDFP ) + O(1).
Proof. Let (F ∗ , b ∗ (·)) be an optimal flight plan for (DFP). Clearly, this plan can be trivially
turned into a feasible solution (F ∗ , x) for (SDFP) by setting x k = B for all Fk ∈ C. It follows that
b ∗ ).
OPTSDFP ≤ d(F

(17)

On the other hand, Lemma 4.3 implies that


3 1+α
b
d(F ) ≤
OPTSDFP .
2 1−α

(18)

OPTDFP ≥ c · d(F ∗ ) + c 0,

(19)

Lemma 4.1 also implies that
while Lemma 4.2 implies that
b(F ) ≤

B − x0 c f ηd
+
d(F ),
ηc
ηc

(20)

b ·) implies
and the definition of d(·,
b ) and d(F
b ∗ ) ≤ c f d(F ∗ ).
c f d(F ) ≤ d(F
, Vol. 1, No. 1, Article 1. Publication date: January 2017.

(21)

Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
1:25
Putting together (17), (18), (19), (20), and (21), we obtain
τ (F ) + τc (b(F )) = c a d(F ) + cb b(F )


B − x0
ηd
d(F ) + cb
≤ c a + c f cb
ηc
ηc





B − x0
η d OPTDFP − c 0
3 1 + α cf
+ cb
≤
.
c a + c f cb
2 1 − α cf
ηc
c
ηc

REFERENCES
[1] 3DR Solo. 2017. https://3dr.com/solo-drone/specs/. (2017). [Online; accessed 19-Sept-2017].
How wireless power charging could recharge a flying drone.
http://www.bbc.com/news/
[2] BBC. 2016.
technology-37821459
[3] S. Bouabdallah, A. Noth, and R. Siegwart. 2004. PID vs LQ control techniques applied to an indoor micro quadrotor. In
International Conference on Intelligent Robots and Systems (IROS).
[4] Endri Bregu, Nicola Casamassima, Luca Mottola, and Kamin Whitehouse. 2016. Reactive Control of Autonomous
Drones. In ACM Mobile Systems, Applications, and Services (Mobisys).
[5] Alesaandn Cappiello, Ismail Chabini, Edward K. Nam, Alessandro Lue, and Maya Abou Zed. 2002. A Statistical Model
of Vehicle Emissions and Fuel Consumption. In IEEE Intelligent Transportation Systems Conf.
[6] Chi-Kin Chau, Khaled Elbassioni, and Chien-Ming Tseng. 2017. Drive Mode Optimization and Tour Planning for
Plug-in Hybrid Electric Vehicles. to be published in IEEE Trans. Intell. Transp. Syst. (2017).
[7] Nicos Christofides. 1976. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report.
CMU. Report 388, Graduate School of Industrial Administration.
[8] DJI Matrice 100. 2017. https://www.dji.com/matrice100/info. (2017). [Online; accessed 19-Sept-2017].
[9] Raghu K Ganti, Nam Pham, Hossein Ahmadi, Saurabh Nangia, and Tarek F Abdelzaher. 2010. GreenGPS: a participatory
sensing fuel-efficient maps application. In ACM Mobile Systems, Applications, and Services (Mobisys).
[10] Stefan Grubwinkler and Markus Lienkamp. 2013. A modular and dynamic approach to predict the energy consumption
of electric vehicles. In Conf. Future Automotive Technology.
[11] Helicopter Flying Handbook. 2012. . US Federal Aviation Administration.
[12] Tianxi Ji, Siheng Chen, Rohan Varma, and Jelena Kovacevic. 2015. Energy-efficient route planning for autonomous aerial
vehicles based on graph signal recovery. In Annual Allerton Conference on Communication, Control, and Computing.
[13] The Wall Street Journal. 2016. Amazon’s Newest Ambition: Competing Directly With UPS and FedEx. http://www.wsj.
com/articles/amazons-newest-ambitioncompeting-directly-with-ups-and-fedex-1474994758
[14] Majid Khonji, Mohammed Alshehhi, Chien-Ming Tseng, and Chi-Kin Chau. 2017. Autonomous Inductive Charging
System for Battery-operated Electric Drones. In ACM Workshop on Electric Vehicle Systems, Data and Applications
(EV-Sys).
[15] Samir Khuller, Azarakhsh Malekian, , and Julin Mestre. 2011. To fill or not to fill: The gas station problem. ACM
Transactions on Algorithm 7 (2011), 534–545.
[16] Eugene Kim, Jinkyu Lee, and Kang G. Shin. 2013. Real-time prediction of battery power requirements for electric
vehicles. In IEEE/ACM Intl. Conf. on Cyber-Physical Systems.
[17] Mingsong Lv, Nan Guan, Ye Ma, Dong Ji, Erwin Knippel, Xue Liu, and Wang Yi. 2016. Speed Planning for Solar-Powered
Electric Vehicles. In ACM Intl. Conf. on Future Energy Systems (e-Energy).
[18] Kenzo Nonami, Farid Kendoul, Satoshi Suzuki, Wei Wang, and Daisuke Nakazawa (Eds.). 2010. Autonomous Flying
Robots: Unmanned Aerial Vehicles and Micro Aerial Vehicles. Springer Publisher.
[19] Yasmina Bestaoui Sebbane (Ed.). 2015. Smart Autonomous Aircraft: Flight Control and Planning for UAV. CRC Press.
[20] Roland Siegwart, Illah Nourbakhsh, and Davide Scaramuzza. 2015. Introduction to Autonomous Mobile Robots. MIT
Press.
[21] Chien-Ming Tseng and Chi-Kin Chau. 2017. Personalized Prediction of Vehicle Energy Consumption based on
Participatory Sensing. to be published in IEEE Trans. Intell. Transp. Syst. (2017).
[22] Chien-Ming Tseng, Chi-Kin Chau, Sohan Dsouza, and Erik Wilhelm. 2015. A Participatory Sensing Approach for
Personalized Distance-to-Empty Prediction and Green Telematics. In ACM Intl. Conf. Future Energy Systems (e-Energy).

, Vol. 1, No. 1, Article 1. Publication date: January 2017.

