The Piano Mover's Problem Reformulated


Wilson, D., Bradford, R. J., Davenport, J. H. and England, M., 2013. The Piano Mover's Problem Reformulated. Department of Computer Science, University of Bath. (Department of Computer Science Technical Report Series; CSBU-2013-03)

Related documents:

PDF (CSBU-2013-03) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (903kB) | Preview


    We revisit the classic problem of moving ladders of various lengths through a right-angled corridor. It has long been known that it is theoretically possible to tackle this problem through cylindrical algebraic decomposition (CAD): the valid positions of the ladder are described through polynomial equations and inequalities, which are then used to create a sign-invariant CAD. However, this formulation is too complex for use with current CAD technology, despite much progress in both CAD theory and hardware. We present a new formulation of the problem, by first considering the invalid positions of the ladder, negating this formula and using this as input for Qepcad (CAD software). We are then able to construct CADs for various lengths of ladder and analyse these through Qepcad’s two-dimensional plots functionality. We speculate on the reason our new formulation is more appropriate for the problem, suggest alternative formulations and discuss future work.


    Item Type Reports/Papers
    CreatorsWilson, D., Bradford, R. J., Davenport, J. H. and England, M.
    DepartmentsFaculty of Science > Computer Science
    ID Code36713


    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...