Journal
THEORY OF COMPUTING SYSTEMS
Volume 53, Issue 4, Pages 569-582Publisher
SPRINGER
DOI: 10.1007/s00224-013-9445-4
Keywords
Planning and scheduling; Computational complexity; Polynomial hierarchy
Categories
Funding
- Netherlands Organisation for Scientific Research (NWO) [639.033.403]
- DIAMANT (an NWO mathematics cluster)
- Alexander von Humboldt Foundation, Bonn, Germany
Ask authors/readers for more resources
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 -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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available