\documentclass[twoside,11pt]{article} 
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{jair}
\usepackage{theapa}
\usepackage{times}

\newtheorem{df}{Definition}
\newtheorem{notation}{Notation}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{col}{Corollary}
\newcommand{\bt}{\begin{theorem}\em}
\newcommand{\et}{\end{theorem}}
\newcommand{\Qed}{$\blacksquare$}
\newcommand{\qed}{$\Box$}
\newcommand{\proof}{{\bf Proof. }}

\newcommand{\nin}{\noindent}

\newcommand{\bea}{\begin{eqnarray}}
\newcommand{\eea}{\end{eqnarray}}

\newcommand{\bdf}{\begin{df}\em}
\newcommand{\edf}{\end{df}}

\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\ie}{\item}

\newcommand{\dist}{\operatorname{dist}}

\newcommand{\travel}{\operatorname{\bf travel}}
\newcommand{\travelc}{\widehat{\operatorname{\bf travel}}}

\newcommand{\solution}{\operatorname{\bf solution}}
\newcommand{\solutionc}{\widehat{\operatorname{\bf solution}}}

\newcommand{\tim}{\operatorname{\bf states}}
\newcommand{\timc}{\widehat{\operatorname{\bf states}}}

\newcommand{\memory}{\operatorname{\bf memory}}
\newcommand{\memoryc}{\widehat{\operatorname{\bf memory}}}

\newcommand{\cost}{\operatorname{\bf cost}}
\newcommand{\IAE}{\operatorname{IAE}}
\newcommand{\SOD}{\operatorname{SOD}}

\newcommand{\avg}{\operatornamewithlimits{avg}}
\renewcommand{\arg}{\operatornamewithlimits{arg}}
\newcommand{\eLRTA}{$\epsilon$-LRTA*~}
\newcommand{\eRTA}{$\epsilon$-RTA*~}
\newcommand{\gTrap}{$\gamma$-Trap~}

\setcounter{page}{119}

\numberwithin{equation}{section}
\numberwithin{theorem}{section}
\numberwithin{lemma}{section}
\numberwithin{df}{section}

\sloppy

% \jairheading{vol}{year}{pages}{Submitted}{published}
\jairheading{25}{2006}{119-157}{04/05}{02/06}

\ShortHeadings{Learning in Real-Time Search: A Unifying Framework}{Bulitko \& Lee}

\begin{document}

\title{Learning in Real-Time Search: A Unifying Framework}

\author{%
\name Vadim Bulitko \email bulitko@ualberta.ca \\
\name Greg Lee \email greglee@cs.ualberta.ca \\
\addr Department of Computing Science\\
       University of Alberta\\
       Edmonton, Alberta T6G 2E8, CANADA
}

\maketitle

\begin{abstract}
%
Real-time search methods are suited for tasks in which the agent is interacting with an initially unknown environment in real time. In such simultaneous planning and learning problems, the agent has to select its actions in a limited amount of time, while sensing only a local part of the environment centered at the agent's current location. 
%
Real-time heuristic search agents select actions using a limited lookahead search and evaluating the frontier states with a heuristic function. Over repeated experiences, they refine heuristic values of states to avoid infinite loops and to converge to better solutions.
%
The wide spread of such settings in autonomous software and hardware agents has led to an explosion of real-time search algorithms over the last two decades. Not only is a potential user confronted with a hodgepodge of algorithms, but he also faces the choice of control parameters they use. In this paper we address both problems.
%
The first contribution is an introduction of a simple three-parameter framework (named LRTS) which extracts the core ideas behind many existing algorithms. We then prove that LRTA*, \eLRTA, SLA*, and $\gamma$-Trap algorithms are special cases of our framework. Thus, they are unified and extended with additional features.
Second, we prove completeness and convergence of any algorithm covered by the LRTS framework. Third, we prove several upper-bounds relating the control parameters and solution quality. Finally, we analyze the influence of the three control parameters empirically in the realistic scalable domains of real-time navigation on initially unknown maps from a commercial role-playing game as well as routing in {\em ad hoc} sensor networks.
%{\bf Keywords:} real-time heuristic search; simultaneous planning and learning.
\end{abstract}


\section{Motivation}

In this paper, we consider a simultaneous planning and learning problem. One motivating application lies with navigation on an initially unknown map under real-time constraints. As an example, consider a robot driving to work every morning. Imagine the robot to be a newcomer to the town. The first route the robot finds may not be optimal because traffic jams, road conditions, and other factors are initially unknown. With the passage of time, the robot continues to learn and eventually converges to a nearly optimal commute. Note that planning and learning happen while the robot is driving and therefore are subject to time constraints.

Present-day mobile robots are often plagued by localization problems and power limitations, but their simulation counter-parts already allow researchers to focus on the planning and learning problem. 
For instance, the RoboCup Rescue simulation league~\cite{Kitano:99} requires real-time planning and learning with multiple agents mapping out an unknown terrain. Pathfinding is done in real time as various crises, involving fire spread and human victims trapped in rubble, progress while the agents plan.

Similarly, many current-generation real-time strategy games employ {\em a priori} known maps. Full knowledge of the maps enables complete search methods such as A*~\cite{AStar} and Dijkstra's algorithm~\cite{EWD:EWD841aPub}. Prior availability of the maps allows pathfinding engines to pre-compute various data to speed up on-line navigation. Examples of such data include visibility graphs~\cite{Woodcock:00}, influence maps~\cite{Pottinger:00},  space triangulation~\cite{kallmann03fully}, state abstraction hierarchies~\cite{Holte:94,Holte:96,Botea:04a} and route waypoints~\cite{Reece:00}.
%
However, the forthcoming generations of commercial and academic games~\cite{ORTS} will require the agent to cope with initially unknown maps via exploration and learning {\em during} the game, and therefore will greatly limit the applicability of complete search algorithms and pre-computation techniques.

Incremental search methods such as dynamic A* (D*) \cite{Stenz:95} and D* Lite~\cite{Koenig:02a} can deal with initially unknown maps and are widely used in robotics, including DARPA's Unmanned Ground Vehicle program, Mars rover, and other mobile robot prototypes~\cite{Hebert:99,Thayer:00}. They work well when the robot's movements are slow with respect to its planning speed~\cite{Koenig:04a}.  In real-time strategy games, however, the AI engine can be responsible for hundreds to thousands of agents traversing a map simultaneously and the planning cost becomes a major factor. To illustrate: even at the smaller scale of the six-year old ``Age of Empires 2"~\cite{AoE2}, 60-70\% of simulation time is spent in pathfinding~\cite{Pottinger:00}. This gives rise to the following questions: \ben

\ie How can planning time per move, and particularly the first-move delay, be minimized so that each agent moves smoothly and responds to user requests nearly instantly?

\ie Given real-time execution, local sensory information, and initially unknown terrain, how can the agent learn a near-optimal path and, at the same time, minimize the learning time and memory required?

\een

\nin The rest of the paper is organized as follows. We first introduce a family of real-time search algorithms designed to address these questions. We then make the first contribution by defining a simple parameterized framework that unifies and extends several popular real-time search algorithms. The second contribution lies with a theoretical analysis of the resulting framework wherein we prove convergence and completeness as well as several performance bounds. Finally, we evaluate the influence of the control parameters in two different domains: single agent navigation in unknown maps and routing in {\em ad hoc} sensor networks. Detailed pseudocode needed to reimplement the algorithms as well as to follow the theorem proofs is presented in Appendix~\ref{sec:pseudocode}. Theorem proofs themselves are found in Appendix~\ref{sec:proofs}.


\section{Real-time Heuristic Search and Related Work} 

We situate our survey of real-time heuristic search literature in the framework of {\em agent-centered search}~\cite{koenig:00c}. While traditional off-line search methods first plan a path from start to goal state and then move the agent along the path, agent-centered search interleaves planning and execution. Furthermore, the planning is restricted to the areas of the search space around the current state of the agent such as the physical location of a mobile robot or the current board position in a game. The agent-centered search methods thus satisfy these two requirements: 
%
(i) at all times, the agent is in a single state which can be changed only via taking actions and, therefore, incurring execution cost;
%
(ii) the agent can see only the states around its current state. 

{\em Real-time heuristic search} methods are a subset of agent-centered search methods. They are distinguished by the following two additional properties: 
%
(i) the planning time per move can be upper-bounded by a user-supplied constant (hence {\em real-time});
%
(ii) they associate a heuristic function with each state (hence {\em heuristic}).
%
The former requirement is motivated by the need to act quickly in control tasks such as flying a helicopter~\cite{Ng:04} or playing a real-time strategy computer game~\cite{ORTS}. The latter property allows the agent to avoid infinite cycles on a map by learning the proper distances from each state to the goal state. Unlike learning the map and using it for planning~\cite{Stenz:95,Koenig:02a,TBS,Sturtevant:05}, acquiring high-quality heuristic values lets the agent select the right action very quickly thereby improving its reaction time. Having the heuristic values also allows the agent to pick the next best action should the primary choice become unavailable (e.g., due to a road block on the map). Remarkably,  learning state and state-action values is the prevailing technique in Reinforcement Learning~\cite{sutton:05a}.

Learning real-time search algorithms, such as LRTA*~\cite{Korf-AIJ}, interleave planning and execution in an on-line decision-making setting. As the planning time per each action executed by the agent is bounded, these algorithms can be used as control policies for autonomous agents, even in an unknown and/or non-stationary environment~\cite{Koenig98,koen:99b,MTS,MTS2,Ishida97}. In particular, the ability to make decisions after only a small-scale local search  makes these algorithms well suited for routing in large-scale wireless networks of simple sensors and actuators where each node is aware only of its nearby neighbors and no global map exists. In such scenarios, not only does the limited amount of computation per node suit the low computing power and energy requirements, but also the network collectively learns its own topology over time~\cite{yu01geographical,Shang03}.

Since the pioneering LRTA*~\cite{Korf-AIJ}, research in the field of learning real-time heuristic search has developed in several major directions. \citeA{MTS} investigated modifications to LRTA* for non-stationary environments.  \citeA{ShimboIshida03} studied convergence to suboptimal solutions as well as mechanisms for bounding the amount of state space exploration. \citeA{FALCONS} considered a different learning mechanism speeding up the convergence. \citeA{RussellWefald-book} researched a decision-theoretic approach to balancing partial planning and execution.  \citeA{Shue:93a} and \citeA{Bulitko:04a} proposed a backtracking component suggesting yet another way to control the exploration of the environment.

Note that while the original LRTA* algorithm can be viewed as a special case of real-time dynamic programming~\cite{barto95}, in general, real-time heuristic search methods have several notable differences from reinforcement learning methods. First, they usually assume a deterministic environment and thus take advantage of more aggressive value update rules. Second, they employ non-trivial initial heuristics and can converge even faster when such a heuristic is admissible~\cite{pearl84} by never decreasing heuristic values of states. Third, real-time heuristic search methods often use more extensive and sophisticated local search methods than the  $\epsilon$-greedy control policy commonly used in reinforcement learning. Examples include dynamically selected lookahead search space in DTA*~\cite{RussellWefald-book}, additional heuristic for tie-breaking in FALCONS~\cite{FALCONS}, and heuristic upper-bounds for safe space exploration in bounded LRTA*~\cite{ShimboIshida03}.  This improves the quality of decision-making by compensating for inaccuracies in the heuristic function and speeds up the learning process.
Finally, backtracking extensions~\cite{Shue:93a,Bulitko:04a} give the agent another mechanism to maintain consistency of its heuristic.

The multitude of learning real-time search algorithms (LRTA*, \eLRTA, $\delta$-LRTA*, FALCONS, eFALCONS, SLA*, $\gamma$-Trap, SLA*T, DTA*, etc.) available to the user can be disorienting since he has to decide not only on the algorithm to use but also on the algorithm parameters which can have a major impact on performance. The problem is further complicated by the fact that the empirical studies have been done in different test beds making the results incomparable directly. To illustrate: \citeA{FALCONS} and \citeA{ShimboIshida03} appear to use the same testbed (the 8-puzzle). Yet, their results on the same algorithm (LRTA*) differ substantially. A closer inspection reveals that two different goal states were used leading to the major discrepancies in the performance. To compound these problems, most performance metrics have been measured with the myopic lookahead search of depth one. This is in contrast to game-playing practice where most competitive systems gain a substantial benefit from a deeper search horizon~\cite{Chinook,DeepBlue,ProbCut}.

We take a step towards a unified view of learning in real-time search and make four contributions. First, we introduce a simple three-parameter framework (named LRTS) that includes LRTA*, \eLRTA, SLA* and $\gamma$-Trap as its special cases. A by-product of this generalization is an extension of the first three algorithms to variable depth lookahead. Second, we prove completeness and convergence for any combination of the parameters. Third, we prove non-trivial theoretical bounds on the influence of the parameters. Fourth, we present a large-scale empirical evaluation in practically relevant domains.



%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Problem Formulation}

In this section, we formally introduce the learning real-time search problem settings and the metrics we will be using. 

\begin{df}\em The search space is defined as a tuple $(S,A,c,s_0,S_g,h_0)$ where $S$ is a finite set of states, $A$ is a finite set of actions, $c : S \times A \to \mathbb{R}^+$ is the cost function with $c(s,a)$ being the incurred cost of taking action $a$ in state $s$, $s_0$ is the initial state, $S_g \subset S$ is the set of goal states, and $h_0$ is the initial heuristic (e.g., Manhattan distance). \edf

We adopt the assumptions of~\citeA{Shue:93a,ShimboIshida03} that (i) for every action in every state there exists a reverse action (possibly with a different cost), (ii) every applicable action leads to another state (i.e., no self-loops), and (iii) at least one goal state in $S_g$ is reachable from $s_0$. Assumption (i) is needed for the backtracking mechanism used in SLA*~\cite{Shue:93a}. It holds in many combinatorial and path-planning problems. Its applicability to domains where reversing an action may require a non-trivial sequence of actions is a subject of future research. Assumption (ii) is adopted for the sake of proof simplicity. In other words, the results presented in this paper hold even if self-loops (of positive cost) are present. As with all real-time search algorithms we are unifying, we assume that the environment is stationary and deterministic. Extension of our algorithms on dynamic/stochastic domains is a subject of current research.

