The parking-lot attendant at the trendy P’SPACE Club has a tough job. Whenever someone leaves the nightspot, she must retrieve the patron’s car from the crammed lot, often having to move other vehicles out of the way to clear a path to the exit. She has to do it quickly to earn a generous tip, but being efficient can be a real challenge. The attendant’s quandary is an example of what computer scientists and engineers describe as a motion-planning problem. Such challenges can arise when a robot needs to shift bulky crates from place to place within a crowded warehouse or find its way through an obstacle-strewn maze. Motion-planning predicaments also come up in seemingly simple puzzles in which a would-be solver slides blocks along given paths to achieve a desired configuration.
In recent years, sliding-block puzzles have served as proving grounds for novel motion-planning strategies. They have also attracted the attention of computer scientists interested in the fundamental limits of computation—for example, in determining the relative running time or amount of memory a computer would require to solve various types of demanding problems in their most difficult form (SN: 5/6/00, p. 296: Changes of Mathematical State).