Logic in the Blocks

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.