
				\|\|\|\|

By Todd W. Neller
Gamasutra
[Author's Bio]
December 12, 2002

Action-Based Discretization for AI Search

Dynamic Action Timing Discretization

Sphere Navigation Search Problem

Submarine Channel Problem

	Printer Friendly Version

Game Developer Magazine Back Issues four CD Set.
Every issue 1994 to April 2002.
Price: $189.00 + S&H

Letters to the Editor:

Write a letter

View all letters

Features

Action-Based Discretization for AI Search

Dynamic Action Timing Discretization

We will assume that the action parameter discretization, i.e. which action parameters are sampled, is already given. From the perspective of the search algorithm, the action discretization is static (cannot be varied by the algorithm). However, action timing discretization is dynamic (can be varied by the algorithm). For this reason, we will call such searches "SADAT searches" as they have Static Action and Dynamic Action Timing discretization.

SADAT searches are different than classical AI searches in only one respect. An action (i.e. operator) additionally takes a time delay parameter indicating how much time will pass before the next action is taken. For dynamical systems where timing is relevant, this is an important generalization.

A SADAT search problem is made up of four parts:

State space (a set of possible states).
An initial state.
A finite set of actions that map a state and a positive time duration to a successor state and a transition cost.
Aset of goal states.

In fact, one could view this as having only three parts if you define the state space in terms of the second and third items above for all possible time durations.

In classical search, a goal path can be specified as a sequence of actions that evolve the initial state to a goal state. Now that the timing of actions is a choice, a goal path can be specified as a sequence of action-duration pairs that evolve the initial state to a goal state. The cost of a path is the sum of all transition costs. Given this generalization, the state space is generally infinite, and the optimal path can generally only be approximated through a sampling of possible paths through the state space.

Algorithms

The following algorithms are all written in Richard Korf’s style of pseudo-code. In an object-oriented implementation, one would naturally have node objects. All of these algorithms simply exit when a goal node is found. Since at any time, the call stack contains all relevant path information for the current node, one could easily modify the algorithms to put node and action information onto a stack while exiting, allowing easy retrieval of the solution path.

Iterative-Deepening A

All searches have exponential time complexity (O(b^d) where b is breadth and d is depth of the search tree.) Depth-first search has linear (O(d)) memory complexity, but does not necessarily find optimal (or even good) solutions. Breadth-first search finds minimum depth solutions, but does so with exponential memory cost. A* search (best-first search with an admissible heuristic) uses a heuristic function to direct search and reduce the cost of search. However, memory complexity is still exponential.

IDA* [Korf, 1985] provides a means of having linear memory complexity and optimality, at the cost of node re-expansion. IDA* performs depth-first searches to successively greater f-value bounds until a solution is found. The pseudo-code for IDA* is as follows:

IDASTAR (node : N)

      B := f(N);

      WHILE (TRUE)

         B := IDASTARB(N, B)

This outermost loop depends on a recursive depth-first search to an f-value bound B:

IDASTARB (node : N, bound : B) IF N is a goal, EXIT algorithm IF N has no children, RETURN infinity FN = infinity FOR each child Ni of N, F[i] := f(Ni) IF f(Ni) <= B, FN := MIN(FN, IDASTARB(Ni,B)) ELSE FN := MIN(FN, f(Ni)) RETURN FN

If the recursive search is unsuccessful, it returns the lowest f-value encountered beyond the current bound. The outermost loop then revises the bound to this value and searches to this greater bound. The amount of node re-expansion is problematic if there are many distinct f-values. Such is true of most real-valued search problems. This problem is addressed by the epsilon-admissible variant described below.

Î-Admissible IDA*

Î-Admissible iterative-deepening A* search, here called Î-IDA*, is a version of IDA* where the f-cost limit is increased "by a fixed amount , on each iteration, so that the total number of iterations is proportional to 1/Î. This can reduce the search cost, at the expense of returning solutions that can be worse than optimal by at most Î."[Russell & Norvig, 1995]

Actually, our implementation is an improvement on Î-IDA* as described above. If Df is the difference between (1) the minimum f-value of all nodes beyond the current search contour, and (2) the current f-cost limit, then the f-cost limit is increased by the maximum of Î and Df. (Df is the increase that would occur in IDA*.) Thus, the limit is increased by at least Î or more if the minimum node f-cost beyond the contour exceeds this increase. This improvement is significant in cases where the f-cost limit changes between iterations can significantly exceed Î. The recursive procedure of Î-IDA* is identical to that of IDA*. The difference is in the computation of successive bounds in the outermost loop:

eIDASTAR (node : N)

      B := f(N);

      WHILE (TRUE)

         B := MAX(IDASTARB(N, B), B+Î)

To make this point concrete, suppose the current iteration of Î-IDA* has an f-cost limit of 1.0 and returns no solution and a new f-cost limit of 2.0. The new f-cost limit is the minimum heuristic f-value of all nodes beyond the current search contour. Let us further assume that Î is 0.1. Then increasing the f-cost limit by this fixed Î will result in the useless search of the same contour for 9 more iterations before the new node(s) beyond the contour are searched. In our implementation above, the f-cost limit would instead increase directly to 2.0.

Recursive Best-First Search

Recursive best-first search (RBFS) [Korf, 1993] is a significant improvement over IDA*. RBFS also expands nodes in best-first order and has linear memory complexity. It also expands fewer nodes than IDA* for nondecreasing cost functions. This is accomplished by some extra bookkeeping concerning node re-expansion. Korf’s RBFS algorithm is as follows:

RBFS (node: N, value: F(N), bound: B) IF f(N)>B, RETURN f(N) IF N is a goal, EXIT algorithm IF N has no children, RETURN infinity FOR each child Ni of N, IF f(N)<F(N), F[i] := MAX(F(N),f(Ni)) ELSE F[i] := f(Ni) sort Ni and F[i] in increasing order of F[i] IF only one child, F[2] := infinity WHILE (F[1] <= B and F[1] < infinity) F[1] := RBFS(N1, F[1], MIN(B, F[2])) insert Ni and F[1] in sorted order RETURN F[1]

RBFS suffers from the same problem as IDA* when there are many distinct f-values. This problem is addressed by the new epsilon-admissible variant of RBFS described below.

Î-Admissible RBFS

Î-Admissible recursive best-first search [Neller, 2000], here called Î-RBFS, is a new Î-admissible variant of recursive best-first search [Korf, 1993]. As with our implementation of Î-IDA*, local search bounds increase by at least Î but possibly more as necessary to avoid redundant search.

In Korf's style of pseudo-code, Î-RBFS is as follows:

eRBFS (node: N, value: F(N), bound: B) IF f(N)>B, RETURN f(N) IF N is a goal, EXIT algorithm IF N has no children, RETURN infinity FOR each child Ni of N, IF f(N)<F(N), F[i] := MAX(F(N),f(Ni)) ELSE F[i] := f(Ni) sort Ni and F[i] in increasing order of F[i] IF only one child, F[2] := infinity WHILE (F[1] <= B and F[1] < infinity) F[1] := eRBFS(N1, F[1], MIN(B, MAX(F[2], F[1]+Î))) insert Ni and F[1] in sorted order RETURN F[1]

The difference between RBFS and Î-RBFS is in the computation of the bound for the recursive call. In RBFS, this is computed as MIN(B, F[2]) whereas in Î-RBFS, this is computed as MIN(B, MAX(F[2], F[1]+Î)). F[1] and F[2] are the lowest and second-lowest stored costs of the children, respectively. Thus, the bound of the recursive call will not exceed that of its parent, and will be the greater of the stored value of the lowest-cost sibling F[2] and its own stored value F[1] plus Î.

The algorithm’s initial call parameters are the root node r, f(r), and ¥. Actually, both RBFS and Î-RBFS can be given a finite bound b if one wishes to restrict search for solutions with a cost of no greater than b, and uses an admissible heuristic function. If no solution is found, the algorithm will return the f-value of the minimum open search node beyond the search contour of b.

In the context of SADAT search problems, both Î-IDA* and Î-RBFS assume a fixed time interval Dt between a node and its child. The following iterative-refinement algorithms do not.



	Figure 2: Iterative-deepening and iterative-refinement depth-first search.

Iterative-Refinement

Iterative-refinement [Neller, 2000] is perhaps best described in comparison to iterative-deepening. Iterative-deepening depth-first search (Figure 2(a)) provides both the linear memory complexity benefit of depth-first search and the minimum-length solution-path benefit of breadth-first search at the cost of node re-expansion. Such re-expansion costs are generally dominated by the cost of the final iteration because of the exponential nature of search time complexity.

Iterative-refinement depth-first search (Figure 2(b)) can be likened to an iterative-deepening search to a fixed time-horizon. In classical search problems, time is not an issue. Actions lead from states to other states. When we generalize such problems to include time, we then have the choice of how much time passes between search states. Assuming that the vertical time interval in Figure 2(b) is Dt, we perform successive searches with delays Dt, Dt/2, Dt/3, … until a goal path is found.

Iterative-deepening addresses our lack of knowledge concerning the proper depth of search. Similarly, iterative-refinement addresses our lack of knowledge concerning the proper time discretization of search. Iterative-deepening performs successive searches that grow exponentially in time complexity. The complexity of previous unsuccessful iterations is generally dominated by that of the final successful iteration. The same is true for iterative-refinement.

However, the concept of iterative-refinement is not limited to the use of depth-first search. In general, for each iteration of an iterative-refinement search, a level of (perhaps adaptive) time-discretization granularity is chosen for search and an upper bound on solution cost is given. If the iteration finds a solution within this cost bound, the algorithm terminates with success. Otherwise, a finer level of time-discretization granularity is chosen, and search is repeated. Search is successively refined with respect to time granularity until a solution is found.

Iterative-Refinement Î-RBFS

Iterative-Refinement Î-RBFS is one instance of such iterative-refinement search. The algorithm can be simply described as follows:

IReRBFS (node: N, bound: B, initDelay: DT) FOR I = 1 to infinity Fix the time interval between states at DT/I eRBFS(N, f(N), B) IF eRBFS exited with success, EXIT algorithm

Iterative-Refinement Î-RBFS does not search to a fixed time-horizon. Rather, each iteration searches within a search contour bounded by B. Successive iterations search to the same bound, but with finer temporal detail.

Iterative-Refinement DFS

The algorithm for Iterative-Refinement DFS is given as follows:

IRDFS (node: N, bound: B, initDelay: DT) FOR I = 1 to infinity Fix the time interval between states at DT/I DFS-NOUB(N, f(N), B) IF DFS-NOUB exited with success, EXIT algorithm

Our depth-first search implementation DFS-NOUB uses a node ordering (NO) heuristic and has a path cost upper bound (UB). The node-ordering heuristic is as usual: Nodes are expanded in increasing order of f-value. Nodes are not expanded that exceed a given cost upper bound. Assuming admissibility of the heuristic function h, no solutions within the cost upper bound will be pruned from search.

______________________________________________________

Sphere Navigation Search Problem