TY - GEN
T1 - Topology preserving approximation of free configuration space
AU - Varadhan, Gokul
AU - Kim, Young J.
AU - Krishnan, Shankar
AU - Manocha, Dinesh
PY - 2006
Y1 - 2006
N2 - We present a simple algorithm for approximating the free configuration space of robots with low degrees of freedom (DOFs). We represent the free space as an arrangement of contact surfaces. We approximate the free space using an adaptive volumetric grid that is computed by performing simple geometric tests on the contact surfaces. We use an isosurface extraction algorithm to compute a piecewise-linear approximation to the boundary of the free space. We prove that our approximation is topologically equivalent to the exact free space boundary. We also ensure that our approximation is geometrically close to the exact free space boundary by bounding its two-sided Hausdorff error. We have applied our algorithm to compute the free configuration space for the following instances: (1) a 2D polygonal robot with translational and rotational DOFs navigating among polygonal obstacles, and (2) a 3D polyhedral robot translating among polyhedral obstacles. In practice, our algorithm works well on robots with three DOFs.
AB - We present a simple algorithm for approximating the free configuration space of robots with low degrees of freedom (DOFs). We represent the free space as an arrangement of contact surfaces. We approximate the free space using an adaptive volumetric grid that is computed by performing simple geometric tests on the contact surfaces. We use an isosurface extraction algorithm to compute a piecewise-linear approximation to the boundary of the free space. We prove that our approximation is topologically equivalent to the exact free space boundary. We also ensure that our approximation is geometrically close to the exact free space boundary by bounding its two-sided Hausdorff error. We have applied our algorithm to compute the free configuration space for the following instances: (1) a 2D polygonal robot with translational and rotational DOFs navigating among polygonal obstacles, and (2) a 3D polyhedral robot translating among polyhedral obstacles. In practice, our algorithm works well on robots with three DOFs.
UR - http://www.scopus.com/inward/record.url?scp=33845635319&partnerID=8YFLogxK
U2 - 10.1109/ROBOT.2006.1642164
DO - 10.1109/ROBOT.2006.1642164
M3 - Conference contribution
AN - SCOPUS:33845635319
SN - 0780395069
SN - 9780780395060
T3 - Proceedings - IEEE International Conference on Robotics and Automation
SP - 3041
EP - 3048
BT - Proceedings 2006 IEEE International Conference on Robotics and Automation, ICRA 2006
T2 - 2006 IEEE International Conference on Robotics and Automation, ICRA 2006
Y2 - 15 May 2006 through 19 May 2006
ER -