Hitchhiker's Guide to Patrolling: Path-Finding for Energy-Sharing Drone-UGV Teams

Teams of Unmanned Ground Vehicles (UGVs) and drones are often proposed for various patrolling applications, where drones quickly move from one point of interest to the next while UGVs act as moving base stations that can both recharge and ferry around the drones. In this paper, we look at how to plan collaborative actions between drones and UGVs for a patrolling mission over an indefinite time horizon. We demonstrate how to form a second-order cone (SOC) program that finds optimal solutions, in polynomial time, to a variant of the larger problem where the order of drone and UGV actions are fixed. We propose two algorithms that use our SOC program to find locally optimal solutions while considering the limited energy of both UGVs and drones. Our numerical simulation results show that both of our algorithms yield a greater than 50% improvement in solution quality when compared to a baseline method from the literature. Additionally, we demonstrate the authenticity of our problem setup through a proof-of-concept experiment on a physical UGV and drone testbed.