Improving LRTA*(k)

1 Introduction

Real-time search interleaves planning and action execution in an on-line manner. This allows to face search problems in domains with incomplete information, where it is impossible to perform the classical search approach.

A real-time agent has a limited time to planify the next action to perform. In such limited time, it can explore only a relatively small part of the search space that is around its current state. This part is often called its local space.

This paper considers some weak points of the updating mechanism of the LRTA*(k) algorithm [Hernandez and Meseguer, 2005]. With this purpose, we present LRTA*LS(k), based on local space selection and updating. Local space selection is learning-oriented. Local space is divided into interior and frontier. Updating is done from the frontier into the interior states, so some kind of lookahead is done. Each state is updated only once. If the initial heuristic is admissible, it remains admissible after updating. LRTA*LS(k) keeps the good properties of LRTA*(k).

The paper structure is as follows. In Section 2 we expose the basic concepts used. In Section 3 we describe some weak points of LRTA*(k). In Section 4, we present LRTA*LS(k), explaining the lookahead and update mechanisms. In Section 5, we relate LRTA*LS(k) with lookahead greater than 1. In Section 6, we provide experimental results. Finally, in Section 7 we extract some conclusions.

1 On leave from Universidad Católica de la Santísima Concepción, Caupolicán 491, Concepción, Chile.

2 Preliminaries

The state space is defined as (X, A, c, s, G), where (X,A) is a finite graph, c : A .notdef [0,.notdef) is a cost function that associates each arc with a positive finite cost, s .notdef X is the start state, and G .notdef X is a set of goal states. X is a finite set of states, and A .notdef X .notdef X \ {(x, x)|x .notdef X} is a finite set of arcs. Each arc (v,w) represents an action whose execution causes the agent to move from v to w. The state space is undirected: for any action (x, y) .notdef A there exists its inverse (y, x) .notdef A with the same cost c(x, y) = c(y, x). k(n, m) is the cost of the path between state n and m. The successors of a state x are Succ(x) = {y|(x, y) .notdef A}. A heuristic function h : X .notdef [0,.notdef) associates with each state x an approximation h(x) of the cost of a path from x to a goal, where h(g)=0, g .notdef G. The exact cost h*(x) is the minimum cost to go from x to a goal. h is admissible iff .notdef x .notdef X, h(x) .notdef h*(x). h is consistent iff 0 .notdef h(x) .notdef c(x,w) + h(w) for all states w .notdef Succ(x). A path (x0, x1, . ., xn) with h(xi) = h*(xi), 0 .notdef i .notdef n is optimal.

LRTA* [Korf 1990] is a real-time search algorithm that is complete under a set of reasonable assumptions. LRTA* improves its performance over successive trials on the same problem, by recording better heuristic estimates. If h(x) is admissible, after a number of trials h(x) converges to their exact values along every optimal path. In each step, LRTA* updates the heuristic estimation of the current state to make it consistent with the values of their successors [Bonnet and Geffner, 2006]. Originally, LRTA* performs one update per step. Some versions perform more than one update per step.

3 LRTA*(k)

