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

被引：18

作者：

Davoodi, Mansoor ^{[1
]}

Abedin, Marjan ^{[2
]}

Banyassady, Bahareh ^{[2
]}

Khanteimouri, Payam ^{[2
]}

Mohades, Ali ^{[2
]}

机构：

[1] Inst Adv Studies Basic Sci, Dept Comp Sci & Informat Technol, Zanjan, Iran

[2] Amirkabir Univ Technol, Dept Math & Comp Sci, Lab Algorithms & Computat Geometry, Tehran, Iran

来源：

ROBOTICS AND AUTONOMOUS SYSTEMS | 2013年 / 61卷 / 12期

关键词：

Multi-robot path planning; Min-Max problem; Grid; Optimal algorithm; MOTION; COMPLEXITY;

D O I：

10.1016/j.robot.2013.07.012

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：1406 / 1414

页数：9

共 26 条

[11] THE COMPLEXITY OF FINDING 2 DISJOINT PATHS WITH MIN-MAX OBJECTIVE FUNCTION [J].

LI, CL ;

MCCORMICK, ST ;

SIMCHILEVI, D .

DISCRETE APPLIED MATHEMATICS, 1990, 26 (01) :105-115

[12]

Li TY, 2003, IEEE INT CONF ROBOT, P4215

[13]

Li Y, 2005, IEEE INT CONF ROBOT, P378

[14] DEADLOCK-FREE AND COLLISION-FREE COORDINATION OF 2 ROBOT MANIPULATORS [J].

ODONNELL, PA ;

LOZANOPEREZ, T .

PROCEEDINGS - 1989 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, VOL 1-3, 1989, :484-489

[15]

Parsons D., 1990, Proceedings 1990 IEEE International Conference on Robotics and Automation (Cat. No.90CH2876-1), P8, DOI 10.1109/ROBOT.1990.125937

[16]

Peis B., 2009, WAOA, P217

[17]

Ratner D., 1986, Proceedings AAAI-86: Fifth National Conference on Artificial Intelligence, P168

[18]

Ryan M.R.K., 2007, 20 INT JOINT C ART I

[19]

Ryan M.R.K., 2006, 19 AUSTR C ROB AUT

[20] Multi-robot motion planning by incremental coordination [J].

Saha, Mitul ;

Isto, Pekka .

2006 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS, VOLS 1-12, 2006, :5960-+

← 1 2 3 →