Latest Issue of Science News


Logic in the Blocks

Simple puzzles can give computers an unexpectedly strenuous workout

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.

Note: To comment, Science News subscribing members must now establish a separate login relationship with Disqus. Click the Disqus icon below, enter your e-mail and click “forgot password” to reset your password. You may also log into Disqus using Facebook, Twitter or Google.

This article is available only to subscribing members. Join SSP today or Log in.