Motion planning with pulley, rope, and baskets

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

Research output: Contribution to journalArticleAcademicpeer-review

8 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 in 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 $¿^p_2$ -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. Keywords: Planning and scheduling; Computational complexity; Polynomial hierarchy
Original languageEnglish
Pages (from-to)569-582
JournalTheory of Computing Systems
Volume53
Issue number4
DOIs
Publication statusPublished - 2013

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

  • Cite this