Computing That Serves

New Results in Memory-Efficient Graph Search


Thursday, September 16, 2004 - 11:00am


Eric Hansen, Mississippi State University


Abstract: Graph-search algorithms such as A*, Dijkstra's algorithm, and breadth-first search, have memory as a bottleneck, since they typically store all visited nodes in order to prevent duplicate search effort. However, recent work shows that it is possible to prevent duplicate search effort by storing only nodes on the frontier of the search, and using a divide-and-conquer technique to recover a solution path. This new approach can dramatically improve the scalability of graph-search algorithms. In this talk, I review recent graph-search algorithms that are based on this idea. I also present a surprising new result: when this approach to memory-efficient graph search is adopted, breadth-first search can be more efficient than best-first search.

This talk describes joint work with Rong Zhou, a PhD candidate at Mississippi State University, and Simon Richards, a recent MS graduate.


Eric Hansen is an Associate Professor of Computer Science and Engineering at Mississippi State University. Educated at Harvard University and the University of Massachusetts, he is a recipient of an NSF Career Award, and spent the past summer as a faculty fellow at NASA Ames Research Center. His research interests include decision-theoretic planning, partially observable Markov decision processes, planning via model checking, and heuristic search.