Using RRT to solve the piano mover’s problem
Tom Chen
1.
Introduction
1.1
Description of the piano mover’s problem
The piano movers’ problem (PMP) is described as follows: ‘Given a body B and a region bounded by a collection of walls, either find a continuous motion connecting two given positions and orientations of B during which B avoids collisions with the walls, or else establish that no such motion exists.’ Such problems commonly arise in robotics. 1
Fig 1. the demonstration of a 2D Piano Mover’s problem
Figure 1 demonstrates a simple example of this type of problem. The red block, the object, is trying to move down to the bottom space of the map, avoiding colliding with black blocks, the obstacles. 2 This essay will focus on solving PMP in 2-dimensional space where both object and obstacles are rectangular shapes. The final part of this essay will discuss possible expansions to more general cases.
1.2 The rapidly-exploring random tree algorithm
A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search non-convex, high- dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally from samples drawn randomly from the search space and is inherently biased to grow towards the large unsearched areas of the problem. RRTs were developed by Steven M. LaValle and James J. Kuffner Jr. 3
1 See Schwartz 1983: 345. 2 See https://www.coursera.org/learn/robotics-motion-planning/lecture/Yh5fc/2-3-piano-movers-problem. 3 See LaValle 1998.
201
Made with FlippingBook interactive PDF creator