Informed Search Strategy

Introduction

Beyond the definition of the problem, informed search strategies can also make use of problem-specific knowledge, i.e., some extra information is imparted to the search algorithm, that is why we call it informed search. In this way, these strategies can find solutions more efficiently compared to uninformed strategies.

The general approach we consider is called best-first search, in which a node is selected for expansion based on an evaluation function. In this article, when we talk of informed search, we are talking about best-first search.

Heuristic Function

Informed search is also called heuristic search, since the problem-specific knowledge is generally in the form of heuristic function(denoted h(n)):

h(n) = estimated cost of the cheapest path from the state at node n to a goal state.

Heuristic function is a guess, which can be used to guide the search and cut down the number of node expansions before finding a goal. How much more efficient the search will be in comparison to uninformed search depends on the quality of the heuristic.

A* Search

A widely known informed search algorithm is A* Search, the evaluation function of which is:

f(node) = g(node) + h(node)

- g(node) is the cost of the actions used to reach this node(the actual cost)
- h(node) is a heuristic function(the guess)

A* search visit the node with the smallest f(node) first. For example, suppose we want to find the shortest path from Oradea to Bucharest:

The heuristic function here is the straight line distance from the state of the node to goal:

The process of finding the goal state is as follows:

When using a consistent heuristic, A* is complete and optimal, i.e., guaranteed to find an optimal solution if one exists.

A consistent heuristic is a heuristic that satisfies the following condition:

The consistency(also called monotonicity) is about how to choose h(n). As shown above, we must guarantee that, for every node n, the estimated cost of reaching the goal from n is smaller or equal to the step cost of getting to n'plus the estimated cost of reaching the goal from n'. In our example, as we choose the straight line distance as our h(n), we can guarantee consistency, so that our solution is optimal.