Planning Algorithms: When Optimal Is Just Not Good Enough

Abstract

Planning is a crucial capability - it enables robots to be autonomous and it helps people save time and conserve natural resources. Unfortunately, most planning problems are NP-hard or worse, so algorithms that guarantee optimal solutions are often impractical. In this talk, I'll discuss alternative guarantees on performance, such as bounded suboptimality and anytime convergence to optimality, and show how a new generation of more-informed heuristic search algorithms can meet them effectively in practice. I'll argue that, in addition to serving as the underlying engines of intelligent systems, heuristic search algorithms themselves can be usefully considered as rational agents.

Wheeler Ruml is an Associate Professor of Computer Science at the University of New Hampshire, where he leads the UNH AI Group. His current interests include heuristic search, optimization, and robotics, with an emphasis on planning under time pressure. He was selected for the DARPA Computer Science Study Panel, an NSF CAREER award, and the UNH Outstanding Assistant Professor Award. Before joining UNH, he led a team at Xerox PARC that used AI techniques to build the world's fastest printer. And yes, Wheeler is his real name!