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