AGENT SEARCHING IN A TREE AND THE OPTIMALITY OF ITERATIVE DEEPENING

The agent searching framework models the effort of a search strategy i n terms of the distance traversed by an agent while exploring the sear ch 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 tha t 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 asym ptotically optimal for uninformed search of uniform b-ary trees. In th is paper we prove the stronger result that for agent searching in unif orm b-ary trees, iterative deepening is optimal up to lower-order term s. We also discuss the problems involved in optimally performing agent search in a graph.