Figure 2.1: The LRTA* algorithm with a lookahead of one.

![0_image_1.png](0_image_1.png)

![0_image_2.png](0_image_2.png)

SLA*

![0_image_3.png](0_image_3.png)

1 initialize the heuristic: h ← h0 2 reset the current state: s ← sstart 3 **while** s 6∈ Sg do 4 generate successor states of state s 5 among them find the state s 0 with the lowest f = g + h 6 if f(s 0) > h(s)
7 update h(s) to f(s

![0_image_4.png](0_image_4.png)

8 execute an action to return to the previous state 9 **else**
10 execute an action to get to s

![0_image_5.png](0_image_5.png)

11 **end if** 12 **end while**
Figure 2.2: The SLA* algorithm.

The backtracking mechanism provides the agent with two opportunities: (i) to update the heuristic value of the previous state and (ii) possibly select a different action in the previous state. An alternative scheme would be to update heuristic values of previously visited states in memory (i.e., without changing the agent's current state and incurring action cost). This is the approach used by some other real-time search algorithms (Hernandez & Meseguer, 2005b; Sigmundarson & Bj ´ ornsson, 2006) and it does not give the ¨
agent the opportunity to select a different action.

## 3 Definitions And Notation

In this section we axiomatically introduce the problem and the formal notation used throughout the rest of the paper.

Definition 1 A *search space* is defined by a connected directed weighted graph G = (*S, E, w*), and a subset of absorbing (goal) states Sg ⊂ G. Elements of S are states of the search problem and the vertices in the graphs. E is the set of directed edges: E ⊂ S × S defining the transitions in the state space. Each LRTA*
1 initialize the heuristic: h ← h0 2 reset the current state: s ← sstart 3 **while** s 6∈ Sg do 4 generate successor states of state s 5 among them find the state s 0 with the lowest f = g + h 6 if f(s 0) > h(s)
7 update h(s) to f(s

![0_image_0.png](0_image_0.png)

8 **end if**
9 execute an action to get to s 0 10 **end while**