The Piano Mover's Problem Reformulated

D. Wilson, R. J. Bradford, J. H Davenport, M. England

Research output: Book/ReportOther report

34 Downloads (Pure)

Abstract

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.
Original languageEnglish
Place of PublicationBath, U. K.
PublisherDepartment of Computer Science, University of Bath
Publication statusPublished - Jun 2013

Publication series

NameDepartment of Computer Science Technical Report Series
No.CSBU-2013-03
ISSN (Print)1740-9497

Fingerprint Dive into the research topics of 'The Piano Mover's Problem Reformulated'. Together they form a unique fingerprint.

Cite this