Abstract: Heuristics are important for improving the performance of search-based algorithms. Pattern databases are the most common form of memory-based heuristics, and have been well-studied over the last decade. But, in many domains pattern databases are ineffective at improving heuristic estimates. In this talk I will describe several of these domains, including path-finding for commercial video games, and motivate how improved heuristics can be used. I will then present new research on canonical and differential heuristics. These heuristics provide an order of magnitude or larger reduction in search effort over the previous best-known techniques.

Short Bio: Nathan Sturtevant is currently an adjunct professor in Computer Science at the University of Alberta, in Edmonton, Canada. He received his bachelor's degree from UC Berkeley and his PhD in from UCLA in 2003. His main research focus is in heuristic search with an interest in single- and multi-player games. Nathan's techniques have been implemented in BioWare's upcoming game, Dragon Age (http://dragonage.bioware.com/). Nathan is also known as the author of the popular 1990s Mac shareware game, Dome Wars.