Faster Heuristic Search Algorithms for Planning with Uncertainty and Full Feedback

1 Introduction

Heuristic search algorithms have been successfully used for computing optimal solutions to large deterministic problems (e.g., [Korf, 1997]). In the presence of non-determinism and feedback, however, solutions are not action sequences but policies, and while such policies can be characterized and computed by dynamic programming (DP) methods [Bellman, 1957; Howard, 1960], DP methods take all states into account and thus cannot scale up to large problems [Boutilier et al., 1999]. Recent algorithms like RTDP [Barto et al., 1995] and LAO* [Hansen and Zilberstein, 2001], combine the strength of Heuristic Search and Dynamic Programming methods by exploiting knowledge of the initial state so and an .admiss~­ ble heuristic function (lower bound) h for computmg opti­ mal policies without having to evaluate the entire space . . In this paper we aim to contribute to the theory and practice of Heuristic Search/Dynamic Programming methods by for­ mulating and analyzing three new HS/DP algorithms. The first algorithm, called FIND-and-REVISE is a general schema

Hector Geffner

Departamento de Tecnologfa ICREA- Universitat Pompeu Fabra Barcelona 08003, Espana

hector.geffner@tecn.upf.es

that comprises a loop in which states reachable from so and the greedy policy that have Bellman residuals greater than a given E (we call them 'inconsistent' states), are found and~~­ dated until no one is left. FIND-and-REVISE makes explicit the basic idea underlying HS/DP algorithms, including RTDP and LAO*. We prove the convergence, complexity, and op­ timality of FIND-and-REVISE, and introduce the second al­ gorithm, HDP, that builds on it, and adds a la?elfng m~ch­ anism for detecting solved states based on TarJan s efficient strongly-connected components procedure [Tarjan, 1972]. A state is solved when it reaches only 'consistent' states, and solved states are skipped in all future searches. HDP termi­ nates when the initial state is solved. HDP inherits the con­ vergence and optimality properties of t.h~ gen~ral F.IN.D-and­ REVISE schema and is strongly competitive with ex1stmg ap­ proaches. The third algorithm, HDP(i),.is like HDP, ~xc~pt that while HDP computes a value functiOn by enforcmg Its consistency over all reachable states (i .e., reachable from so and the greedy policy), HDP( i) enforces consis~ency ove: the 'likely' reachable states only. We show that ~his ~pp:oxima­ tion, suitably formalized, can lead to great savmgs m time and memory, with no much apparent loss in quality, when transi­ tions have probabilities that differ greatly in value.

Our motivation is twofold: to gain a better understanding of HS/DP methods for planning with uncertainty, and to de­ velop more effective HS/DP algorithms for both optimal and approximate planning.

2 Preliminaries

2.1 Model

We model non-deterministic planning problems with full feedback with state models that differ from those used in the classical setting in two ways: first, state transitions become probabilistic; second, states are fully observable. The result­ ing models are known as Markov Decision Processes (MDPs) and more specifically as Stochastic Shortest-Path Problems [Bertsekas, 1995], and they are given by: 1

MI. a discrete and finite state spaceS,

M2. an initial state so E S,

M3. a set G ~ S of goal states,

M4. actions A(s) ~A applicable in each states E S,

MS. transition probabilities Pa(s'/s) for s E S, a E A(s), M6. positive action costs c( a, s) > 0, and M7. fully observable states.

1 For discounted and other formulations, see [Puterman, 1994].

Due to the presence of full feedback (M7) and the standard Markovian assumptions, the solution of an MOP takes the form of a function 1r mapping states s into actions a E A(s). Such a function is called a policy. A policy 1r assigns a prob­ ability to every state trajectory s0 , s 1 , s2 , .. . starting in state s0 which is given by the product of the transition probabili­ ties Pa, (si+1 ls;) where a;= 1r(s;). If we further assume that actions in goal states have no costs and produce no changes (i.e., c(a, s) = 0 and Pa(sls) = 1 if s E G), the expected cost associated with a policy 7r starting in state s0 is given by the weighted average of the probability of such trajectories times their cost L~o c( 1r( s;), s;). An optimal solution is a policy 1r* that has a minimum expected cost for all possible initial states. An optimal solution is guaranteed to exist provided the following assumption holds [Bertsekas, 1995]:

M8. the goal is reachable from every state with non-zero probability.

Since the initial state s0 of the system is fixed, there is in principle no need to compute a complete policy but a partial policy prescribing the action to take in the states that can be reached following the policy from s0 . Traditional dynamic programming methods like value or policy iteration compute complete policies, while recent heuristic search DP methods like RTOP and LAO* compute partial policies. They achieve this by means of suitable heuristic functions h( s) that provide admissible estimates (lower bounds) of the expected cost to reach the goal from any states.

2.2 Dynamic Programming

Any heuristic or value function h defines a greedy policy 7rh :

where the expected cost from the resulting states s' is as­ sumed to be given by h(s'). We call 7rh(s) the greedy action in s for the value function h. If we denote the optimal (ex­ pected) cost from a states to the goal by V*(s), it is well known that the greedy policy 7rh is optimal when h is the op­ timal cost function, i.e. h = V*.

While due to the possible presence of ties in (1 ), the greedy policy is not unique, we will assume throughout the paper that these ties are broken systematically using an static order­ ing on actions. As a result, every value function V defines a unique greedy policy 1rv, and the optimal cost function V* defines a unique optimal policy 1rv·. We define the relevant states as the states that are reachable from s0 using this opti­ mal policy; they constitute a minimal set of states over which the optimal value function needs to be defined. 2

Value iteration (vi) is a standard dynamic programming method for solving MOPs and is based on computing the op­ timal cost function V* and plugging it into the greedy policy ( 1 ). This optimal cost function is the only solution to the fixed point equation:

2 This definition of 'relevant states' is more restricted than the one in (Barto et al., 1995] that includes the states reachable from so by any optimal policy.

also known as Bellman's equation. For stochastic short­ est path problems like Ml-M8 above, the border condition V(s) = 0 is also needed for goal states s E G. Value it­ eration solves (2) by plugging an initial guess for v· in the right-hand side of (2) and obtaining a new guess on the left­ hand side. In the form of VI known as asynchronous value iteration [Bertsekas, 1995], this operation can be expressed as:

where Vis a vector of size lSI initialized arbitrarily (normally to 0) and where the equality in (2) is replaced by assignment. The use of expression (3) for updating a state value in V is called a state update or simply an update. In standard (syn­ chronous) value iteration, all states are updated in parallel, while in asynchronous value iteration, only a selected subset of states is selected for update at a time. In both cases, it is known that if all states are updated infinitely often, the value function V converges eventually to the optimal value func­ tion. From a practical point of view, value iteration is stopped when the Bellman error or residual defined as the difference between left and right in (2):

over all states s is sufficiently small. In the discounted MOP formulation, a bound on the policy loss (the difference be­ tween the expected cost of the policy and the expected cost of the optimal policy) can be obtained as a simple expres­ sion of the discount factor and the maximum residual. In stochastic shortest path models, no similar closed-form bound is known, although such bound can be computed [Bertsekas, 1995]. Thus, one can execute value iteration until the max­ imum residual becomes smaller than a given E, then if the bound on the policy loss is higher than desired, the same pro­ cess can be repeated with a smaller E (e.g., E/2) and so on (see [Hansen and Zilberstein, 2001] for a similar idea). For these reasons, we will take as our basic task below, the computa­ tion of a value function V ( s) with residuals no greater than a given parameter E > 0.

One last definition and a few known results before we pro­ ceed. We say that cost function V is monotonic iff

for every s E S. Notice that a monotonic value function never decreases when updated, and moreover, must increase by more than E when updated in a state s whose residual is greater than E. As in the deterministic setting, a non­ monotonic cost function can be made monotonic by simply taking the value V(s) to be the max between V(s) and the right-hand side of Bellman's equation. The following results are well known.

Theorem 1 a) The optimal values V* ( s) of a model M 1-MB are non-negative and finite; b) the monotonicity and admis­ sibility of a value function are preserved through updates.

start with a lower bound function V := h repeat

I until no such state is found 1·eturn V

FIND a states in the greedy graph Gv with R(s) > c: REVISE Vats

Algorithm 1: FIND-and-REVISE

3 Find-and-Revise

The FIND-and-REVISE schema is a general asynchronous VI algorithm that exploits knowledge of the initial state an? an admissible heuristic for computing optimal or nearly optimal policies without having to evaluate the entire space. Let us say that a value function V is f.-consistent (inconsistent) over a states when the residual overs is no greater (greater) than f., and that V itself is f.-consistent when it is f.-consistent over all the states reachable from s0 and the greedy policy 7ry. Then FIND-and-REVISE computes an f.-consistent value function by simply searching for inconsistent states in the greedy graph and updating them until no such states are left; see Alg. I.

The greedy graph Gv refers to the graph resulting from the execution of the greedy policy 7ry starting in so; i.e., so is the single root node in G v ,and for every non-goal state s in G v, its children are the states that may result from executing the action 1r(s) ins.

The procedures FIND and REVISE are the two parameters ~f the FIND-and-REVISE procedure. For the convergence, opti­ mality, and complexity of FIND-and-REVISE, we assume that FIND searches the graph systematically, and REVISE of V at s updates V at s (and possibly at some other states), both operations taking O(ISI) time.

Theorem 2 (Convergence) For a planning model Ml-M8 with an initial value function h that is admissible and monotonic, FIND-and-REVISE yields an f.-consistent value function in a number of loop iterations no greater than C 1 LsES V*(s)- h(s), where each iteration has time com­ plexity O(ISI).

Theorem 3 (Optimality) For a planning model M 1 -M8 with an initial admissible and monotonic value function, the value function computed by FIND-and-REVISE approaches the op­ timal value function over all relevant states as f. goes to 0.

4 Labeling

We consider next a particular instance of the general FIND­ and-REVISE schema in which the FIND operation is carried out by a systematic Depth-First Search that keeps track of the states visited. In addition, we consider a labeling scheme on top of this search that detects, with almost no overhead, when a state is solved, and hence, when it can be skipped in all future searches. A state s is defined as solved when the value function V is f.-consistent overs and over all states reachable from s and the greedy policy 7ry. Clearly, when this condition holds no further updates are needed ins or the states reachable from s. The resulting algorithm terminates when the initial state so is solved and hence when an f.-consistent value function has been obtained.

Due to the presence of cycles in the greedy graph, bottom­ up algorithms common in AO* implementations cannot be used. Indeed, if s is reachable (in the greedy graph) from a descendants' of s, then bottom-up approaches will be un­ able to label either state as solved. A labeling mechanism that works in the presence of cycles is presented in [Bonet and Geffner, 2003] for improving the convergence of RTDP. Basi­ cally, after each RTDP trial, an attempt is made to label the last unsolved state s in the trial by triggering a systematic search for inconsistent states from s. If one such state is found, it is updated, and a new trial is executed. Otherwise, the state s and all its unsolved descendants are labeled as solved, and a new cycle of RTDP trials and labeling checks is triggered. Here we take this idea and improve it by removing the need of an extra search for label checking. The label checking will be done as part of the FIND (DFS) search with almost no over­ head, exploiting Tarjan's linear algorithm for detecting the strongly-connected components of a directed graph [Tarjan, 1972], and a correspondence between the strongly-connected components of the greedy graph and the minimal collections of states that can be labeled at the same time.

Consider the (directed) greedy graph Gv and the relation ', .... .' between pairs of states s and s' that holds when s = s' or when s is reachable from s' and s' is reachable from s in G v. The strongly-connected components of G v are the equivalence classes defined by this relation and form a parti­ tion of the set of states in Gv. For example, for the greedy graph in Fig. 1, where 2 and 4 are terminal (goal) states, the components are cl = { 4}, c2 = {1, 5}, c3 = {2}, and C4 = {0, 3, 6, 7}. Tarjan's algorithm detects the strongly­ connected components of a directed graph in time O(n +e) while traversing the graph depth-first, where n stands for the number of states (n ~ lSI in Gv) and e for the number of edges.

The relationship between labeling and strongly-connected components in Gv is quite direct. Let us say first that a component C is f.-consistent when all states s E C are f.­ consistent, and that a component C is solved when every state s E C is solved. Let's then define �~ as the graph whose nodes are the components of G v and whose directed edges are C ~ C' when some state in C' is reachable from some state in C. Clearly, �~ is an acyclic graph as two compo­ nents which are reachable from each other will be collapsed into the same equivalence class. In addition,

1. a state s is solved iff its component C is solved, and furthermore,

1. a component C is solved iff C is consistent and all components C', C -+ C', are solved.

The problem of labeling states in the cyclic graph Gv can thus be mapped into theJroblem of labeling the components in the acyclic graph Gv, which can be done in bottom up fashion.

From Fig. I is easy to visualize the component graph asso­ ciated to the greedy graph. Thus, if 2 is the only inconsistent state, for example, we can label the components cl and c2 as solved, while leaving c3 and c4 unsolved.

The code that simultaneously checks in depth-first fashion the consistency of the states and the possibility of labeling them is shown in Alg. 2. We call the resulting algorithm, HOP. HOP inherits its convergence and optimality properties from the FIND-and-REVISE schema and the correctness of the labeling mechanism.

We do not have space to explain HOP code in detail, yet it should be clear to those familiar with Tarjan's algorithm; in particular, the use of the state visit number, S.IDX, and the 'low-link' number, S.LOW, for detecting when a new compo­ nent has been found. The flag flag and the (normal) propa­ gation of the visit numbers prevent a component from being labeled as solved when it is inconsistent or can reach an in­ consistent component.

