TY - GEN
T1 - Decidability of robot manipulation planning
T2 - 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
AU - Vendittelli, Marilena
AU - Laumond, Jean Paul
AU - Mishra, Bud
N1 - Funding Information:
B. Mishra—This work is supported by the EU FP7 ICT-287513 SAPHARI project.
Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - This paper considers the problem of planning collision-free motion of three disks in the plane. One of the three disks, the robot, can autonomously translate in the plane, the other two move only when in contact with the robot. This represents the abstract formulation of a manipulation planning problem. Despite the simplicity of the formulation, the decidability of the problem had remained unproven so far.We prove that the problem is decidable, i.e., there exists an exact algorithm that decides whether a solution exists in finite time.
AB - This paper considers the problem of planning collision-free motion of three disks in the plane. One of the three disks, the robot, can autonomously translate in the plane, the other two move only when in contact with the robot. This represents the abstract formulation of a manipulation planning problem. Despite the simplicity of the formulation, the decidability of the problem had remained unproven so far.We prove that the problem is decidable, i.e., there exists an exact algorithm that decides whether a solution exists in finite time.
UR - http://www.scopus.com/inward/record.url?scp=84946041908&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84946041908&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-16595-0_37
DO - 10.1007/978-3-319-16595-0_37
M3 - Conference contribution
AN - SCOPUS:84946041908
SN - 9783319165943
T3 - Springer Tracts in Advanced Robotics
SP - 641
EP - 657
BT - Algorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
A2 - van der Stappen, A. Frank
A2 - Levent Akin, H.
A2 - Amato, Nancy M.
A2 - Isler, Volkan
PB - Springer Verlag
Y2 - 3 August 2014 through 5 August 2014
ER -