文章基本信息

标题：Motion planning with pulley, rope, and baskets
本地全文：下载
作者：Christian E.J. Eggermont ; Gerhard J. Woeginger
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：14
页码：374-383
DOI：10.4230/LIPIcs.STACS.2012.374
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：planning and scheduling; computational complexity