Cover Image


View/Hide Left Panel

applications; as director of DARPA/IPTO, he influenced the research agenda on parallel computing; and he became a consultant for the Thinking Machines Corporation, an early maker of massively parallel thinking machines.

Another beautiful example of this style of research occurs in Jack’s work on robot motion planning, which appeared in a series of papers, all entitled “On the Piano Mover’s Problem” and all co-authored with his computational geometer colleague Micha Sharir. There the problem they tackle concerns a robot that wishes to move from a source configuration (say, consisting of a position and an orientation) to a destination configuration but must move through a space cluttered with obstacles while avoiding them. The simplest version of the problem is in a three-dimensional space, where the robot and the obstacles are all polyhedral (geometric solids with straight edges and flat faces); this is the same problem that a “piano mover” faces when removing a polyhedral piano from a rectoidal New York apartment, furnished disorderedly with polyhedral furniture. The basic idea is to simply consider all possible configurations of the robots (say, all possible ordered pairs of positions and orientations) in a configuration space (a six-dimensional space of positions and orientations), which can then be divided into admissible (those configurations not obstructed by any obstacles) and inadmissible (those configurations obstructed by some obstacles) components. Because of the algebraic nature of the configurations, there are only finitely many admissible and inadmissible components, and their boundary is described by algebraic equalities and inequalities (the so-called semialgebraic sets).

All these ideas can be expressed mathematically as sentences in Tarski algebra and then verified algorithmically. In particular, the sentence that asks whether there is a semialgebraic connected component containing both the source and destination configurations also answers the piano mover’s problem. This elegant solution not only energized the research in robot motion planning but also rekindled an interest in “algorithmic algebra,” which has since found many other applications of similar nature: geometric theorem

The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement