This article explains how to solve problems using AI search techniques. This is an introductory article on AI search that helps the beginners understand searching in Artificial Intelligence.
When we have a problem we search for solution. If the search is done systematically there is a greater chance for getting the solution. To make the search systematic, intelligence and knowledge are required. Nowadays we tend to make use of machines to solve our problems. We could easily assume that if intelligence and knowledge are created artificially in machines, they will be able to solve problems. In the field of artificial intelligence (AI), number of search techniques have been developed for problem-solving. This article presents an overview of AI search techniques.
Problems And Solutions
Problems can be characterized as a space consisting of a set of states and a set of operators that map from one state to other states. There will be one or more initial states, intermediate states and one or more goal states. A solution will be a sequence of operators (or path) that map an initial state to goal state. The best solution will be the shortest path consisting of fewer number of operations. The solution path forms a tree structure. Assume that we need to reach a particular place farther away and we have to go by road. Now, the initial state is one we are currently staying and the goal state is obviously the place we need to reach. And there will be number of places, say intermediate states, in between. What is the best solution to reach the place? Obviously the shortest distance between the two places.
Types of Search Techniques
Search techniques can be classified based on the amount of relevant information available. There are two broad categories: uninformed search and informed search.
Uninformed Search
It is not always possible to get all the relevant information to solve problems. In this situation, we have to search blindly with less information. Uninformed search is also called blind search. Searching is similar to traversing a tree where each node represents a state. One way of solving a problem is to search for all the states at the first level. Each state can then be explored to expand the tree to the next level. This search process continues level by level till the goal (or solution) state is reached. This is like searching for all the neighboring places first, then exploring all their adjacent places and so on till we reach the destination. This search technique is called breadth-first search (BFS). Though it takes a lot of time to reach the goal state, BFS guarantees that we can reach a state with shortest path from the initial state.
Instead of searching all the states at each level of the tree, search can be done by exploring one level deeper, usually left-wards till the goal state is reached or considerable number of levels explored. If no goal is reached then it has to backtrack to the previous level and continue searching in another direction. This technique is called depth-first search (DFS). If the goal state exists earlier in the search path then DFS is guaranteed to find it with less time. If the goal state is at the right most of the tree then DFS is no better than BFS. Sometimes it would be better to search in both directions: one from the initial state and another from the goal state. This is called bidirectional search.
Informed Search
When we have enough relevant information or clues, we can solve the problem at hand in a smarter way. The information that may lead to the solution is called heuristic information and informed search is commonly known as heuristic search. Instead of searching one path or many paths blindly, informed search uses the clue to decide whether to explore the current state further.
While climbing a hill we will look around to evaluate with the information at hand and decide which is the better position to move next. A search technique which behaves like a hill climber, known as hill climbing search, chooses the most promising node as successor and moves on. It is important to note that the explored nodes on the path are simply discarded. Though hill climbing can produce substantial savings when reliable information is available it has some drawbacks such as foothill, ridge and plateau traps. It would be wise to store the already expanded nodes so that we can backtrack if we realize that the present path is not promising one. A technique that follows this approach is called best-first search.
Apart from the search techniques mentioned above there are many variants of these techniques available. Which technique should be used entirely depend on the application and the information availabe for search.