Multi-Agent Pickup and Delivery with Batteries

In a Multi-Agent Pickup and Delivery (MAPD) problem, the goal is to find coordinated paths for a group of moving agents that execute pickup and delivery tasks in a known environment. Tasks appear dynamically and are assigned to the agents in an online manner. The typical application of MAPD is in warehouses, where the agents are mobile robots powered by batteries. Current research on MAPD does not explicitly take into account the need for the agents to recharge their batteries when planning paths. In this paper, we study a variant of the MAPD problem, called MAPD-b, which considers battery consumption and charging stations, and we propose two main algorithms to solve it. One of them guarantees (under mild conditions) that agents will never run out of battery. We empirically evaluate the performance of our algorithms, showing that ensuring that no agent runs out of battery has a higher computing cost but does not worsen the performance in fulfilling tasks much.