Path planning in expansive configuration spaces

被引：201

作者：

Hsu, D ^{[1
]}

Latombe, JC ^{[1
]}

Motwani, R ^{[1
]}

机构：

[1] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1999年 / 9卷 / 4-5期

关键词：

motion planning; path planning; configuration space; random sampling; probabilistic roadmap;

D O I：

10.1142/S0218195999000285

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We introduce the notion of expansiveness to characterize a family of robot configuration spaces whose connectivity can be effectively captured by a roadmap of randomly-sampled milestones. The analysis of expansive configuration spaces has inspired us to develop a new randomized planning algorithm. This new algorithm tries to sample only the portion of the configuration space that is relevant to the current query, avoiding the cost of precomputing a roadmap for the entire configuration space. Thus, it is well-suited for problems where only a single query is submitted for a given environment. The algorithm has been implemented and successfully applied to complex assembly maintainability problems from the automotive industry.

引用

页码：495 / 512

页数：18

共 18 条

[1]

Amato NM, 1996, IEEE INT CONF ROBOT, P113, DOI 10.1109/ROBOT.1996.503582

[2] ROBOT MOTION PLANNING - A DISTRIBUTED REPRESENTATION APPROACH [J].

BARRAQUAND, J ;

LATOMBE, JC .

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 1991, 10 (06) :628-649

[3]

Barraquand J., 1996, P INT S ROB RES, P249

[4]

Challou D. J., 1993, Proceedings IEEE International Conference on Robotics and Automation (Cat. No.93CH3247-4), P46, DOI 10.1109/ROBOT.1993.292122

[5]

CHANG H, 1995, IEEE INT CONF ROBOT, P1012, DOI 10.1109/ROBOT.1995.525415

[6]

GILBERT EG, 1988, IEEE T ROB AUT, V4

[7]

Gottschalk S., 1996, Computer Graphics Proceedings. SIGGRAPH '96, P171, DOI 10.1145/237170.237244

[8]

HORSCH T, 1994, IEEE INT CONF ROBOT, P3318, DOI 10.1109/ROBOT.1994.351060

[9]

KAVRAKI L, 1994, IEEE INT CONF ROBOT, P2138, DOI 10.1109/ROBOT.1994.350966

[10]

KAVRAKI L, 1995, ACM S THEOR COMP, P353

← 1 2 →