Iterative deepening

The iterative deepening approach is usually preferable if the search tree has a large branching factor (i.e., there are many more vertices in the next level than in the current level). This could occur if there are many actions per state and only a few states are revisited. The idea is to use depth-first search and find all states that are distance $ i$ or less from $ {x_{I}}$. If the goal is not found, then the previous work is discarded, and depth first is applied to find all states of distance $ i+1$ or less from $ {x_{I}}$. This generally iterates from $ i=1$ and proceeds indefinitely until the goal is found. Iterative deepening can be viewed as a way of converting depth-first search into a systematic search method. The motivation for discarding the work of previous iterations is that the number of states reached for $ i+1$ is expected to far exceed (e.g., by a factor of $ 10$) the number reached for $ i$. Therefore, once the commitment has been made to reach level $ i+1$, the cost of all previous iterations is negligible.

The iterative deepening method has better worst-case performance than breadth-first search for many problems. Furthermore, the space requirements are reduced because the queue in breadth-first search is usually much larger than for depth-first search. If the nearest goal state is $ i$ steps from $ {x_{I}}$, breadth-first search in the worst case might reach nearly all states of distance $ i+1$ before terminating successfully. This occurs each time a state $ x \not \in
{X_{G}}$ of distance $ i$ from $ {x_{I}}$ is reached because all new states that can be reached in one step are placed onto $ {Q}$. The $ A^*$ idea can be combined with iterative deepening to yield $ IDA^*$, in which $ i$ is replaced by $ C^*(x') + \hat{G}^*(x')$. In each iteration of $ IDA^*$, the allowed total cost gradually increases [777].

Steven M LaValle 2012-04-20