\bdf The execution cost of traveling from state $s_1$ to state $s_2$ denoted by $\dist(s_1,s_2)$ is defined as the minimal cumulative execution cost the agent is to incur by traveling from $s_1$ to $s_2$. Throughout the paper, we will assume that $\dist$ satisfies the standard triangle inequality: $\forall s_1, s_2, s_3 \in S \left[ \dist(s_1,s_3) \le \dist(s_1,s_2) + \dist(s_2,s_3) \right]$. Then, for any state $s$ its true execution cost $h^*$ is defined as the minimal execution cost to the nearest goal: $h^*(s)=\min_{s_g \in S_g} \dist(s,s_g)$. A heuristic approximation $h$ to the true execution cost is called admissible iff $\forall s \in S \left[ h(s) \le h^*(s) \right]$. The value of $h$ in state $s$ will be referred to as the heuristic value of state $s$. We will assume that the heuristic value of the initial heuristic function is 0 for any goal state. The latter assumption holds trivially if the initial heuristic function is admissible.
%
A depth $d$ child of state $s$ is any state $s'$ reachable from $s$ in the minimum of $d$ actions (denoted by $\|s,s'\| = d$). The depth $d$ neighborhood of state $s$ is then defined as $S(s,d) = \{s_d \in S \mid \|s,s_d\| = d\}$. \edf


\begin{df}\em Search agents operate by starting in a fixed start state $s_0$ and executing actions suggested by their control policies. A {\em trial} is defined as a sequence of states the algorithm visits between the start state and the first goal state it encounters. Once a trial is completed, the agent is reset to the start state and the next trial begins. {\em Final trial} is defined as the first trial on which no learning (i.e., updates to the heuristic function) occurs.\footnote{Note that if random tie-breaking is used, more learning can actually take place after a learning-free trial. We use fixed tie-breaking throughout this paper for simplicity.} A {\em convergence run} is the sequence of trials from the first trial to the final trial. \edf

\section{Performance Measures}\label{sec:defs}

Each problem instance is fully specified by the search space which includes the start and goal states. The agent is run until convergence and the following statistics are collected: \begin{description}

\item[execution convergence cost] is the sum of execution costs of the actions taken by the agent during the convergence process (i.e., on the convergence run);

\item[planning cost] is the average cost of planning per action during the convergence process. Planning cost of an action is the number of states the agent considered to decide on taking the action;

\item[total convergence cost] is the total planning convergence cost for all actions during convergence plus the execution convergence cost scaled by a factor called ``planning speed". The scaling factor represents the amount of planning (measured in the number of nodes considered) the agent would be able to do in the time it takes to execute a unit of travel. For instance, the computer on-board an AIBO robodog may be able to plan with 10,000 states in the time it takes the AIBO to traverse 1 foot of distance on the ground. Correspondingly, the planning speed will be 10,000 states per foot. This is a commonly used way of combining the execution and planning costs into a single metric~\cite{RussellWefald-book,Koenig:04a};\footnote{Note that unlike total planning cost, total convergence cost allows us to model domains where some actions are expensive disproportionally to their running time (e.g., taking damage by running into a wall). Additionally, we use the standard real-time search framework and assume that planning and execution are not simultaneous but interleaved.}

\item[memory] is the total amount of memory (measured in the number of state values) the agent used to store the heuristic function during the convergence run. Note that the initial heuristic is usually represented in a compact algorithmic form as opposed to a table. Therefore, memory is required to store only the heuristic values modified during learning;

\ie[first-move delay (lag)] is the amount of planning time (measured in milliseconds\footnote{All timings are taken on a PowerMac G5 running at 2GHz. Apple gcc 3.3 compiler is used.}) the agent takes before deciding on the first move. This is an important metric in real-time strategy games, wherein hundreds to thousands of units can be tasked simultaneously and yet have to react to user's commands as quickly as possible;

\ie[suboptimality of the final solution] is defined as the percentage by which the execution cost of the {\em final} trial exceeds that of the best possible solution. For instance, if a pathfinding agent had the execution cost of 120 on the final trial and the shortest path has the cost of 100, the suboptimality is 20\%.

\end{description}


\section{Application Domains}

In the paper, we illustrate the algorithms in two realistic testbeds: real-time navigation in unknown terrain and routing in {\em ad hoc} wireless sensor networks. The former domain is more standard to single-agent search and so we will use it throughout the paper to illustrate our points. The latter domain is a relative newcomer to the field of real-time heuristic search. We will use it later in the paper (Section~\ref{sec:combos}) to demonstrate how learning single-search methods  can handle a practically important yet different task.

Note that both domains have the desired attributes listed in the introduction. Indeed, in both domains, the state space is initially unknown, the agent is in a single current state to be changed via executing actions, the agent can sense only a local part of the state space centered on the agent's current state, the planning time per action should be minimized, and there are repeated trials.



\subsection{Real-time navigation in next-generation video games}\label{sec:HOG}

The agent is tasked to travel from the start state $(x_s,y_s)$ to the single goal state $(x_g,y_g)$. The coordinates are on a two-dimensional rectangular grid. In each state, up to eight moves are available leading to the eight immediate neighbors. Each straight move (i.e., north, south, west, east) has a {\em travel cost} of $1$ while each diagonal move has a travel cost of $\sqrt{2}$. Each state on the map can be passable or occupied by a wall. In the latter case, the agent is unable to move into it. Initially, the map in its entirety is unknown to the agent. In each state $(x,y)$ the agent can see the status (occupied/free) in the neighborhood of the {\em visibility radius} $v$: $\{ (x',y') \mid |x'-x| \le v \And |y'-y| \le v\}$. The initial heuristic we use is the so-called {\em octile distance} defined as the length of a shortest path between the two locations if all cells are passable. It is a translation of Manhattan distance onto the case of eight moves and can be easily computed in a closed form.

Note that classical A* search  is inapplicable due to an initially unknown map. Specifically, it is impossible for the agent to plan its path through state $(x,y)$ unless it is either positioned within the visibility radius of the state or has visited this state on a prior trial.  A simple  solution to this problem is to generate the initial path under the assumption that the unknown areas of the map contain no occupied states \cite<the free space assumption of>{Koenig:03a}. With the octile distance  as the heuristic, the initial path is close to the straight line since the map is assumed to be empty. The agent follows the existing path until it runs into an occupied state. During the travel, it updates the explored portion of the map in its memory. Once the current path is blocked, A* is invoked again to generate a new complete path from the current position to the goal. The process repeats until the agent arrives at the goal. It is then reset to the start state and a new trial begins. The convergence run ends when no new states are seen.\footnote{Note that this framework can be easily extended to the case of multiple start and goal states.}

To increase planning efficiency, several methods of re-using information over subsequent planning episodes have been suggested. Two popular versions are D*~\cite{Stenz:95} and D*~Lite \cite{Koenig:02a}. Powerful as they are, these enhancements do not reduce the first-move lag time. Specifically, after the agent is given the destination coordinates, it has to conduct an A* search from its position to the destination before it can move. Even on small maps, this delay can be substantial. 
This is in contrast to LRTA*~\cite{Korf-AIJ}, which only performs a small local search to select the first move. As a result, several orders of magnitude more agents can respond to a user's request in the time it takes one A* agent.

As present-day games circumvent these problem by using fully observable maps and pre-computing auxiliary data structures beforehand, we conduct our experiments in a research prototype, called Hierarchical Open Graph (HOG), developed at the University of Alberta by Nathan Sturtevant. It allows one to load maps from commercial role-playing and real-time strategy games such as Baldur's Gate~\cite{BaldurGate} and WarCraft III ~\cite{WarCraft3}. We use five maps ranging in size from 214 $\times$ 192 states (of which 2765 are traversable) to 235 $\times$ 204 (with 16142 traversable states). The largest map is shown in Figure~\ref{fig:BGmap}.  A total of 1000 problem instances on the five maps were randomly chosen so that their shortest path lengths fall in the ten bins: 1-10, 11-20, \dots, 91-100 with 100 problems per bin. We will use this suite of 1000 problems throughout the paper.  

