"How to Use Disk Storage to Detect Duplicate Nodes in Best-First Search"

9/26/2003: 10:30am - 12:00pm
11th Floor Large Conference Room

Abstract: Many search algorithms are limited by the memory needed to store nodes in order to detect duplicates. Large-capacity disks can greatly expand the amount of storage available, but randomly accessing a disk is extremely slow. Rather than checking newly-generated nodes immediately against a list of previously-generated nodes, we append them to a disk file, then sort the file, and finally scan the sorted file in one pass to detect and remove duplicate nodes. This allows memory-bounded searches to make effective use of large-capacity disk storage. It also speeds up such searches that fit entirely in memory, by improving cache performance. We present algorithms that implement this idea for breadth-first search, and illustrate it by performing complete breadth-first searches of sliding-tile puzzles, and finding optimal solutions to the 22-disk, 4-peg Towers of Hanoi puzzle.

About Rich Korf: Richard Korf is a Professor of computer science at the University of California, Los Angeles. He received his B.S. from M.I.T. in 1977, and his M.S. and Ph.D. from Carnegie-Mellon University in 1980 and 1983, respectively, all in computer science. From 1983 to 1985, he served as Herbert M. Singer Assistant Professor of Computer Science at Columbia University. His research is in the areas of problem solving, planning, and heuristic search in artificial intelligence. He is the author of "Learning to Solve Problems by Searching for Macro-Operators" (Pitman, 1985). He serves on the editorial board of the {\it Journal of Applied Intelligence} and {\it Artificial Intelligence}. Dr. Korf is the recipient of a 1985 IBM Faculty Development Award, a 1986 NSF Presidential Young Investigator Award, the first UCLA Computer Science Department Distinguished Teaching Award in 1989, and the UCLA Engineering School First Annual Student's Choice Award for Excellence in Teaching in 1996. He is a Fellow of the American Association for Artificial Intelligence.

Last updated: Mon Jun 19 17:44:06 2006