Motion planning with pulley, rope, and baskets

Eggermont, Christian E.J.; Woeginger, Gerhard J.

doi:10.4230/LIPIcs.STACS.2012.374

Document

Motion planning with pulley, rope, and baskets

Authors Christian E.J. Eggermont, Gerhard J. Woeginger

Part of: Volume: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2012-02-24

PDF

File

PDF

LIPIcs.STACS.2012.374.pdf

Filesize: 499 kB
10 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2012.374
URN: urn:nbn:de:0030-drops-33900

Subject Classification

Keywords

planning and scheduling; computational complexity

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get BibTex

Christian E.J. Eggermont and Gerhard J. Woeginger. Motion planning with pulley, rope, and baskets. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 374-383, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012) https://doi.org/10.4230/LIPIcs.STACS.2012.374

Author Details

Christian E.J. Eggermont

Gerhard J. Woeginger

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail