Motion planning with pulley, rope, and baskets

C.E.J. Eggermont, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)

Abstract

We study a motion planning problem where items have to be transported from the top room of a tower to the bottom of the tower, while simultaneously other items have to be transported into the opposite direction. Item sets are moved in two baskets hanging on a rope and pulley. To guarantee stability of the system, the weight difference between the contents of the two baskets must always stay below a given threshold. We prove that it is Pi-2-p-complete to decide whether some given initial situation of the underlying discrete system can lead to a given goal situation. Furthermore we identify several polynomially solvable special cases of this reachability problem, and we also settle the computational complexity of a number of related questions.
Original languageEnglish
Title of host publicationProceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), February 29-March 3, 2012, Paris, France
EditorsC. Dürr, T. Wilke
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages374-383
ISBN (Print)978-3-939897-35-4
DOIs
Publication statusPublished - 2012
Event29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) - Paris, France
Duration: 29 Feb 20123 Mar 2012
Conference number: 29

Publication series

NameLIPIcs: Leibniz International Proceedings in Informatics
Volume14
ISSN (Print)1868-8968

Conference

Conference29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Abbreviated titleSTACS 2012
CountryFrance
CityParis
Period29/02/123/03/12

Fingerprint Dive into the research topics of 'Motion planning with pulley, rope, and baskets'. Together they form a unique fingerprint.

Cite this