Visiting pebbles on rectangular grids: coordinating multiple robots in mobile fulfilment systems

Multi-robot path finding and coordination is one of the key performance-affecting subsystems of the overall robotic order fulfilment process for use in warehouse applications. The purpose of path finding and coordination is to plan and coordinate the motions of multi-robot systems such that all robots reach their assigned goals safely. Much research has focused on solving the multi-robot path finding problem in a general way. As a result, researchers have considered a system-wide goal state where all robots are at their goal destinations in some final time. In this paper, a novel algorithm is designed specifically for order fulfilment used in warehouse applications. The key assumption is that all robots do not necessarily need to be at their destination locations at the same time. The resulting solution is referred to as visiting pebble motion on rectangular grids. More specifically, a starvation-free, semi-decentralized, scalable multi-robot coordination algorithm is presented. The proposed algorithm takes the constraints of real robot dynamics and collision avoidance into account and is capable of operating under asynchronous conditions while providing analytical performance guarantees.