Decidability of robot manipulation planning: Three disks in the plane

Marilena Vendittelli; Jean Paul Laumond; Bud Mishra

doi:10.1007/978-3-319-16595-0_37

Decidability of robot manipulation planning: Three disks in the plane

Marilena Vendittelli, Jean Paul Laumond, Bud Mishra

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	Algorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
Editors	A. Frank van der Stappen, H. Levent Akin, Nancy M. Amato, Volkan Isler
Publisher	Springer Verlag
Pages	641-657
Number of pages	17
ISBN (Print)	9783319165943
DOIs	https://doi.org/10.1007/978-3-319-16595-0_37
State	Published - 2015
Event	11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014 - Istanbul, Turkey Duration: Aug 3 2014 → Aug 5 2014

Publication series

Name	Springer Tracts in Advanced Robotics
Volume	107
ISSN (Print)	1610-7438
ISSN (Electronic)	1610-742X

Other

Other	11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
Country/Territory	Turkey
City	Istanbul
Period	8/3/14 → 8/5/14

ASJC Scopus subject areas

Electrical and Electronic Engineering
Artificial Intelligence

Access to Document

10.1007/978-3-319-16595-0_37

Cite this

Vendittelli, M., Laumond, J. P., & Mishra, B. (2015). Decidability of robot manipulation planning: Three disks in the plane. In A. F. van der Stappen, H. Levent Akin, N. M. Amato, & V. Isler (Eds.), Algorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014 (pp. 641-657). (Springer Tracts in Advanced Robotics; Vol. 107). Springer Verlag. https://doi.org/10.1007/978-3-319-16595-0_37

Decidability of robot manipulation planning: Three disks in the plane. / Vendittelli, Marilena; Laumond, Jean Paul; Mishra, Bud.
Algorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014. ed. / A. Frank van der Stappen; H. Levent Akin; Nancy M. Amato; Volkan Isler. Springer Verlag, 2015. p. 641-657 (Springer Tracts in Advanced Robotics; Vol. 107).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Vendittelli, M, Laumond, JP & Mishra, B 2015, Decidability of robot manipulation planning: Three disks in the plane. in AF van der Stappen, H Levent Akin, NM Amato & V Isler (eds), Algorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014. Springer Tracts in Advanced Robotics, vol. 107, Springer Verlag, pp. 641-657, 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014, Istanbul, Turkey, 8/3/14. https://doi.org/10.1007/978-3-319-16595-0_37

Vendittelli M, Laumond JP, Mishra B. Decidability of robot manipulation planning: Three disks in the plane. In van der Stappen AF, Levent Akin H, Amato NM, Isler V, editors, Algorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014. Springer Verlag. 2015. p. 641-657. (Springer Tracts in Advanced Robotics). doi: 10.1007/978-3-319-16595-0_37

Vendittelli, Marilena ; Laumond, Jean Paul ; Mishra, Bud. / Decidability of robot manipulation planning : Three disks in the plane. Algorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014. editor / A. Frank van der Stappen ; H. Levent Akin ; Nancy M. Amato ; Volkan Isler. Springer Verlag, 2015. pp. 641-657 (Springer Tracts in Advanced Robotics).

@inproceedings{6513d71636c7424387ecdc26d580e37a,

title = "Decidability of robot manipulation planning: Three disks in the plane",

abstract = "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.",

author = "Marilena Vendittelli and Laumond, {Jean Paul} and Bud Mishra",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014 ; Conference date: 03-08-2014 Through 05-08-2014",

year = "2015",

doi = "10.1007/978-3-319-16595-0_37",

language = "English (US)",

isbn = "9783319165943",

series = "Springer Tracts in Advanced Robotics",

publisher = "Springer Verlag",

pages = "641--657",

editor = "{van der Stappen}, {A. Frank} and {Levent Akin}, H. and Amato, {Nancy M.} and Volkan Isler",

booktitle = "Algorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014",

}

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 - 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 -

Decidability of robot manipulation planning: Three disks in the plane

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this