The Persistent Robot Charging Problem for Long-Duration Autonomy

This paper introduces a novel formulation for finding the recharging schedule for a fleet of $n$ heterogeneous robots that minimizes utilization of recharging resources. This study provides a foundational framework applicable to Multi-Robot Mission Planning, particularly in scenarios demanding Long-Duration Autonomy (LDA) or other contexts that necessitate periodic recharging of multiple robots. A novel Integer Linear Programming (ILP) model is proposed to calculate the optimal initial conditions (partial charge) for individual robots, leading to minimal utilization of charging stations. This formulation was further generalized to maximize the servicing time for robots when charging stations are limited. The efficacy of the proposed formulation is evaluated through a comparative analysis, measuring its performance against the thrift price scheduling algorithm documented in the existing literature. The findings not only corroborate the effectiveness of the proposed approach but also underscore its potential as a valuable tool in optimizing resource allocation for a range of robotic and engineering applications.

I. Introduction

An Increasing number of companies, such as Amazon, Google, UPS, FedEx, and DHL, are actively integrating UAVs into their operations for last-mile delivery [1], [2]. Despite their wide usage, UAVs face limitations in flight time due to their limited battery capacity. For example, a heavy-duty drone like the Prism Lite, which uses 16,000 mAh batteries, can achieve only 40 minutes of flight time without any external payload [3]. In Long Duration Autonomy (LDA) and persistent monitoring applications, UAVs are expected to operate over long durations (typically, a few days) without human intervention and hence, this necessitates UAVs to frequently recharge their batteries at a charging station while carrying out their tasks.