\begin{figure}[ht]
\begin{center}
\includegraphics[height=5cm]{BG1.pdf}\hspace{1cm}
\includegraphics[height=5cm]{BG2.pdf}
\caption{{\bf Left:} one of the five test maps from Baldur's Gate -- a commercial role-playing game by BioWare. {\bf Right:} a close-up showing the agent as a dot in the middle.}\label{fig:BGmap}
\end{center}\vspace{-1.2cm}
\end{figure}


\section{LRTS: A Unifying Framework}

In this section we will introduce the primary contribution of this paper --- the unifying framework of real-time heuristic search --- in an incremental fashion. Namely, we will start with the base algorithm, LRTA*, and then analyze three extensions: deeper lookahead, optimality weight, and backtracking. Each extension is illustrated with a hand-traced micro-example and empirical results in the real-time pathfinding domain. A unifying algorithm constitutes the section's finale.

\subsection{Learning Real-Time A* (LRTA*)}
%
LRTA* introduced by~\citeA{Korf-AIJ}, is the first and best known learning real-time heuristic search algorithm . The key idea lies with interleaving acting and backing up heuristic values (Figure~\ref{fig:LRTA-simple}).\footnote{For clarity, all pseudocode in this paper describes a single trial only.} Specifically, in the current state $s$, LRTA* with a lookahead of one considers the immediate neighbors (lines 4-5 in Figure~\ref{fig:LRTA-simple}). For each neighbor state, two values are computed: the execution cost of getting there from the current state (henceforth denoted by $g$) and the estimated execution cost of getting to the closest goal state from the neighbor state (henceforth denoted by $h$). While $g$ is known precisely, $h$ is a heuristic estimate. LRTA* then travels to the state with the lowest $f = g + h$ value (line 7). Additionally, it updates the heuristic value of the current state if the minimum $f$-value is greater than the heuristic value of the current state (line 6).\footnote{This condition is not necessary if the heuristic is consistent as $f$-values will be non-decreasing along all lookahead branches. In general, there is no need to decrement the $h$-value of any state if the initial heuristic is admissible.}

\begin{figure}[ht]
%\vspace{0.4cm}
%\small
\hrule\smallskip
\textbf{LRTA*}

\vspace{1mm}

\begin{tabular} {p{0.2cm}l}
1 & initialize the heuristic: $h \leftarrow h_0$ \\
2 & reset the current state:  $s \leftarrow s_\text{start}$ \\
3 & {\bf while} $s \not \in S_g$ {\bf do} \\
4 & \hspace{2mm} generate children one move away from state $s$ \\
5 & \hspace{2mm} find the state $s'$ with the lowest $f = g + h$ \\
6 & \hspace{2mm} update $h(s)$ to $f(s')$ if $f(s')$ is greater \\
7 & \hspace{2mm} execute the action to get to $s'$ \\
8 & {\bf end while} \\
\end{tabular}

\smallskip\hrule\vspace{-0.1cm}
\caption{LRTA* algorithm with a lookahead of one.}\label{fig:LRTA-simple}
\vspace{-0.2cm}
\end{figure} 


\citeA{Korf-AIJ} showed that in finite domains where the goal state is reachable from any state and all action costs are non-zero, LRTA* finds a goal on every trial. Additionally, if the initial heuristic function is admissible then LRTA* will converge to an optimal solution after a finite number of trials. 
%
Compared to A* search, LRTA* with a lookahead of one has a considerably shorter first-move lag and finds suboptimal solutions much faster. However, converging to an optimal (e.g., lowest execution cost) solution can be expensive in terms of the number of trials and the total execution cost. Table~\ref{tab:LRTA} lists measurements averaged over 1000 convergence runs on the five game maps in the pathfinding domain (details in Section~\ref{sec:HOG}). The differences become more pronounced for larger problems (Figure~\ref{fig:LRTA-scale}).  

\begin{table}[ht]
\vspace{-0.3cm}
\caption{LRTA* with a lookahead of one vs. A* in pathfinding.}\label{tab:LRTA}
{\begin{center}\vspace{0.2cm}
\begin{tabular}{c|c|c}
\hline
 Algorithm & First-move lag & Convergence execution cost \\ 
 \hline
A* & 3.09 ms & 159 \\
LRTA* & 0.05 ms & 9346 \\
\hline
\end{tabular}
\end{center}}\vspace{-0.7cm}
\end{table}

\begin{figure}[ht]
\begin{center}
\includegraphics[height=4.5cm]{LRTA-scale1.pdf}%\hspace{0.1cm}
\includegraphics[height=4.7cm]{LRTA-scale2.pdf}\vspace{-0.2cm}
\caption{Differences between LRTA* and A* as pathfinding problems scale up.}\label{fig:LRTA-scale}
\end{center}\vspace{-0.7cm}
\end{figure}



\subsection{Extension 1: Deeper Lookahead Search}\label{sec:d}

LRTA* follows the heuristic landscape to a local minimum. It avoids getting stuck there by raising the heuristic values and eventually eliminating the local minimum. Thus, local heuristic minima, caused by inaccuracies in the initial heuristic values, are eliminated through the process of learning. 
%
\citeA{Ishida97} referred to such inaccuracies in the heuristic as ``heuristic depressions". He studied them for the basic case of LRTA* with a lookahead of one. Heuristic depressions were later generalized for the case of weighted LRTA* and arbitrary lookahead in~\cite{Bulitko:04a} under the name of $\gamma$-traps. 

In the process of ``filling in" heuristic depressions, the agent can incur substantial execution cost by moving back and forth {\em inside} the depression. This happens due to the fact that LRTA* with a lookahead of one is myopic and conducts a minimum amount of planning per move. If planning is cheaper than execution, then a natural solution is to increase the amount of planning per move with the hope of eliminating heuristic local minima at a lower execution cost. 

In LRTA*, additional planning per move is implemented through deeper lookahead search. The heuristic update and action selection rules introduced in the previous section can be extended to an arbitrary lookahead depth in a manner inspired by the standard mini-max search in games~\cite{Korf-AIJ}. Korf called the new rule ``mini-min" and empirically observed that deeper lookahead decreases the execution cost but increases the planning cost per move. The phenomenon can be illustrated with a hand-traceable example in Figure~\ref{fig:d-illustrated1}. Each of the six states is shown as a circle with the actions shown as edges. Each action has the cost of 1. The initial heuristic $h_0$ is admissible but inaccurate. Heuristic values before and after the first trial are shown as numbers under each state (circle). 

\begin{figure}[ht]\vspace{-0.3cm}
\begin{center}
\includegraphics[width=\textwidth]{d-illustrated1.pdf}
\vspace{-0.7cm}
\caption{Initial and final heuristics of LRTA* with a lookahead of one (left) and two (right).}\label{fig:d-illustrated1}
\end{center}\vspace{-0.5cm}
\end{figure}

\nin Both LRTA* with a lookahead of one and two converge to their final heuristics in one trial. However, the additional ply of lookahead takes advantage of the two extra heuristic values and, as a result, reduces the execution cost from 5 to 3 moves. On the other hand, the planning cost of each move increases from 2 to 4 nodes. 

In general, more planning per action ``compensates" for inaccuracies in the heuristic function and allows one to select better moves. Table~\ref{tab:d-avg} demonstrates this effect averaged over the 1000 pathfinding problems. The reduction of execution cost due to deeper lookahead becomes more pronounced in larger problems (Figure~\ref{fig:d-scale}). 


\begin{table}[ht]\vspace{-0.5cm}
\caption{Effects of deeper lookahead in LRTA*.}\label{tab:d-avg}
{\begin{center}\vspace{0.2cm}
\begin{tabular}{c|c|c}
\hline
Lookahead & First move lag & Execution convergence cost \\ 
 \hline
1 & 0.05 ms & 9346 \\
3 & 0.26 ms & 7795 \\
5 & 0.38 ms & 6559 \\
7 & 0.68 ms & 5405 \\
9 & 0.92 ms & 4423 \\
\hline
\end{tabular}
\end{center}}\vspace{-0.6cm}
\end{table}

\begin{figure}[ht]\vspace{-0.3cm}
\begin{center}
\includegraphics[width=10cm]{d-scale.pdf}
\vspace{-0.3cm}
\caption{Convergence of LRTA* with different lookaheads as problems scale up.}\label{fig:d-scale}
\end{center}\vspace{-0.5cm}
\end{figure}

Lookahead search in LRTA*-like algorithms has received considerable attention in the literature. \citeA{RussellWefald-book} and \citeA{Koenig:04a} analyzed selection of the lookahead depth optimal in terms of the {\em total} cost (i.e., a weighted combination of the planning and execution costs). \citeA{Bulitko:03c} and \citeA{Bulitko:03d} examined pathological cases of deeper lookahead increasing {\em both} execution and planning costs.



\subsection{Extension 2: Heuristic Weight}\label{sec:gamma}
%
Scalability of LRTA* to large problems is determined by two of its attributes. First, it uses the initial ``optimistic" heuristic function for the unknown areas of the search space and more informed, ``realistic" function for the explored areas. This results in the so-called ``optimism in the face of uncertainty" where the agent eagerly explores novel parts of the space. Consequently, the convergence time is lengthened and the solution quality oscillates significantly over consecutive trials~\cite{ShimboIshida03}. Second, the complete convergence process can be intractable in terms of running time and the amount of memory required to store the heuristic because optimal solutions are sought. Indeed, even simple problems can be intractable in terms of finding optimal solutions \cite<e.g., the generalized sliding tile puzzle of>{Ratner86}.

A weighted version of LRTA* was proposed by~\citeA{ShimboIshida03} as a systematic way of giving up  optimality of the converged solution. The authors argued that optimal solutions are rarely needed in practice, nor can they be achieved in large domains. Consequently, the user must settle for suboptimal but satisficing solutions. Weighted LRTA* is the same algorithm (LRTA*) run with an inadmissible initial heuristic. The inadmissibility is bounded as for every state its $h(s)$ value is required to be upper-bounded by $(1+\epsilon)h^*(s)$ where $h^*(s)$ is the true distance to goal. The resulting $\epsilon$-admissibility leads to $\epsilon$-optimality of the solution to which such an \eLRTA converges. By giving up optimality in the $\epsilon$-controlled fashion, the algorithm gains faster convergence, smaller memory requirements, and higher stability. Note that $0$-LRTA* is equivalent to the original LRTA*. 

\citeA{ShimboIshida03} used Manhattan distance scaled by $(1+\epsilon)$ as the initial heuristic $h_0$. The underlying idea can be illustrated in a five-state domain (Figure~\ref{fig:gamma-illustrated1}). On the left, the initial heuristic is listed immediately under the five states (shown as circles). Each action (shown with an edge) has the execution cost of 1. Every trial of LRTA* will involve four moves and will update the heuristic values. The values after each trial are listed as successive rows. After 16 moves (4 trials), LRTA* will converge to the perfect heuristic. On the right, we start with the same heuristic multiplied by $(1+\epsilon) = 2$. As shown there, $1$-LRTA* takes only one trial (i.e., 4 moves) to converge.

\begin{figure}[ht]\vspace{-0.3cm}
\begin{center}
\includegraphics[width=\textwidth]{gamma-illustrated1.pdf}
\vspace{-0.7cm}
\caption{Heuristic values over successive trials of: LRTA* (left) and $1$-LRTA* (right).}\label{fig:gamma-illustrated1}
\end{center}\vspace{-0.5cm}
\end{figure}

In general, by scaling the initial (admissible) heuristic by $(1+\epsilon)$, the amount of underestimation of an admissible initial heuristic relative to the perfect heuristic is reduced in many states. Therefore, the number of updates (line 6 in LRTA*, Figure~\ref{fig:LRTA-simple}) needed to increase the initial heuristic value of a state to its final value is reduced. Correspondingly, the execution convergence cost is lowered and learning is sped up. Figure~\ref{fig:discrepancy} illustrates the correlation in the pathfinding domain. The discrepancy is the amount of underestimation in the initial heuristic $(1+\epsilon)h_0$ averaged over all states of the map at hand ($s \in S$):
%
\bea \avg_{s_{\text{goal}}, \ s \in S} \frac{h^*(s,s_{\text{goal}}) \dot{-} (1+\epsilon)h_0(s,s_{\text{goal}})}{h^*(s,s_{\text{goal}})}. \eea
%
\nin Here $\dot{-}$ denotes non-negative subtraction: $a \dot{-}  b$ equals $a-b$ if the result is positive and 0 otherwise. As usual, $h^*$ is the perfect heuristic and $h_0$ is the octile distance. The heuristics are taken with respect to the 1000 random goal states ($s_{\text{goal}}$) defined in Section~\ref{sec:HOG}.


\begin{figure}[ht]
\begin{center}
\includegraphics[height=5cm]{discrepancy.pdf}\vspace{-0.2cm}
\caption{Convergence cost of \eLRTA vs. the weighted initial heuristic discrepancy. The points on the graph correspond to these values of $(1+\epsilon)$: 3.3, 2.0, 1.5, 1.1, 1.0.}\label{fig:discrepancy}
\end{center}\vspace{-0.7cm}
\end{figure}


On the negative side,  the scaling is uniform over all states and will sometimes result in the scaled values exceeding the perfect heuristic values. Such inadmissibility can lead to suboptimal solutions as illustrated in Figure~\ref{fig:gamma-illustrated2}. Specifically, the initial heuristic is admissible (the values of the five states are shown above the circles in the left part of the figure). All actions (shown as arrows) have the execution cost of 1. Thus, LRTA* converges to the optimal path (i.e., through the top state). On the other hand, scaling the heuristic by $(1+\epsilon)=3$ (shown on the right) leads $2$-LRTA* to converge on a longer suboptimal path (through the bottom two states). 

\begin{figure}[ht]\vspace{-0.1cm}
\begin{center}
\includegraphics[width=10cm]{gamma-illustrated2.pdf}
\vspace{-0.3cm}
\caption{$2$-LRTA* converges to a suboptimal path.}\label{fig:gamma-illustrated2}
\end{center}\vspace{-0.5cm}
\end{figure}

In summary, scaling an initial (admissible) heuristic by $1+\epsilon$ tends to reduce the underestimation error of the heuristic thereby speeding up convergence. As the weighted heuristic becomes progressively more overestimating, suboptimality of the final solutions increases and, eventually, overall convergence slows down (due to less informative weighted heuristic). Table~\ref{tab:eLRTA} illustrates the trends in the pathfinding domain. 
%
Once again, the effect is more pronounced for larger problems (Figure~\ref{fig:eLRTA-scale}).

Note that a similar effect has been observed with weighted A* search wherein a weight $w$ is put on the heuristic $h$. When $w$ exceeds $1$, fewer nodes are expanded at the cost of suboptimal solutions~\cite{Korf-LSBFS}. Table~\ref{tab:wA} lists the results of running weighted A* on the pathfinding problems used in Table~\ref{tab:eLRTA}.



\begin{figure}[ht]
\begin{center}
\includegraphics[height=4.65cm]{eLRTA-scale1.pdf}%\hspace{0.1cm}
\includegraphics[height=4.4cm]{eLRTA-scale2.pdf}\vspace{-0.2cm}
\caption{Impact of heuristic weight as pathfinding problems scale up.}\label{fig:eLRTA-scale}
\end{center}\vspace{-0.7cm}
\end{figure}

\begin{table}[ht]\vspace{-0.2cm}
\caption{Effects of scaling the initial heuristic in \eLRTA.}\label{tab:eLRTA}
{\begin{center}\vspace{0.2cm}
\begin{tabular}{l|c|c}
\hline
Heuristic weight ($1+\epsilon$) & Execution convergence cost & Suboptimality\\ 
 \hline
10.0 & 2832 & 3.17\% \\
5.0 & 2002 & 2.76\% \\
3.3 & 1908 & 2.20\% \\
2.0 & 2271 & 1.52\% \\
1.5 & 3639 & 0.97\% \\
1.1 & 6520 & 0.25\% \\
1.0 (LRTA*) & 9346 & 0.00\% \\
\hline
\end{tabular}
\end{center}}\vspace{-0.6cm}
\end{table}

\begin{table}[ht]\vspace{-0.2cm}
\caption{Effects of scaling the initial heuristic in weighted A*.}\label{tab:wA}
{\begin{center}\vspace{0.2cm}
\begin{tabular}{l|c|c}
\hline
Heuristic weight & Planning convergence cost & Suboptimality\\ 
 \hline
10.0 & 1443 & 3.48\% \\
5.0 & 1568 & 3.08\% \\
3.3 & 1732 & 2.37\% \\
2.0 & 2074 & 1.69\% \\
1.5 & 3725 & 1.16\% \\
1.1 & 5220 & 0.30\% \\
1.0 (A*) & 10590 & 0.00\% \\
\hline
\end{tabular}
\end{center}}\vspace{-0.4cm}
\end{table}


\subsection{Extension 3: Backtracking}\label{sec:T}

Both LRTA* and \eLRTA learn by updating their heuristic function while advancing in the state space.  SLA*~\cite{Shue:93a}  introduced a backtracking mechanism. That is, upon making an update to heuristic value of the current state, the agent backtracks to its previous state. This 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 physically moving the agent there). This is the approach exploited, for example, by temporal difference methods with eligibility traces~\cite{Qlambda,MDP}. It does not give the agent opportunity (ii) above. Naturally, all backtracking moves are counted in execution cost.

\begin{figure}[ht]\vspace{-0.3cm}
\begin{center}
\includegraphics[width=\textwidth]{backtracking-illustrated.pdf}
\vspace{-1.0cm}
\caption{Heuristic values over successive trials of: LRTA* (left) and SLA* (right).}\label{fig:backtracking-illustrated}
\end{center}\vspace{-0.5cm}
\end{figure}

The underlying intuition can be illustrated with a simple example in Figure~\ref{fig:backtracking-illustrated}. Once again, consider a one-dimensional five-state domain. Each action has an execution cost of one.  The initial heuristic is accurate in the left two states and one lower in the right three states. On each trial, LRTA* will raise the heuristic value of a single state. Therefore, three trials (12 moves) are needed to make the heuristic perfect. SLA*, on the other hand, gets to the middle state in 2 moves, updates its value from 1 to 2, backtracks to the second state from the right, increases its value from 2 to 3, backtracks to the right most state, and increases its value from 3 to 4. The agent will then take 4 moves towards the goal, following the now perfect heuristic. As a result, the first trial is longer (8 vs. 4 moves) but the overall number of moves until convergence is reduced (from 12 to 8).

The SLA* algorithm is nearly identical to LRTA* with a lookahead of one (Figure~\ref{fig:LRTA-simple}). The only difference is that upon increasing the state value in line 6, the agent takes an action leading to its previous state and not the state $s'$ as in line 7 of LRTA*. If the previous state does not exist (i.e., the algorithm reached the start state) then no action is taken but the heuristic value is still updated.

SLA* backtracks {\em every time} its heuristic is updated (i.e., learning took place). This causes very substantial execution cost of the first trial. In fact, as we will prove in Theorem~\ref{th:SLA}, {\em all} learning occurs during the first trial. In larger problems, the user may want a suboptimal solution before the convergence process completes. To address this problem, SLA*T, introduced in~\cite{Shue:01}, gives the user control over the amount of learning to be done per trial. Namely, SLA*T backtracks only after it exhausts a user-specified {\em learning quota}. 

There are two primary effects of backtracking on the metrics we consider in this paper. First, larger values of learning quota decrease the execution cost on each trial as less backtracking occurs. In the extreme, the learning quota can be set to infinity, transforming SLA*T into backtracking-free LRTA* with a lookahead of one. On the other end of the spectrum (with a learning quota of zero), SLA*T always backtracks upon updating a heuristic value and becomes equivalent to SLA*. More backtracking tends to speed up the convergence process (i.e., decrease the convergence execution cost) as fewer trials are needed to converge (recall the example in Figure~\ref{fig:backtracking-illustrated}). Empirically, the first effect of backtracking is most clearly seen in the 8-puzzle (Table~\ref{tab:T-8p}) as well as the pathfinding task with small maps (Table~\ref{tab:T-smallMaps}).  It is still an open question why the trend is not observed on larger pathfinding tasks (Table~\ref{tab:T-largeMaps}).

\begin{table}[ht]\vspace{-0.5cm}
\caption{Effects of backtracking in the 8-puzzle.}\label{tab:T-8p}
{\begin{center}\vspace{0.2cm}
\begin{tabular}{l|c|c|c}
\hline
Learning quota & First trial execution cost & Convergence execution cost & Memory required \\ \hline
0 (SLA*) & 1846 & 2321 & 728 \\
7 & 424 & 52766 & 18751 \\
13 & 375 & 57816 & 20594 \\
$\infty$ (LRTA*) & 371 & 58002 & 25206 \\
\hline
\end{tabular}
\end{center}}\vspace{-0.6cm}
\end{table}

\begin{table}[ht]\vspace{-0.2cm}
\caption{Effects of backtracking in the pathfinding domain with small maps.}\label{tab:T-smallMaps}
{\begin{center}\vspace{0.2cm}
\begin{tabular}{l|c|c}
\hline
Learning quota & First trial execution cost & Convergence execution cost \\ \hline
0 (SLA*) & 434 & 457 \\
10 & 413 & 487 \\
50 & 398 & 592 \\
1000 & 390 & 810 \\
$\infty$ (LRTA*) & 235 & 935  \\
\hline
\end{tabular}
\end{center}}\vspace{-0.4cm}
\end{table}

The second effect of backtracking is reduction in the amount of memory required to store the learned heuristic values.\footnote{Recall that the initial heuristic values are not stored in the table but come from an effectively computable function such as the Manhattan distance.} During backtracking, the agent tends to update heuristic values in previously visited states. Such updates do not require additional memory to be allocated. The memory-saving effect is seen across all problem sizes in Table~\ref{tab:T-8p} and Table~\ref{tab:T-largeMaps}.