Theorem 4 (Correctness) The value function computed by HOP for a planning model Ml-M8, given an initial admissible and monotonic value function, is f.-consistent.

5 Experimental Results

We now evaluate the performance of HOP in comparison with other recent Heuristic Search/DP algorithms such as the sec­ ond code for LAO* in [Hansen and Zilberstein, 2001], that we call Improved LAO* (!LAO*), and Labeled RTDP (LRTDP), a recent improvement of RTDP that accelerates its convergence [Bonet and Geffner, 2003]. We use parallel Value Iteration as the baseline. We've implemented all these algorithms in C++ and the experiments have been run on a Sun Fire-280R with 750 MHz and 1Gb of RAM.

The domain that we use for the experiments is the racetrack from [Barto et al., 1995]. The states are tuples (x, y, dx, dy) that represent the position and speed of the car in the x, y dimensions. The actions are pairs a = (ax, ay) of instan­ taneous accelerations where ax, ay E { -1, 0, 1 }. Uncer­ tainty in this domain comes from assuming that the road is 'slippery' and as a result, the car may fail to accelerate or desaccelerate. More precisely, an action a = (ax, ay) has its intended effect with probability 1 - p, while with prob­ ability p the action effects correspond to those of the action a0 = (0, 0) . Also, when the car hits a wall, its velocity is set to zero and its position is left intact (this is different than in [Barto et al., 1995] where for some reason the car is moved to the start position).

We consider the track large-b from [Barto eta!., 1995], h- track from [Hansen and Zilberstein, 2001], 3 and five other tracks (squares and rings of different size). Informa­ tion about these instances can be found in the first three rows

3 Taken from the source code of LAO*.

