Motion Planning with Pulley, Rope, and Baskets |
| |
Authors: | Christian E. J. Eggermont Gerhard J. Woeginger |
| |
Affiliation: | 1. Department of Mathematics and Computer Science, TU Eindhoven, P.O. Box 513, 5600 MB, Eindhoven, Netherlands
|
| |
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 $varPi_{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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|