  We study a resource allocation problem for the cooperative aerial-ground
vehicle routing application, in which multiple Unmanned Aerial Vehicles (UAVs)
with limited battery capacity and multiple Unmanned Ground Vehicles (UGVs) that
can also act as a mobile recharging stations need to jointly accomplish a
mission such as persistently monitoring a set of points. Due to the limited
battery capacity of the UAVs, they sometimes have to deviate from their task to
rendezvous with the UGVs and get recharged. Each UGV can serve a limited number
of UAVs at a time. In contrast to prior work on deterministic multi-robot
scheduling, we consider the challenge imposed by the stochasticity of the
energy consumption of the UAV. We are interested in finding the optimal
recharging schedule of the UAVs such that the travel cost is minimized and the
probability that no UAV runs out of charge within the planning horizon is
greater than a user-defined tolerance. We formulate this problem ({Risk-aware
Recharging Rendezvous Problem (RRRP))} as an Integer Linear Program (ILP), in
which the matching constraint captures the resource availability constraints
and the knapsack constraint captures the success probability constraints. We
propose a bicriteria approximation algorithm to solve RRRP. We demonstrate the
effectiveness of our formulation and algorithm in the context of one persistent
monitoring mission.
