Optimal path planning for mobile robot navigation

被引：77

作者：

Jan, Gene Eu ^{[1
]}

Chang, Ki Yin ^{[2
]}

Parberry, Ian ^{[3
]}

机构：

[1] Natl Taipei Univ, Inst Elect Engn, Taipei 104, Taiwan

[2] Natl Taiwan Ocean Univ, Dept Merchant Marine, Chilung 20224, Taiwan

[3] Univ N Texas, Dept Comp Sci, Denton, TX 76203 USA

来源：

IEEE-ASME TRANSACTIONS ON MECHATRONICS | 2008年 / 13卷 / 04期

关键词：

lambda-geometry maze router; path planning; piano mover's problem;

D O I：

10.1109/TMECH.2008.2000822

中图分类号：

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

学科分类号：

0812 ;

摘要：

Some optimal path planning algorithms for navigating mobile rectangular robot among obstacles and weighted regions are presented. The approach is based on a higher geometry maze routing algorithm. Starting from a top view of a workspace with obstacles, the so-called free workspace is first obtained by virtually expanding the obstacles in the image. After that, an 8-geomerty maze routing algorithm is applied to obtain an optimal collision-free path with linear time and space complexities. The proposed methods cannot only search an optimal path among various terrains but also find an optimal path for the 2-D piano mover's problem with 3 DOE Furthermore, the algorithm can be easily extended to the dynamic collision avoidance problem among multiple autonomous robots or path planning in the 3-D space.

引用

页码：451 / 460

页数：10

共 30 条

[1] FASTER ALGORITHMS FOR THE SHORTEST-PATH PROBLEM [J].

AHUJA, RK ;

MEHLHORN, K ;

ORLIN, JB ;

TARJAN, RE .

JOURNAL OF THE ACM, 1990, 37 (02) :213-223

[2] PATH PLANNING FOR A MOBILE ROBOT [J].

ALEXOPOULOS, C ;

GRIFFIN, PM .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1992, 22 (02) :318-322

[3] NUMERICAL POTENTIAL-FIELD TECHNIQUES FOR ROBOT PATH PLANNING [J].

BARRAQUAND, J ;

LANGLOIS, B ;

LATOMBE, JC .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1992, 22 (02) :224-241

[4] DYNAMIC DIGITAL DISTANCE MAPS IN 2-DIMENSIONS [J].

BOULT, TE .

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1990, 6 (05) :590-597

[5] A method for searching optimal routes with collision avoidance on raster charts [J].

Chang, KY ;

Jan, GE ;

Parberry, I .

JOURNAL OF NAVIGATION, 2003, 56 (03) :371-384

[6] Automatic path planning for a mobile robot among obstacles of arbitrary shape [J].

de Leon, JLD ;

Sossa, JH .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 1998, 28 (03) :467-472

[7]

Dijkstra E.W., 1959, Numerische mathematik, V1, P269, DOI [10.1007/BF01386390, DOI 10.1007/BF01386390]

[8] Adaptive routing for road traffic [J].

Fawcett, J ;

Robinson, P .

IEEE COMPUTER GRAPHICS AND APPLICATIONS, 2000, 20 (03) :46-53

[9] Faster shortest-path algorithms for planar graphs [J].

Henzinger, MR ;

Klein, P ;

Rao, S ;

Subramanian, S .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1997, 55 (01) :3-23

[10] SOME VARIATIONS OF LEES ALGORITHM [J].

HOEL, JH .

IEEE TRANSACTIONS ON COMPUTERS, 1976, 25 (01) :19-24

← 1 2 3 →