0
77

Heuristically Informed Searches:

So far we have looked into procedures that search the search space in an uninformed manner. Such procedures are usually costly with respect to either time, space or both. We now focus on a few techniques that search the solution space in an informed manner using something which is called a heuristic. Such techniques are called heuristic searches. The basic idea of a heuristic search is that rather than trying all possible search paths, you try and focus on paths that seem to be getting you closer to your goal state using some kind of a “guide”.

Of course, you generally can’t be sure that you are really near your goal state. However, we might be able to use a good guess for the purpose. Heuristics are used to help us make that guess. It must be noted that heuristics don’t always give us the right guess, and hence the correct solutions.

Recall the example of the mouse searching for cheese. The smell of cheese guides the mouse in the maze, in other words, the strength of the smell informs the mouse how far is it from the goal state. Here the smell of cheese is heuristic and it is quite accurate.

Similarly, consider that the maze has fences fixed along some of the paths through which the smell can pass. Our heuristic might guide us on a path that is blocked by a fence, hence again the heuristic is misguiding us.

AI problem solver employs heuristics in two basic situations:

1. A problem because of ambiguities may not have the exact solution.
2. A problem may have an exact solution, but the computational cost of finding it may be prohibitive.

Heuristics attack this complexity by guiding the search along the most “promising” path through space. By eliminating unpromising states and their descendants from consideration, a heuristic algorithm can defeat this combinatorial explosion and find an acceptable solution. It is useful to think of heuristic algorithms as consisting of two parts: the heuristic measure and an algorithm that uses it to search the state space.

Also Read: What is Artificial Intelligence?

Example: tic-tac-toe

In a complete search space, there are 9! Possible state to search, through heuristics this search can be reduced. Symmetry reduction decreases the search space. Many problem configurations are actually equivalent under symmetric operation on the game board.
In tic-tak, there are only three initial moves: to a corner, to the center of a side and to the center of the grid.

The conclusion then is that heuristics do help us reduce the search space, but it is not at all guaranteed that we’ll always find a solution. Still, many people use them as most of the time they are helpful. The key lies in the fact that how do we use the heuristic. Consider the notion of a heuristic function.

Whenever we choose a heuristic, we come up with a heuristic function that takes as input the heuristic and gives us out a number corresponding to that heuristic. The search will now be guided by the output of the heuristic function. Depending on our application we might give priority to either larger numbers or smaller numbers.

A simple heuristic, however, can almost eliminate search entirely: we may move to the board in which X has the most winning lines. In case of a state with equal numbers of potential wins, take the first such state found. The algorithm then selects and moves to the state with the highest heuristic value. In this case, X takes the center of the grid. The opponent will have only two choices to go head. And after that again the most winning option will be selected.

Heuristic Evaluation Function:

We now evaluate the performance of several different heuristics for solving the 8-puzzle, The following figure shows a start and goal state for the 8-puzzle, along with the first three states generated in the search.

In order to measure the more favorable choice that will quickly lead towards the goal might be the number of tiles out of place. E.g. in the following diagram 5 tiles are out of place i.e. 1,2,8,6,7

However, this heuristics does not give you the good guess because it does not take into account the distance each tile must be moved. E.g. in the above diagram the tile 8 is at distance two because to reach a desire position it must have to make two moves.

So, a better heuristic may be the sum of distances for each out of place tile. Both of these explained heuristics can be criticized for failing to acknowledge the difficulty of tilt reversal. That is if two tiles are next to each other and the goal requires their being in the opposite locations. It takes more than two moves to put them back in place. E.g.

To cope with reversal tiles, Another heuristics can be taken into account. Third heuristics multiply a small number (2, for example) with each direct tile traversal. The following figure represents the already discussed three different heuristics

Among these three “sum of distance” indeed seem to provide a more accurate estimate of the work to be done than the simple count of the number of tiles out of place. Also, the tile traversal heuristic fails to distinguish between these three different states, giving each an equal evaluation of 0. Although it is an intuitively appealing heuristics, it breaks down since none of these states have any direct reversal. After discussing all these, we come up with a fourth heuristic that is basically the sum of second and third heuristic.

However, this example illustrates the difficulty of devising good heuristics. The design of good heuristics is an empirical problem; judgment and intuition help.

SHARE
Previous articleStructure and Strategies for State Space Search AI Part 2
I am a Linux enthusiast still learning more about Linux and get my way around. I love writing articles and share what I know and Learn new things. I am also a security researcher and penetration tester.