companies impose a time-per-action limit on their pathfinding algorithms. As an example, Bioware Corp., a major game company, limits planning time to 1-3 ms for all pathfinding units (and there can be many units planning simultaneously).

The original real-time search algorithms, RTA* and LRTA*, form a local search space (LSS) around the agent's current state. Then they greedily take an action toward the most promising state on the frontier of the LSS. A large number of subsequent real-time heuristic search algorithms have followed this canon (e.g., Russell & Wefald, 1991; Furcy & Koenig, 2000; Shimbo & Ishida, 2003; Koenig, 2004; Hernandez & ´ Meseguer, 2005a, 2005b; Koenig & Likhachev, 2006; Rayner, Davison, Bulitko, Anderson, & Lu, 2007; Bulitko, Sturtevant, Lu, & Yau, 2007; Bulitko, Lustrek, Schaeffer, Bj ˇ ornsson, & Sigmundarson, 2008). ¨ Arguably, the most radical departure was an introduction of the so-called backtracking moves by Shue and Zamani (1993a, 1993b), Shue, Li, and Zamani (2001). Their impact on performance of real-time heuristic search and, in particular the cost of the solution the agent finds, has been studied mostly empirically (Shue & Zamani, 1993a, 1993b; Shue et al., 2001; Bulitko, 2004; Bulitko & Lee, 2006; Sigmundarson & Bjornsson, ¨
2006). As a result, it is unclear to what extent the reported findings and trends are specific to the particular algorithms and/or to the testbed environments used.

The contribution of this paper is an entirely theoretical investigation of effects of backtracking on realtime search performance. We describe a theoretical framework that generalizes a broad class of existing realtime search algorithms. We show that in the worst case, solution cost can be exponential in the parameter controlling the amount of backtracking. We then identify a special case that affords linear solution cost.

Because we consider real-time heuristic search on general graphs, the results of our study are domainindependent and, thus, broadly applicable. The rest of the paper is organized as follows. We first informally review the pioneering LRTA* algorithm and introduce the notion of backtracking in Section 2. The search problem and performance metrics are formally defined in Section 3. Section 4 introduces our framework of real-time search. We then use the framework to derive properties responsible for exponential (Section 5.1) and linear (Section 5.2) solution cost. We review existing theoretical work in Section 6. The paper is concluded with a discussion of limitations and future work directions. Note that there are no proofs in this version of the paper. We are working on polishing their presentation for a future version.

## 2 Backtracking In Real-Time Heuristic Search

To begin, we present the original real-time search called Learning Real-Time A* or LRTA* (Korf, 1990)
that constitutes the core of most modern real-time search algorithms. In the current state s, LRTA* with a lookahead of one considers the immediate neighbors (lines 4-5 in Figure 2.1). For each neighbor state, two values are computed: the distance of getting there from the current state (henceforth denoted by g) and the heuristic estimate h of the distance to the closest goal state from the neighbor state. LRTA* then travels to the state with the lowest f = g + h value (line 7). Then it updates the heuristic value of the current state if the minimum f-value is higher (line 6). The process repeats until a goal state is reached.

This paper analyzes the role of backtracking moves which were introduced in an algorithm called Search and Learning A*, or SLA* (Shue & Zamani, 1993a, 1993b). The SLA* is based on the LRTA* algorithm with a lookahead of one we described above with one notable difference. Namely, whenever the heuristic value of the current state is updated (line 7 in Figure 2.2), the algorithm returns to the previous state (line 8). Otherwise (i.e., when there is no learning), SLA* proceeds to the most promising successor state using the same rule as LRTA* (line 10). Naturally, all backtracking moves incur the travel cost as do regular (forward) moves.