Motion planning with pulley, rope, and baskets

C.E.J. Eggermont; G.J. Woeginger

doi:10.4230/LIPIcs.STACS.2012.374

Motion planning with pulley, rope, and baskets

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

9 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 language	English
Title of host publication	Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), February 29-March 3, 2012, Paris, France
Editors	C. Dürr, T. Wilke
Place of Publication	Dagstuhl, Germany
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	374-383
ISBN (Print)	978-3-939897-35-4
DOIs	https://doi.org/10.4230/LIPIcs.STACS.2012.374
Publication status	Published - 2012
Event	29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) - Paris, France Duration: 29 Feb 2012 → 3 Mar 2012 Conference number: 29

Publication series

Name	LIPIcs: Leibniz International Proceedings in Informatics
Volume	14
ISSN (Print)	1868-8968

Conference

Conference	29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Abbreviated title	STACS 2012
Country/Territory	France
City	Paris
Period	29/02/12 → 3/03/12

Access to Document

10.4230/LIPIcs.STACS.2012.374

Cite this

Eggermont, C. E. J., & Woeginger, G. J. (2012). Motion planning with pulley, rope, and baskets. In C. Dürr, & T. Wilke (Eds.), Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), February 29-March 3, 2012, Paris, France (pp. 374-383). (LIPIcs: Leibniz International Proceedings in Informatics; Vol. 14). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2012.374

Eggermont, C.E.J. ; Woeginger, G.J. / Motion planning with pulley, rope, and baskets. Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), February 29-March 3, 2012, Paris, France. editor / C. Dürr ; T. Wilke. Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. pp. 374-383 (LIPIcs: Leibniz International Proceedings in Informatics).

@inproceedings{f735f73c847246668408937dcde710ee,

title = "Motion planning with pulley, rope, and baskets",

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

author = "C.E.J. Eggermont and G.J. Woeginger",

year = "2012",

doi = "10.4230/LIPIcs.STACS.2012.374",

language = "English",

isbn = "978-3-939897-35-4",

series = "LIPIcs: Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "374--383",

editor = "C. D{\"u}rr and T. Wilke",

booktitle = "Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), February 29-March 3, 2012, Paris, France",

note = "29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), STACS 2012 ; Conference date: 29-02-2012 Through 03-03-2012",

}

Eggermont, CEJ & Woeginger, GJ 2012, Motion planning with pulley, rope, and baskets. in C Dürr & T Wilke (eds), Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), February 29-March 3, 2012, Paris, France. LIPIcs: Leibniz International Proceedings in Informatics, vol. 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp. 374-383, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), Paris, France, 29/02/12. https://doi.org/10.4230/LIPIcs.STACS.2012.374

Motion planning with pulley, rope, and baskets. / Eggermont, C.E.J.; Woeginger, G.J.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), February 29-March 3, 2012, Paris, France. ed. / C. Dürr; T. Wilke. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. p. 374-383 (LIPIcs: Leibniz International Proceedings in Informatics; Vol. 14).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Motion planning with pulley, rope, and baskets

AU - Eggermont, C.E.J.

AU - Woeginger, G.J.

N1 - Conference code: 29

PY - 2012

Y1 - 2012

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

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

U2 - 10.4230/LIPIcs.STACS.2012.374

DO - 10.4230/LIPIcs.STACS.2012.374

M3 - Conference contribution

SN - 978-3-939897-35-4

T3 - LIPIcs: Leibniz International Proceedings in Informatics

SP - 374

EP - 383

BT - Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), February 29-March 3, 2012, Paris, France

A2 - Dürr, C.

A2 - Wilke, T.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl, Germany

T2 - 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Y2 - 29 February 2012 through 3 March 2012

ER -

Eggermont CEJ, Woeginger GJ. Motion planning with pulley, rope, and baskets. In Dürr C, Wilke T, editors, Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), February 29-March 3, 2012, Paris, France. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2012. p. 374-383. (LIPIcs: Leibniz International Proceedings in Informatics). doi: 10.4230/LIPIcs.STACS.2012.374

Motion planning with pulley, rope, and baskets

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this