Smoothed analysis of probabilistic roadmaps

被引：10

作者：

Chaudhuri, Siddhartha ^{[1
]}

Koltun, Vladlen ^{[1
]}

机构：

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

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2009年 / 42卷 / 08期

关键词：

Motion planning; Probabilistic roadmap; Smoothed analysis; Locally orthogonal decomposition; SCHEME;

D O I：

10.1016/j.comgeo.2008.10.005

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The probabilistic roadmap algorithm is a leading heuristic for robot motion planning. It is extremely efficient in practice, yet its worst case convergence time is unbounded as a function of the input's combinatorial complexity. We prove a smoothed polynomial upper bound on the number of samples required to produce an accurate probabilistic roadmap, and thus Oil the running time of the algorithm, in an environment of simplices. This sheds light on its widespread empirical Success. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：731 / 747

页数：17

共 40 条

[1] COMPUTING DEPTH ORDERS FOR FAT OBJECTS AND RELATED PROBLEMS [J].

AGARWAL, PK ;

KATZ, MJ ;

SHARIR, M .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1995, 5 (04) :187-206

[2]

[Anonymous], LNCS

[3] CASTLES IN THE AIR REVISITED [J].

ARONOV, B ;

SHARIR, M .

DISCRETE & COMPUTATIONAL GEOMETRY, 1994, 12 (02) :119-150

[4]

ARTHUR D, 2006, P 47 IEEE S FDN COMP

[5]

BANDERIER C, 2003, P 28 S MATH FDN COMP, P198

[6] A random sampling scheme for path planning [J].

Barraquand, J ;

Kavraki, L ;

Latombe, JC ;

Motwani, R ;

Li, TY ;

Raghavan, P .

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 1997, 16 (06) :759-774

[7]

Berretty RP, 1997, LECT NOTES COMPUT SC, V1272, P3

[8]

Blum A, 2002, SIAM PROC S, P905

[9] Pattern matching for spatial point sets [J].

Cardoze, DE ;

Schulman, LJ .

39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :156-165

[10] A SINGLY EXPONENTIAL STRATIFICATION SCHEME FOR REAL SEMIALGEBRAIC VARIETIES AND ITS APPLICATIONS [J].

CHAZELLE, B ;

EDELSBRUNNER, H ;

GUIBAS, LJ ;

SHARIR, M .

THEORETICAL COMPUTER SCIENCE, 1991, 84 (01) :77-105

← 1 2 3 4 →