WHAT IS GUIDED AND UNGUIDED SEARCH IN AI | BLOG |

DATE :- 10/02/2020 

A typical chess playing program might need to evaluate a million states during a serious chess game.

We will look at two types of search, guided and unguided. Unguided search is done without the help of heuristics while guided search takes the help of heuristic in choosing seemingly better path than the rest.

Guided and unguided search

Let us go back to the previous chapter and look at the 8-5-3 gallon milk jug problem. Suppose we have no clue about how to achieve the solution, we may start randomly and try applying any rule which is applicable to a given state space. We may have a sequence which is different than what led to the solution in the previous chapter but if given enough amount of tries it is quite likely to reach to a solution barring an important point; the solution path should not contain any cycles.

For example consider following sequences

8-0-0, 3-5-0, 8-0-0, ...

8-0-0, 5-0-3, 0-5-3, 3-5-0, 8-0-0, ..

8-0-0, 5-0-3, 5-3-0, 2-3-3, 0-5-3, 5-0-3...

The process may continue forever but we will not find a final state as state sequences are repeated.
So we may form the rule for a search that if the same state which is generated earlier should not be
generated again. Sometimes this requirement is known as being systematic.

Even if we follow that rule you may clearly see that some futile states may be traveled before embarking on the right path. Even when we are dealing with such a simple problem we may end up traversing a very long path before getting a solution.

Such search, which operates blindly, applying random moves to try for a final state, is known as
unguided or blind search.

 On the contrary, it is usually possible to have some domain knowledge to learn that some typical types of moves are better than others. Trying them before others usually lead to a solution faster. Such domain knowledge is called heuristics and search which operates using heuristics is called guided search.

 Though they are less efficient than guided search methods, they are useful when there is not enough domain knowledge and when some other guided search is applied in conjunction with them.

Generate and test

This method is quite known to us. For example, when my father leaving for job and cannot find my car keys on the place he usually keep them, he try looking for them in my table drawer, in the showcase, on my study table and so on, may be finally looking at the place where her daughter is playing. What he is doing? he is generating states one after another, checking if it is a solution state, if so quits or otherwise try looking at some other option.

This simple method is useless if the state space is too large. For example, if I have to search my entire
house for the key, it is impossible in real time. That is why to generate and test is applied when the state space is either small enough or some other technique is used to reduce the number of states to a
manageable level.

Glossaries

Search                                  search is a common component in most AI solutions. A Search is a way                                                 to find a solution using the state space.

Unguided search                  Search without using any heuristics or not using any domain knowledge.
                                             This is also known as blind search.

Guided search                      Search using some heuristic. This type of search takes the advantage of
                                             domain knowledge to determine which type of states are better compared
                                             to others in choosing the next state

State sequence                     sequence of states which results in a solution

Generate and Test                an unguided search method where random selection of states are chosen                                                 and  tested for a solution

Dendral                                Expert system for geological information designed based on generate                                                     and  test and constraint satisfaction methods

Breadth First Search(BFS)   the search method where each level of the tree is explored first and the                                                  next level is explored is explored after that till the final level.                                                                  Exploration a method of exploring the tree level by level in BFS

Depth First Search               The search method where each branch of tree is explored one after                                                          another from left to right till the rightmost branch

Depth bound DFS               This method is a depth first search considering the length of the DFS                                                       search for a typical value. This is also known as Depth-Limited Search

Optimum path                     a path to solution which is nearest from the root node

Finite Search space             If the state space contains a finite number of nodes it is called finite                                                        search space. For a finite search space, both DFS and BFS is guaranteed                                                to give an optimum solution.