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 条

[1]

ALAMI R, 1995, IEEE INT CONF ROBOT, P2573, DOI 10.1109/ROBOT.1995.525645

[2]

ARDEMA MD, 1991, LECT NOTES CONTR INF, V156, P118

[3] A MINIMUM-TIME TRAJECTORY PLANNING METHOD FOR 2 ROBOTS [J].

BIEN, ZN ;

LEE, JH .

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1992, 8 (03) :414-418

[4] OPTIMAL ROBOT PATH PLANNING USING THE MINIMUM-TIME CRITERION [J].

BOBROW, JE .

IEEE JOURNAL OF ROBOTICS AND AUTOMATION, 1988, 4 (04) :443-450

[5]

FIORINI P, 1993, PROCEEDINGS : IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, VOLS 1-3, P560, DOI 10.1109/ROBOT.1993.292038

[6] Conflict-free vehicle routing Load balancing and deadlock prevention [J].

Gawrilow, Ewgenij ;

Klimm, Max ;

Moehring, Rolf H. ;

Stenzel, Bjoern .

EURO JOURNAL ON TRANSPORTATION AND LOGISTICS, 2012, 1 (1-2) :87-111

[7] ON THE COMPLEXITY OF MOTION PLANNING FOR MULTIPLE INDEPENDENT OBJECTS - PSPACE-HARDNESS OF THE WAREHOUSEMANS PROBLEM [J].

HOPCROFT, JE ;

SCHWARTZ, JT ;

SHARIR, M .

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 1984, 3 (04) :76-88

[8] Probabilistic roadmaps for path planning in high-dimensional configuration spaces [J].

Kavraki, LE ;

Svestka, P ;

Latombe, JC ;

Overmars, MH .

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1996, 12 (04) :566-580

[9]

Latombe J.-C., 2012, Robot motion planning, V124

[10]

Leroy S, 1999, IJCAI-99: PROCEEDINGS OF THE SIXTEENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOLS 1 & 2, P1118

← 1 2 3 →