ITERATIVE BROADENING

Conventional blind search techniques generally assume that the goal nodes for a given problem are distributed randomly along the fringe of the search tree. We argue that this is often invalid in practice and suggest that a more reasonable assumption is that decisions made at each point in the search carry equal weight. We go on to show that a new search technique called iterative broadening leads to orders-of-magnitude savings in the time needed to search a space satisfying this assumption; the basic idea is to search the space using artificial breadth cutoffs that are gradually increased until a goal is found. Both theoretical and experimental results are presented.