### path finding AI – search tree A*

####################################
####     Path Finding in AI     ####
####################################

one effective problem solving algo used in AI is a state-tree structure where the root = initial state, and child nodes for potential moves, and so on.

(1) game tree (aka and/or tree)  : two players take alternating turns. e.g. chess, tic-tac-toe
===> DFS/BFS, A*
(2) search tree                  : a single player game. e.g. 8-puzzle
===> minimax, negmax, alphabeta pruning

branching factor BF = the # of possible moves from a given state.

obviously, a game like chess has BF = 30ish, which means the state tree can quickly explode.

(assumption):
- a state can be represented effectively enough to be processed in the algos we use.
- we have access to all available moves for a given state of the game.
- those available moves are finite.
- in many games, relation between possible states are not really a tree structure, but rather a mesh graph, but we just treat as a tree to apply the below discussed algo.

##
## heuristic
##

Wikipedia summarizes this concisely.
"In computer science, artificial intelligence, and mathematical optimization, a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed."

it's an easier and often simpler methodology for estimating a fairly viable answer.
to be distinguished from established algo that guarantees an optimal solution but with possibly enormous computation or approximation algo.
approxation algo and heuristics - there can be only a thin line semantically.

obviously, for our path-finding in AI context, heuristic is a way to aid in the ranking scheeme for eliminating candidates. in the 8-puzzle example, you can measure how far each piece is from its goal position, add the distance up and pick the move with the lowest. this is commonly known as a static (cost/distance) evaluation function.

(ref)
http://en.wikipedia.org/wiki/Heuristic_(computer_science)
http://ja.m.wikipedia.org/wiki/%E3%83%92%E3%83%A5%E3%83%BC%E3%83%AA%E3%82%B9%E3%83%86%E3%82%A3%E3%82%AF%E3%82%B9

#######################
####    DFS/BFS    ####
#######################

(see the DFS/BFS article from Graph category)

# input: initial & goal states

# output: a sequence of moves from the init state to the goal state (or declares no path)

(assumption)
we need to define the max depth "d" otherwise, it can traverse in an infinite loop fashion.
because depending on the sequence of moves you pick, it's possible to go into an infinite loop.
this "d" should be small enough to not overflow the heap mem.

DFS is a blind backtracking recursive search algo for a search tree.
because of its nature that it does not search all the available nodes in a given depth before searching the next depth nodes, even if a path between the init and goal states is found, it is not guaranteed to be "the shortest" path.

BFS on the other hand does guarantee the shortest path when it finds a path. but its expense is best case computation complexity.

------------------------------ // DFS psuedo code

search(init,goal)

if(init == goal) return "solution found";
init.depth = 0;
unvisited = new Stack;
visited = new Set;               // better use something like a hash cos search cost can be big later.
unvisited.insert(copy(init));

while(!unvisited.empty())
{
n = unvisited.pop();  // n = a state
visited.insert(n);
foreach m (all moves of n)
{
nxt = state after playing m at n;
if(!visited.contain(nxt))
{
nxt.depth = n.depth + 1;  // obviously
if(nxt == goal) return "solution found";
if(nxt.depth < d) unvisited.insert(nxt);  // d = maxDepth. as long as not reaching d, we go further.
}
}
}
return "no solution"

------------------------------

===> for implementation, each state needs to store;
(1) depth of the state
(2) prev state
(3) the move that generated

------------------------------ // BFS psuedo code

search(init,goal)

if(init == goal) return "solution found";
unvisited = new Queue;       // notice how we just changed Stack to Queue
visited = new Set;
unvisited.insert(copy(init));

while(!unvisited.empty())
{
n = unvisited.enqueue();  // n = a state
visited.insert(n);
foreach m (all moves of n)
{
nxt = state after playing m at n;
if(!visited.contain(nxt))
{
if(nxt == goal) return "solution found";
unvisited.insert(nxt);  // unlike DFS, we dont check max depth
}
}
}
return "no solution";