LRTA*(k) [Hernandez and Meseguer, 2005], is a LRTA*- based algorithm that consistently propagates heuristic changes up to k states per step, following a bounded propagation strategy. If the heuristic of the current state x changes, the heuristic of its successors may change as well, so they are reconsidered for updating. If the heuristic of some successor v changes, the successors of v are reconsidered again, and so on. The propagation mechanism is bounded to reconsider up to k states per step. This updating strategy maintains heuristic admissibility, so LRTA*(k) inherits the good properties of LRTA* (in fact, LRTA*(k reduces to LRTA* when k=1). Experimentally, LRTA*(k)

improves significantly with respect to LRTA*.

The updating mechanism is implemented with a queue Q, that maintains those states that should be reconsidered for updating. We have identified some weak points:

1. If y enters Q, after reconsideration it may happen that h(y) does not change. This is a wasted effort.
2. A state may enter Q more than once, making several updatings before reaching its final value. Would it not be possible to perform a single updating per state?
3. The order in which states enter Q, combined with the value of k parameter, may affect the final result.

As example, in the Figure 1 (i), a, b, c and d are states, the left column is the number of the update iteration, and the numbers below the states are their heuristic values. Moving from a state to a successor costs 1. Sucessors are revised in left-right order. The current state is d, iteration 0 shows the initial heuristic values. In iteration 1, h(d) changes to 4, Q = {c}. In iteration 2, h(c) changes to 5, Q = {b, d}. In iteration 3, h(b) does not change. In iteration 4, h(d) changes to 6, Q = {c}. In iteration 5, h(c) does not change. After five iterations no more changes are made and the process stops. We see that c and d enters two times in Q, d is updated twice while c is updated only once. If k = 3, the final result depends on the entering order in Q. If the left successor goes first, the states d, c, b will enter Q in that order, producing the heuristic estimates of Figure 1 (ii). The agent moves to c, and then it may move again to d. If the right successor goes first, the states in Q will be d, c, d, causing heuristic values equal to those of iteration 5. Then, the agent moves from d to c, and then to b, not revisiting d.

In [Hernandez and Meseguer, 2005] it is required that updates are done on previously visited states only. In that case, weak point 1 is solved by the use of supports 2 . However, there is a version of LRTA*(k), called LRTA*2(k), which updates any state (not just previously visited states). In this case, supports can only partially solve this issue.

2 There, support usage does not consider ties. It is straightforward to develop a support management including ties.

4 LRTA*LS(k)

Trying to solve those weak points, we propose a new algorithm LRTA*LS(k), based on the notion of local space around the current state. Formally, a local space is a pair (I, F), where I.notdef X is a set of interior states and F.notdef X is the set of frontier states, satisfying that F surrounds I inmediate and completely, so I .notdef F = .notdef. LRTA*LS(k) selects the local space around the current state and then updates its interior states. Each state is updated only once. Under some circumstances, we can prove that every interior state will change its heuristic. The number of interior states is upper-bounded by k. If the initial heuristic is admissible, LRTA*LS(k) maintains the admissibility, so it inherits the good properties of LRTA* (and LRTA*(k)).

4.1 Selecting the Local Space

We want to find a local space around the current state such that its interior states will have a high chance to update its heuristic. We propose the following method,

1. Set I = .notdef, Q = {x | x is the current state}.
2. Loop until Q empty or |I| = k

Extract a state w from Q. If w is a goal, exit loop. Otherwise, check by looking at Succ(w) that are not in I if h(w) is going to change (that is, if h(w) < minv.notdef{Succ(w)-I} h(v) + c(w,v), we call this expression the updating condition). If so, include w in I, and Succ(w) \ I in Q.

1. The set F surrounds I inmediate and completely.

For example, let us apply this strategy to Figure 1 (i). It starts with I = {d} since h(d) < minv.notdefSucc(d) h(v) + 1. Then, it checks the successors of d, adding c to I, I = {c, d} since h(c) < minv.notdef{Succ(c)-I} h(v) + 1. Then, it checks the successors of c that do not belong to I, that is, b . Since h(b) = minv.notdef{Succ(b)-I} h(v) + 1, it is not possible to add more states to I. Then I = {c, d} and F = {b}. If the heuristic is initially consistent, all interior states of the local space (I, F) built with the previous method will change their heuristic, as proven in the following result.

Proposition 1. If the heuristic is initially consistent, starting from x LRTA*2 (k=.notdef) will update every state of I.

Proof. By induction in the number of states of I. If |I| = 1, then I = {x}, the current state. In this case, h(x) is updated because by construction it satisfies the updating condition. Let us assume the proposition for |I| = p, and let us prove it for |I| = p + 1. Let z .notdef I, z .notdef x, y = argminv.notdefSucc(z) h(v) + c(z,v). If y .notdef I , z satisfies the updating condition by construction. If y .notdef I, let I' = I - {z}. Since |I'| = p, every state of I' will be updated, so y will be updated, passing from hold(y) to hnew(y), hold(y) < hnew(y). We will see that this causes z to be updated. We consider two cases:

1. If y is still argminv.notdefSucc(z) c(z,v) + h(v). The initial heuristic is consistent so h(z) .notdef c(z,y) + hold(y) < c(z,y) + hnew(y). So z satisfies the updating condition and h(z) will change.
2. If w = argminv.notdefSucc(z) c(z,v) + h(v), w .notdef y. If w .notdef I', z satisfies the updating condition by construction. If w .notdef I', w has

passed from hold(w) to hnew(w), hold(w) < hnew(w). Since y was the initial minimum, we know that c(z,y) + hold(y) < c(z,w) + hnew(w). So, h(z) .notdef c(z,y) + hold(y) < c(z,w) + hnew(w). Then, z satisfies the updating condition and h(z) will change.

LRTA*2(k=.notdef) reaches all interior states because every successor of a changing state enters the queue Q, which has no limit in length (k=.notdef). qed.

If the heuristic is admissible but not consistent, some interior states may not change. For instance, consider the states a-b-c-d in a linear chain, with heuristic values 1, 1, 5, 6, and b is the current state. The previous method will generate I = {b, c}. h(b) will change to 2, but h(c) will not change.

4.2 Updating the Local Space

LRTA*LS(k) updates the interior states of (I, F) as follows,

Loop while I is not empty:

1. Calculate the pair of connected states (i, f), i .notdef I, f .notdef F, f .notdef Succ(i), such that (i, f) = argmin v .notdef I, w .notdef F, w .notdef Succ(v) c(v, w) + h(w).
2. Update h(i) = c(i,f) + h(f).
3. Remove i from I, include i in F.

For example, in Figure 1 (i), I = {c, d} and F = {b}, the results of each iteration with the new updating appear in Figure 1 (iii). In iteration 1, (i, f) = (c, b), and h(c) changes to 5. In iteration 2, (i, f) = (d, c), and h(d) changes to 6. As I = .notdef process stops. Update keeps admissibility, as proved next.

Proposition 2. If the initial heuristic is admissible, after updating interior states the heuristic remains admissible.

Proof. Let (i, f) = argmin v .notdef I, w .notdef F, w .notdef Succ(v) c(v, w) + h(w). Since i .notdef I and connected to a frontier state f, it will be updated (it satisfies the updating condition by construction). There is an optimal path from i to a goal that passes through a successor j. We distinguish two cases:

1. j .notdef F. After updating

h(i)=c(i, f) + h(f) .notdefc(i, j) + h(j) (i, f) minimum c(v,w) + h(w) .notdefc(i, j) + h*(j) h admissible =h*(i) because optimal path

2. j .notdef F. If I contains no goals, the optimal path at some point will pass through F. Be p the state in the optimal path that belongs to F and q the interior state in the optimal path just before p. After updating

h(i)=c(i, j) + h(j) .notdefc(q, p) + h(p) (i, f) minimum c(v,w) + h(w) .notdefk(i, p) + h(p) k(i, p) includes c(q, p) .notdefk(i, p) + h*(p) h admissible =h*(i) because optimal path

In both cases h(i).notdefh*(i) so h remains admissible. qed.

Proposition 3. Every state updated by LRTA*2(k=.notdef) is also updated by LRTA*LS(k=.notdef).

The proof is direct, but it is omitted for space reasons. With these selection and updating strategies, the weak points of LRTA*(k) are solved partial or totally. Regarding point 1, if the heuristic is consistent all interior states will change its heuristic estimator (propositions 1 and 3). If the heuristic is just admissible, some internal states may not change (example in Section 4.1). Point 2 is totally solved, since the updating strategy considers every state only once. About point 3, it is not solved since the final result may still depend on the order in which successors are considered and the value of k parameter. Since LRTA*LS(k) performs a better usage of k than LRTA*(k) (non repeated states and with high chance to change), we expect that, with the same k value, the former will depend less than the latter on the successor ordering. If the heuristic is consistent, after updating interior nodes the local space is locally consistent and agent decisions are locally optimal [Pemberton and Korf, 1992].

It is important to see that the new update method makes a more aggressive learning than LRTA*(k), because LRTA*(k) updates a state x considering all its successors, while LRTA*LS(k) considers those successors that are frontier states only. One update of LRTA*LS(k) may be greater than one update of LRTA*(k). For instance, see the updating of h(d) in Figure 1 (i): it goes from 2 to 4, and then to 6, in two steps. In Figure 1 (iii), h(d) goes from 2 to 6 in one step.

4.3 The algorithm

The LRTA*LS(k) is a algorithm based on LRTA* similar to LRTA*(k). The algorithm appears in Figure 2. The main differences with LRTA* appear in the LRTA-LS-Trial procedure, calling to SelectionUpdateLS. This procedure performs the selection and updating of the local space around the current state. Procedure SelectionUpdateLS first performs the selection of the local space and then updates it. To select the local space, a queue Q keeps states candidates to be included in I or in F. Q is initialized with the current state and F and I are empty. At most k states will be entered in I. This is controlled by the counter cont. The following loop is executed until Q contains no states or cont is equal to k. The first state v in Q is extracted. The state y .notdef argminw.notdefSucc(v), w .notdef I h(w) + c(v, w) is computed. If h(v) satisfies the updating condition, then v enters I, the counter increments and those successors of v that are not in I or Q enters in Q in the last position. Otherwise, v enters F. When exiting the loop, if Q still contains states then these states go to F. Once the local space has been selected, its interior states are updated as follows. The pair (i, f) .notdef argmin v.notdefI, w.notdefF, w.notdefSucc(v) h(w) + c(v, w) is selected, h(i) is updated, i exits I and enters F.

Since the heuristic always increases, compleneteness holds (Theorem 1 of [Korf, 1990]). Heuristic admissibility is maintained, so convergence of to optimal paths is guaranteed in the same terms as LRTA* (Theorem 3 of [Korf, 1990]). LRTA*LS(k) inherits the good properties of LRTA*.

procedure LRTA*-LS(k) (X, A, c, s,G, k) for each x .notdef X do h(x) .notdefh0(x); repeat LRTA*-LS-trial(X, A, c, s,G, k); until h does not change; procedure LRTA*-LS-trial(X, A, c, s,G, k) x .notdef s; while x .notdef G do SelectUpdateLS(x, k); y.notdef argminw.notdefSucc(x) [h(w) + c(x,w)];(Break ties randomly) execute(a .notdef A such that a = (x, y)); x .notdef y; procedure SelectUpdateLS (x, k) Q .notdef .notdefx.notdef; F .notdef.notdef; I .notdef.notdef; cont .notdef 0; while Q .notdef.notdef.notdef cont < k do v .notdef extract-first(Q); y.notdef argminw.notdefSucc(v) .notdef w .notdef I h(w) + c(v, w); if h(v) < h(y) + c(v, y) then I .notdefI .notdef {v}; cont .notdef cont + 1; for each w .notdef Succ(v) do if w .notdef I .notdef w .notdef Q then Q .notdef add-last(Q,w); else if I .notdef.notdef then F.notdefF .notdef {v}; if Q .notdef .notdef then F .notdefF .notdef Q; while I .notdef .notdef do (i, f) .notdef argmin v.notdefI, w.notdefF, w.notdefSucc(v) h(w) + c(v, w); h(i) .notdef max[h(i), c(i, f) + h(f)]; I .notdefI - {i}; F.notdefF .notdef {i};

5 Lookahead and Local Space

Real-time agents restrict planning to the local space [Koenig, 2001]. Basically an agent performs three steps: (i) lookahead on the local space, (ii) updating the local space and (iii) moving in the local space.

On lookahead, in RTA*, LRTA* [Korf, 1990; Knight, 1993] and in LRTS [Bulitko and Lee, 2006] the local space is determined by the depth of the search horizon. The search tree, rooted at the current state, is explored breadth-first until depth d. In the LRTA* version of [Koenig, 2004] and in RTAA* [Koenig and Likhachev, 2006], the local space is determined by a bounded version of A*, limiting the number of states that can enter in CLOSED. LRTA*LS(k) tries to find those states that will change in the updating process. Lookahead is limited by the k parameter: a maximum of k states can enter the set of interior states. About updating, there are two approaches: updating the current state only (like LRTS with the max-min rule), and updating all interior states of the local space (like RTAA* that update all states in CLOSED and LRTA*LS(k)). Regarding moving, for unknown environments the free space assumption is assumed [Koenig et al., 2003]. In RTAA* the agent tries to move to the frontier of the local space. If it finds an obstacle, the whole process is repeated again. In LRTA*-based algorithms the agent moves to its best successor.

Figure 3 shows an example of a goal-directed navigation task on a grid (legal moves: north, south, east, west; all moves of cost 1) with three different algorithms: LRTA*LS(k=6), RTAA* with lookahead 6 and LRTS (with parameters .notdef=1 and T=.notdef) with lookahead 3. The visibility radius is one [Bulitko and Lee, 2006]. Black cells are obstacles. The initial heuristic is the Manhattan distance. The current state is indicated with a circle. With similar lookahead, LRTA*LS(k) expands less states (the set of interior states contains 5 states with k = 6, because only those 5 states will changes their heuristic) and after updating it obtains a heuristic more informed than RTAA* and LRTS.

The updating mechanism of LRTA*LS(k) is a general method. Therefore, it is possible to use it with different lookahead mechanisms, like those of RTTA* and LRTS.

6 Experimental Results

We compare LRTA*LS(k) versus LRTA*(k). In addition, we compare LRTA*LS(k) with RTAA* and LRTS, algorithms with lookahead greater than 1. As benchmarks we use these four-connected grids,

• Grid35: grids of size 301x301 with a 35% of obstacles placed randomly. In this type of grid heuristics tend to be slightly misleading.
• Grid70: grids of size 301x301 with a 70% of obstacles placed randomly. In this type of grid heuristics could be misleading.
• Maze: acyclic mazes of size 151x151 whose corridor structure was generated with depth-first search. Here heuristics could be very misleading.

Results are averaged over 1000 different instances. In grids and mazes, the start and goal state are chosen randomly assuring that there is a path from the start to the goal. All actions have cost 1. As initial heuristic we use the Manhattan distance. The visibility radius of the agent is 1. Results are presented in percentage with respect to the value of row 100%, in terms of total search time, solution cost, trials to convergence, number of updated states, and time per step, for the convergence to optimal path.

Comparing LRTA*LS(k) and LRTA*(k), we consider first trial and convergence to optimal paths. Results for convergence to optimal paths appear in Table 1, where the LCM algorithm [Pemberton and Korf, 1992] is also included (LCM has the same updating mechanism as LRTA*(k), but without supports and limitation of entrances in the queue). LRTA*LS(k) converges to optimal paths with less cost, number of trials and total time than LRTA*(k) for all values of k tested between 1 and .notdef (except for Grid35 in total time with k = 5). Respect to time per step, LRTA*LS(k) obtains better results than LRTA*(k ) except for Grid35. LRTA*LS(k) requires slightly more memory than LRTA*(k) (except for Grid70 with k = .notdef). LRTA*(k = .notdef) and LCM have the same cost and number of trials to convergence, but LRTA*(k=.notdef) improves over LCM in time because the use of supports. LRTA*LS(k = .notdef) has similar results in cost and number of trials to convergence, requiring less time than LRTA*(k=.notdef) and LCM (except for Grid35 in time per step). We observe that the worse the heuristic information is, the better results LRTA*LS(k) obtains, for all values of k. For Grid35, LRTA*LS (5) improves over LRTA*(5) in steps and trials, but it requires more running time. This is due to the extra overhead of LRTA*LS(k) has over LRTA*(k) (minimizing on two vs. one argument), that counterbalances the benefits in steps and trials.

Results for first trial appear in Table 2. LRTA*LS(k) obtains a solution with less cost than LRTA*(k) for all tested values of k between 1 and .notdef (except for Maze with k = 5). Respect to time, LRTA*LS(k) obtains better solution for Maze and Grid70 than LRTA*(k). In Grid35, LRTA*(k) shows better results in total time and time per step. Trying to improve the running time, we have developed LRTA*LS(k)-path, that only updates states that have been visited previously (like LRTA*(k) and LCM). LRTA*LS(k)- path improves the cost of the solution and total time for small values of k, and this improvement is larger when worse is the heuristic information (in Grid35 it improves for k = 5 only, in Maze it improves for k = 5, 25, 61 and 113). This fact can be explained as follows. Due to the free space assumption, LRTA*LS(k) may perform an inefficient use of k, updating states that are blocked (will never appear in any solution). Since a great part of the states in Maze are blocked, is better to update only states in the current path, as the results show. Considering memory, LRTA*LS(k) uses more memory than LRTA*(k) and LRTA*LS(k)-path with increasing k and more than LCM with k = .notdef.

Comparing with lookahead algorithms, results for first trial appear in Table 2. Comparing LRTA*LS(k) and RTAA*, the former obtains costs equal to or better than the latter in Grid70 and Maze for all values of k. However, from k = 25, RTAA* obtains slightly better costs in Grid35. RTAA* takes more time in finding a solution for all values of k in all benchmarks. Considering time per step, LRTA*LS(k) requires a smaller time for all values of k in all benchmarks (except for Maze with k = 5, 25). From k = 25 in Maze and from k = 61 in G70, RTAA* uses more memory than LRTA*LS(k). In G35, RTAA* uses less memory for all values k. LRTS uses the radius of a circle centered in the current state as lookahead parameter, while LRTA*LS(k) and RTAA* use the number of the states they consider in advance. To perform a fair comparison, we use LRTS (with parameters .notdef=1 and T=.notdef) lookahead values that generate circles including k states, where k is the lookahead of LRTA*LS(k) and RTAA*. LRTS does not show a good performance in terms of cost and time to find a solution respect to LRTA*LS(k). LRTS uses less memory than LRTA*LS(k) and smaller time per step.

In summary, LRTA*LS(k) shows better performance than LRTA*(k) both in first trial and convergence to optimal paths. Sometimes updating only previously visited states could improve performance: if the heuristic quality is good, it is advisable to update any state, but with bad quality heuristics it is safer to update visited states only. In first trial, LRTA*LS(k) performs equal or better than RTAA* in two benchmarks, while there is no clear winner for the third. LRTA*LS(k) performs better than LRTS. On memory usage, LRTS wins, while the second is unclear between LRTA*LS(k) and RTAA*.

7 Conclusions

Trying to solve some inefficiencies in LRTA*(k) propagation, we have developed LRTA*LS(k) a new real-time search algorithm. It is based on the selection and update of a local space, composed of interior and frontier states. The number of interior states is upper-bounded by k. LRTA*LS(k) updates the interior states from the heuristic values of frontier states, so it performs a kind of lookahead with varying depth. If the heuristic is initially consistent, all interior states are updated. Experimentally, we show that LRTA*LS(k) improves over LRTA*(k) (lookahead 1). and improves over RTAA* and LRTS (with lookahead greater than 1).