AI Search

What is AI Search?

AI search is an intelligent way of solving problems in the field of Artificial Intelligence. Adding some ntelligence to the search techniques have proved worthy. There are many search techniques developed in the area of Artificial Intelligence. This article explains the background for AI search and some of the AI search techniques.

Problem Space

What is problem space? A problem space is a set of states and a set of operators. The operators map from one state to another state. There will be one or more states that can be called initial states, one or more states which we need to reach what are known as goal states and there will be states in between initial states and goal states known as intermediate states. So what is the solution? The solution to the given problem is nothing but a sequence of operators that map an initial state to a goal state. This sequence forms a solution path. What is the best solution? Obviously the shortest path from the initial state to the goal state is the best one. Shortest path has only a few operations compared to all other possible solution paths. Solution path forms a tree structure where each node is a state. So searhing is nothing but exploring the tree from the root node.

Types of AI Search Techniques

Solution can be found with less information or with more information. It all depends on the problem we need to solve. Usually when we have more information it will be easy to solve the problem. There are two kinds of AI search techniques: uninformed searh and informed search.

Uninformed Search

Sometimes we may not get much relevant information to solve a problem. Suppose we lost our car key and we are not able to recall where we left, we have to search for the key with some information such as in which places we used to place it. It may be our pant pocket or may be the table drawer. If it is not there then we have to search the whole house to get it. The best solution would be to search in the places from the table to the wardrobe. Here we need to search blindly with less clue. This type of search is called uninformed search or blind search. There are two popular AI search techniques in this category: breadth first search and depth first search.

Breadth first search (BFS), as the name implies, searches from the initial state breadth-wise. That is it searches all the states in the tree level by level. Only after exploring all the states in one level it will jump to the next level. Once the solution is found the search stops. The breadth first search is guaranteed to find the solution if one exists. Another approach is to explore only one branch deeper till the solution is found or there is no new state to explore and then start searching the adjacent level. This technique is called depth first searh (DFS). By chance the solution exists in the first branch then depth first search can find the solution quickly. If the solution exists in some other branches farther away, there won't be much difference between depth first search and breadth first search. The problem with DFS is that it may get trapped in a indefinite loop. An alternate way is to search in both directions. That is one search from initial state to goal state and another search from goal state to initial state. This technique is called bidirectional search. Uninformed search is also called brute force search.

Informed Search

We can solve the problem in an efficient manner if we have relevant information, clues or hints. The clues that help solve the problem constitute heuristic information. So informed search is also called heuristic search. Instead of searching one path or many paths just like that informed search uses the given heuristic information to decide whether or not to explore the current state further. Hill climbing is an AI search algorithm that explores the neighboring states and chooses the most promising state as successor and continue searching for the subsequent states. Once a state is explored, hill climbing algorithm simply discard it. Hill climbing search technique can make substantial savings if it has reliable information. It has to face three challenges: foothill, ridge and plateau. Best first search is a heuristic search technique that stores the explored states as well so that it can backtrack if it realizes that the present path proves unworthy.