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.