# A Contribution of Shortest Paths Algorithms to the NetworkX Python Library
## 3 Foundations
### Real-Time Adaptive A* (RTAA*)  
[PERSON] and [PERSON] (2006) [35] explained that 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 is required to select its actions in a limited amount of time, while perceiving only a local part of the environment centred at the agent's current location. Real-time heuristic search agents select actions using a limited lookahead search, evaluating the frontier states with a heuristic function [35]. The Real-time Adaptive A* (RTAA*) algorithm, proposed by [PERSON] and [PERSON] (2006) [55], is a real-time heuristic search method that chooses its local search spaces in a very fine-grained way in which the main idea is to update the heuristics of all states in the local search space very quickly and to save the heuristics to speed up future A* searches. As in A*, the merit of a node \(n\) is \(f(n)=g(n)+h(n)\). However, unlike A*, the interpretation of \(g(n)\) in RTAA* is the actual distance of a node \(n\) from the current state of the problem solver, rather than from the original initial state. The key difference between RTAA* and A* is that, in RTAA*, the merit of every node is measured relative to the current position of the problem solver, and the initial state is irrelevant. RTAA* is simply a best-first search given this slightly different cost function. In parallel studies in real-time search methods, Learning Real-time A* (LRTAA*) [35] produces feasible paths any time during its execution and minimum length paths if allowed to run to completion [54]. [PERSON] et al. (2006) [54] applied the LRTAA* in the context of a path planner for unmanned air vehicle target sensing, which resulted in a planner that produces short-distance paths in acceptably short running times. The pseudo code of the RTAA* is presented in Algorithm 6. ```
1 Constants and function
2\(S\)-set of states of the search task, a set of states
3\(GOAL\)-set of goal states, a set of states
4\(A\)()-sets of actions, a set of actions for every state
5\(succ(\)-successor function, a state for every state-action pair
6 variables
7 Lookahead-number of states to expand at most, an integer larger than zero
8 Movements-number of actions to execute at most, an integer larger than zero
9\(S\)-current state of the agent, a state [USER]
10\(c\)-current action costs, a float for every state-action pair [USER]
11\(h\)-current action costs, a float for every state-action pair [USER]
12\(g\)-\(g\)-values, a float for every state [A*]
13 CLOSED-closed list of A*(= all expanded states), a set of states [A*]
14\(s\)-state that A* was about to expand when it terminated, a state [A*]
15 procedurerealtime adaptive astar():
16 while(\(s\)-curr \(\in\) GOAL)do
17\(lookahead:=any\) desired integer greater than zero;
18 astar();
19 ifs = FAILUREthen
20 return FAILURE;
21 forall s 2 CLOSEDdo
22\(h[s]:=g[s]+h[s]-g[s]\);
23 movements := any desired integer greater than zero;
24 while(\(s\)-curr \(\
eq\) s AND movements > 0)do
25\(h\)-:= the action in \(H(S\)-curr) on the cost-minimal trajectory from \(s\)-curr to \(s\);
26\(s\)-curr = succ(\(s\)-curr);
27 movements := movements - 1;
28 forany desired number of times (including zero)do
29 increase any desired cls; a] where s \(\in\) S and a \(\in\) A(s);
30 ifany increased cls; a] is on the cost-minimal trajectory from \(s\)-curr to \(s\)then
31 break
32 return SUCCESS;
```  
**Algorithm 6** Real-time Adaptive A* (RTAA*) algorithm pseudocode [54]. [PERSON] et al. (2011) [56] presented an approach of RTAA* that incorporates depression avoidance, in other words, a strategy to prevent the algorithm from getting trapped in heuristic depressions, which are bounded regions in the search space where the heuristic values are significantly lower than those on the surrounding boundary, in problems with limited time constraints.