------------------------------

===> search space cost can be enormous.

##
## complexity analysis
##

b = branching factor
d = max depth

DFS
- best    : O(b*d)
- worst   : O(b^d)
- average : O(b^d)

DFS
- best    : O(b^d)
- worst   : O(b^d)
- average : O(b^d)

#######################
####   A* Search   ####
#######################

A* search adds heuristic intelligence. "*" refers to hueristic.

A* says for each possible successor state, calculate the distance from the start state to the successor state g and estimate the distance from the successor state to the goal state h, and then select the successor state the minimizes f = g + h.

n: successor state from open set(we use PQ in psuedo code)
g*(n) : an eval func to estimate shortest sequence of moves from the init state to n
h*(n) : an eval func to estimate shortest sequence of moves from n to the goal state
f*(n) : = g*(n) + h*(n)   i.e. estimates shortest sequence of moves from init to goal via n

note: we can think of the cost/distance as depth essentially
all of the above functions are estimate functions. the actual cost f(n) = g(n) + h(n) are unknown until a solution is found.

thus for each of the states in the open set(= contains all the available moves atm), we calc f*(n) and pick n that gives the lowest f*(n)

##
## Constraints
##

(1)  g*(n) >= g(n)      : because any path you found init-n, there can be a shorter path. (we just check depth essentially)
(2)  0 <= h*(n) <= h(n) : see below.

if h*(n) < 0, means it thinks n already passed the goal state
if h*(n) = 0, means BFS. if h*(n) > h(n)
if h*(n) > h(n), means it's estimating the depth/cost/distance to the goal from n to be more than the actual depth/cost/distance, thus picks the unproductive state. (e.g. going into unproductive subtree of DFG, etc. However, it is still possible to reach a solution. )

# input & output : same as DFS/BFS

just like DFS/BFS, A* maintains open/closed sets of states.
open = availables next moves

if a state S that is already in the closed set is found to have a less cost, then A* removes S from the closed set, and re-inserts to the open set with the updated cost.

------------------------------- // psuedo code

search(init,goal)

init.depth = 0;
pq = new PQ;  // manages the open states
closed = new Set;  // all passed states
pq.insert(copy(init));

while(!pq.empty())
{
n = pq.enqueue();  // get the smallest cost/distance state n
closed.insert(n);
if(n == goal) return "solution";
foreach m in (all possible moves at n)
{
nxt = state when playing m at n;
nxt.depth = n.depth + 1;
if(closed.contain(nxt))
{
prior = state in closed Set matching nxt;
if(nxt.cost() < prior.cost())    // this cost() function better be good.
{
closed.remove(prior);  // as discussed in the past, need to somehow track its index to keep O(logN)
pq.insert(nxt);
}
}
else
{
pq.insert(nxt);
}
}
}

return "no solution";

-------------------------------

====> notice we dont compare if(nxt == goal) because goal may be already in the open set, in which case we want the one already in the open as that comes with less depth, i.e. a shorter path.

implementation wise, each board state should store:  (so that we can reconstruct the path init-goal)
(1) the move that generated it
(2) a ref to prev state
(3) known(estimated) depth(cost) of the state

##
## complexity analysis
##

just like DFS

best    : O(b*d)
average : O(b^d)
worst   : O(b^d)

########################
###   related algo   ###
########################

IDA* : Iterative Deepening applid to A*search. do DFS to a certain depth, then prioritize which subtree to pursue further down. then repeat that ID process.

transposition tables : a technique for pruning unproductive subtrees. use a hash table to store state-distance(from init state) key-value pair. and if a state being examined has a worse distance, then avoid that subtree.

HPA* : hierachical path finding A*

SMA* : simplified memory bounded A*

(ref) Algorithms in a nutshell. Heineman et al.

1. 2014-08-28 10:43:51 |
2. Category : algo
3. Page View: