# A Bilevel Optimization Framework For fuel-constrained UAV-UGV Cooperative
Routing: Planning and Experimental Validation

Md Safwan Mondal1, Subramanian Ramasamy1, Pranav Bhounsule1 *This work was
supported by ARO grant W911NF-14-S-003.1Md Safwan Mondal, Subramanian Ramasamy
and Pranav A. Bhounsule are with the Department of Mechanical and Industrial
Engineering, University of Illinois Chicago, IL, 60607 USA<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Fast moving unmanned aerial vehicles (UAVs) are well suited for aerial
surveillance, but are limited by their battery capacity. To increase their
endurance UAVs can be refueled on slow moving unmanned ground vehicles (UGVs).
The cooperative routing of UAV-UGV to survey vast regions within their speed
and fuel constraints is a computationally challenging problem, but can be
simplified with heuristics. Here we present multiple heuristics to enable
feasible and sufficiently optimal solutions to the problem. Using the UAV fuel
limits and the minimum set cover algorithm, the UGV refueling stops are
determined. These refueling stops enable the allocation of mission points to
the UAV and UGV. A standard traveling salesman formulation and a vehicle
routing formulation with time windows, dropped visits, and capacity
constraints is used to solve for the UGV and UAV route, respectively.
Experimental validation of the approach on a small-scale testbed shows the
efficacy of the approach.

##  1 INTRODUCTION

The integration of Unmanned Aerial Vehicles (UAVs) and Unmanned Ground
Vehicles (UGVs) has been increasingly utilized in various applications, such
as search and rescue, surveillance, and reconnaissance missions, and
transportation [1, 2, 3, 4] etc. One of the most significant challenges in
such cooperative routing is the limited fuel capacity of UAVs, which restricts
their operational time and range. However, effective cooperation between UAVs
and UGVs can enhance the mission efficiency and extend the coverage range of
UAVs, thereby enabling them to achieve longer range and persistent operations.
The complexity of such cooperative routing for UAV-UGV systems lies in its
combinatorial nature, making it computationally challenging to solve the
formulation with exact methods. Therefore, suitable heuristics should be used
to achieve high-quality solutions quickly.

In this paper, we propose a bi-level optimization framework for solving the
fuel-constrained UAV-UGV cooperative routing problem that optimizes the
operational time and fuel consumption of both vehicles. To validate our
proposed algorithm, we conducted hardware testing that provides practical
insights into the real-world application and feasibility of our proposed
approach. By maximizing the efficiency of the cooperative system, our
algorithm has the potential to overcome the limitations posed by fuel capacity
and speed constraints, enabling successful implementation of UAV-UGV
cooperative routing in a variety of applications.

###  1-A Related works

(a) given mission scenario with MSC

(b) first subproblem

(c) second subproblem

Figure 1: Minimum set cover algorithm and task allocation technique a) Given
mission scenario with minimum set cover algorithm. Blue circle indicates
radial coverage of UAV. Here, three refuel stops (including starting depot)
can cover entire mission b) First subproblem where UGV moves from starting
depot to first refuel stop and UAV missions points within radial coverage are
assigned. c) Second subproblem where UGV moves from first refuel stop to
second refuel stop and UAV missions points within radial coverage are
assigned.

Fuel-constrained vehicle routing problem of UAVs has been an area of
considerable research. Several studies have investigated the routing of
multiple fuel-constrained UAVs with recharging on fixed depots. Levy et al.
[5] investigated this routing of multiple fuel-constrained UAVs with fixed
recharging depots using variable neighborhood descent (VND) and variable
neighborhood search (VNS) heuristics to find feasible solutions for large
instances. Similarly, Sundar et al. [6] developed a mixed-integer linear
programming model (MILP) that can be solved using an off-the-shelf MILP
solver. Instead of fixed depot, Maini et al. [7] addressed cooperative routing
of a single UAV-UGV system, with the UGV serving as a mobile charging point
for the UAV on a road. Unlike previous studies, the authors developed a greedy
heuristic method to find the rendezvous locations of recharging along the UGV
route. Manyam et al. [8] investigated the cooperative routing problem of a
team comprising a UAV and UGV subject to communication constraints. They
formulated the problem as a mixed-integer linear program (MILP) and developed
a branch-and-cut algorithm to solve the problem optimally.

Researchers extended the UAV-UGV cooperative vehicle routing problem by
solving it in a tiered two-echelon approach. To solve the two-echelon
cooperative routing problem, Luo et al. [9] proposed a binary integer
programming model with two heuristics. Liu et al. [10] developed a two-stage
route based framework to optimize both the truck’s main route and the drone’s
adjoint flying routes for a truck and drone based parcel delivery system. They
created a hybrid heuristic that combined nearest neighbor and cost-cutting
strategies to quickly build a viable solution. In our previous research [11,
12], we explored a hierarchical bi-level optimization framework for
cooperative routing of multiple fuel-constrained UAVs and a single UGV. The
framework employs K-means clustering at the outer level to generate UGV visit
points, which can be connected using the traveling salesman problem (TSP) to
obtain the UGV route. At the inner level, a vehicle routing problem with
capacity constraints, time windows, and dropped visits for the UAV is
formulated and solved using the UGV path. In an extension to our work [13], we
demonstrated that optimizing the heuristics parameters with Genetic Algorithm
(GA) and Bayesian Optimization (BO) methods can lead to a significant
improvement in the quality of the solutions. But the past framework was
scenario specific making it hard to generalize for any unknown scenario, which
was driving force for this study to come up with a robust optimization
framework that can be generalized and implemented experimentally on hardware.
On the experimental front, few significant works have been done to demonstrate
localization and mapping of UAVs in indoor environments. Nigam et al. [14, 15,
16] investigated for high-level scalable control techniques for unmanned
aerial vehicles (UAVs) for performing persistent surveillance in an uncertain
stochastic environment in a hardware testbed. Two UAVs were used by Frew et
al. [17] to demonstrate road following, obstacle avoidance, and convoy
protection in a fligt testing, while Jodeh et al. [18] provided an overview of
cooperative control algorithms of heterogeneous UAVs by the Air Force Research
Laboratories (AFRL). Leahy et al. [19, 20] experimentally validated their
proposed method for automating persistent surveillance missions involving
multiple vehicles. Automata-based techniques were used to generate collision-
free motion plans and vector fields were created for use with a differential
flatness-based controller, allowing vehicle flight and deployment to be fully
automated according to the motion plans. They used charging platforms for the
UAVs for truly persistent missions. Boeing’s Vehicle Swarm Technology
Laboratory (VSTL) [16, 21, 22, 23] and MIT’s RAVEN laboratory [24] testbed
have conducted significant UAV flight testing demonstrations in indoor lab
scale setups.

The novelty of our work lies in the development of a robust bi-level
optimization framework that uses minimum set cover algorithm and a task
allocation technique to solve UAV-UGV cooperative routing in two echelon
fashion. We have validated our proposed methodology with a hardware flight
testing in lab scale experimental setup. To this end, we present following
novel contributions: 1) The overall framework uses bilevel optimization with
task allocation technique for mission allocation and constrained programming
based routing solvers. 2) The task allocation technique based on minimum set
cover algorithm divides the entire problem into decoupled subproblems which
radically simplifies the overall problem. 3) A constraint programming-based
formulation for vehicle routing problem with time windows, dropped visits, and
fuel constraints enables quick solutions of each subproblem. 4) Hardware
validation of our work demonstrates the practical feasibility and real-world
applicability of our proposed algorithms and methods.

###  1-B Problem Description

The aim of the problem is to perform an cooperative mission involves visiting
a set of designated mission points ( see figure 1(a)) $x_{n_{i}}\in
X\equiv\left(x_{i},t_{i}\right)$, using either the UGV road-based visit or the
UAV aerial flyover, where $x_{i}\in R^{2}$ is a position on the ground plane;
$t_{i}$ is the timestamp of the last visit to the node. The cost of travel
between any two mission points is defined as the time required to travel from
one point to another, $c_{ij}=t_{j}-t_{i}$. The UGV ${g_{i}\in
G\equiv(\tau_{i},f_{i},x_{i})}$, and UAV ${a_{i}\in
A\equiv(\tau_{i},f_{i},x_{i})}$, are heterogeneous in nature, with the UAV
having a higher velocity but a lower fuel capacity compared to the UGV. During
the mission, the vehicles are represented by current task or state $\tau_{i}$,
fuel level $f_{i}$ and position $x_{i}$. Unlike UAV, the UGV is restricted to
traveling along the road network, and the fuel consumption rate of both
vehicles is a function of the velocity of the vehicle. The UAV can be
recharged by the UGV at any refueling stop or at the starting depot, with the
recharging time dependent on the fuel level of the UAV. The UGV is assumed to
have an infinite fuel capacity due to its larger fuel capacity compared to the
UAV. With the described assumptions, the objective is to find the quickest
route for the UAV and UGV to visit all mission points together, with the
starting depot being both the starting and ending point, while ensuring that
the UAV never runs out of fuel.

To find the time-optimized route, the following goals must be achieved:

  1. 1.

Identification of suitable stop locations where UAV will synchronize with UGV
to get recharged to cover all the mission points, i.e, $x_{r}\equiv
x_{i}=x_{j}$, here, $x_{i}\in a_{i},x_{j}\in g_{i}$.

  2. 2.

Determination of optimal times during the mission, when UAV, UGV will meet at
those refuel stops i.e, $t_{r}\equiv t_{i}=t_{j}$, here, $t_{i}\in A,t_{j}\in
G$.

  3. 3.

Determination of the optimal routes $\tau_{i}\in A,\ \ \tau_{j}\in G$ for both
the UGV and UAV based on the refueling locations $x_{r}$ and times $t_{r}$.

##  2 OPTIMIZATION FRAMEWORK

For the UAV-UGV cooperative routing, we proposed a bilevel optimization
framework, which is shown in Fig. 2. The framework is designed as a two-level
hierarchical structure, where at the higher level, we determine the UGV route
using the “UGV First, UAV Second” heuristic method, which involves
prioritizing the UGV route and then constructing the UAV route based on it. To
ensure the feasibility of the cooperative route, it is critical to locate
suitable refueling sites along the UGV route. We employed a minimum set cover
algorithm to identify the best locations for refueling. The inner-level UAV
route was built based on the UGV route by dividing the entire scenario into
subproblems what could be solved by modeling them as an energy constrained
vehicle routing problem (E-VRP).

Figure 2: optimization framework

###  2-A Outer level: UGV route

Maini et al. [7] demonstrated that in order to establish a viable cooperative
route, it is necessary to ensure that at least one refueling stop is located
within the UAV fuel coverage radius for each data point. Thus to determine the
minimum number of refueling stops required to cover the entire mission
scenario, we can adopt the minimum set cover algorithm (MSC). This is a well-
established problem that can be solved using a variety of methods, including
greedy heuristics [7]. However, in this study, we proposed a constraint
programming formulation for minimum set cover algorithm. For a same scenario,
we employed both greedy method and constraint programming approach
individually to solve the minimum set cover problem where constraint
programming method outperformed greedy heuristics.

####  2-A1 Greedy heuristics method

Using a greedy heuristic approach can help to reduce the complexity of the
minimum set cover problem. This method starts with the mission scenario points
that require coverage $x_{n}$ and the UAV’s fuel capacity $F$ as the inputs,
as an output we aim of determining the minimum number of mission points that
can serve as refueling stops $x_{r}$ to cover the entire mission points
$x_{n}$. In other words, given a set of mission points
$X=\\{x_{1},x_{2},...,x_{n}\\}$ the goal is to identify a subset
$X_{r}=\\{x_{1},x_{2},...,x_{r}\\}$ that has the least number of elements to
act as refueling stops to cover the entire scenario. The greedy algorithm
selects the initial point as the first refueling stop and then sequentially
adds the mission points that cover the greatest number of other mission points
to the refueling stop set until all points are covered.

Although the greedy heuristic can produce an optimal result for a minimum set
cover problem quickly, there is possibility of multiple optimal solutions for
a given scenario. Since we are implementing a bilevel optimization framework,
it is essential to consider all the other optimal solutions of the outer level
algorithm. As it is not possible to acquire all optimal solutions using the
greedy heuristic, we employed the constraint programming method. This approach
can rapidly generate multiple optimal results, if any are present. Also, the
greedy method may result into locally optimal solution which can be overcome
through an alternate constraint programming formulation of the minimum set
cover problem.

####  2-A2 Constraint programming method

The minimum set cover problem can be transformed into a linear integer
programming model using the constraint programming method (CP method). The
objective function in Eq. 2.1 determines the minimum number of refueling
stops, and the constraint function Eq. 2.2 ensures that each mission point
$x_{i}$ has at least one refueling stop $x_{r}$ assigned to it. The decision
variable $y_{i}$ determines whether a mission point will be selected as a
refueling stop or not. We utilized Google’s OR-Tools™ CP-SAT solver [25] to
solve this linear integer formulation, and it can record multiple optimal
solutions if they exist. After identifying the refueling stop locations, a UGV
route can be created by connecting these stops on the road network. We can
solve a simple travelling salesman problem (TSP), considering the refueling
stops, to determine an optimal UGV route. Once the optimal UGV route is
established, we can proceed to the inner loop UAV routing. Objective,

$\operatorname{min}\sum_{i=1}^{r}y_{i}$ (2.1)

s.t.,

$\sum_{j=1}^{r}y_{j}\geq 1,\forall x_{i},\ i=1,\ldots,n$ (2.2)
$y_{i}\in\\{0,1\\},\forall i=1,\ldots,n$ (2.3)

###  2-B Inner level: UAV route

At the inner level of our framework, we employed a task allocation technique
to divide the entire mission scenario into independent subproblems which were
solved individually as an energy constrained vehicle routing problems (E-VRP).

####  2-B1 Task allocation technique

Given the scenario and the obtained UGV route from outer loop MSC algorithm,
we can divide the entire problem into $n-1$ number of subproblems ($n$ =
number of refuel stops with starting depot) with an assumption that UGV
travels only between two refuel stops in each subproblem. Before the
subproblem division, each mission point is assigned to its nearest refuel stop
(including starting depot) that covers it. In the subproblems, the first
refuel stop is the origin node and the second refuel stop is the destination
node of UGV route. The sub-problems are decoupled from each other by
allocating separate mission points in them. The UAV mission points assigned to
the destination refuel stop under each subproblem are allocated to that
subproblem. Only, for the first subproblem the mission points assigned to both
origin and destination node should be allocated to it.

Figure 1 demonstrate the process of subproblem division and mission
allocation. Figure 1(a) shows refuel stop locations along the UGV route
obtained from outer level MSC algorithm for a given scenario, the first
subproblem (figure 1(b)) is created by taking the starting depot as the origin
node and the refuel stop 1 as the destination node. The UAV mission points
covered by origin node (starting depot) and destination node (refuel stop 1)
are assigned for subproblem 1. Similarly, the second subproblem (figure 1(c))
is created by taking the refuel stop 1 as origin node and refuel stop 2 as
destination node and the mission points covered by the destination node
(refuel stop 2) are assigned for this subproblem. Once we get an independent
set of subproblems through task allocation, we tried to solve each subproblem
by modeling it as energy constrained vehicle routing problem (E-VRP).

####  2-B2 E-VRP model

The formulation of the E-VRP can be described with a graph theory. Consider an
undirected graph $G=(V,E)$ where $V$ is the set of vertices
$V=\\{0,1,2,...k\\}$ and $E$ is the set of edges between the vertices $i$ and
$j$ as $E=\\{(i,j)\,\|\ i,j\,\in\,V,i\neq j\\}$. The non-negative arc cost
between the vertices $i$ and $j$ is expressed as $c_{ij}$ and $x_{ij}$ is a
binary decision variable whose value will be 1 if a vehicle travels from $i$
to $j$, and 0 otherwise. The objective function of the E-VRP problem is
indicated by Eq. 2.4 which minimizes the total travel time, the other
formulation of the constraints like fuel constraint, time window constraint
and generic constraints of the E-VRP can be found here [13].

$\min\sum_{i}\sum_{j}c_{ij}x_{ij}\quad\forall i,j\in V\\\ $ (2.4)

Again, we used Google OR-Tools ™ as our heuristic implementation for solving
the E-VRP model with constrained programming (CP). OR-Tools ™ uses a search
tree, local search, and meta-heuristics to identify feasible and optimal
solutions. The heart of OR-Tools ™ is a CP-SAT solver that employs
DecisionBuilder to find an initial feasible solution using the Path Cheapest
Arc Strategy [26]. OR-Tools ™ then performs a local search to find the best
solution in the neighborhood of the current solution. This local search uses
move operators to rewire nodes and check for feasibility and cost, and the
moves are repeated until a termination criterion is met [12].

##  3 RESULTS

(a)

(b)

Figure 3: UAV & UGV trajectory obtained from bilevel optimization with Greedy
and CP method at the outer loop. Numerical and alphabetical order shows the
UAV and UGV motion respectively. a) CP method based trajectory b) greedy
method based trajectory.

Figure 3 provides an illustrative example of the input and output of the
problem at hand. The input, depicted in Figure 3, consists of mission points
denoted by black crosses. The UAV and UGV must both initiate and terminate at
the starting depot, while ensuring that all mission points are covered either
by the UAV or UGV. The UAV can recharge at the depot or at designated
refueling sites from the UGV. The UAV and UGV have fixed velocities of 10 m/s
and 4 m/s, respectively, and their fuel capacities are 287.7 kJ and 25.01 MJ,
respectively.

To carry out the optimizations, we employed Python 3 and OR Tools ™ library,
which ran on a 3.7 GHz Intel Core i9 processor with 48 GB RAM on a 64-bit
operating system. For the scenario, two types of cooperative routes (if
different) were generated by implementing the Greedy method and the CP method
at the outer loop of the suggested framework. The UGV-only route, where only a
UGV completes the whole mission was also determined for the scenario. Based on
the metrics of total mission completion time and total energy consumption, the
impact of collaboration between the UAV and UGV on mission execution was
assessed by comparing the cooperative route with the UGV only route which
served as the upper limit.

Table I shows the improvement that was achieved through cooperative routing of
UAV-UGV on the mission scenario. Cooperative routing is extremely energy
efficient. Both CP method and greedy method at the outer loop showed positive
improvement reducing total energy consumption in the mission by 36-39%.
However, for total mission time greedy method at the outer loop had a negative
impact. This is due to position of refuel stops ( see trajectory in figure
3(b) ) what made the UAV to take frequent detours (6 times) for recharging at
the refuel sites elongating the total mission time. However, appropriate
refuel stop locations obtained CP method ( see trajectory in figure 3(a) )
helped UAV to complete its route with less recharging detour (4 times), which
effectively reduced total mission time.

Further insights about the trajectory of the cooperative route can be drawn
from Table II. As discussed earlier, greedy results in longer UAV travel time
which ultimately costs higher mission time. Energy consumption of UGV is low
in greedy method as UAV is visiting majority of mission points compare to CP
method. In sum, both CP method and greedy heuristics are capable of providing
feasible cooperative route for constrained complex mission scenario; however
CP method outperforms greedy method at the cost of some computational
efficiency.

TABLE I: Impact of the optimal solution of the cooperative routing. Metrics |  | Cooperative
---
routing
| UGV
---
only route
Improvement (%)
|  | CP
---
method
| Greedy
---
method
|  | CP
---
method
| Greedy
---
method
| Time
---
consumption
(min.)
200 | 272 | 233 | 14.16 | -16.74
| Energy
---
consumption
(MJ)
21.98 | 21.14 | 34.69 | 36.62 | 39.06
TABLE II: Comparison between trajectories of CP method and greedy heuristics  Metrics |  CP method |  Greedy method
---|---|---
Total time (min) |  200 |  272
Computational time (min) |  9 |  4
UGV results |  |
Travel time (minutes) |  200 |  272
Energy consumed (MJ) |  20.79 |  19.52
Mission visited |  22 |  18
UAV results |  |
Travel time (minutes) |  100 |  136.203
Energy consumed (kJ) |  1186.464 |  1618.092
Recharging stops on UGV |  3 |  6
Recharging stops on Depot |  1 |  0
Missions visited |  22 |  26

##  4 EXPERIMENT DESIGN

The most stringent way of validating a framework is by hardware demonstration,
but it often has limitations in terms of scope and variety. Therefore,
simulation results are often utilized to assess method performance, while
experiments are used to verify some of those outcomes. The validation of a
surveillance planning framework through experiments is especially significant
as it is a highly challenging problem to solve. We devised a small laboratory
scale scenario to test the proposed framework methodology with just one UAV
and UGV. In order to fully achieve autonomy during the experiment, each robot
must be capable of independently locating, planning, and executing its desired
route to each location without relying on external input. Our localization,
planning, and control strategies are built on the hardware’s sensing,
processing, and communication capabilities. However, developing an appropriate
experimental system poses various challenges as we need to consider the
integration of software, hardware, and communication to accomplish the task.
We have separately described the individual blocks of the hardware
architecture (see figure 4) as follows:

Figure 4: Hardware architecture

(a)

(b)

Figure 5: Comparison between simulation and experimental results. In the
trajectory, the alphabetical order represents the direction of motion of the
UAV

(a)

(b)

Figure 6:  Experiment instances a) UAV, UGV are moving towards their
designated locations b) UAV landed on UGV for recharging.

  1. 1.

Hardware: For our UAV, we chose the DJI Tello quadcopter due to its compact
size and affordability. It is a small quadrotor measuring 9.8 x 9.2 x 4.1cm
and weighing 80 g, including the battery (Li-Po, 1100mAh, 3.8V) and 3 inch
propellers. The drone comes with a built-in flight controller that offers
basic features such as flight stabilization and attitude regulation,
translational velocity control, and simple trajectory execution. This flight
controller is closed hardware and operated using a dedicated command protocol.
However, a higher level of autonomy can be achieved by using an external
ground-based computer that uses received telemetry and video feed to control
the drone with the same communication protocol.

For the UGV, we built a small raspberry-based omnidirectional car with a
landing pad for charging the UAV. The UGV can be controlled by controlling its
four wheels through the raspberry pi.

  2. 2.

Control & communication: A wireless 2.4 GHz 802.11n WiFi connection was used
to communicate with the drone. The approach makes use of the official Tello
SDK 2.0. The UDP port is used to send text messages to the drone programming
interface. To create the application, we used the SDK and the low-level Python
library DJItelloPy. Wireless 5 GHz Wifi communication was also established
with the Raspberry Pi for controlling the UGV.

  3. 3.

Central manager: The final element of the system design is the centralized
system manager. Based on the input scenario, this manager solves a fuel
constrained vehicle routing problem using the proposed bi-level optimization
framework to generate separate routes for the UAV and UGV. Then the manager
communicates with the UAV and the UGV, assigns respective tasks to them to
begin the surveillance. The manager continuously monitors their progress by
collecting the positional data of the vehicles from motion capture system. The
UGV runs on an open loop control and stops on its assigned stop locations on
the route. While the central system enforce an feedback control on the UAV to
navigate it correctly and make a successful landing on the UGV during
recharge.

  4. 4.

Experiment scenario: The experiments were conducted in the Robotics and Motion
Lab at the University of Illinois Chicago. The lab has a designated flight
area equipped with a motion capture system that serves as a reference for the
position of reflective markers placed on the quadrotor and the ground vehicle.
This enables real-time localization of the robots during the experiment. The
positional data of the vehicles can be obtained at a rate of 100 Hz, with a
latency of less than 9 ms. A mission scenario was created by selecting 12
different points over an area of $4m\times 4m$ for the UAV, a road network was
designed for UGV and a fuel constraint was introduced by limiting the UAV’s
flight time in a single recharge (endurance limit). For this experimental
setup the endurance limit was setup to be 50 seconds, the UAV and UGV speed
was 0.20 m/s and 0.15 m/s respectively This required the UAV to visit the UGV
at regular intervals for recharging in order to complete the mission. However
no real recharging took place, it was only hypothesized that UAV gets
recharged instantly when it lands on the UGV. The UGV road network was also
designed to be challenging, with the farthest points on the mission requiring
the UAV to operate near its maximum endurance limit, thus testing the
robustness of the proposed framework.

###  4-A Flight test results

Multiple trials of the experiment were carried out on the scenario. The
algorithm was fed with the locations of the mission points of the UAV and the
road network points as input. The outer-loop of the algorithm determined the
UGV traversal path with refueling spots in space and time, while the inner-
loop of the framework generated the UAV route. Both the routes were provided
to the individual agents from the central manager, and the agents started
performing their missions. The purpose of the experiment was to verify the
feasibility of the algorithm’s output and to determine if the multi-agent
experiment could be successfully carried out with our experimental
architecture. The motion capture system was used to track the positional data
of the UAV and UGV, which was processed to produce the experimental route. The
figure 5(a) shows a comparison between the simulation route and the
experimental route. During the experiment, due to dynamics, the UAV drifted
away in some places but successfully managed to visit the mission points and
get recharged from the UGV by landing on it, because of the feedback control.
The endurance limit constraint was also tested, and it was observed that the
maximum flight time in a single recharge was always below the maximum limit in
figure 5(b). Dynamics of the UAV played an important role in the experiment
which was compensated by considering buffer time period in the modeling of
take off and landing of the UAV in the simulation counterpart. Instances of
the flight test can be seen in figure 6.

##  5 CONCLUSIONS

We conclude that a bilevel optimization framework with suitably designed
heuristics is an effective method for solving cooperative routing problems.
Our heuristics involved solving for UGV route first using the minimum set
cover algorithm and traveling salesman followed by the UAV route based on
mission allocation and a vehicle routing formulation. We found constraint
programming outperform greedy heuristics to solve the minimum set cover
algorithm although the former takes more computational time than the latter.
Experimental validation of the framework on a small testbed shows a close
match between simulation and hardware and confirming the proposed approach.

## ACKNOWLEDGMENT

The authors would like to thank Jean-Paul F. Reddinger, James M. Dotterweich,
and Marshal A. Childers from DEVCOM Army Research Laboratory, Aberdeen Proving
Grounds, Aberdeen, MD 21005 USA and James D. Humann is with DEVCOM Army
Research Laboratory, Los Angeles, CA, 90094 USA for providing solutions that
helped improve the formulation and solutions.

## References

  * [1] Daniel H Stolfi, Matthias R Brust, Grégoire Danoy, and Pascal Bouvry.  Uav-ugv-umv multi-swarms for cooperative surveillance.  Frontiers in Robotics and AI, 8:616950, 2021.
  * [2] Yu Wu, Shaobo Wu, and Xinting Hu.  Cooperative path planning of uavs & ugvs for a persistent surveillance task in urban environments.  IEEE Internet of Things Journal, 8(6):4906–4919, 2020.
  * [3] Yao Liu, Zhihao Luo, Zhong Liu, Jianmai Shi, and Guangquan Cheng.  Cooperative routing problem for ground vehicle and unmanned aerial vehicle: The application on intelligence, surveillance, and reconnaissance missions.  IEEE Access, 7:63504–63518, 2019.
  * [4] Jianqiang Li, Genqiang Deng, Chengwen Luo, Qiuzhen Lin, Qiao Yan, and Zhong Ming.  A hybrid path planning method in unmanned air/ground vehicle (uav/ugv) cooperative systems.  IEEE Transactions on Vehicular Technology, 65(12):9585–9596, 2016\.
  * [5] David Levy, Kaarthik Sundar, and Sivakumar Rathinam.  Heuristics for routing heterogeneous unmanned vehicles with fuel constraints.  Mathematical Problems in Engineering, 2014, 2014.
  * [6] Kaarthik Sundar, Saravanan Venkatachalam, and Sivakumar Rathinam.  Formulations and algorithms for the multiple depot, fuel-constrained, multiple vehicle routing problem.  In 2016 American Control Conference (ACC), pages 6489–6494. IEEE, 2016.
  * [7] Parikshit Maini and PB Sujit.  On cooperation between a fuel constrained uav and a refueling ugv for large scale mapping applications.  In 2015 International Conference on Unmanned Aircraft Systems (ICUAS), pages 1370–1377. IEEE, 2015.
  * [8] Satyanarayana G Manyam, Kaarthik Sundar, and David W Casbeer.  Cooperative routing for an air–ground vehicle team—exact algorithm, transformation method, and heuristics.  IEEE Transactions on Automation Science and Engineering, 17(1):537–547, 2019.
  * [9] Zhihao Luo, Zhong Liu, and Jianmai Shi.  A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle.  Sensors, 17(5):1144, 2017.
  * [10] Yao Liu, Zhong Liu, Jianmai Shi, Guohua Wu, and Witold Pedrycz.  Two-echelon routing problem for parcel delivery by cooperated truck and drone.  IEEE Transactions on Systems, Man, and Cybernetics: Systems, 51(12):7450–7465, 2020.
  * [11] Subramanian Ramasamy, Jean-Paul F Reddinger, James M Dotterweich, Marshal A Childers, and Pranav A Bhounsule.  Cooperative route planning of multiple fuel-constrained unmanned aerial vehicles with recharging on an unmanned ground vehicle.  In 2021 International Conference on Unmanned Aircraft Systems (ICUAS), pages 155–164. IEEE, 2021.
  * [12] Subramanian Ramasamy, Jean-Paul F Reddinger, James M Dotterweich, Marshal A Childers, and Pranav A Bhounsule.  Coordinated route planning of multiple fuel-constrained unmanned aerial systems with recharging on an unmanned ground vehicle for mission coverage.  Journal of Intelligent & Robotic Systems, 106(1):1–18, 2022.
  * [13] Subramanian Ramasamy, Md Safwan Mondal, Jean-Paul F Reddinger, James M Dotterweich, James D Humann, Marshal A Childers, and Pranav A Bhounsule.  Heterogenous vehicle routing: comparing parameter tuning using genetic algorithm and bayesian optimization.  In 2022 International Conference on Unmanned Aircraft Systems (ICUAS), pages 104–113. IEEE, 2022.
  * [14] Nikhil Nigam, Stefan Bieniawski, Ilan Kroo, and John Vian.  Control of multiple uavs for persistent surveillance: Algorithm and flight test results.  IEEE Transactions on Control Systems Technology, 20(5):1236–1251, 2011.
  * [15] Nikhil Nigam.  The multiple unmanned air vehicle persistent surveillance problem: A review.  Machines, 2(1):13–72, 2014.
  * [16] Nikhil Nigam, Stefan Bieniawski, Ilan Kroo, and John Vian.  Control of multiple uavs for persistent surveillance: Algorithm description and hardware demonstration.  In AIAA Infotech@ Aerospace Conference and AIAA Unmanned… Unlimited Conference, page 1852, 2009.
  * [17] Eric Frew, Xiao Xiao, Stephen Spry, Tim McGee, ZuWhan Kim, Jack Tisdale, Raja Sengupta, and J Karl Hedrick.  Flight demonstrations of self-directed collaborative navigation of small unmanned aircraft.  In AIAA 3rd” Unmanned Unlimited” Technical Conference, Workshop and Exhibit, page 6608, 2004.
  * [18] Nidal Jodeh, Mark Mears, and David Gross.  An overview of the cooperative operations in urban terrain (counter) program.  In AIAA Guidance, Navigation and Control Conference and Exhibit, page 6308, 2008.
  * [19] Kevin Leahy, Dingjiang Zhou, Cristian-Ioan Vasile, Konstantinos Oikonomopoulos, Mac Schwager, and Calin Belta.  Persistent surveillance for unmanned aerial vehicles subject to charging and temporal logic constraints.  Autonomous Robots, 40:1363–1378, 2016.
  * [20] Kevin Leahy, Dingjiang Zhou, Cristian-Ioan Vasile, Konstantinos Oikonomopoulos, Mac Schwager, and Calin Belta.  Provably correct persistent surveillance for unmanned aerial vehicles subject to charging constraints.  In Experimental Robotics: The 14th International Symposium on Experimental Robotics, pages 605–619. Springer, 2016.
  * [21] Josh Redding, Tuna Toksoz, N Kemal Ure, Alborz Geramifard, Jonathan P How, Matthew A Vavrina, and John Vian.  Distributed multi-agent persistent surveillance and tracking with health management.  In Proceedings of the AIAA Guidance Navigation and Control Conference, Portland, OR, USA, pages 8–11, 2011.
  * [22] Emad Saad, John Vian, Gregory Clark, and Stefan Bieniawski.  Vehicle swarm rapid prototyping testbed.  In AIAA Infotech@ Aerospace Conference and AIAA Unmanned… Unlimited Conference, page 1824, 2009.
  * [23] David Halaas, Stefan Bieniawski, Paul Pigg, and John Vian.  Control and management of an indoor, health enabled, heterogenous fleet.  In AIAA Infotech@ Aerospace Conference and AIAA Unmanned… Unlimited Conference, page 2036, 2009.
  * [24] Jonathan P How.  Multi-vehicle flight experiments: Recent results and future directions.  Technical report, MASSACHUSETTS INST OF TECH CAMBRIDGE, 2007.
  * [25] Google.  Google OR-tools.  https://developers.google.com/optimization, 2021.  Online; accessed Feb 2, 2021.
  * [26] Bingkai Lin.  A simple gap-producing reduction for the parameterized set cover problem.  arXiv preprint arXiv:1902.03702, 2019.