## 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:Expand the node at the shallowest depth**Breadth-First Search:**Expand the node at the deepest depth**Depth-First Search:**Expand the node with the smallest cost of reaching it from the root**Uniform-Cost Search (Dijkstra):**Repeatedly run DFS with increasing depth limits**Iterative Deepening Search:**Search from both**Bidirectional Search:***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:

Expand the node $n$, with the lowest $C(n)+h(n)$ where $C(n)$ is the cost of reaching that node and $h(n)$**A*:***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.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**Branch & Bound:***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:Move the neighboring state which results in maximum increase in energy until no neighbor can increase the energy**Hill Climbing:**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**Simulated Annealing:**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**Local Beam Search:**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**Genetic Algorithms:**

## Searching in continuous spaces

Two simplest algorithms are:

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

## 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:Predefined for instance $\{0, 1, 0.5\}$ for outcomes {**Terminal state:***Checkmate, Win, Draw*} in chessChoose the action that leads to a state of maximum**Our (max's) turn:***minimax*Choose the action that lead to a state of minimum**Adversary's turn:***minimax*

However, sometimes the search tree might be exponentially large to enumerate all possible state sequences.

*can be used to prune out subtrees early on avoiding further search along those paths. It is a form of***Alpha-Beta Pruning***algorithm where an inorder-DFS-traversal is performed in the tree and whenever a node is revisited the bound on the***Branch & Bound***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.