In recent years, collaborative multi-robot systems have had great initial success in industrial applications. Notable examples include the deployment of automated straddle carriers at container shipping ports (e.g., Brisbane, Rotterdam, Los Angeles) and the use of mobile robots at order fulfillment centers of online retailers (e.g., Amazon). Operational efficiency plays a pivotal role in the viability of these multi-robot systems, the underlying structure of which is yet to be fully understood. A thorough investigation of large-scale collaborative multi-robot systems will lead to solutions for the effective routing of many robots in dynamic and dense settings with provable availability, safety, and optimality guarantees, which will help lower the barrier of entry for industrial multi-robot applications and contribute to productivity increases of the US labor force.
Algorithmic issues rising from the domain possess unique features that distinguish them from well-studied problems. On one hand, classical pickup and delivery problems (PDP) do not model the non-trivial geometry of physical robots and the possible collisions among multiple robots sharing a limited workspace. On the other, multi-robot path and motion planning research has yet to systematically address the coordination of hundreds to thousands of robots for the continuous execution of dynamic and stochastic tasks. The proposed study intends to fill this gap between research and application through the modeling and subsequent algorithmic resolution of the problem, which we call the dynamic multi-robot dispatching problem (DMD). Depending on the specific application domain, DMD may be subdivided into unlabeled (e.g., container unloading from ships) and labeled (e.g., order fulfillment) variants, providing rich grounds for structural exploration. Despite the fact that optimal multi-robot coordination is a computationally intractable problem, preliminary efforts indicate that approximately optimal solutions could be computed in polynomial time, through the careful integration of the state-of-the-art multi-robot motion planners and the global coordination of robot flows. Following this route, the proposed research will develop algorithmic solutions for DMD with provable availability and optimality guarantees under stringent safety assurances for human co-workers. Working with collaborators, the research will also seek to maximize its applicability to industrial setups.
