Decidability of robot manipulation planning: Three disks in the plane

Marilena Vendittelli, Jean Paul Laumond, Bud Mishra

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationAlgorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
EditorsA. Frank van der Stappen, H. Levent Akin, Nancy M. Amato, Volkan Isler
PublisherSpringer Verlag
Pages641-657
Number of pages17
ISBN (Print)9783319165943
DOIs
StatePublished - 2015
Event11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014 - Istanbul, Turkey
Duration: Aug 3 2014Aug 5 2014

Publication series

NameSpringer Tracts in Advanced Robotics
Volume107
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X

Other

Other11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
CountryTurkey
CityIstanbul
Period8/3/148/5/14

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Decidability of robot manipulation planning: Three disks in the plane'. Together they form a unique fingerprint.

Cite this