An optimal algorithm for two robots path planning problem on the grid

• Introducing a new concept, time collision cell, for coordinating multi-robots.
• Introducing a new concept, parking cell, for coordinating multi-robots.
• Proposing an optimal algorithm for solving min–max path planning for two robots.

This paper is a study on the problem of path planning for two robots on a grid. We consider the objective of minimizing the maximum path length which corresponds to minimizing the arrival time of the last robot at its goal position. We propose an optimal algorithm that solves the problem in linear time with respect to the size of the grid. We show that the algorithm is complete; meaning that it is sure to find an optimal solution or report if any does not exist.