Searching in Large Spaces

I mentioned some recent advances in search algorithms for large (gargantuan) state spaces during the homework recitation. The first one reminds me of SMA*, in so far as SMA* keeps track of f values to guide its re-expansion strategy. Beam-Stack Search is clever, as I recall, in that it keeps track of upper and lower bounds to re-expand portions of the tree in a way reminiscent of the algorithm in 7.2 of homework 1. The second reference is an earlier algorithm by the same author which is not able to reconstruct the solution after finding the goal (for the first time) --- it has to start search over, recursively, to re-generate the solution.

Rong Zhou, Eric A. Hansen: Beam-Stack Search: Integrating Backtracking with Beam Search. ICAPS 2005: 90-98

Rong Zhou, Eric A. Hansen: Breadth-First Heuristic Search. ICAPS 2004: 92-100

The latter paper has been published in multiple places; KR, ICAPS, and AAAI, for example. Hopefully the paper, if not the title, differs in the details or exposition from conference to conference. If so, then one has a better chance of understanding the algorithm by reading all of the multiple publications.

Another line of work by the same author has to do with partially eliminating duplicates in undirected graphs, in the context of searches like the prior ones (i.e., huge spaces). Richard Korf also publishes extensively on techniques for searching large state spaces. For example,

Richard E. Korf: Best-First Frontier Search with Delayed Duplicate Detection. AAAI 2004: 650-657

There are many other authors of course. In the same time frame as all the prior references, there is one last algorithm that comes to mind:

Stefan Edelkamp: External Symbolic Heuristic Search with Pattern Databases. ICAPS 2005: 51-60

Which is interesting because it uses external memory, pattern databases, and symbolic methods.

-Will