Lookahead Pathologies for Single Agent Search

1 Lookahead Pathologies in Real-time Single-agent Search

Complete search methods such as A* [Hart eta!., 1968] and IDA* [Korf, 1985] produce optimal solutions when based on an admissible and monotonic heuristic function. The primary drawbacks are the exponential running time and the necessity to wait until the search completes before the first action can be taken [Korf, 1990]. This limits the applicability of com­ plete search in practice as the deliberation time per action can be severely limited [Higgins, 2002], the domain model can be expensive [Bulitko and Wilkins, 2002], the goal states can be difficult to recognize [Levner et al., 2002] . Consequently, despite numerous advances in improving heuristic functions [Korf and Taylor, 1996; Culberson and Schaeffer, 1994; Reinefeld, 1993; Korf, 1997], incomplete real-time/on-line search methods remain the practical choice for complex real­ life problems.

Various incomplete search methods have been proposed including: RTA* [Korf, 1990], RTDP [Barto eta/., 1995], SRTA *, and DTA * [Russell and Wefald, 1991]. Such algo­ rithms base their decisions on heuristic information collected from a partial tree expansion (lookahead) prior to reaching the goal state. Since the heuristic function is generally inac­ curate and the search is incomplete, suboptimal solutions can be produced even with admissible and consistent heuristics.

It is widely believed that looking ahead deeper improves the chances of taking the right action. Consequently, a con­ siderable amount of effort has been put into increasing the lookahead depth by using selective search (search extensions) and hardware and software optimizations.

In this paper we demonstrate that looking ahead deeper can actually decrease the chances of taking the optimal ac­ tion even when admissible and consistent heuristic functions are used.

2 Related Past Research & Our Novel Contributions

Lookahead pathologies within the mini-max search in two­ player games have been investigated extensively in the past. In [Nau, 1982; 1983; Beal, 1980; 1982; 1983; Bratko and Gams, 1982; Pearl, 1983 ], the primary cause of pathologies was deemed to be the independence of heuristic values of the leaf nodes. Such games were called non-incremental. Large branching factors were also considered contributing to a pathology. Later, [Michon, 1983] added non-inertness (i.e., the constant branching factor) to the "black list" of properties that can cause a pathology.

The efforts presented in this paper differ from the past work in several key areas: (i) we demonstrate lookahead pathologies in single-agent heuristic search; (ii) pathologies are shown to take place even when the true and heuris­ tic values of sibling states are correlated (i.e., in incre­ mental domains); (iii) unlike research in [Schriifer, 1986; Beal, 1980] that dealt with two-valued (win/loss) heuristics, we consider real-valued heuristic functions; (iv) we show pathologies with the smallest non-trivial branching factor (two); (v) pathologies are demonstrated for admissible and consistent heuristic functions.

3 Framework

In this study we consider a single-agent heuristic search in a discrete state domain with a finite number of deterministic actions. The states (setS) and actions (set A) form a directed graph with certain specified vertices representing the goal states. The edges (actions) are weighed with action costs:

c : A ---+ R. The agent is provided with a perfect domain model : 6 : S x A ---+ S .

