Title :
Robust Free Space Computation for Curved Planar Bodies
Author :
Milenkovic, V. ; Sacks, Elisha ; Trac, Steven
Author_Institution :
Dept. of Comput. Sci., Univ. of Miami, Coral Gables, FL, USA
Abstract :
We present a free space computation algorithm for two planar bodies bounded by line segments and circular arcs. The computational complexity is O(((mn)2+k)log(mn)) with m and n the number of boundary curves of the two bodies, and with k the number of configurations with three pairs of curves in contact. Although k is in O((mn)3), mild input restrictions reduce it to O(mn). We develop a robust implementation that is accurate, is fast, and handles degenerate input.
Keywords :
computational complexity; computational geometry; mobile robots; path planning; O(((mn)2+k)log(mn)) computational complexity; boundary curves; circular arcs; curved planar bodies; free space computation algorithm; line segments; mild input restrictions; robot path planning; robust free space computation; Algorithm design and analysis; Computational geometry; Path planning; Robot kinematics; Robustness; Smoothing methods; Configuration spaces; robust computational geometry;
Journal_Title :
Automation Science and Engineering, IEEE Transactions on
DOI :
10.1109/TASE.2013.2277781