2013 | OriginalPaper | Chapter
Robust Complete Path Planning in the Plane
Authors : Victor Milenkovic, Elisha Sacks, Steven Trac
Published in: Algorithmic Foundations of Robotics X
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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((
n
4
+ c
3
) log
n
) with
c
3
ε
O(
n
6
) 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.