Robust Complete Path Planning in the Plane

Victor Milenkovic; Elisha Sacks; Steven Trac

doi:10.1007/978-3-642-36279-8_3

Back

Robust Complete Path Planning in the Plane

Book chapter

Peer reviewed

Robust Complete Path Planning in the Plane

Victor Milenkovic, Elisha Sacks and Steven Trac

Algorithmic Foundations of Robotics X, pp.37-52

Springer Tracts in Advanced Robotics, Springer Berlin Heidelberg

2013

DOI: https://doi.org/10.1007/978-3-642-36279-8_3

Abstract

Computational Geometry

Critical Angle

Narrow Passage

Path Planning

Path Planning Algorithm

We present a complete path planning algorithm for a plane robot with three degrees of freedom and a static obstacle. The part boundaries consist of n linear and circular edges. The algorithm constructs and searches a combinatorial representation of the robot free space. Its computational complexity is O((n4 + c3) log n) with c3ε O(n6) the number of configurations with three simultaneous contacts between robot and obstacle edges. The algorithm is implemented robustly using our adaptive-precision controlled perturbation library. The program is fast and memory efficient, is provably accurate, and handles degenerate input.

Metrics

6 Record Views

Details

Title: Robust Complete Path Planning in the Plane
Creators: Victor Milenkovic - University of Miami, Coral Gables, USA
Elisha Sacks - Purdue University, West Lafayette, USA
Steven Trac - Epic Systems Corporation, Madison, USA
Publication Details: Algorithmic Foundations of Robotics X, pp.37-52
Series: Springer Tracts in Advanced Robotics
Publisher: Springer Berlin Heidelberg; Berlin, Heidelberg
ISSN: 1610-742X
Academic Unit: College of A&S; A&S - Computer Science
Language: English
Resource Type: Book chapter
Record Identifier: 991031620152902976