\begin{table}[ht]\vspace{-0.2cm}
\caption{Effects of backtracking in the pathfinding domain with large maps.}\label{tab:T-largeMaps}
{\begin{center}\vspace{0.2cm}
\begin{tabular}{l|c|c}
\hline
Learning quota & Convergence execution cost & Memory required \\ \hline
0 (SLA*) & 9741 & 174 \\
10 & 10315 & 178 \\
100 & 11137 & 207 \\
1000 & 10221 & 258 \\
10000 & 9471 & 299 \\
$\infty$ (LRTA*) & 9346 & 303 \\
\hline
\end{tabular}
\end{center}}\vspace{-0.5cm}
\end{table}

\subsection{Combining the Extensions}\label{sec:LRTS-simple}

\begin{table}[ht]\vspace{-0.2cm}
\caption{Real-time heuristic methods compared along several dimensions.}\label{tab:sCases}
{\begin{center}\vspace{0.3cm}
\begin{tabular}{c|c|c|c|c|c}
\hline
Algorithm & Lookahead & Learning rule & Execution & Optimality & Backtracking  \\ 
 \hline
LRTA* & arbitrary & mini-min, frontier & one action & optimal & none \\
\eLRTA & arbitrary & mini-min, frontier & one action & $\epsilon$-optimal & none \\
SLA* & one ply & mini-min, frontier & one action & optimal & always \\
SLA*T & one ply & mini-min, frontier & one action & optimal & controlled by $T$ \\
$\gamma$-Trap & arbitrary & max of min, all states & $d$ actions & $\gamma$-optimal & always \\
\bf LRTS & \bf arbitrary & \bf max of min, all states & \bf $d$ actions & \bf $\gamma$-optimal & \bf controlled by $T$ \\
\hline
\end{tabular}
\end{center}}\vspace{-0.7cm}
\end{table}

The previous sections introduced three extensions of the base algorithm LRTA*.  Table~\ref{tab:sCases} lists six algorithms that use the extensions. The first entry summarizes the arbitrary-depth LRTA* which uses the mini-min backup rule to propagate the heuristic values from the search frontier to the interior states in the lookahead tree. It executes one action and converges to an optimal solution. No backtracking is used. Weighted LRTA* (\eLRTA) converges to an $\epsilon$-optimal solution but is identical to LRTA* in all other columns of the table. SLA* and SLA*T are myopic versions of LRTA* but use backtracking: unlimited or controlled by the learning quota $T$ respectively. Backtracking was independently introduced in another algorithm, called \gTrap \cite{Bulitko:04a}, which also used a heuristic weight parameter $\gamma = 1/(1+\epsilon)$ to the same effect as weighted LRTA*. Additionally, \gTrap employed a more aggressive heuristic update rule, denoted by ``max of min" in the table, and used heuristic values of all states (as opposed to the frontier of the lookahead search only). Instead of taking a single action between the lookahead search episodes, it applied $d$ actions to amortize the planning cost.  

We will now combine the three extensions into a single algorithm called Learning Real-Time Search or LRTS. It is shown in the last row of the table and, in a simplified fashion, in Figure~\ref{fig:LRTS-simple}. The detailed pseudo-code necessary to re-implement the algorithm as well as to follow the theorem proofs is found in Figure~\ref{fig:LRTS}, Appendix~\ref{sec:pseudocode}. We will now step through the operation of LRTS and explain the control parameters.

