Heuristic Search Techniques in AI: Generate & Test, Hill Climbing and Best-first search (Part I)

What is Heuristic Search technique?

Heuristic search is an AI search technique that employs heuristic for its moves. Heuristic is a rule of thumb that probably leads to a solution. Heuristics play a major role in search strategies because of exponential nature of the most problems. Heuristics help to reduce the number of alternatives from an exponential number to a polynomial number. In Artificial Intelligence, heuristic search has a general meaning, and a more specialized technical meaning. In a general sense, the term heuristic is used for any advice that is often effective, but is not guaranteed to work in every case. Within the heuristic search architecture, however, the term heuristic usually refers to the special case of a heuristic evaluation function.

•         Generate-and-test

•         Hill climbing

•         Best-first search

Generate-and-test

Algorithm:

1. Generate a possible solution.
2. Test to see if this is actually a solution.
3. Quit if a solution has been found. Otherwise, return to step 1.

Advantages & Disadvantages:

•         Acceptable for simple problems.

•         Inefficient for problems with large space.

Hill Climbing

•         Searching for a goal state = Climbing to the top of a hill

•         Generate-and-test + direction to move.

•         Heuristic function to estimate how close a given state is to a goal state.

Algorithm:

1. Evaluate the initial state.
2. Loop until a solution is found or there are no new operators left to be applied:

                        - Select and apply a new operator

                        - Evaluate the new state:

                                    goal-> quit

                                    better than current state-> new current state

Steepest-Ascent Hill Climbing (Gradient Search)

•         Considers all the moves from the current state.

•         Selects the best one as the next state.

Algorithm:

1. Evaluate the initial state.
2. Loop until a solution is found or a complete iteration produces no change to current state:

                        - SUCC = a state such that any possible successor of the

                           current state will be better than SUCC (the worst state).

                        - For each operator that applies to the current state, evaluate

                           the new state:

                                    goal-> quit

                                    better than SUCC-> set SUCC to this state

                         - SUCC is better than the current state-> set the current

                            state to SUCC.

Hill Climbing: Disadvantages

Local maximum

A state that is better than all of its neighbors, but not better than some other states far away.

Plateau

It is a flat area of the search space in which all neighboring states have the same value.

Ridge

The orientation of the high region, compared to the set of available moves, makes it impossible to climb up. However, two moves executed serially may increase the height.

Ways Out:

•         Backtrack to some earlier node and try going in a different direction.

•         Make a big jump to try to get in a new section.

•         Moving in several directions at once.

Conclusion

•   Hill climbing is a local method: Decides what to do next by looking only at the “immediate” consequences of its choices.

•         Global information might be encoded in heuristic functions.

•         Can be very inefficient in a large, rough problem space.

•     Global heuristic may have to pay for computational complexity. Often useful when combined with other methods, getting it started right in the right general neighborhood.