Agent searching in a tree and the optimality of iterative deepening

Abstract

The agent searching framework models the effort of a search strategy in terms of the distance traversed by an agent while exploring the search space. The framework has been found to be useful in modeling search problems where the cost of backtracking and retracing search paths is important in determining search complexity. In this paper we show that depth-first iterative deepening (DFID) strategies are optimal for an agent searching in a line, in m concurrent rays, and in uniform b-ary trees. In the conventional search model it is known that DFID is asymptotically optimal for uninformed search of uniform b-ary trees. In this paper we prove the stronger result that for agent searching in uniform b-ary trees, iterative deepening is optimal up to lower-order terms. We also discuss the problems involved in optimally performing agent search in a graph.