In line 1, the trial is initialized by setting the current state $s$ of the agent to the start state $s_{\text{start}}$ and resetting the amount of learning done on the trial ($u$). As long as the goal state $s_{\text{goal}}$ is not reached, the LRTS agent interleaves planning (lines 3 and 4), learning (line 5), and execution (lines 6-11). During the planning state, LRTS uses the model of its environment (implicitly updated when new states comes into the agent's radius of visibility) to generate all child states of the current state up to $d$ moves away. On each lookahead level ($i = 1, 2, \dots, d$), LRTS finds the most promising state ($s_i$) that minimizes the weighted estimate of the total distance: \bea 
s_i = \arg \min_{s' \in S(s,i)} \left(\gamma \cdot g(s') + h(s') \right),
\eea
\nin where $g(s')$ is the shortest distance from the current state $s$ to its child $s'$ and $h(s')$ is the heuristic estimate of the distance from the child state $s'$ to the goal state $s_{\text{goal}}$. Throughout this paper we will be breaking ties in a systematic fashion as detailed later in the paper. Note that the distance $g(s')$ from the current state $s$ to the child state $s'$ is weighted by the control parameter $\gamma \in (0,1]$. The same behavior can be obtained by multiplying the initial heuristic by $1+\epsilon = 1 / \gamma$ in \eLRTA except that it makes the initial heuristic inadmissible (Theorem~\ref{th:eqeLRTA}).


\begin{figure}[ht]
\vspace{-0.1cm}
\hrule\smallskip
\textbf{LRTS($d,\gamma,T$)}

\vspace{1mm}

\begin{tabular} {p{0.2cm}l}
1 & initialize: $s \leftarrow s_\text{start}$, $u \leftarrow 0$ \\
2 & {\bf while} $s \not \in S_g$ {\bf do} \\
3 & \hspace{2mm} generate children $i$ moves away, $i = 1 \dots d$ \\
4 & \hspace{6mm} on level $i$, find the state $s_i$ with the lowest  $f = \gamma \cdot g + h$ \\
5 & \hspace{2mm} update $h(s)$ to $\max\limits_{1 \leq i \leq d}f(s_i)$ if it is greater \\
6 & \hspace{2mm} increase the amount of learning $u$ by $|\Delta h|$ \\
7 & \hspace{2mm} {\bf if} $u \le T$ {\bf then} \\
8 & \hspace{4mm} execute $d$ moves to get to the state $s_d$ \\
9 & \hspace{2mm} {\bf else} \\
10 & \hspace{4mm} execute $d$ moves to backtrack to the previous state, set $u = T$ \\
11 & \hspace{2mm} {\bf end if} \\
12 & {\bf end while} \\
\end{tabular}

\smallskip\hrule%\vspace{-0.2cm}
\caption{LRTS algorithm combines the three extensions of LRTA*.}\label{fig:LRTS-simple}
\vspace{-0.1cm}
\end{figure} 

The lookahead search conducted in line 5 has the complexity of $O(b^d)$ if no child state is reached more than once and $b$ is the branching factor. On maps, however, the complexity is much reduced to $O(d^n)$ where $n$ is the dimensionality of the map. Thus, in both the path-planning and the sensor network routing task, the lookahead has a complexity of $O(d^2)$. 

Like \gTrap, LRTS uses the so-called ``max of min" heuristic update (or learning) rule in line~5. Specifically, if the initial heuristic is admissible, then the agent will want to increase it as aggressively as possible while keeping it admissible. Lemma~\ref{th:adm} will prove that setting the heuristic value $h$ of the current state $s$ to the {\em maximum} of minima found on each ply preserves the admissibility of $h$ at all times.

In line 6 the amount of increase to the heuristic value of the current state ($h(s)$) is then added to the cumulative amount of learning done so far on the trial ($u$). If the new amount of learning does not exceed the learning quota $T$ then the agent will execute $d$ moves to the most promising frontier state $s_d$ seen during the lookahead (line 8). The moves are added to the path so that they can be ``undone" later on during backtracking. If the new amount of learning exceeds the learning quota $T$ then the agent will backtrack to its previous state (line 10). By doing so, it will ``undo" the last $d$ actions. The last $d$ actions are thus removed from the path traveled so far on the trial. Note that the backtracking actions count in execution cost. 

We now encourage the reader to revisit the hand-traceable examples found in Sections~\ref{sec:d}, \ref{sec:gamma}, \ref{sec:T} as they show LRTS operation in simple domains. In the weighting example (Section~\ref{sec:gamma}), $\gamma$ should be set to $1 / (1+\epsilon)$ to enable LRTS to behave as \eLRTA.
%
This concludes the presentation of the LRTS algorithm and we will now highlight its properties with theoretical and empirical results.

\section{Theoretical Results}\label{sec:theory}

The LRTS framework includes LRTA*, weighted LRTA*, SLA*, and $\gamma$-Trap as special cases (Table~\ref{tab:sCases}). This fact is presented formally in the following theorems. All proofs are found in Appendix~\ref{sec:proofs}. Note that while the following assumptions are not mandatory for real-time search, they are needed for the proofs. Specifically, the search space is assumed to be deterministic and stationary. Additionally, the agent's current state is affected only by the agent's actions. Finally, the agent possesses a sufficient knowledge of the environment to conduct a local-search (i.e., lookahead) of depth $d$ in its current state.

\bt\label{th:eqLRTA} LRTS$(d=1, \gamma=1, T=\infty)$ is equivalent to LRTA* with a lookahead of one. 
\et

\bt\label{th:eqeLRTA} LRTS$(d=1, \gamma=\frac{1}{1+\epsilon}, T=\infty)$ initialized with an admissible heuristic $h_0$ is equivalent to \eLRTA initialized with $(1+\epsilon)h_0$. \et

\bt\label{th:eqSLA} LRTS$(d=1, \gamma=1, T=0)$ is equivalent to SLA*. 
\et

\bt\label{th:eqgTrap} LRTS$(d,\gamma,T=0)$ is equivalent to $\gamma$-Trap$(d,\gamma)$. 
\et

In the past, convergence and completeness have been proven for the special cases (LRTA*, \eLRTA, and SLA*). We will now prove these properties for any valid values of the lookahead $d \in \mathbb{N}, d \ge 1$, the heuristic weight $\gamma \in \mathbb{R}, \gamma \in (0,1]$, and the learning quota $T \in \mathbb{R} \cup \{\infty\}, T \ge 0$.

\begin{df}\em A tie-breaking scheme is employed when two or more states have equal $f=g + h$ values.  Among candidate states with equal $f$-values, {\em random tie-breaking} selects one at random. This scheme was used in~\cite{ShimboIshida03}. {\em Systematic tie-breaking} used by \citeA{FALCONS} uses a fixed action ordering per current state. The orderings are, however, generated randomly for each search problem. Finally, {\em fixed tie-breaking} always uses the same action ordering. We use the latter scheme for all our experiments as it is the simplest.
\end{df}

\begin{lemma}\label{th:adm} {\bf (Admissibility) }\em For any valid $T, \gamma, d$ and an admissible initial heuristic $h_0$, the heuristic function $h$ is maintained admissible at all times during LRTS$(d,\gamma,T)$ search.
\end{lemma}

\bt\label{th:completeness} {\bf (Completeness)} For any valid $T, \gamma, d$ and an admissible initial heuristic $h_0$, LRTS$(d,\gamma,T)$ arrives at a goal state on every trial. \et

\bt\label{th:convergence} {\bf (Convergence)} For any valid $T, \gamma, d$ and an admissible initial heuristic $h_0$, LRTS$(d,\gamma,T)$ with systematic or fixed tie-breaking converges to its final solution after a finite number of trials. It makes zero updates to its heuristic function on the final trial. Each subsequent trial will be identical to the final trial. \et

\bt\label{th:gamma} {\bf (Suboptimality)} For any valid $T, \gamma, d$ and an admissible initial heuristic $h_0$, the execution cost of the final trial of LRTS$(d,\gamma,T)$ is upper-bounded by $\frac{h^*(s_0)}{\gamma}$. In other words, the suboptimality of the final solution is no worse than $\frac{1}{\gamma}-1$. \et

A non-trivial upper-bound of $\frac{h^*(s_0)+T}{\gamma}$ can be imposed on the solution produced by LRTS on the {\em first} trial. This requires, however, a minor extension of the LRTS algorithm. Thus, we list the extension and the theorem in Figure~\ref{fig:LRTS-pruning}, Appendix~\ref{sec:pseudocode} and Theorem~\ref{th:SLAT}, Appendix~\ref{sec:proofs} respectively.

\bt\label{th:SLA} {\bf (One trial convergence)} For any valid $\gamma, d$ and an admissible initial heuristic $h_0$, the second trial of LRTS$(T=0)$ with systematic or fixed tie-breaking is guaranteed to be final. Thus, all learning and exploration are done on the first trial. \et

\section{Combinations of Parameters}\label{sec:combos}

We have introduced a three-parameter algorithm unifying several previously proposed extensions to the base LRTA*. We have also demonstrated theoretically and empirically the influence of each parameter {\em independently} of the other two parameters in Sections~\ref{sec:d}, \ref{sec:gamma}, and \ref{sec:T}. The summary of the influences is found in Table~\ref{tab:influences-summary}. An up-arrow/down-arrow means an increase/decrease in the metric. Notation $a \to p \to b$ indicates that the parameter $p$ increases from $a$ to $b$. To illustrate: $\downarrow$ at the intersection of the row labeled ``convergence execution cost" and the column labeled ``$1 \to d \to \infty$" states that the convergence execution cost decreases as $d$ goes up.

\begin{table}[ht]\vspace{-0.2cm}
\caption{Summary of influences of LRTS parameters in the pathfinding domain.}\label{tab:influences-summary}
{\small \begin{center}\vspace{0.1cm}
\begin{tabular}{c|c|c|c}
\hline
metric / parameter & $1 \to d \to \infty $ & $0 \to \gamma \to 1$ & $0 \to T \to \infty$ \\ \hline
convergence execution cost & $\downarrow$ & $\downarrow$ for small $\gamma$, $\uparrow$ for large $\gamma$ & $\uparrow$ for small $T$, $\downarrow$ for large $T$ \\
planning cost per move & $\uparrow$ & no influence & no influence \\
convergence memory & $\downarrow$ & $\uparrow$ & $\uparrow$ \\
first-move lag & $\uparrow$ & no influence & no influence \\
suboptimality of final solution & $\downarrow$ for small $\gamma$ & $\downarrow$ & no influence \\
\hline
\end{tabular}
\end{center}}\vspace{-0.6cm}
\end{table}

\subsection{Interaction among parameters}

In this section we consider effects of parameter {\em combinations}. 
%
Figure~\ref{fig:d-gammaT} shows the impact of the lookahead depth $d$ as a function of the heuristic weight $\gamma$ and the learning quota $T$. Specifically, for each value of $\gamma$ and $T$, the left plot shows the difference between the convergence execution costs for lookahead values of $d=1$ and $d=10$: \bea \text{impact-of-d}(\gamma,T) = \text{execution-cost}(d=1,\gamma,T) - \text{execution-cost}(d=10,\gamma,T). \eea 

\begin{figure}[ht]
\begin{center}
\includegraphics[height=4.75cm]{d-EC.pdf}%\hspace{0.1cm}
\includegraphics[height=4.8cm]{d-Mem.pdf}\vspace{-0.2cm}
\caption{Impact of lookahead $d$ for different values of heuristic weight $\gamma$ and learning quota $T$.}\label{fig:d-gammaT}
\end{center}\vspace{-0.2cm}
\end{figure}

Brighter shades indicate higher impact of increasing $d$ from 1 to 10. Likewise, the right plot demonstrates the impact of $d$ on the memory required for convergence. Brighter shades indicate stronger impact of $d$ (i.e., larger differences). Each point is averaged over the 1000 convergence runs in the pathfinding domain. We observe that larger values of learning quota and higher values of heuristic weight magnify the reduction of memory due to increasing lookahead depth. Note that the plot does not show the memory requirements for different values of $\gamma$ and $T$ but rather the {\em reduction} in the memory requirements when $d$ increases from 1 to 10. 

Figure~\ref{fig:gamma-dT} shows the impact of $\gamma$ as a function of $d$ and $T$ under the same conditions. Learning quota does not seem to affect the impact of $\gamma$ on suboptimality of the final solution. However, deeper lookahead does make $\gamma$ less effective in that respect. We believe it is because deeper lookahead compensates for more inaccuracies in the heuristic function. Therefore, weighting the heuristic with $\gamma$ makes less difference.

\begin{figure}[ht]
\begin{center}
\includegraphics[height=5.5cm]{gamma-EC.pdf}%\hspace{0.1cm}
\includegraphics[height=5.5cm]{gamma-subOpt.pdf}\vspace{-0.2cm}
\caption{Impact of heuristic weight $\gamma$ for different values of lookahead $d$ and learning quota $T$.}\label{fig:gamma-dT}
\end{center}\vspace{-0.6cm}
\end{figure}

Figure~\ref{fig:T-gammad} shows the impact of $T$ as a function of $d$ and $\gamma$ on the same 1000 pathfinding problems. Reducing the learning quota $T$ from 500 to 0 results in an increased amount of backtracking. As discussed previously, more backtracking tends to save memory and speed up convergence. The figure shows both trends and demonstrates that $d$ and $\gamma$ affect the impact of backtracking. The left plot shows that more backtracking is most effective in speeding up convergence for lower heuristic weights ($\gamma = 0.1$). On the contrary, the right plot indicates that higher heuristic weights (close to $\gamma = 1$) make backtracking most effective in reducing the memory required for convergence.

\begin{figure}[ht]
\begin{center}
\includegraphics[height=5.1cm]{T-EC.pdf}%\hspace{0.1cm}
\includegraphics[height=5.1cm]{T-Mem.pdf}\vspace{-0.2cm}
\caption{Impact of learning quota $T$ for different values of heuristic weight $\gamma$ and lookahead $d$.}\label{fig:T-gammad}
\end{center}\vspace{-0.4cm}
\end{figure}

Overall, the influences are non-trivial and, according to our experiments, domain-specific. While some can be explained readily, others appear to be a result of the interaction of the three parameters with the structure of the problem space. Consequently, selection of optimal parameters for a specific performance metric and a concrete domain is presently a matter of trial and error. While manual tuning of control parameters is a typical scenario in Artificial Intelligence, future research will investigate automatic parameter adjustment. 

\subsection{Minimizing performance measures}

In this section, we list parameter combinations optimizing each of the performance measures and explain the underlying rationale. 
%
The best combinations of parameters are sought in the following parameter space: lookahead $d \in \{1, 2, \dots, 10\}$, heuristic weight $\gamma \in \{0.1, 0.2, \dots, 1.0 \}$, and the learning quota $T \in \{0, 5, 10, 50, 100, 500, 1000, 5000, 10000, \infty \}$. For each of the one thousand combinations of the parameters, we ran LRTS until convergence on the test suite of 1000 pathfinding problems described in Section~\ref{sec:HOG}. The results are shown in Table~\ref{tab:metricMinimization} and explained below.

\begin{table}[ht]
\vspace{-0.2cm}
\caption{LRTS control parameters minimizing performance metrics.}\label{tab:metricMinimization}
\small\begin{center}
\vspace{0.3cm}
\begin{tabular}{c|c|c|c}
\hline
Metric & Lookahead $d$ & Heuristic weight $\gamma$ & Learning quota $T$ \\ \hline
execution convergence cost & 10 & 0.3 & $\infty$ \\
planning convergence cost & 1 & 0.3 & $\infty$ \\
planning cost per move & 1 & any & any \\
total convergence cost (speed $<$ 185.638) & 1 & 0.3 & $\infty$ \\ 
total convergence cost (speed $\ge$ 185.638) & 10 & 0.3 & $\infty$ \\ 
suboptimality & any & 1.0 & any \\
memory & 10 & 0.3 & 0 \\
\hline
\end{tabular}
\end{center}
\vspace{-0.2cm}
\end{table}

{\bf Execution convergence cost} is lowest when the quality of individual moves is the highest. Thus, deeper lookahead leading to more planning per move is favored. High values of $\gamma$ are undesirable as LRTS seeks near-optimal solutions and takes longer to converge. Very low values of $\gamma$ are also undesirable as the weighted initial heuristic becomes less and less informative (Table~\ref{tab:eLRTA}). Hence, the best value lays somewhere in the middle (0.3). Finally, no backtracking is preferred as then convergence is the fastest on the larger maps used in this experiment (Table~\ref{tab:T-largeMaps}).

{\bf Planning convergence cost} is defined as the total planning cost of all moves until convergence is achieved. Deeper lookahead leads to faster convergence but quadratically increases the planning cost of every move (cf., Section~\ref{sec:LRTS-simple}). Hence, overall, shallow lookahead is preferred. This also explains the optimal parameter combination for minimizing {\bf planning cost per move} which in LRTS depends on $d$ only.

{\bf Total convergence cost.} Here we minimize a weighted sum of the planning and execution costs. This is a common objective previously studied in~\cite{RussellWefald-book,Koenig:04a}. We adopt the settings of the latter and bring the two metrics (the execution cost and the planning cost) to a single scalar expressed in the number of states. Namely, our total convergence cost is defined as the convergence execution cost multiplied by the planning speed plus the total planning cost (Section~\ref{sec:defs}). For instance, if the agent converged in 1000 units of execution cost, considered a total of 5000 states while planning (i.e., an average of five states per unit of execution cost), and the planning speed is 200 (i.e., 200 states can be considered in planning while one unit of travel is executed), then the total convergence cost is $1000 \times 200 + 5000 = 205000$, clearly dominated by the execution component.
%
More planning per move tends to decrease the convergence execution cost and thus is preferred when the planning speed is high (i.e., planning is cheap relative to execution and the execution cost dominates the total cost). Conversely, less planning per move is preferred when the planning speed is low. Both~\citeA{RussellWefald-book} and~\citeA{Koenig:04a} used this reasoning to select the optimal lookahead depth in their LRTA*-based real-time search algorithms. In the pathfinding domain, the best values of $\gamma$ and $T$ for fastest convergence are 0.3 and $\infty$ as discussed above. The best value of lookahead depends on the planning speed: deeper lookahead (10 vs. 1) is preferred when the planning speed is sufficiently high and more planning per move can be afforded. 

{\bf Suboptimality} is zero with $\gamma = 1$ regardless of $d$ and $T$.

{\bf Memory.} The optimal parameter combination $(10,0.3,0)$ is consistent with the previous analysis: more backtracking ($T=0$) reduces memory consumption, lower heuristic weight $\gamma$ leads to less exploration (since LRTS is satisfied with suboptimal solutions), and since heuristic values are stored $d$ actions apart, higher lookahead is preferred. 

Adjusting LRTS control parameters allows the agent to achieve convergence where it has been previously impossible due to memory limitations. In the following, we adopt the settings of \citeA{ShimboIshida03} and \citeA{Bulitko:04a} and consider one hundred 15-puzzles first published by \citeA{IDAStar}. It is known that FALCONS and LRTA* with a lookahead of one are unable to converge to optimal solutions on {\em any} of the 100 puzzles with memory limited to 40 million states \cite{ShimboIshida03}. On the other hand, convergence to suboptimal solutions can be achieved with both \eLRTA \cite{ShimboIshida03} and $\gamma$-Trap \cite{Bulitko:04a}. 

\begin{table}[ht]
\vspace{-0.3cm}
\caption{Convergence on Korf's one hundred 15-puzzles in four million states of memory.}\label{tab:memKorf100}
\begin{center}
\vspace{0.3cm}
\begin{tabular}{c|c|c|c|c}
\hline
Algorithm & $d$ & $T$ & $\max \gamma$  & Suboptimality \\ \hline
FALCONS & - & - & - & no convergence on any problem \\
LRTA* & - & - & - & no convergence on any problem \\
LRTS & 1 & $\infty$ & 0.29 & 50\% \\
LRTS & 2 & 0 & 0.6 & 10\% \\
\bf LRTS & \bf 4 & \bf 0 & \bf 0.7 & \bf 4\% \\
\hline
\end{tabular}
\end{center}
\vspace{-0.7cm}
\end{table}

We make the task more challenging by reducing the memory limit ten fold from forty to four million states. While we were unable to find a set of $d, T, \gamma$ parameters that allowed LRTS to converge to optimal solutions on all 100 instances, the algorithm did converge to solutions that were, on average, only 4\% worse than optimal on {\em all} 100 puzzles (Table~\ref{tab:memKorf100}). Lower values of $T$ and higher values of $d$ increase the memory cost efficiency and allow to increase $\gamma$ which leads to higher quality solutions. 

In summary, adjusting the control parameters of LRTS significantly affects its performance. Our analysis of the individual and combined influence of the parameters on several practically relevant performance metrics gives a practitioner a better intuition for application-specific parameter tuning. Perhaps more importantly, it opens an interesting line of research on automatic selection of optimal parameters on the basis of effectively measurable properties of a domain and the target performance metric.

\subsection{Application Domain \#2: Routing in Sensor Networks}

A second application of LRTS considered is routing in {\em ad hoc} wireless sensor networks.  Sensor nodes generally have limited computational power and energy, thus simple, energy efficient routing routines are typically used within sensor networks.  Various applications exist, including military \cite{Shang03}, environmental monitoring \cite{braginsky} and reconnaissance missions \cite{yan}.  As such, routing in sensor networks is of interest to a large community of users.

The Distance Vector Routing (DVR) algorithm is widely used in network routing~\cite{review}.  In particular, DVR is employed within the Border Gateway Protocol used to route traffic over the entire Internet. In DVR, each network node maintains a heuristic estimate of its distance to the destination/goal node. We observe that DVR is conceptually very similar to LRTA* with a lookahead of one. Thus, applying LRTS in the network routing domain is essentially equivalent to extending DVR with the heuristic weight $\gamma$ and the backtracking mechanism controlled by the learning quota $T$. Note that there is no analogue of deeper lookahead in DVR since each network node does not learn an explicit model of the network and, consequently, is not aware of any network nodes beyond its immediate neighbors. Hence, $d$ is limited to one.

In order to demonstrate the impact of the two DVR extensions, we chose the setup used in a recent application of real-time heuristic search to network routing~\cite{Shang03}. Specifically, the network sensor nodes are assumed to be dropped from the sky to monitor territory, landing in a random dispersion, and thus necessitating {\em ad hoc} routing in order to allow for data transmissions.  We consider the case of a fixed destination for each transmission, simulating each source node providing information to a central information hub (e.g., a satellite up-link).  

Note that LRTA* in the pathfinding domain has access to the heuristic values of its neighbors at no extra cost since all heuristic values are stored in centralized memory. This is not the case in {\em ad hoc} networks, wherein each node maintains an estimate of the number of hops to the goal node (the $h$ heuristic). A naive application of LRTA* would query the neighbor nodes in order to retrieve their $h$ values.  This would, however, substantially increase the amount of network traffic, thereby depleting nodes' energy sources faster and making the network more easily detectable. We adopted the standard solution where each node not only stores its own heuristic value but also the last known heuristic values of its immediate neighbors. Then, whenever a node updates its own heuristic value, it notifies all of its neighbors of the change by broadcasting a short control message.  The last major difference from pathfinding is that the nodes do not know either their geographical position or the coordinates of the destination node. Thus, the Euclidian distance is not available and the initial heuristic is initialized to one for all nodes except the destination node where it is set to zero. 

In the experiments reported below, $N$ sensor nodes are randomly distributed on an $X \times Y$ two-dimensional grid so that no two nodes occupy the same location.  Each node has a fixed transmission radius which determines the number of neighbors a node can broadcast messages to (and whose heuristic values it has to store). 
%
To specify a single problem instance, distinct start (source) node and goal (destination or hub) nodes are randomly selected from the $N$ nodes. The start node needs to transmit a data message to the goal node. In doing so, it can send a message to one of its neighbors who will then re-transmit the message to another node, etc. Each transmission between two neighboring nodes incurs an execution cost of one hop. Once the message reaches the destination/goal node, a new trial begins with the same start and goal nodes. Convergence occurs when no heuristic values are updated during the trial. 

The objective is to find a shortest route from the start node to the goal node by learning better heuristic values over repeated trials.  We take measurements of four metrics paralleling those used in the domain of pathfinding: \begin{description}

\item[convergence execution cost] is the total number of hops traveled by messages during convergence;

\item[first trial execution cost] is the number of hops traveled on the first trial;

\item[suboptimality of the final solution] is the excess of the execution cost of the final trial over the shortest path possible. For instance, if the network converged to a route of 120 hops while the shortest route is 100 hops, the suboptimality is 20\%;

\item[convergence traffic] is defined as the total volume of information transmitted throughout the network during convergence. Each data message counts as one. Short control messages (used to notify node's neighbors of an update to the node's heuristic function) count as one third.

\end{description}


\nin Interference is not modeled in this simulation.  We assume scheduling is performed independently of the routing strategy, and that different schedules will not severely affect the performance of the routing algorithms.  Note that, since transmission delay and timings are not modeled, it would be difficult to model interference accurately.  

% Empirical Results

Four batches of networks of 50, 200, 400, and 800 nodes each were considered. The nodes were randomly positioned on a square grid of the dimensions $20 \times 20$, $30 \times 30$, $50 \times 50$, and $80 \times 80$ respectively. Each batch consisted of 100 randomly generated networks. For each network, 25 convergence runs were performed with the parameter values running $\gamma$ = $\{0.1,0.3,0.5,0.7,1\}$ and $T=\{0,10,100,1000, 100000 \}$. In the following, we present the results from the batch of 800-node networks. The same trends were observed in smaller networks as well. 

We start out by demonstrating the influence of the two control parameters in isolation. Table~\ref{tab:net-gamma} shows the influence of the heuristic weight $\gamma$ with no backtracking. As expected, smaller values of $\gamma$ speed up the convergence but increase the suboptimality of the final solution. These results parallel the ones reported in Table~\ref{tab:eLRTA} for the pathfinding domain.

\begin{table}[ht]\vspace{-0.2cm}
\caption{Effects of heuristic weighting in network routing.}\label{tab:net-gamma}
{\begin{center}\vspace{0.2cm}
\begin{tabular}{l|c|c}
\hline
Heuristic weight $\gamma$ & Execution convergence cost & Suboptimality\\ 
 \hline
1.0 (DVR) & 8188 & 0\% \\
0.7 & 8188 &  0\% \\
0.5 & 8106 &  0\% \\
0.3 & 7972 &  0.29\% \\
0.1 & 7957 & 0.33\% \\
\hline
\end{tabular}
\end{center}}\vspace{-0.6cm}
\end{table}

\nin Table~\ref{tab:net-T} demonstrates the influence of the learning quota $T$  when the heuristic weight $\gamma$ is set to one. Smaller values of $T$ increase the amount of backtracking and speed up convergence cost but lengthen the first trial. This parallels the results in the 8-puzzle (Table~\ref{tab:T-8p}) as well as in pathfinding with small maps (Table~\ref{tab:T-smallMaps}).  

\begin{table}[ht]\vspace{-0.5cm}
\caption{Effects of backtracking in network routing.}\label{tab:net-T}
{\begin{center}\vspace{0.2cm}
\begin{tabular}{l|c|c}
\hline
Learning quota $T$ & First trial execution cost & Convergence execution cost  \\ \hline
$10^5$ (DVR) & 549 & 8188 \\
$10^3$  & 1188 & 8032 \\
$10^2$ & 4958 & 6455 \\
$10$  & 5956 & 6230 \\
$0$  & 6117 & 6138 \\
\hline
\end{tabular}
\end{center}}\vspace{-0.6cm}
\end{table}

\nin We will now consider the impact of parameter combination. The fixed  lookahead depth of one makes the two-dimensional parameter space easier to visualize on contour plots. Thus, instead of plotting the {\em impact} of a parameter on a metric as a function of the other two control parameters, we will now plot the {\em metric} itself. Figure~\ref{fig:net-ec} shows the first trial and convergence execution costs for all combinations of $\gamma$ and $T$. Brighter areas indicates higher costs. 

\begin{figure}[ht]
\begin{center}
\includegraphics[height=5.1cm]{ftrial800.pdf}%\hspace{0.1cm}
\includegraphics[height=5.1cm]{convec800.pdf}\vspace{-0.2cm}
\caption{First-trial and convergence execution costs in network routing.}\label{fig:net-ec}
\end{center}\vspace{-0.4cm}
\end{figure}

\nin Figure~\ref{fig:net-sub-traff} shows the suboptimality of the final solution and the total traffic on a convergence run, averaged over 100 networks of 800 nodes each. Again, brighter areas indicate higher values.

\begin{figure}[ht]
\begin{center}
\includegraphics[height=5.1cm]{subopt800.pdf}%\hspace{0.1cm}
\includegraphics[height=5.1cm]{traffic800.pdf}\vspace{-0.2cm}
\caption{Suboptimality of the final solution and the total traffic in network routing.}\label{fig:net-sub-traff}
\end{center}\vspace{-0.4cm}
\end{figure}

\nin In summary, by extending the DVR algorithm with the heuristic weight and the backtracking mechanisms of LRTS, reduction of the convergence execution cost and the total network traffic can be achieved. As a result, near-optimal routes are found faster, at a lower energy consumption. This promising result raises several questions for further research. First, how will additional routing constraints, such as the ones investigated in~\cite{Shang03}, affect the performance of LRTS? Second, how will the benefits of LRTS scale to the case of several messages with the same destination passing through the network {\em simultaneously}? The latter question also applies to path-planning with multiple memory-sharing units which is a common situation in squad-based games.



\section{Summary and Future Research}

In this paper, we considered simultaneous planning and learning problems such as real-time pathfinding in initially unknown environments as well as routing in {\em ad hoc} wireless sensor networks.  
Learning real-time search methods plan by conducting a limited local search and learn by maintaining and refining a state-based heuristic function. Thus, they can react quickly to user's commands and yet converge to better solutions over repeated experiences.

We analyzed three complementary extensions of the base LRTA* algorithm and showed their effects with hand-traceable examples, theoretical bounds, and extensive empirical evaluation in two different domains. We then proposed a simple algorithm, called LRTS, unifying the extensions and studied the problem of choosing optimal parameter combinations.

Current and future work includes extending LRTS with automated state space abstraction mechanisms, function approximation methods for the heuristic, and automated parameter selection techniques. It will also be of interest to investigate the convergence process of a team of LRTS-based agents with shared memory and extend LRTS for moving targets and stochastic/dynamic environments in video games, robotics, and networking.

\section*{Acknowledgements} 
Input from Valeriy Bulitko, Sven Koenig, Rich Korf, David Furcy, Nathan Sturtevant, Masashi Shimbo, Rob Holte, Douglas Aberdeen, Reza Zamani, Stuart Russell, and Maryia Kazakevich is greatly appreciated. Nathan Sturtevant kindly provided and supported Hierarchical Open Graph simulator. Additionally, Valeriy Bulitko, David Furcy, Sven Koenig, Rich Korf, Scott Thiessen, and Ilya Levner have taken time to proof read an early draft of this paper. Great thanks to JAIR reviewers for working with us on improving the manuscript. 
We are grateful for the support from NSERC, the University of Alberta, the Alberta Ingenuity Centre for Machine Learning, and Jonathan Schaeffer.

\appendix

\clearpage\section{Detailed Pseudocode}\label{sec:pseudocode}

In this section we list pseudocode of the algorithms at the level of detail necessary to implement them as well as to follow the proofs listed in the Appendix~\ref{sec:proofs}.

\begin{figure}[ht]
\vspace{0.4cm}
\small
\hrule\smallskip
\textbf{LRTA*}

\vspace{1mm}

\textsc{Output}: a series of actions leading from $s_0$ to a goal state
\vspace{2mm}

\begin{tabular} {p{0.5cm}l}
1 & {\bf if} $h$ is undefined {\bf then} set $h$ to $h_0$ \\
2 & reset the current state:  $s \leftarrow s_0$ \\
3 & {\bf while} $s \not\in S_g$ {\bf do} \\
4 & \hspace{5mm} generate depth $1$ neighborhood $S(s,1) = \{s' \in S \mid \|s,s'\| = 1\}$ \\
5 &  \hspace{5mm} compute $h'(s) = \min\limits_{s' \in S(s,1)} \left( \dist(s,s') + h(s')\right)$ \\
6 &  \hspace{5mm} {\bf if} $h'(s) > h(s)$ {\bf then} update $h(s) \leftarrow h'(s)$ \\
7 &  \hspace{5mm} update current state $s \leftarrow \arg \min\limits_{s' \in S(s,1)} \left( \dist(s,s') + h(s')\right)$\\
\end{tabular}

\smallskip\hrule
\caption{LRTA* algorithm.}\label{fig:LRTA}
\vspace{-0.7cm}
\end{figure} 


\begin{figure}[ht]
\vspace{0.4cm}
\small
\hrule\smallskip
\textbf{SLA*}

\vspace{1mm}

\textsc{Output}: a series of actions leading from $s_0$ to a goal state
\vspace{2mm}

\begin{tabular} {p{0.5cm}l}
1 & {\bf if} $h$ is undefined {\bf then} set $h$ to $h_0$ \\
2 & reset the current state:  $s \leftarrow s_0$ \\
3 & reset the path traveled so far:  $path \leftarrow \emptyset$ \\
4 & {\bf while} $s \not\in S_g$ {\bf do} \\
5 & \hspace{5mm} generate depth $1$ neighborhood $S(s,1) = \{s' \in S \mid \|s,s'\| = 1\}$ \\
6 & \hspace{5mm} compute $h'(s) = \min\limits_{s' \in S(s,1)} \left( \dist(s,s') + h(s')\right)$ \\
7 & \hspace{5mm} {\bf if} $h'(s) > h(s)$ {\bf then} \\
8 & \hspace{10mm} update $h(s) \leftarrow h'(s)$ \\
9 & \hspace{10mm} update current state $s \leftarrow pop(path)$ [or remain in state $s$ if $path=\emptyset$]\\
10 & \hspace{5mm} {\bf else} \\
11 & \hspace{10mm} push $s$ onto the stack $path$\\
12 & \hspace{10mm} update current state $s \leftarrow \arg \min\limits_{s' \in S(s,1)} \left( \dist(s,s') + h(s')\right)$\\
\end{tabular}
\smallskip\hrule
\caption{SLA* algorithm.}\label{fig:SLA}
\vspace{-0.7cm}
\end{figure} 

\begin{figure}[ht]
\vspace{0.4cm}
\small
\hrule\smallskip
\textbf{$\gamma$-Trap}$(d,\gamma)$

\vspace{1mm}

\textsc{Input}:

\vspace{1mm}

\begin{tabular} {l l}
\hspace{5mm} $d$: & lookahead depth \\
\hspace{5mm} $\gamma$: & optimality weight \\
\end{tabular}

\vspace{2mm}

\textsc{Output}: $path$: a series of actions leading from $s_0$ to a goal state
\vspace{2mm}

\begin{tabular} {p{0.5cm}l}
1 & {\bf if} $h$ is undefined {\bf then} set $h$ to $h_0$ \\
2 & reset the current state:  $s \leftarrow s_0$ \\
3 & reset the stack:  $path \leftarrow \emptyset$ \\
4 & reset the cumulative learning amount $u \leftarrow 0$ \\
5 & {\bf while} $s \not\in S_g$ {\bf do} \\
6 & \hspace{5mm} set $d \leftarrow \min \{ d, \min \{k \mid S(s,k) = \emptyset \}\}$ \\
7 & \hspace{5mm} reset set $G \leftarrow \emptyset$ \\
8 & \hspace{5mm} {\bf for} $k$=1 to $d$ {\bf do} \\
9 & \hspace{10mm}  generate depth $k$ neighborhood $S(s,k) = \{s' \in S \mid \|s,s'\| = k\}$ \\
10 & \hspace{10mm}  {\bf if} $S(s,k) \cap S_g \neq \emptyset$ {\bf then} update $G \leftarrow G \cup \{k\}$ \\
11 & \hspace{10mm} compute $f_{\min}(s,k) = \min\limits_{s' \in S(s,k)} \left( \gamma \cdot \dist(s,s') + h(s')\right)$ \\
12 & \hspace{10mm} compute $s_{\min}(s,k) = \arg\min\limits_{s' \in S(s,k)} \left( \gamma \cdot \dist(s,s') + h(s')\right)$ \\
13 & \hspace{5mm} {\bf end for} \\
14 & \hspace{5mm} compute $h'(s) \leftarrow \begin{cases} 
\max\limits_{1 \le k \le d} f_{\min}(s,k) & \text{ if $G = \emptyset$,} \\
\max\limits_{1 \le k \le \min\{G\}} f_{\min}(s,k) & \text{ otherwise.} \\
\end{cases}$ \\
15 & \hspace{5mm} {\bf if} $h'(s) \le h(s)$ {\bf then} \\
16 & \hspace{10mm} push $s$ onto stack $path$ \\
17 & \hspace{10mm} update the current state $s \leftarrow \begin{cases}
s_{\min}(s,d) & \text{if $G = \emptyset$,} \\ 
\arg \min\limits_{k \in G} f_{\min}(s,k) & \text{otherwise.}\\ 
\end{cases}$ \\
18 & \hspace{5mm} {\bf else} \\
19 & \hspace{10mm} update $h(s) \leftarrow h'(s)$ \\
20 & \hspace{10mm} backtrack: $s \leftarrow pop(path)$ \ [or remain in state $s$ if $path=\emptyset$].\\
21 & \hspace{5mm} {\bf end if} \\
22 & {\bf end while} \\
\end{tabular}
\smallskip\hrule
\caption{$\gamma$-Trap algorithm.}\label{fig:gTrap}
\vspace{-0.5cm}
\end{figure} 

\begin{figure}[ht]
\vspace{0.4cm}
\small
\hrule\smallskip
\textbf{LRTS}$(d,\gamma,T)$

\vspace{1mm}

\textsc{Input}:

\vspace{1mm}

\begin{tabular} {l l}
\hspace{5mm} $d'$: & lookahead depth \\
\hspace{5mm} $\gamma$: & optimality weight \\
\hspace{5mm} $T$: & learning threshold \\
\end{tabular}

\vspace{2mm}

\textsc{Output}: $path$: a series of actions leading from $s_0$ to a goal state
\vspace{2mm}

\begin{tabular} {p{0.5cm}l}
1 & {\bf if} $h$ is undefined {\bf then} set $h$ to $h_0$ \\
2 & reset the current state:  $s \leftarrow s_0$ \\
3 & reset the stack:  $path \leftarrow \emptyset$ \\
4 & reset the cumulative learning amount $u \leftarrow 0$ \\
5 & {\bf while} $s \not\in S_g$ {\bf do} \\
6 & \hspace{5mm} set $d \leftarrow \min \{ d', \min \{k \mid S(s,k) = \emptyset \}\}$ \\
7 & \hspace{5mm} reset set $G \leftarrow \emptyset$ \\
8 & \hspace{5mm} {\bf for} $k$=1 to $d$ {\bf do} \\
9 & \hspace{10mm}  generate depth $k$ neighborhood $S(s,k) = \{s' \in S \mid \|s,s'\| = k\}$ \\
10 & \hspace{10mm}  {\bf if} $S(s,k) \cap S_g \neq \emptyset$ {\bf then} update $G \leftarrow G \cup \{k\}$ \\
11 & \hspace{10mm} compute $f_{\min}(s,k) = \min\limits_{s' \in S(s,k)} \left( \gamma \cdot \dist(s,s') + h(s')\right)$ \\
12 & \hspace{10mm} compute $s_{\min}(s,k) = \arg\min\limits_{s' \in S(s,k)} \left( \gamma \cdot \dist(s,s') + h(s')\right)$ \\
13 & \hspace{5mm} {\bf end for} \\
14 & \hspace{5mm} compute $h'(s) \leftarrow \begin{cases} 
\max\limits_{1 \le k \le d} f_{\min}(s,k) & \text{ if $G = \emptyset$,} \\
\max\limits_{1 \le k \le \min\{G\}} f_{\min}(s,k) & \text{ otherwise.} \\
\end{cases}$ \\
15 & \hspace{5mm} {\bf if} $h'(s) > h(s)$ {\bf then} \\
16 & \hspace{10mm} compute amount of learning on this move: $\ell \leftarrow h'(s)-h(s)$ \\
17 & \hspace{10mm} update $h(s) \leftarrow h'(s)$ \\
18 & \hspace{5mm} {\bf else} \\
19 & \hspace{10mm} reset $\ell=0$ \\
20 & \hspace{5mm} {\bf end if} \\
21 & \hspace{5mm} {\bf if} $u+\ell \le T$ {\bf then} \\
22 & \hspace{10mm} push $s$ onto stack $path$ \\
23 & \hspace{10mm} update the current state: $s \leftarrow \begin{cases}
s_{\min}(s,d) & \text{if $G = \emptyset$,} \\ 
\arg \min\limits_{k \in G} f_{\min}(s,k) & \text{otherwise.}\\ 
\end{cases}$ \\
%23a & \hspace{10mm} {\bf if} $\exists s' \left[s  = s' \And s' \in path \right]$ {\bf then} \\
%23b & \hspace{15mm} remove $s'$ and all following states from $path$ \\
%23c & \hspace{10mm} {\bf end if} \\
24 & \hspace{10mm} accumulate learning amount $u \leftarrow u + \ell$\\
25 & \hspace{5mm} {\bf else} \\
26 & \hspace{10mm} backtrack: $s \leftarrow pop(path)$ \ [or remain in state $s$ if $path=\emptyset$].\\
27 & \hspace{5mm} {\bf end if} \\
28 & {\bf end while} \\
\end{tabular}
\smallskip\hrule
\caption{LRTS algorithm.}\label{fig:LRTS}
\vspace{-0.5cm}
\end{figure} 

\begin{figure}[ht]
\vspace{0.4cm}
\small
\hrule\smallskip
\begin{tabular} {p{0.5cm}l}
23a & \hspace{10mm} {\bf if} $\exists s' \left[s  = s' \And s' \in path \right]$ {\bf then} \\
23b & \hspace{15mm} remove $s'$ and all following states from $path$ \\
23c & \hspace{10mm} {\bf end if} \\
\end{tabular}
\smallskip\hrule
\caption{Additional lines facilitating incremental pruning in LRTS. These are to be inserted between lines 23 and 24 in Figure~\ref{fig:LRTS}.}\label{fig:LRTS-pruning}
\vspace{-0.7cm}
\end{figure} 



\clearpage\section{Theorem Proofs}\label{sec:proofs}

\nin\nin {\bf Theorem~\ref{th:eqLRTA}} LRTS$(d=1, \gamma=1, T=\infty)$ is equivalent to LRTA* with a lookahead of one. 

\medskip\nin\proof We will show that in any state $s$ LRTS$(d=1, \gamma=1, T=\infty)$ (i) takes the same action as LRTA* does and (ii) updates the $h$ function in the same way LRTA* does. 

(i) In state $s$, LRTS$(d=1, \gamma=1, T=\infty)$ goes to state $s_{\min}(s,1)$ (line 23, Figure~\ref{fig:LRTS}) which is equivalent to the state $\arg \min\limits_{s_1 \in S(s,1)} \left( \dist(s,s_1) + h(s_1)\right)$ to which LRTA* will move (line 7, Figure~\ref{fig:LRTA}).\footnote{Throughout the paper we assume that tie-breaking is done in a consistent way among all algorithms.}

(ii) LRTS$(d=1, \gamma=1, T=\infty)$ updates $h(s)$ to $h'(s)$  in line 17 in Figure~\ref{fig:LRTS} when $h'(s)>h(s)$ (line 15) which is equivalent to LRTA*'s update under the same condition in line 6, Figure~\ref{fig:LRTA}. \qed

\bigskip

\nin {\bf Theorem~\ref{th:eqeLRTA}} LRTS$(d=1, \gamma=\frac{1}{1+\epsilon}, T=\infty)$ initialized with an admissible heuristic $h_0$ is equivalent to \eLRTA initialized with $(1+\epsilon)h_0$. 

\medskip\nin\proof These two algorithms begin with and maintain different heuristic functions. Let $h^\text{LRTS}_t$ be the heuristic function LRTS$(d=1, \gamma=\frac{1}{1+\epsilon}, T=\infty)$ maintains at iteration $t$.\footnote{One can measure iterations by counting the number of times the {\bf while} condition is executed (line 5 in Figure~\ref{fig:LRTS} and line 3 in Figure~\ref{fig:LRTA}).} Likewise, let $h^\text{\eLRTA}_t$ denote the heuristic function \eLRTA maintains at iteration $t$. We will also denote by $s_t^\text{LRTS}$ the current state of LRTS$(d=1, \gamma=\frac{1}{1+\epsilon}, T=\infty)$ at iteration $t$. Likewise, $s_t^\text{\eLRTA}$ is the current state of \eLRTA at iteration $t$.
%
We show by induction over iteration number $t$ that for $\forall t$: \bea h^\text{\eLRTA}_t = (1+\epsilon)h^\text{LRTS}_t. \label{eq:h}\eea \nin Base step: since \eLRTA initialized with $(1+\epsilon)h_0$ and LRTS$(d=1, \gamma=\frac{1}{1+\epsilon}, T=\infty)$ is initialized with $h_0$, equation~\ref{eq:h} trivially holds at $t=0$.

\nin Inductive step: suppose equation~\ref{eq:h} holds at iteration $t$. We will show that it holds at iteration $t+1$. 

First, we show that both algorithms are bound to be at the same state $s_t$. Suppose not: $s_t^\text{LRTS} \neq s_t^\text{\eLRTA}$. Then since both start in state $s_0$ there must have been the earliest $t_0<t$ such that $s_{t_0}^\text{LRTS} = s_{t_0}^\text{\eLRTA}$ but $s_{t_0+1}^\text{LRTS} \neq s_{t_0+1}^\text{\eLRTA}$. This means that in state $s_{t_0}$ different actions were taken by LRTS and \eLRTA. LRTS takes action in line 23 of Figure~\ref{fig:LRTS} and would move to state: \bea \arg\min_{s' \in S(s_{t_0},1)} \left( \frac{1}{1+\epsilon} \cdot \dist(s_{t_0},s') + h_{t_0}^\text{LRTS}(s')\right). \label{eq:LRTS-move}\eea \eLRTA moves to the following state (line 7 in Figure~\ref{fig:LRTA}): \bea \arg\min_{s' \in S(s_{t_0},1)} \left( \dist(s_{t_0},s') + h_{t_0}^\text{\eLRTA}(s')\right). \label{eq:eLRTA-move}\eea Since $ h^\text{\eLRTA}_{t_0} = (1+\epsilon)h^\text{LRTS}_{t_0}$ (as $t_0<t$ and equation~\ref{eq:h} holds at time $t$ by the inductive hypothesis), the action in~\ref{eq:LRTS-move} is the same as in~\ref{eq:eLRTA-move}. 

The update to $h$ in LRTS$(d=1, \gamma=\frac{1}{1+\epsilon}, T=\infty)$ occurs in line 17, Figure~\ref{fig:LRTS}.  Substituting the expression for $h'(s)$ we arrive at: \bea h^\text{LRTS}_{t+1}(s_t) &=&  \min_{s' \in S(s_t,1)} \left( \frac{1}{1+\epsilon}  \dist(s_t,s') + h_t^\text{LRTS}(s')\right) \\ &=& \frac{1}{1+\epsilon}  \min_{s' \in S(s_t,1)} \left( \dist(s_t,s') + (1+\epsilon) h_t^\text{LRTS}(s')\right) \\ &=& \frac{1}{1+\epsilon}  \min_{s' \in S(s_t,1)} \left( \dist(s_t,s') +  h_t^\text{\eLRTA}(s')\right) \\ &=& \frac{1}{1+\epsilon}  h_{t+1}^\text{\eLRTA}(s_t)\eea \nin which concludes the inductive proof.
\qed

\bigskip

\nin {\bf Theorem~\ref{th:eqSLA}} LRTS$(d=1, \gamma=1, T=0)$ is equivalent to SLA*. 

\medskip\nin\proof When $T=0$, condition $u+\ell \le T$ in line 21 of Figure~\ref{fig:LRTS} will hold if and only if $h(s)$ is not updated (i.e., $h'(s) \le h(s)$ in line 15). If that is the case the forward move executed in line 23 is equivalent to SLA*'s forward move in lines 11, 12 of Figure~\ref{fig:SLA}. If $h(s)$ is indeed updated then both LRTS and SLA* will backtrack by executing line 26 in Figure~\ref{fig:LRTS} and line 9 in Figure~\ref{fig:SLA} respectively. The proof is concluded with the observation that $h'(s)$ computed by LRTS$(d=1,\gamma=1,T=0)$ is equivalent to $h'(s)$ computed by SLA* in line 6 of Figure~\ref{fig:SLA}.
\qed

\bigskip

\nin {\bf Theorem~\ref{th:eqgTrap}} LRTS$(d, \gamma, T=0)$ is equivalent to $\gamma$-Trap$(d,\gamma)$. 

\medskip\nin\proof Substituting $T=0$ in line 21 of Figure~\ref{fig:LRTS}, we effectively obtain $\gamma$-Trap (Figure~\ref{fig:gTrap}).
\qed

\bigskip

\nin {\bf Lemma~\ref{th:adm}} {\bf (Admissibility)} For any valid $T, \gamma, d$ and an admissible initial heuristic $h_0$, the heuristic function $h$ is maintained admissible at all times during LRTS$(d,\gamma,T)$ search.

\medskip\nin\proof We will prove this lemma by induction over the iteration number $t$. At $t=0$ the statement trivially holds since the initial heuristic $h_0$ is admissible. Suppose $h_t$ is admissible then we will show that $h_{t+1}$ is admissible. Heuristic $h_{t+1}$ can be different from $h_t$ only in state $s_t$ as it is updated in lines 14 and 17 of Figure~\ref{fig:LRTS}. Combining the expressions together, we obtain: \bea h_{t+1}(s_t) = \max_{1 \le k \le d} \min_{s' \in S(s_t,k)} (\gamma \dist(s_t,s')+h_t(s')), \eea \nin 
if no goal states have been discovered during the lookahead ($G=\emptyset$) and: \bea h_{t+1}(s_t) = \min_{k \in G} \min_{s' \in S(s_t,k)} (\gamma \dist(s_t,s')+h_t(s')), \eea \nin otherwise. 
%
Suppose the $\max \min$ or $\min \min$ is reached in state $s^\circ$: \bea h_{t+1}(s_t) = \gamma \dist(s_t,s^\circ)+h_t(s^\circ), s^\circ \in S(s_t,m), 1 \le m \le d. \eea \nin The shortest path from state $s_t$ and the closest goal state intersects neighborhood $S(s_t,m)$ of depth $m$. Let us denote state from $S(s_t,m)$ belonging to the shortest path by $s^*$ (Figure~\ref{fig:adm}). 

\begin{figure}[t]
\begin{center}
\includegraphics[width=8cm]{adm.pdf}
\caption{To the proof of admissibility.}\label{fig:adm}
\end{center}\vspace{-0.7cm}
\end{figure}

Since $h_t$ is admissible in all states, $\gamma \le 1$, and $s^\circ$ was chosen as $\arg \min\limits_{s \in S(s_t,m)} \left( \gamma \dist(s_t,s) + h_t(s)\right)$ we conclude that: \bea
h_{t+1}(s_t) & = & \gamma \dist(s_t,s^\circ) + h_t(s^\circ) \\
& \le & \gamma \dist(s_t,s^*) + h_t(s^*) \\
& \le & \dist(s_t,s^*) + h^*(s^*) \\
& = & h^*(s_t). 
\eea

\nin Thus, $h_{t+1}$ is an admissible heuristic which concludes the induction.
\qed

\bigskip

\nin {\bf Theorem~\ref{th:completeness}} {\bf (Completeness)} For any valid $T, \gamma, d$ and an admissible initial heuristic $h_0$, LRTS$(d,\gamma,T)$ arrives at a goal state on every trial. 

\medskip\nin\proof Since heuristic $h$ is maintained admissible at all times and each update increases its value by a positive amount lower-bounded by a constant, only a finite number of updates can be made on any trial. Let the last update be made in state $s_{u-1}, u \ge 0$ in the sequence of states $s_0, s_1, \dots$ traversed on the trial. We will show that the sequence of states $s_u, s_{u+1}, \dots$ is guaranteed to terminate in a goal state. In other words, LRTS cannot loop in the finite state space forever avoiding the goal states. As there are no updates made in $s_u, s_{u+1}, \dots$, it must hold that\footnote{Similar reasoning applies to the case of $G \neq \emptyset$ when $\min \min$ is used instead of $\max \min$.} for $\forall j \ge u$:
\bea h(s_j) &\ge& \max_{1 \le k \le d} \min_{s' \in S(s_j,k)} (\gamma \dist(s_j,s')+h(s')), \\ h(s_j) &\ge& \gamma \dist(s_j,s_{j+1}) + h(s_{j+1}), \\  h(s_j) - h(s_{j+1}) &\ge& \gamma \dist(s_j,s_{j+1}). \eea \nin 
%
Since $\gamma > 0$ and for any states $a \neq b \left[ \dist(a,b) > 0 \right]$, it follows that $h(s_u) > h(s_{u+1}) > h(s_{u+2}) > \dots$. As the state space is finite, this series of states must terminate in a goal state with $h(s_n) = 0$. Thus, for any valid parameter values, LRTS ends in a goal state on every trial.
\qed

\bigskip

\nin {\bf Theorem~\ref{th:convergence}}  {\bf (Convergence)} For any valid $T, \gamma, d$ and an admissible initial heuristic $h_0$, LRTS$(d,\gamma,T)$ with systematic or fixed tie-breaking converges to its final solution after a finite number of trials. It makes zero updates to its heuristic function on the final trial. Each subsequent trial will be identical to the final trial.

\medskip\nin\proof From the proof of Theorem~\ref{th:completeness} it is clear that there will be a trial with zero updates to the heuristic function $h$. We will call this trial the final trial and will demonstrate that each subsequent trial will be identical to the final trial. Suppose not. Then in the final trial $s_0, s_1, \dots, s_n$ there is the earliest state $s_j$ such that the next trial is different from the final trial in state $s_{j+1}$. This implies that on the subsequent trial LRTS took a different action in state $s_j$ from the action it took in the same state on the final trial.  As there are no updates to the heuristic function, the action must have been selected in line 23 of Figure~\ref{fig:LRTS}. Expanding the expression, we get:\footnote{The case of $G \neq \emptyset$ is handled similarly.} \bea s_{j+1} = s_{\min}(s_j,d) = \arg \min_{s' \in S(s_j,d)} (\gamma \dist(s_j,s') + h(s')). \eea \nin Since the ties are broken in a systematic or fixed fashion, the choice of state $s_{j+1}$ is unique which contradicts with our assumption on existence of a subsequent trial different from the final trial.
\qed

\bigskip


\nin {\bf Theorem~\ref{th:gamma}} For any valid $T, \gamma, d$ and an admissible initial heuristic $h_0$, the converged solution cost\footnote{Henceforth ``converged solution cost" is defined as the execution cost of the final trial.} of LRTS$(d,\gamma,T)$ is upper-bounded by $\frac{h^*(s_0)}{\gamma}$. 

\medskip\nin\proof First, let us denote the converged solution cost (i.e., the execution cost of the final trial) by $\solutionc$. From theorem~\ref{th:convergence} it follows that there will be a final trial with no updates to the heuristic function. Suppose $s_0, \dots, s_n$ are the states traversed during the final trial. Since no updates are made to the heuristic function, the condition $h'(s_i) \le h(s_i)$ in line 15 of Figure~\ref{fig:LRTS} must have held for all $s_i, i=0, \dots, n$. Substituting the expression for $h'(s_i)$ from line 14, we arrive at:\footnote{Once again, the case of $G \neq \emptyset$ is handled similarly.} \bea \max_{1 \le k \le d} \min_{s' \in S(s_i,k)} \left(\gamma \dist(s_i,s')+h(s')\right) \le h(s_i). \eea \nin Since: \bea s_{i+1} = \min_{s' \in S(s_i,d)} \left(\gamma \dist(s_i,s')+h(s')\right)\eea \nin we conclude that: \bea \gamma \dist(s_i,s_{i+1})+h(s_{i+1}) &\le& h(s_i) \\  \gamma \dist(s_i,s_{i+1}) &\le& h(s_i)-h(s_{i+1}).\label{eq:forwardMove} \eea \nin Summing up these telescoping inequalities for $i=0, \dots, n-1$, we derive: \bea \sum_{i=0}^{n-1} \dist(s_i,s_{i+1}) \le \frac{h(s_0)-h(s_n)}{\gamma}. \eea Since $s_n \in S_g$, $h(s_n)=0$. The sum of distances travelled is the travel cost of the final trial and is the converged solution cost by definition.\footnote{It is easy to check that there the sequence of states on the final trial has no repetitions. Therefore, $\solutionc = \sum_{i=0}^{n-1} \dist(s_i,s_{i+1})$.} Thus, we conclude that the converged solution cost is upper bounded by $\frac{h(s_0)}{\gamma} \le \frac{h^*(s_0)}{\gamma}$. \qed

\bigskip

\nin {\bf Theorem~\ref{th:SLA}} For any valid $\gamma, d$ and an admissible initial heuristic $h_0$, the second trial of LRTS$(T=0)$ with systematic or fixed tie-breaking is guaranteed to be final. Thus, all learning and exploration are done on the first trial.

\medskip\nin\proof Consider a sequence of states $[s_0,s_1,\dots,s_n]$ traversed during the first trial. Here $s_0$ is the start state and $s_n$ is the goal state found. Each transition $s_t \to s_{t+1}, t=0,\dots,n-1$ was carried out via a forward move (line 23 in Figure~\ref{fig:LRTS}) or backtracking move (line 26). During move $t=0, \dots, n-1$, the heuristic function may have been changed (line 17) in state $s_t$. We will use $h_t$ to denote the heuristic function before the update in line 17. The update results in $h_{t+1}$. Note that the update changes $h$ in state $s_t$ only so that  $h_t(s) = h_{t+1}(s)$ for all $s \neq s_t$. In particular, since $s_{t+1} \neq s_t$\footnote{Except for possibly the case of backtracking in $s_t=s_0$ which does not affect the proof.}  we have $h_{t+1}(s_{t+1}) = h_t(s_{t+1})$.

Since $T=0$, all $n$ moves can be divided in two groups: forward moves that do not change the $h$ function and backtracking moves which do. We will now prune the sequence of states  $[s_0,s_1,\dots,s_n]$ using a backtracking stack. Namely, at the beginning the stack contains $s_0$. Every forward move $0 \le t \le n-1$ will add $s_{t+1}$ to the stack. Every backtracking move $0 \le t \le n-1$ will remove $s_{t+1}$ from the stack. Carrying this procedure for $t=0,\dots,n-1$, we derive the sequence of states: $p'=[s_0,\dots,s_m]$ leading from the initial state $s_0$ to the goal state $s_m$. Clearly, $m \le n$.

Observe that since all backtracking moves were removed from the original move sequence, the only moves left are forward moves with no updates to $h$. Thus, let us define $\widehat{h}$-value of any state $s$ visited on the trial as: \bea \widehat{h}(s) = \begin{cases} h(s) & \text{\small after the most recent backtracking move from state $s$;} \\ \text{initial $h(s)$} & \text{\small if no backtracking move was taken in $s$ during the trial.}\end{cases} \nonumber \eea Since now $T=0$, for any state $s_i, i=0, \dots, m$ there have been no updates in $h$ {\em after} the last backtracking move from that state (if any). In other words, if $h$ is the final heuristic then $\forall i=0,\dots,m \left[ h(s_i) = \widehat{h}(s_i)\right]$. It also means that in every $k$-neighborhood ($1 \le k \le d$) of each state $s_i \in p'$ there was a state $s'$ with $\widehat{h}(s') + \gamma \dist(s_i,s') \le \widehat{h}(s_i)$. 

We now have to show that no updates to $h$ will be done on the second trial. Suppose this is not the case. Then there must exist the earliest state $s_j \in p', 0 \le j < m$ such that LRTS on the second trial updated $h(s_j)$ to be greater than $\widehat{h}(s_j)$. As we reasoned above, the final value of $h(s_j)$ on the first trial was $\widehat{h}(s_j)$ and there was no need to increase it. By the assumption, LRTS did  increase $h(s_j)$ on the second trial. Consequently, at least one state in one of $s_j$'s neighborhoods was updated during {\em first trial} (as no updates on the second trial had happened yet). 

\begin{figure}[t]
\begin{center}
\includegraphics[width=9cm]{toProofSLA.pdf}
\caption{To the proof of Theorem~\ref{th:SLA}.}\label{fig:toProofSLA}
\end{center}\vspace{-0.7cm}
\end{figure}

Formally, $h(s')$, where $s' \in S(s_j,k)$ for some $1 \le k \le d$, was increased during the first trial but {\em after} state $s_j$ was visited in $p'$. Additionally, this means that as a result of this update it must hold that: \bea h_\text{new}(s') + k > h(s_j).\label{eq:newUpdate}\eea 
%
Thus, on the first trial, state $s'$ must have been arrived at via a sequence of forward moves starting in state $s_j$ (shown as the dashed curve in Figure~\ref{fig:toProofSLA}). During the forward moves with no $h$-updates, $h(s_\text{current}) > h(s_\text{next})$ holds. This means that there was a sequence of states traversed by forward moves that started with $s_j$ and ended with $s'$. Since $h_\text{new}(s') + k > h(s_j)$, LRTS must have had to backtrack from $s'$ to at least $s_j$. Then it would have updated $h(s_j)$ to $h_\text{new}(s_j) \ge h_\text{new}(s') + k$ on the first trial. Consequently, state $s'$ cannot be the cause of an update to $h(s_j)$ on the second trial as inequality~\ref{eq:newUpdate} will no longer hold, leading to a contradiction.
Thus, no updates to $h$ are carried out on the second trial.  \qed

\bigskip

Let us define $\solution(i)$ as the execution cost of a path $p$ between the start and the goal states such that: (i) $p$ lies fully in the set of states traversed by the agent on trial $i$ and (ii) $p$ minimizes the execution cost.  

\bt\label{th:SLAT} For any valid $T, \gamma, d$ and an admissible initial heuristic $h_0$, the first trial of LRTS$(d,\gamma,T)$ with systematic or fixed tie-breaking and incremental pruning (see Figure~\ref{fig:LRTS-pruning}) results in $\solution(1) \le \frac{h^*(s_0) + T}{\gamma}$. \et

\medskip\nin\proof We will prove this theorem in three steps. \medskip

{\bf Notation}. Consider a sequence of states $[s_0,s_1,\dots,s_n]$ traversed during the first trial. Here state $s_0$ is the start state and state $s_i$ is the current state ($s$) after $i$-th iteration line 27 in LRTS (Figure~\ref{fig:LRTS}). State $s_n$ is the goal state reached at the end of the first trial. Within iteration $i$ ($0 \le i \le n-1$), two states are computed as follows. At the beginning of the iteration (line 6), $s_i$ is the current state $s$. During the forward move (line 23), state $s$ is set to $s_{i+1} = s_{\min}(s_i,d)$.\footnote{The case of seeing a goal state, i.e., $G \neq \emptyset$, is dealt with in a similar fashion.} Let us denote the heuristic value of state $s_i$ at the beginning of iteration $i$ as $h_i(s_i)$. After the possible update in line 17, the new heuristic value is $h_{i+1}(s_i)$. Also, let us denote the amount of learning $\ell$ during iteration $i$ as $\ell_i$. More precisely: \bea \ell_i = \begin{cases} h_{i+1}(s_i) - h_i(s_i) & \text{if $h'(s) > h(s)$ in line 15,} \\ 0 & \text{otherwise.} \end{cases} \eea  Under this notation, it is easy to see that the following inequality holds: \bea\label{eq:dist-main} \gamma \dist(s_i, s_{i+1}) + h_i(s_{i+1}) \le h_i(s_i) + \ell_i \eea when a forward move (line 23) happens. Note that on iteration $i$, state $s_i$ is the only state in which the heuristic value can be updated. Thus, for $\forall s_j \neq s_i \left[h_{i+1}(s_j) = h_i(s_j)\right]$. In particular\footnote{The special case of $s_i = s_0$ can be dealt with in a simple fashion.}, $h_{i+1}(s_{i+1}) = h_i(s_{i+1})$ which allows to transform inequality~\ref{eq:dist-main} into: \bea\label{eq:dist-main2} \gamma \dist(s_i, s_{i+1}) + h_{i+1}(s_{i+1}) \le h_i(s_i) + \ell_i. \eea

{\bf Forward moves.} We will now consider the case of revisiting states during forward moves. Namely, suppose that in the sequence of states $[s_0,s_1,\dots,s_n]$, state $s_{i+k} = s_i$ and $k>0$ is the smallest $k$ such that this equation holds. We will also assume that no backtracking (line 26) took place between states $s_i$ and $s_{i+k}$. The pruning module (lines 23a through 23c in Figure~\ref{fig:LRTS-pruning}) will purge all states between $s_i$ and $s_{i+k}$. Therefore, move $s_{i+k} \to s_{i+k+1}$ will immediately follow move $s_{i-1} \to s_i$ making the new sequence: $s_{i-1} \to s_i (= s_{i+k}) \to s_{i+k+1}$.

For state $s_{i-1}$, the inequality~\ref{eq:dist-main2} is: \bea\label{eq:dist-main3} \gamma \dist(s_{i-1}, s_i) + h_i(s_i) \le h_{i-1}(s_{i-1}) + \ell_{i-1}. \eea For state $s_{i+k}$, the inequality~\ref{eq:dist-main2} is: \bea\label{eq:dist-main4} \gamma \dist(s_{i+k}, s_{i+k+1}) + h_{i+k+1}(s_{i+k+1}) \le h_{i+k}(s_{i+k}) + \ell_{i+k}. \eea Remembering that $s_i = s_{i+k}$ and the only increase of $h(s_i)$ was possible when the algorithm {\em left} state $s_i$, we conclude that $h_i(s_i) + \ell_i = h_{i+k}(s_{i+k})$. To be consistent with the pruned move sequence $s_{i-1} \to s_{i+k} \to s_{i+k+1}$, we re-write inequality~\ref{eq:dist-main3} as: \bea\label{eq:dist-main5} \gamma \dist(s_{i-1}, s_{i+k}) + h_{i+k}(s_{i+k}) - \ell_i \le h_{i-1}(s_{i-1}) + \ell_{i-1}. \eea Adding \ref{eq:dist-main4} and \ref{eq:dist-main5} and re-grouping terms, we arrive at: \bea \gamma \left[ \dist(s_{i-1},s_{i+k}) + \dist(s_{i+k}, s_{i+k+1}) \right] \nonumber \\ \le h_{i-1}(s_{i-1}) - h_{i+k+1}(s_{i+k+1}) + \ell_{i-1} + \ell_i + \ell_{i+k}.\label{eq:dist-chain1} \eea 
%
This means that the weighted sum of distances in the sequence of states $[s_{i-1},s_{i+k},s_{i+k+1}]$ can be upper bounded by the differences in $h$ in the first and the last states plus the sum of learning amounts for each of the three states. It is easy to show that in the absence of backtracking, inequality~\ref{eq:dist-chain1} generalizes for the entire {\em pruned} sequence $[s_0,s_1,\dots,s_n]$ sequence. Note that pruning done to the sequence will manifest itself as gaps in the enumeration of the states. This is similar to the subsequence $s_{i-1}, s_i, s_{i+1}, \dots, s_{i+k}, s_{i+k+1}$ used earlier in the proof becoming $s_{i-1}, s_{i+k}, s_{i+k+1}$. Let us denote the pruned sequence of indices as $I$. Then inequality~\ref{eq:dist-chain1} becomes:\bea\label{eq:dist-chain2} \gamma \sum_{i \in I} \dist(s_i,s_{i+1}) \le h_0(s_0) - h_n(s_n) + \sum_{i=0}^{n-1} \ell_i.  \eea Noticing that $h_0(s_0) \le h^*(s_0)$ and $h_n(s_n) = 0$ as $s_n$ is a goal state, we arrive at: \bea\label{eq:dist-chain3} \gamma \sum_{i \in I} \dist(s_i,s_{i+1}) \le h^*(s_0) + \sum_{i=0}^{n-1} \ell_i.  \eea 
%
Finally, observing that the total amount of learning is upper bounded by the learning quota $T$ and that the sum of distances along the pruned state sequence is exactly $\solution(1)$, we derive the desired upper bound: \bea\label{eq:dist-chain4} \solution(1) \le \frac{h^*(s_0) + T}{\gamma}.  \eea

{\bf Backtracking.} The finale of the proof lies with showing that backtracking (line 26 in LRTS) does not affect the derivation in the previous section. Suppose, LRTS traversed states $s_i \to s_{i+1} \to s_{i+2} \to \dots$ and then backtracked to state $s_i$ on iteration $i+k$ (i.e., $s_{i+k} = s_i$). In the pruned solution sequence all states between $s_{i-1}$ and $s_{i+k}$ will be removed from $path$ (line 26) creating a gap in the enumeration: $\dots, s_{i-1}, s_{i+k}, s_{i+k+1}, \dots$. Observing that states $s_{i-1}, s_i = s_{i+k}, s_{i+k+1}$ (i) were not backtracked from  and (ii) were not among the states removed from the $path$ during backtracking,\footnote{The fact the three states cannot be among the states removed during backtracking is due to the incremental pruning mechanism in lines 23a, 23b, and 23c of Figure~\ref{fig:LRTS-pruning}. The pruning mechanism clearly separates updates to the heuristic function made during forward and backward moves.} we conclude that backtracking did not affect the heuristic value of these three states. Therefore, the previous derivation still holds which concludes the proof of the theorem. \qed

\bibliography{lrts}
\bibliographystyle{theapa}

\end{document}
