Multiple Query Probabilistic Roadmap Planning using Single Query Planning Primitives

Kostas E. Bekris; Brian Y. Chen; Andrew M. Ladd; Erion Plaku; Lydia E. Kavraki

Multiple Query Probabilistic Roadmap Planning using Single Query Planning Primitives

Kostas E. Bekris, Brian Y. Chen, Andrew M. Ladd, Erion Plaku, Lydia E. Kavraki

Research output: Contribution to conference › Paper › peer-review

Abstract

We propose a combination of techniques that solve multiple queries for motion planning problems with single query planners. Our implementation uses a probabilistic roadmap method (PRM) with bidirectional rapidly exploring random trees (BI-RRT) as the local planner. With small modifications to the standard algorithms, we obtain a multiple query planner which is significantly faster and more reliable than its component parts. Our method provides a smooth spectrum between the PRM and BI-RRT techniques and obtains the advantages of both. We observed that the performance differences are most notable in planning instances with several rigid nonconvex robots in a scene with narrow passages. Our work is in the spirit of non-uniform sampling and refinement techniques used in earlier work on PRM.

Original language	English (US)
Pages	656-661
Number of pages	6
State	Published - 2003
Externally published	Yes
Event	2003 IEEE/RSJ International Conference on Intelligent Robots and Systems - Las Vegas, NV, United States Duration: Oct 27 2003 → Oct 31 2003

Other

Other	2003 IEEE/RSJ International Conference on Intelligent Robots and Systems
Country/Territory	United States
City	Las Vegas, NV
Period	10/27/03 → 10/31/03

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Software
Computer Vision and Pattern Recognition
Computer Science Applications

Cite this

@conference{0ef6e3dcb95e4cd59cbcb59f45b89e8a,

title = "Multiple Query Probabilistic Roadmap Planning using Single Query Planning Primitives",

abstract = "We propose a combination of techniques that solve multiple queries for motion planning problems with single query planners. Our implementation uses a probabilistic roadmap method (PRM) with bidirectional rapidly exploring random trees (BI-RRT) as the local planner. With small modifications to the standard algorithms, we obtain a multiple query planner which is significantly faster and more reliable than its component parts. Our method provides a smooth spectrum between the PRM and BI-RRT techniques and obtains the advantages of both. We observed that the performance differences are most notable in planning instances with several rigid nonconvex robots in a scene with narrow passages. Our work is in the spirit of non-uniform sampling and refinement techniques used in earlier work on PRM.",

author = "Bekris, {Kostas E.} and Chen, {Brian Y.} and Ladd, {Andrew M.} and Erion Plaku and Kavraki, {Lydia E.}",

year = "2003",

language = "English (US)",

pages = "656--661",

note = "2003 IEEE/RSJ International Conference on Intelligent Robots and Systems ; Conference date: 27-10-2003 Through 31-10-2003",

}

TY - CONF

T1 - Multiple Query Probabilistic Roadmap Planning using Single Query Planning Primitives

AU - Bekris, Kostas E.

AU - Chen, Brian Y.

AU - Ladd, Andrew M.

AU - Plaku, Erion

AU - Kavraki, Lydia E.

PY - 2003

Y1 - 2003

N2 - We propose a combination of techniques that solve multiple queries for motion planning problems with single query planners. Our implementation uses a probabilistic roadmap method (PRM) with bidirectional rapidly exploring random trees (BI-RRT) as the local planner. With small modifications to the standard algorithms, we obtain a multiple query planner which is significantly faster and more reliable than its component parts. Our method provides a smooth spectrum between the PRM and BI-RRT techniques and obtains the advantages of both. We observed that the performance differences are most notable in planning instances with several rigid nonconvex robots in a scene with narrow passages. Our work is in the spirit of non-uniform sampling and refinement techniques used in earlier work on PRM.

AB - We propose a combination of techniques that solve multiple queries for motion planning problems with single query planners. Our implementation uses a probabilistic roadmap method (PRM) with bidirectional rapidly exploring random trees (BI-RRT) as the local planner. With small modifications to the standard algorithms, we obtain a multiple query planner which is significantly faster and more reliable than its component parts. Our method provides a smooth spectrum between the PRM and BI-RRT techniques and obtains the advantages of both. We observed that the performance differences are most notable in planning instances with several rigid nonconvex robots in a scene with narrow passages. Our work is in the spirit of non-uniform sampling and refinement techniques used in earlier work on PRM.

UR - http://www.scopus.com/inward/record.url?scp=0348041521&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0348041521&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0348041521

SP - 656

EP - 661

T2 - 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems

Y2 - 27 October 2003 through 31 October 2003

ER -

Multiple Query Probabilistic Roadmap Planning using Single Query Planning Primitives

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this