Path planning in expansive configuration spaces

被引：198

作者：

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
BARRAQUAND, J
LATOMBE, JC
[J]. 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 →