Iterative-Deepening-A*: An Optimal Admissible Tree Search

I. Introduction

Heuristic search is ubiquitous in artificial intelligence The performance of most Al systems is . dominated by the complexity of a search algonthm . m the1r mner loops. The best known admJSSJ ble algonthm, A *, has a serious space Iimitation, which can be overcome by applying an iterative-deepening technique. This article descri bes the apphcatJOn of 1terat1ve-deepemng to A *, proves its optimality for exponential tree searches m terms of time, space, and solution cost, and demonstrates its practicality on the Fifteen Puzzle. A more com prehens1ve treatment of iterative-deepening, including Jts apphcatJOn to brute-force, bJ-dJrectJOnal, and two-ferson game searches, can be found in [Korf 85.

The A * algorithm was first proposed by Hart, Nilsson, and Raphael [Hart 68] . Iterative-deepening has no doubt been red1scovered many t1mes independently . The first use of the technique that is documented in the Iiterature is in Slate and Atkin's Chess 4.5 program [Slate . 77] Pear13 initially suggested the 1terat1ve-deepemng extension of A *, and Berliner and Goetsch [Berliner 84] have implemented such . an algonthm concurrently with this work. In add1tJon, StJCkel and Tyson [Stickel 85] have mdependently analyzed iterative-deepening for the spec1al case of brute-force search.

1 This research was supported in part by the Defense Advanced Research ProJects Agency _ under contract N00039-84-C-0165, and by tne National Science Foundation under grant IST-84-18879.

2 Current address Department of Computer Science, University of California, Los Angeles, Ca. 90024

3 personal comm unication, 1984

The complexity of a search algorithm for a given problern will be expressed in terms of two parameters: the cost of a solution to the problem, and the effective branching factor of the algonthm. The cost (c) of a solution to a problern is the cost of the least expensive sequence of operators that map the initial state into a goal state. The effective branching factor (b) of a search algorithm is the ratio of the number of nodes that are generated at a given cost compared to those generated at the next smaller cost, and in generat depends on the accuracy of the heuristic function . We will assume that the branching factor is constant throughout the problern space . The time complexity of a search algorithm in this model is simply the n um ber of nodes that are generated, since we assume that the amount of time is proportional to the num ber of nodes generated. Similarly, since we assume that the amount of space required is proportional to the number of states that are stored, the space complexity of an algorithm in this model will be the num ber of states that must be stored.

Strictly speaking, the results in this paper hold only for trees. The reason is that the iterative-deepening algorithm is inherently depth-first and hence is constrained to explore all paths to a given cutoff. For graphs with cycles, the number of paths can be an exponential function of the number of nodes, and hence a depth-first approach would be dominated by a breadth-first algorithm. The performance of a depth­ first algorithm on a graph is a function of the average num ber of edges that are incident to a given state rather than the num ber of nodes that are adjacent. For trees the edge and node branching factors are equal but can be quite different for some graphs.

This work is focused on searches which produce optimal solutions. We recognize that for most applications, optimal solutions are not required and that their price is often prohibitive . There are occasions, however, when optimal solutions are needed . For example, in assessing the quality of non-optimal solutions, it is often enlightening to compare them to optimal solutions for the same problern instances.

2. A Limitation of A ·

The A * algorithm [Hart 68] works as follows : starting with the initial state, a node is expanded, an evaluation function is applied to its descendents, they are placed in a priority queue, and another node is chosen for expansion. The evaluation function of a node is the sum of the cost so far in reaching that. node from the initial state (g), plus the heuristic. estimate of the cost remaining to reach a goal state from the node (h). The next node expanded is always a nodF of least cost among all those m the queue. To fac1htate companson w1th the iterative-deepening algorithm, we will assume that ties are broken by expanding the most recently generated node among all those of least cost. The algorithm terminates when a goal state is chosen for expansion.

The disadvantage . of A * is its space requirement. Every open node, Je. those on the frontier of the search tree, m ust be stored since any one may eventually becom~ the one with the least cost. Pearl has shown that if the heuristic used by A * exhibits even constant relative error, then the num ber of nodes generated by the algorithm increases exponentially with solution cost [Pearl 84]. He also observes that heunstJcs w1th better accuracy almost never occur in practice. For example, most physical measurements are subject to eonstant relative error. Thus we can concl ude that in practice the n um ber of nod~s on the open Iist is an exponential function of solution cost and as a result is of the same asymptotic order as the total number of nodes generated

As a practical matter, an A * search of most problern spaces will exhaust the available rnemory long before an apprec1able amount of time is used. The reason for this is that the typical ratio of memory to speed in modern computers is a million words of memory for each m1lhon mstructions per second (MIPS) of processor speed. For example, if we can generate a mJ!hon states per minute and require a word to store each state, memory will be exhausted in one minute.

3. lterative-Deepening-A ·

The memory limitat10n . of .A* can be overcome by applymg Jteratlve-deepemng. Iterative-deepening-A * (IDA *) works as follows: Starting from the initial state perform a depth-first search, cutting off a branch whe~ 1ts total cost (g+h) exceeds a given threshold. Repeat the depth-hrst search w1th successively increasing thresholds untll a goal state Js selected for expansion. The threshold starts at the heuristic estimate of the cost of the initial state After each iteration the next· threshold is always the lninimum cost of 'all values that exceeded the previous threshold.

A well-known property of A * is that it always finds a cheapest solution path if the heuristic is admissible or in other words never overestimates the actual distance to the goal [Hart 68] As we will see, his property also holds for iterative-deepening-A * In addition, since IDA *. is a series of depth-first searches, at any g1ven pomt only the stack of states corresponding to the current search path need be stored, and hence the space complexity of this algorithm is linear in the solution cost. Furthermore, we will show that for tree searches IDA * expands the same number of nodes, asymptotically, as A*

Theorem 1: Given an admissible heuristic with constant relative error, then heuristic depth-first iterative-deepening is optimal in terms of solution cost, tune, and space, over the class of admissible best-first tree searches.

Proof: We first consider solution cost. Since the initial cost cutoff of IDA * is the heuristic estimate of the cost of the initial state, and the heuristic never overestimates cost, the cost of the shortest solution cannot be less than the initial cost cutoff. In addition, since the cost cutoff for each succeeding iteration is the minimum value which exceeded the previous cutoff and again the heuristic never overestimates, no path~ can have a cost which lies in a gap between two successive cutoffs. Finally, cons1der an optimal solution path Since the cost function never overestimates, no node on such a path can have a value exceeding the optimal cost. Therefore, this path­ will be generated by IDA * when the threshold equals the optimal cost. Furthermore, no greater cost solution will be found first because no nodes with a greater cost will be expanded on that iteration.

To determine the time used by IDA *, consider the final iteration, in other words the one which finds a solution. It must expand all paths from the initial state whose maximum values are less than the optimal solution cost, plus some number of nodes whose cost equals the optimal solution cost . If A* employs the depth-first tie-breaking rule of "most recently generated", it will also expand these same nodes. Thus, the fmal 1terat10n of IDA * expands the same set of nodes as A * under this tie-breaking rule, and expands each one only once if the graph is a tree.

. IDA* must also expand nodes during the previous 1terat10ns as weil. As mentioned above, if the heuristic used by A * exhibits constant relative error, then the number of nodes generated by the al,gorithm increases exponentially with cost [Pearl 84]. The branching factor b_ is determined by the accuracy of the heunstlc functJOn. We can use this fact to show that the previous iterations of IDA * do not affect the asymptotic order of the total number of nodes generated, as follows.

Let e be the smallest cost difference between two nodes of different cost, and Iet d be cje, or the optimal solut10n cost expressed as a m ultlple of this smallest cost difference . In the worst case, the initial cost threshold would be zero and each successive threshold would increase by e. Under these conditions, d represents the "depth" of the solution or the iterat10n during which the solution is found . Since b was defined as the ratio between the num ber of nodes whose costs differ by e, the nJlmber of nodes at the frontier of iteration d is b . These nodes are expanded once during the final iteration of the search. The nodes at the frontier of iteration d-1 are expanded twice, once during iteration d, and once during iteration d-1 . Similarly, the nodes at iteration d-2 are expanded three times, during iterations d, d-1, and d-2, etc. Thus, the total number of nodes expanded in a heuristic depth-first iterative-deepening search with d 1terat10ns Js

bd+2bd-1+8bd-2+ ... +db Factoring out bd, bd{1+2b-1+sb-2+ ... +db1-d) Letting x=1/b bd{1+2x1+Sx2+ ... +dxd-1) This is less than bd{1+2x 1 +Sx 2 +4x 3 + .. .) which equals bd{1-xf 2 for abs(x}<1

Smce {1-xf2, or {1-1jbf2, IS a constant mdependent of d, 1f b>1 then thJ runmng depth-hrst iteratlve-deepenmg JS O(b ) that Js time of

Thus, IDA* expands the same number of nodes asymptotically, as A* for exponential tree searches. A recent result of Dechter and Pearl [Dechter 83] shows that A * is optimal, in terms of number of nodes generated, over the class of admissible best-first searches with monotone heuristics. A monotone heuristic function is one which never decreases along a path. This is not a serious restriction since given an admissible heuristic, we can trivially construct a monotone one by taking the maximum value along the path so far as the value of each succeeding node on the path [Mero 84]. Therefore, IDA* is asymptotically optimal in terms of time over the class of admissible best-first tree searches.

Finally, we consider the space used by IDA * Since IDA * at any point is engaged in a depth-first search, 1t need only store a stack of nodes which represents the branch of the tree it is expanding. Since it finds a solution of optimal cost, the maximum depth of this stack is d, and hence the maximum amount of space is O(d).

To show that this is optimal, we note that any al_gorithm which uses f(n} time must use at least k log f(n} space for some constant k [Hopcroft 79] The reason is that the algorithm must proceed through f(n) distinct states before Iooping or terminating, and hence m ust be able to store that many states. SJnce storing f(n) states requires log f(n) bits, and log b is d log b, any brute-force algorithm must use kd space, for some constant k . QE D

As mentioned above, most heuristics in practice exhibit at least constant relative error. Thus, we can conclude that heuristic depth-first iterative-deepening is asymptotically optimal for most best-first tree searches which occur in practice. An additional benefit of IDA * over A * is that it is simpler to im plement since there are no open or closed lists to be managed. A simple recursion performs the depth-first search, and an outer loop handles the iterations.

As an empirical test of the practicality of this algorithm, both IDA* and A* were implemented for the Fifteen Puzzle. The implementations were in Pascal and were run on a DEC 2060. The heuristic function used for both was the admissible Manhattau distance heuristic: for each movable tile, the number of grid units between the current position of the tile and its goal position are computed, and these values are summed for all tiles . The two algorithms were tested against 100 randomly generated, solvable initial states. IDA * solved all instances with a median time of 30 CPU minutes, generating over 1.5 million nodes per minute . The average solution Jength was 53 moves and the maximum was 66 moves. A* solved none of the instances since it ran out of space after about 30,000 nodes were stored. As far as we know, this is the first algorithm to find optimal solutions to randomly generated instances of the Fifteen Puzzle within practical resource Iimits. An additional observation is that in experiments with the Eight Puzzle, even though IDA * generated more nodes than A *, it actually ran faster than A * on the same problern mstances, due to the reduced overhead per node. The actual data from these experiments are reported in [Korf 85] .

4. Conclusions

The best known admissible search algorithm, A* . is severely hm1ted by . 1ts exponentJal space requirement. An 1teratJve~deepemng verswn of A * uses only linear space, and IS asymptotJcally optimal in terms of cost of solutwn, runmng time, and space reqmred for exponent1al tree searches .. Since almost all heuristic searches have exponentJal complexity iterative­ deepenmg-A * IS an optimal admissible tr~e search in practice . In addition, it was easier to implement and ran faster than A* in our experiments.

Acknow ledgments

I would like to acknowledge the helpful comments of M1ke Lebowttz, Andy Mayer, and Mike Townsend who read an earher draft of this paper, and several helpful dJscussJons w1th Hans Berliner and Judea Pearl concerning this research.. In addition, Andy Mayer 1mplemented the A * verswn that was compared with IDA*

Heferences

[Berliner 84] Berliner, Hans, and Gordon Goetsch. A. quantitative study of search methods and the effect of constraint satisfaction . technical report CMU­ CS-84-147, Department of Com_puter Science, Carnegie­ Mellon University, Pittsburgh, Pa, July, 1984.

[Dechter 83] Dechter, Rina, and Judea Pearl. The ()ptimality of A * revisited . Proceedings of the National Conference on Artificial Intelligence, Washmgton , D.C., August, 1983, pp . 95-99.

fHart 681 Hart, Peter E , Nils J Nilsson, and Bertram ltaphael. "A formal basis for the heuristic determination of minimum cost paths." IEEE Transactions on Systems Science and Cybernetics SSC-4, 2 (1968)

fHoJ>croft 7g] Hopcroft, John E, and Jeffrey b Ullman Jntroduction to Automata Theory, Languages, and Computation. Addison-Wesley, Readmg, Mass, 1979.

[Korf 86] Korf, Richard E . "Depth-first iterative­ aeepeni ng An optimal admissible tree search'' Arttficial Jntelltgence to appear (1985).

~ero 84] Mero, Laszlo "A heuristic search algorithm with modifiable estimate" Artificial Intelligence 23 (1984)

[Pearl 841 Pearl , Judea Heuristics . Addison-Wesley, t:?.eadmg, M:ass, 1984.

[Slate 771 Slate, David J, and Lawrence R Atkin. CHESS 4.S - The Northwestern University chess pr~gram . In Frey, Peter W, Ed , Chess Skill in Man and Machine, Springer-Verlag, New York, 1977.

[Stickel 86] Stickel, Mark E, and W. Mabry Tyson . An analys1s of consecutJvely bounded depth-first search w1th apJJhcatwns m automated deduction. Proceedings of the Internatwnal Jomt Conference on Artificial Intelligence (IJCAI-85), Los Angeles, Ca , August, 1985.