Effective Heuristics for Multi-Robot Path Planning in Warehouse Environments

Abstract

In this preliminary study, we propose a new centralized decoupled algorithm for solving one-shot and dynamic optimal multi-robot path planning problems in a grid-based setting mainly targeting warehouse like environments. In particular, we exploit two novel and effective heuristics: path diversification and optimal sub-problem solution databases. Preliminary evaluation efforts demonstrate that our method achieves promising scalability and good solution optimality.