Sustainability-aware Online Task and Charge Allocation for Autonomous Ground Robot Fleets

Ensuring low battery degradation of Autonomous Ground Robot (AGR) fleets operating in online scenarios (e.g., delivery) through an efficient task and charge scheduling strategy can significantly enhance their long-term sustainability. Most existing studies are either based on offline methods, which are unsuitable for online scenarios requiring instant decisions, or concentrated on maximizing task allocation, resource usage, and/or revenues without considering the battery health. To overcome these limitations, this paper proposes a family of two joint task allocation and charge scheduling algorithms that activate at specific events to maximize the total revenue while minimizing the battery degradation of the fleet in online scenarios. Utility functions are defined to trade off revenues for battery degradation while deciding, for all the AGRs in the fleet, how to allocate tasks, charging stations, and idle periods. The first algorithm is based on the Kuhn-Munkres approach that makes decisions at each event optimally. The second algorithm utilizes a greedy approach achieving a sub-optimal solution with reduced computational overhead. Our results, obtained through extensive simulations based on a real AGR against several baselines, show that it is possible to achieve up to 20% longer battery lifespan with minimal revenue losses.