Wednesday, 11 November 2015

Search Algorithms in AI

Search in AI

Many problems in AI can be formulated as finding a sequence of actions that lead us from the current state to one of the goal states, for instance finding the shortest path through a maze. Such problems can be categorized as follows:

  • Based on the nature of search space: Discrete vs Continuous 
  • Based on the type of percept or information available: Uninformed vs Informed
  • Based on the type of solution desired: Global vs Local 
  • Based on ability to find optimal solution: Complete vs Incomplete
  • Based on the environment: Deterministic vs Non-deterministic
  • Miscellaneous: Adversarial 

Searching as traversing a tree

When the search space is discrete it is possible to enumerate all possible sequence of states that can be reached from a given state. This is often done in the form of a tree where the nodes represent states and branches represent actions that can be taken at a particular state. Leaves of such a tree are reached as a result of taking a finite sequence of actions that either end in a goal state or a dead-end. Goal states might also occur at non-leaf nodes. Any path from the root node to the goal node is a valid solution sequence but often we are looking for shortest sequence that gets us to the goal. If at any state the maximum number of possible actions/branches is $b$ and the maximum length of action sequences is $l$, then searching for the goal can take upto $\mathcal{O}(b^l)$ time. Some brute force search algorithms are:
  • Breadth-First Search: Expand the node at the shallowest depth
  • Depth-First Search: Expand the node at the deepest depth
  • Uniform-Cost Search (Dijkstra): Expand the node with the smallest cost of reaching it from the root
  • Iterative Deepening Search: Repeatedly run DFS with increasing depth limits
  • Bidirectional Search: Search from both start and goal until the paths meet 
In cases where no additional information is available about the states these are the only options. However, when additional information is available to guide the search other possibilities exist:
  • A*: Expand the node $n$, with the lowest $C(n)+h(n)$ where $C(n)$ is the cost of reaching that node and $h(n)$ is an estimate of closeness to goal. This algorithm is complete iff $h(.)$ is admissible, meaning that it never overestimates the distance to goal, for instance straight line distance to the target on a map. 
  • Branch & Bound: Perform an inorder traversal of tree while updating the bounds on the optimal solution based on the information available at the node each time it is visited. If the bound at node $n$ does not have an intersection with its parent then prune the subtree.  

Searching as exploring the energy landscape

In discrete or combinatorial optimization problems with some kind of structure and an available energy function to measure the goodness of the solution (more energy meaning a better solution), one can explore the local neighborhood of a current state to incrementally improve the solution. Some algorithms in this domain are:
  • Hill Climbing: Move the neighboring state which results in maximum increase in energy until no neighbor can increase the energy
  • Simulated Annealing: Randomly choose a neighboring state and if it the change in energy $\nabla E$ is positive then accept the move. Else accept the move with probability $e^{\nabla E/T}$ where T decreases with each iteration
  • Local Beam Search: Keep track of $k$ best states rather than just $1$. In each iteration generate all $k$ successors of all $k$ states and select the $k$ best
  • Genetic Algorithms: Begin with a population. Assign a fitness score to each member. Choose pairs for cross over with probability proportional to the fitness score. Merge/Cross over the members in each pair. Mutate the result and iterate

Searching in continuous spaces

Two simplest algorithms are:
  • Gradient Ascent: $x \leftarrow x + \alpha\nabla f$
  • Newton Raphson: Used to find zeros of a function. Maxima occurs when the gradient is $0$ leading to $x = x - H^{-1}(x)\nabla f(x)$

Searching with non-deterministic actions

If actions can lead to stochastic transition behaviour, then contingencies need to be planned for. This usually amounts to constructing an AND-OR search tree and modified version of DFS algorithm to look for goal while handling cycles appropriately. Some of the paths from the root lead to loops while others lead to goal state. One needs to find the path which avoids the loop. 

Searching in presence of adversary

Searching in presence of adversary amounts to playing a two player, zero sum game (utility values at the end of the game are always equal and opposite). Optimal decision can be taken by using the minimax algorithm. First a state space search tree is created. The minimax value (utility of being in a state assuming both players play optimally from there to the end of the game) at each node is then defined as being one of the following:
  • Terminal state: Predefined for instance $\{0, 1, 0.5\}$ for outcomes {Checkmate, Win, Draw} in chess
  • Our (max's) turn: Choose the action that leads to a state of maximum minimax 
  • Adversary's turn: Choose the action that lead to a state of minimum minimax 
However, sometimes the search tree might be exponentially large to enumerate all possible state sequences. Alpha-Beta Pruning can be used to prune out subtrees early on avoiding further search along those paths. It is a form of Branch & Bound algorithm where an inorder-DFS-traversal is performed in the tree and whenever a node is revisited the bound on the minimax value is updated based on the children that have been observed so far. If the bound on a node has a null intersection with its parent then the subtree situated at that node is pruned out.