Decentralized Multi-Agent Path Finding in Warehouse Environments for Fleets of Mobile Robots

Mobile robots have already made their way into warehouses, and significant effort has consequently been devoted to designing effective algorithms for the related multi-agent path finding (MAPF) problem. It is defined on a graph with given start and goal vertices for each agent. Each agent is allowed to wait at its current vertex or move to an adjacent vertex from one discrete time step to the next one. 

The objective is to find a path for each agent such that no two agents are at the same vertex or cross the same edge at any timestep. The objective is to minimize the sum-of-costs (or flow time), that is, the sum over all agents of the time steps required to reach their target locations.

Most of the proposed MAPF algorithms still rely on centralized planning as well as simplistic assumptions, such as that robots have full observability of the environment and move at equal and constant speeds. The resultant plans thus cannot be executed directly on physical robots where these assumptions generally do not hold.

To mitigate these issues, we consider the decentralized partially observable multi-robot setting where robots do not have access to the full state of the world. In this context, our main objective consists of developing a decentralized approach based on online conflict resolution, wherein each robot coordinates with neighbors within a limited communication range.