An optimal algorithm for two robots path planning problem on the grid |
| |
| Authors: | Mansoor Davoodi Marjan Abedin Bahareh Banyassady Payam Khanteimouri Ali Mohades |
| |
| Affiliation: | 1. Department of Computer Science and Information Technology, Institute for Advanced Studies in Basic Sciences (IASBS), Zanjan, Iran;2. Laboratory of Algorithms and Computational Geometry, Department of Mathematics and Computer Science, Amirkabir University of Technology, Iran |
| |
| Abstract: | 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. |
| |
| Keywords: | Multi-robot path planning Min–Max problem Grid Optimal algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
