Name
Abstract | ||
|---|---|---|
In this paper, we address the problem determining the connectivity of a robot's free configuration space. Our method iteratively builds a constructive proof that two configurations lie in disjoint components of the free configuration space. Our algorithm first generates samples that correspond to configurations for which the robot is in collision with an obstacle. These samples are then weighted by their generalized penetration distance, and used to construct alpha shapes. The alpha shape defines a collection of simplices that are fully contained within the configuration space obstacle region. These simplices can be used to quickly solve connectivity queries, which in turn can be used to define termination conditions for sampling-based planners. Such planners, while typically either resolution complete or probabilistically complete, are not able to determine when a path does not exist, and therefore would otherwise rely on heuristics to determine when the search for a free path should be abandoned. An implementation of the algorithm is provided for the case of a 3D Euclidean configuration space, and a proof of correctness is provided. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/ICRA.2012.6225300 | Robotics and Automation |
Keywords | Field | DocType |
computational geometry,iterative methods,mobile robots,path planning,sampling methods,3D Euclidean configuration space,alpha shapes,configuration space obstacle region,connectivity queries,disjoint components,first iterative sampling schemes,generalized penetration distance,motion planning problem,path nonexistence,path planning,proof-of-correctness,robot free configuration space,sampling shapes,sampling-based planners,termination conditions | Motion planning,Constructive proof,Mathematical optimization,Disjoint sets,Alpha shape,Control theory,Correctness,Computational geometry,Algorithm,Heuristics,Mathematics,Configuration space | Conference |
Volume | Issue | ISSN |
2012 | 1 | 1050-4729 E-ISBN : 978-1-4673-1404-6 |
ISBN | Citations | PageRank |
978-1-4673-1404-6 | 11 | 0.76 |
References | Authors | |
15 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| McCarthy, Z. | 1 | 11 | 0.76 |
| Timothy Bretl | 2 | 547 | 45.57 |
| Seth Hutchinson | 3 | 3373 | 260.24 |