We define the true distance-to-goal function h*(s) as the sum of action costs along the shortest path from state s to the closest goal state. Generally speaking, the agent uses an approximation h to the unavailable h* . The approximation is typically inaccurate insomuch as: :ls E S [h*(s) =/= h(s)J .

For a fixed starting state s, function g( s') is defined as the sum of action costs along the shortest path from s to s'. Fi­ nally, the sum of h or h* and g is typically denoted by f or j* . It easy to see that f* remains constant along any opti­ mal path from a fixed state s to the closest goal. Also note that, for any state s', action a 1 is inferior to action a2 iff j* ( 6 ( s', a 1)) > j* ( 6 ( s', a2)) .

Located in state s, the agent can use its perfect model 6 to predict the states it will get to upon taking various sequences of actions. A binary lookahead tree is illustrated in Figure 1. For the sake of clarity and simplicity we will be using small binary lookahead trees to illustrate the discussion throughout the paper.

The lookahead policy rr( s, p) operates as follows: (i) start in the current state s; (ii) construct the lookahead search tree of p plies deep by envisioning terminal states of all action se­ quences of p actions (whenever possible); (iii) evaluate the leaf nodes of the lookahead tree using the f function and se­ lect the minimum-valued state; (iv) output the single action leading to selected leaf state (resolve ties randomly).

Depending on the lookahead tree, random tie resolu­ tion, and the approximate heuristic f, the action a = rr( s,p) output by rr(s , p) can be suboptimal: :la* =/= a [f*(6(s , a* )) < j*(6(s, a))]. The probability of such an er­ ror for state s E S is denoted by E1-r( s, p) . Additionally, we will consider the expected value of Err( s, p) over the states s. Such state-independent quantity will be referred to as Err (p).

The combination of domain and heuristic function h (f) is called pathological iff :lp1 < p2 [Err(s ,pi) < Err(s,p2)]. The corresponding state-independent version is: :lp1 < P2 [Err(pl) < Err(p2)]. The intuitive meaning is quite transparent: lookahead search is pathological iff looking deeper ahead is expected to increase the chances of taking a suboptimal action.

We adopt the following standard terminology. Function h is called admissible iff Vs E S [h(s) ~ h*(s)]. It is called consistent iff Va E A,s E S[h(s) ~ c(a) + h(6(s ,a)) ]. It can be shown that consistency of h is equivalent to non-decreasing monotonicity of f = g + h: Va E A, s E S [f(s) ~ f(6(s , a))]. In the following we will assume that the true h* satisfies the mini-min relation: Vs [h*(s) = minaEA (c(a) + h*(6(s, a)))] and h* is, there­ fore, consistent and, trivially, admissible.

4 Admissible & Consistent Heuristics

Complete searches (e.g., A* and IDA*) produce optimal so­ lutions with admissible heuristics. Thus, much effort has gone into derivation of admissible heuristics either manu­ ally or automatically (e.g., [Korf and Taylor, 1996; Prieditis, 1993]). Consistency of h leads to non-decreasing monotonic­ ity off and often speeds up complete searches conducted by A */IDA*. Incomplete searches (e.g., RTA *)can produce sub­ optimal solutions even with consistent and admissible heuris­ tics. It is widely believed, however, that deeper lookahead reduces chances of such errors. Remarkably, this is not nec­ essarily the case.

Consider the binary lookahead tree in Figure 2. Each node is shown with its true value f* ( s) inside the circle. For each state s, heuristic f(s) is drawn uniformly from [f(sparem) , f*(s)] (indicated with the 'rv' in the boxes next to the circles). The value (A) of the root state is drawn from [0, j*(sroot)]. This makes the f function admissible and monotonically non-decreasing.

We will refer to the drawn values of f as A, B , C, D , E , F, G (illustrated in the figure) . Assume that uD > 1, ua > up > 1. By definition, the lookahead will be_ pathological iff Err(sroot> 2) > Err(s,001 , 1). The p_robab1~1ty of taking the suboptimal action (i.e., going to the nght child of the root node) with the lookahead of one is :

Similarly we derive an expression for the lookahead of two: Err(sr00t, 2) which can not be reproduced in this short paper*. By analyzing the difference of the two expressions we arrive at a criterion of pathology.

A concrete illustration of this phenomenon can be found in Figure 3. The tree on the left is non-pathological as: Err(srooll1) ~ 0.0945 > 0.0226 ~ Err(srooll 2). The tree on the right, however, is indeed pathological. Averaged over I 0 million trials: Err( Srooll 1) ~ 0.4607 < 0.4861 ~ Err(sroot, 2).

5 Future Work & Conclusions

ln practice, lookahead pathologies with real-time (single­ agent or two-player) search are infrequently observed even when inadmissible heuristics are used ( cf., [Thompson, 1982] for the game of chess). Consequently, future work directions include: (i) identification of the properties of practically used heuristic functions (e.g., Manhattan distance in the 8 puzzle) that are responsible for the lack of pathologies, (ii) extension of the current formal analysis to lookahead trees with a vari­ able branching factor and a deeper lookahead, (iii) methods for on-line and off-line pathology detection and correction and (iv) connections between the probability of taking sub­ optimal actions and a decrease in the cumulative expected re­ ward.

Acknowledgements

Rene Levia, Dan Lizotte, Omid Madani, Xin Li, and Yiping Zhou have contributed in various ways. We are grateful for the funding from the University of Alberta, NSERC, and the Alberta Ingenuity Centre for Machine Learning.