10.4230/LIPICS.STACS.2012.374
Eggermont, Christian E.J.
Christian E.J.
Eggermont
Woeginger, Gerhard J.
Gerhard J.
Woeginger
Motion planning with pulley, rope, and baskets
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2012
Article
planning and scheduling; computational complexity
Dürr, Christoph
Christoph
Dürr
Wilke, Thomas
Thomas
Wilke
2012
2012-02-24
2012-02-24
2012-02-24
en
urn:nbn:de:0030-drops-33900
10.4230/LIPIcs.STACS.2012
978-3-939897-35-4
1868-8969
10.4230/LIPIcs.STACS.2012
LIPIcs, Volume 14, STACS 2012
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
2013
14
34
374
383
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Dürr, Christoph
Christoph
Dürr
Wilke, Thomas
Thomas
Wilke
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2012
14
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
10 pages
511319 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), pages 374-383