The Piano Mover's Problem Reformulated

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

Research output: Book/ReportOther report

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.
LanguageEnglish
Place of PublicationBath, U. K.
PublisherDepartment of Computer Science, University of Bath
StatusPublished - Jun 2013

Publication series

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

Fingerprint

Ladders
Decomposition
Computer aided design
Polynomials
Hardware

Cite this

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

The Piano Mover's Problem Reformulated. / Wilson, D.; Bradford, R. J.; Davenport, J. H; England, M.

Bath, U. K. : Department of Computer Science, University of Bath, 2013. (Department of Computer Science Technical Report Series ; No. CSBU-2013-03).

Research output: Book/ReportOther report

Wilson, D, Bradford, RJ, Davenport, JH & England, M 2013, The Piano Mover's Problem Reformulated. Department of Computer Science Technical Report Series , no. CSBU-2013-03, Department of Computer Science, University of Bath, Bath, U. K.
Wilson D, Bradford RJ, Davenport JH, England M. The Piano Mover's Problem Reformulated. Bath, U. K.: Department of Computer Science, University of Bath, 2013. (Department of Computer Science Technical Report Series ; CSBU-2013-03).
Wilson, D. ; Bradford, R. J. ; Davenport, J. H ; England, M. / The Piano Mover's Problem Reformulated. Bath, U. K. : Department of Computer Science, University of Bath, 2013. (Department of Computer Science Technical Report Series ; CSBU-2013-03).
@book{088300e8ad264ad58d155f04558d5e78,
title = "The Piano Mover's Problem Reformulated",
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-dimensionalplots functionality. We speculate on the reason our new formulation is more appropriate for the problem, suggest alternative formulations and discuss future work.",
author = "D. Wilson and Bradford, {R. J.} and Davenport, {J. H} and M. England",
year = "2013",
month = "6",
language = "English",
series = "Department of Computer Science Technical Report Series",
publisher = "Department of Computer Science, University of Bath",
number = "CSBU-2013-03",

}

TY - BOOK

T1 - The Piano Mover's Problem Reformulated

AU - Wilson, D.

AU - Bradford, R. J.

AU - Davenport, J. H

AU - England, M.

PY - 2013/6

Y1 - 2013/6

N2 - 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-dimensionalplots functionality. We speculate on the reason our new formulation is more appropriate for the problem, suggest alternative formulations and discuss future work.

AB - 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-dimensionalplots functionality. We speculate on the reason our new formulation is more appropriate for the problem, suggest alternative formulations and discuss future work.

M3 - Other report

T3 - Department of Computer Science Technical Report Series

BT - The Piano Mover's Problem Reformulated

PB - Department of Computer Science, University of Bath

CY - Bath, U. K.

ER -