Multi-Robot Path Planning With Due Times

We formulate the problem of multi-robot path planning with due times (MRPP-DT), which is a variant of the classical path planning problem with task due times explicitly considered. The objectives are to obtain collision-free paths with the minimization of maximum lateness, total tardiness or total unit penalties. When task due times are available, formulating the path planning problem as the MRPP-DT is more preferable because of task awareness in path coordination level. This problem is NP-hard to solve optimally for all these three objectives. To solve this problem optimally, we develop integer linear programming (ILP) models for three objectives respectively, and propose reduction-based algorithms. We also extend these algorithms to the problems of anonymous multi-robot path planning with due times. Theoretically, we prove the structure property and computational complexity of these problems, and the completeness of the proposed algorithms. Empirically, we compare their performance on different maps with random obstacles. Computational results demonstrate that these algorithms are suitable for different problem settings, and capable of computing high-quality solutions within allocated time.