Posts Tagged ‘heuristic search techniques’

PostHeaderIcon Heuristic Evaluation Function

Heuristic evaluation function estimates the cost of an optimal path between a pair of states in a single-agent path-finding problem. For example, Euclidean or airline distance is an estimate of the highway distance between a pair of locations.

Manhattan Distance

Manhattan distance is a common heuristic function for the sliding-tile puzzles. Manhattan distance is computed by counting the number of moves along the grid that each tile is displaced from its goal position, and summing these values over all faces. For a fixed goal state, a heuristic evaluation is a function of a node, say h(n), that estimates the distance from node, say n to the given state.

Key Properties of a Heuristic Evaluation Function

The key properties of a heuristic evaluation function are that it estimates actual cost, and that it be inexpensive to compute. For example, the Euclidean distance between a pair of points can be computed in constant time. The Manhattan distance between a pair of states can be computed in time proportional to the number of tiles. In addition, most heuristic functions are derived from relaxations of the original problem, and hence are lower bounds on actual cost, a property referred to as admissibility. For example, airline distance is a lower bound on road distance between two points, since the shortest path between a pair of points is a straight line. Similarly, Manhattan distance is a lower bound on the actual number of moves necessary to solve an instance of a sliding tile puzzle, since every tile must move at least as many times as its distance in grid units from its goal position.

Applications of Heuristic Evaluation Functions

A number of algorithms make use of heuristic functions, including pure heuristic search, the A* algorithm, depth-first branch-and-bound, and the heuristic path algorithm. In addition, heuristic information can be employed in bidirectional search as well.

PostHeaderIcon Heuristic Search

What is Heuristic Search?

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.

Heuristic Information

In order to solve larger problems, domain-specific knowledge must be added to improve search efficiency. Information about the problem include the nature of states, cost of transforming from one state to another, and characteristics of the goals. This information can often be expressed in the form of heuristic evaluation function, say f(n,g), a function of the nodes n and/or the goals g.

Following is a list of heuristic search techniques.

Pure Heuristic Search

A* algorithm

Iterative-Deepening A*

Depth-First Branch-And-Bound

Heuristic Path Algorithm

Recursive Best-First Search

Complexity Of Finding Optimal Solutions

The time complexity of a heuristic search algorithm depends on the accuracy of the heuristic function. For example, if the heuristic evaluation function is an exact estimator, then A* search algorithm runs in linear time, expanding only those nodes on an optimal solution path. Conversely, with a heuristic that returns zero everywhere, A* algorithm becomes uniform-cost search, which has exponential complexity.

In general, the time complexity of A* search and IDA* search is an exponential function of the error in the heuristic function. For example, if the heuristic has constant absolute error, meaning that it never underestimates by more than a constant amount regardless of the magnitude of the estimate, then the running time of A* is linear with respect to the solution cost. A more realistic assumption is constant relative error, which means that the error is a fixed percentage of the quantity being estimated. The base of the exponent, however, is smaller than the brute-force branching factor, reducing the asymptotic complexity and allowing larger problems to be solved. For example, using appropriate heuristic functions, IDA* can optimally solve random instance of the twenty-four puzzle and Rubik’s Cube.

For further study

Incremental Heuristic Search

Related Articles

Brute Force Search
Two-Player Games Search
Interleaving Search
AI Search Techniques