HDP( s : state) begin end while ~s.SOLVED do l II perjimn DFS index:= 0 DFS(s) [reset IDX to = for visited states) [clean stack and visited) DFS(s : state) begin end II buse case if s .SOLVED V s.GOAL then L s.SOLVED := true return false II check residual if s.RESIDUAL > f then L s.UPDATE(} return true II mark stair as actiwt visited. PUSH ( s) stack.PVSH(s) s.IDX := s.LOW := index index := index + 1 II rrcursi1·r call flag := false for s' E s.SUCCESSORS do l if s' .IDX = =then L flag := flag V DFS(s') s.LOW :=min{ s.LOW, s 1 .LOW} else if s' E stack then L s.LOW :=min{ s.LOW, s' .IDX} II update if t~t·res.wcry if flag then L s.UPDATE(} return true II 1 r:v to label else if s.IDX = s.LOW then l while stack .TOP # s do L ·: := stack.POP(} s .SOLVED := true stack.POP(} s.SOLVED :=true return flag

of Table I, including number of states, optimal cost, and per­ centage of states that are relevant.

As heuristic, we follow [Bonet and Geffner, 2003], and use the domain independent admissible and monotonic heuristic hmin, obtained by replacing the expected cost in Bellman equation by the best possible cost. The total time spent com­ puting heuristic values is roughly the same for the different algorithms (except VI), and is shown separately in the fifth row in the table, along with its value for s0 . The experiments are carried with three heuristics: h = hmin· h = hmin/ 2, and h = 0.

The results are shown in Table 1. HOP dominates the other algorithms over all the instances for h = hmin· while LRTDP is best (with one or two exceptions) when the weaker heuris­ tics hmin/2 and 0 are used. Thus, while HOP seems best for exploiting good heuristic information over these instances, LRTDP bootstraps more quickly (i.e., it quickly computes a good value function). We hope to understand the reasons for these differences in the future.

6 Approximation

HDP, like FIND-and-REVISE, computes a value function V by enforcing its consistency over the states reachable from so and the greedy policy 1rv. The final variation we consider, that we call HDP(i), works in the same way, yet it enforces the consistency of the value function V only over the states that are reachable from so and the greedy policy with some minimum likelihood.

For efficiency, we formalize this notion of likelihood, using a non-negative integer scale, where 0 refers to a normal out­ come, 1 refers to a somewhat surprising outcome, 2 to a still more surprising outcome, and so on. We call these measures plausibilities, although it should be kept in mind, that 0 refers to the most plausible outcomes, thus 'plausibility greater than i', means 'a plausibility measure smaller than or equal to i.'

We obtain the transition plausibilities K:a(s'ls) from the corresponding transition probabilities by the following dis­ cretization:

with K:a(s'ls) = oo when Pa(s'ls) = 0. Plausibilities are thus 'normalized': the most plausible next states have always plausibility 0. These transition plausibilities are then com­ bined by the rules of the K: calculus [Spohn, 1988] which is a calculus isomorphic to the probability calculus (e.g. [Gold­ szmidt and Pearl, 1996]). The plausibility of a state trajectory given the initial state, is given by the sum of the transition plausibilities in the trajectory, and the plausibility of reach­ ing a state, is given by the plausibility of the most plausible trajectory reaching the state.

The HDP(i) algorithm, for a non-negative integer i, com­ putes a value function V by enforcing its (f-)consistency over the states reachable from s0 with plausibility greater than or equal to i. HDP(i ) produces approximate policies fast by pruning certain paths in the search. The simplest case results from i = 0, as the code for HDP(O) corresponds exactly to the code for HDP, except that the possible successors of a states in the greedy graph are replaced by the plausible successors.

HDP(i) computes lower bounds that tend to be quite tight over the states that can be reached with plausibility no smaller than i. At run time, however, executions may contain 'sur­ prising' outcomes, taking the system 'out' of this envelope, into states where the quality of the value function and its cor­ responding policy, are poor. To deal with those situations, we define a version of HDP(i) , called HDP(i,j), that inter­ leaves planning and execution as follows. HDP(i,j) plans from s = s0 by means of the HDP(i) algorithm, then exe­ cutes this policy until a state trajectory with plausibility mea­ sure greater than or equal to j, and leading to a (non-goal) state s' is obtained. At that point, the algorithm replans from s' with HDP(i), and the same execution and replanning cycle is followed until reaching the goal. Clearly, for sufficiently largej , HDP(i,j) reduces to HDP(i), and for large i, HDP(i) reduces to HDP.

Table 2 shows the average cost for HDP(i , j) for i = 0 (i.e., most plausible transitions considered only), and several values for j (replanning thresholds). Each entry in the ta­ ble correspond to an average over 100 independent execu­ tions. We also include the average cost for the greedy policy with respect to hmin as a bottom-line reference for the fig­ ures. Memory in the table refers to the number of evaluated states. As these results show, there is a smooth tradeoff be­ tween quality (average cost to the goal) and time (spent in initial planning and posterior replannings) as the parameter j vary. We also see that in this class of problems the hmin heuristic delivers a very good greedy policy. Thus, further research is necessary to assess the goodness of HDP( i, j) and the hmin heuristic.

7 Related Work

We have built on [Barto et al., 1995] and [Bertsekas, 1995], and more recently on [Hansen and Zilberstein, 2001] and [Bonet and Geffner, 2003]. The crucial difference between FIND-and-REVISE and general asynchronous value iteration is the focus of the former on the states that are reachable from the initial state s0 and the greedy policy. In RTDP, the FIND procedure is not systematic and is carried out by a stochas­ tic simulation that may take time greater than O([SI) when the inconsistent states are reachable with low probability (this explains why RTDP final convergence is slow; see [Bonet and Geffner, 2003]). LAO*, on the other hand, keeps track of a subset of states, which initially contains s0 only, and over which it incrementally maintains an optimal policy through a somewhat expensive REVISE (full DP) procedure. This is then relaxed in the second algorithm in [Hansen and Zilber­ stein, 2001], called Improved LAO* here. The use of an ex­ plicit envelope that is gradually expanded is present also in [Dean et al., 1993] and [Tash and Russell, 1994]. Interest­ ingly, these envelopes are expanded by including the most 'likely' reachable states not yet in the envelope. The algo­ rithm HDP( i) exploits a similar idea but formulates it in a dif­ ferent form and has a crisp termination condition.

8 Summary

We have introduced and analyzed three HS/DP algorithms that exploit knowledge of the initial state and an admissible heuristic function for solving planning problems with uncer­ tainty and feedback: FIND-and-REVISE, HDP, and HDP(i). FIND-and-REVISE makes explicit the basic idea underlying HS/DP algorithms: inconsistent states are found and updated, until no one is left. We have proved its convergence, complex­ ity, and optimality. HDP adds a labeling mechanism based on Tarjan's SCC algorithm and is strongly competitive with current algorithms. Finally, HDP( i) and HDP( i, j) offer great time and memory savings, with no much apparent loss in quality, in problems where transitions have probabilities that differ greatly in value, by focusing the updates on the states that are more likely to be reached.

Acknowledgements: We thank Eric Hansen and Shlomo Zil­ berstein for making the code for LAO* available to us. Blai Bonet is supported by grants from NSF, ONR, AFOSR, DoD MURI program, and by a USBICONICIT fellowship from Venezuela. Hector Geffner is supported by grant TIC200204470-C03-02 from MCyT, Spain.