Heuristic Function in AI

Heuristic function refers to a mathematical function used in estimating the cost of getting to a goal state starting from a particular state in a search problem. In artificial intelligence, the system uses the estimation denoted by h(n) when making a decision on which path should be searched as opposed to checking all paths.

The exhaustive search algorithm tries out every state in a problem before giving a solution. It can be applied in solving small problems, but in many cases, the number of states exceeds what can practically be solved using exhaustive search. The examples include route search, puzzles, and games. The heuristic function eliminates the process of exhaustive checking with an estimate.

This article gives a detailed explanation of heuristic functions, differences between heuristic and cost function, reliability of a heuristic function, and different ways in which the heuristic search algorithms apply the heuristic function.

What Is a Heuristic Function?

A heuristic function, written as h(n), estimates the remaining cost from a state n to the goal state, without calculating the exact cost. 

The function accepts the state as an argument and produces an integer as output. The output number gives an indication of how far away the algorithm thinks the state is from being the goal state. If the h(n) value is low, then the algorithm thinks the state is near the goal. A search algorithm uses the output of this function to decide on which state to look at next.

Heuristic functions do not necessarily give an exact solution. Rather, they give us an estimate that is based on our understanding of the problem domain. For instance, in a road navigation problem, the straight-line distance between two points is an example of a heuristic function since it estimates the distance while ignoring roads, traffic, and turns.

Peter Hart, Nils Nilsson, and Bertram Raphael gave an official name to the process of using heuristic functions in search algorithms in their paper entitled “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” It was published in the IEEE Transactions on Systems Science and Cybernetics in 1968. The paper introduced the A* algorithm and described conditions for a heuristic function to produce an optimal solution.

Heuristic Function vs. Cost Function: What Is the Difference?

While the cost function gives the cost incurred up to the current state, the heuristic function provides an estimate of the cost still left to reach the goal. Both values are used in search algorithms to evaluate a state.

Symbol	Name	What It Measures	Known or Estimated?
g(n)	Cost function	Actual cost from the start state to state n	Known
h(n)	Heuristic function	Estimated cost from state n to the goal state	Estimated
f(n)	Evaluation function	Total estimated cost of a solution path through n	Combination of both

The following equation gives the relation between the three: f(n)=g(n)+h(n). The A* algorithm applies the above equation directly, but the Greedy Best-First Search uses just h(n).

How Heuristic Functions Guide Search Algorithms

Search algorithms that use a heuristic function are called informed search algorithms. Three informed search algorithms use heuristic functions in different ways: A*, Greedy Best-First Search, and Hill-Climbing.

Algorithm	Uses g(n)	Uses h(n)	Guarantees Optimal Path	Typical Speed
A*	Yes	Yes	Yes, if h(n) is admissible	Moderate
Greedy Best-First Search	No	Yes	No	Fast
Hill-Climbing	No (compares neighbors only)	Yes	No	Fastest, but can stop at a local optimum

A* Algorithm

The A algorithm selects the next state to explore based on f(n) = g(n) + h(n), which combines the known cost so far with the estimated cost remaining.* 

In A*, both g(n), the cost from the beginning to the state, and h(n), the estimated cost from the state to the goal, are maintained for each state examined by the algorithm. The algorithm combines these two values to form f(n), and expands the node with the least value of f(n).

If the heuristic function used in A* is admissible, A* will give us the optimum path; otherwise, A* might choose a path that is cheaper than the optimum path.

Greedy Best-First Search

The Greedy Best First Search will use the heuristic value h(n) alone for selecting the next state, completely ignoring the cost incurred up until now.

The Greedy Best First Search algorithm chooses the next state with the least heuristic value. It completely neglects g(n), which results in it being faster than the A* search because there is less computation involved per node. It may not find the optimal solution because of the tendency to choose a path with a better heuristic value while disregarding its cumulative cost.

The Greedy Best First Search works well when speed is a priority over optimality, such as in the case of approximate route calculations.

Hill-Climbing Algorithm

Hill Climbing starts by moving to the neighboring state with the smallest heuristics from the current state until it encounters the point from which no neighbor is better than itself.

Unlike A* and Greedy Best First Search algorithms, Hill Climbing doesn’t have any list of visited nodes because it simply takes the current state into account along with the neighboring state. This makes the memory requirement less than that of A* and Greedy Best-First Search algorithms.

There is one major drawback associated with this algorithm – the possibility of getting stuck in a local optimal point – a point from which no other neighboring node will be better according to the heuristics.

Admissibility and Consistency: What Makes a Heuristic Function Reliable

Two properties determine whether a heuristic function produces a reliable result: admissibility and consistency. A search algorithm that requires an optimal solution depends on both properties.

Admissible Heuristic Functions

A heuristic function is said to be admissible when its estimation is always lesser than or equal to the actual cost to reach the goal from that state. Mathematically, h(n) <= true cost of reaching from n to the goal for all states n.

The example below illustrates the admissible heuristic function estimation in a grid based path finding task. In this task a searching agent positioned at (2, 3) needs to reach a goal located at (5, 7). The searching agent can travel in four different ways which include moving upwards, downwards, to the right, and to the left with a cost of 1 for every move.

Manhattan distance heuristic estimation works as below:

If the minimum cost required to move from (2, 3) to (5, 7) is 7, then the admissible heuristic value obtained above perfectly matches the true cost. If there exist some obstacles in between (2, 3) and (5, 7) such that the searching agent takes 9 steps to reach the destination, then still the admissible heuristic value 7 satisfies the condition of admissibility, since the value did not overestimate the actual cost.

Consistent (Monotonic) Heuristic Functions

Heuristic functions are said to be consistent if the cost estimate for going from one state to another state will not exceed the cost estimate of reaching the goal state from that state.

Mathematically, the above statement can be shown by writing h(n) ≤ cost(n, n′) + h(n′), where n′ is the neighboring state. It means that consistency ensures that the estimated cost does not increase as the algorithm approaches the goal state. Consistent heuristics are always admissible heuristics, although not vice versa.

Inadmissible and Weighted Heuristic Functions

Heuristics which are not admissible tend to overestimate the true cost for at least one node, thereby making the search algorithm choose a longer route than what it perceives to be the shorter one.

A few search algorithms may utilize inadmissible heuristics, and this is done via a process known as weighted A*. In this process, the h(n) function is multiplied by a factor that exceeds one, thereby giving more weight to the h(n) part as compared to g(n). As a result, the process of expansion in Weighted A* is reduced as compared to A*, thereby decreasing computing time; however, it is no longer guaranteed to find the shortest path.

Common Heuristic Functions, Compared

There are different heuristic functions which have been named and are applicable for certain types of movements or states. The table below is an example comparison of four different heuristics in terms of a particular state (2, 3) and a goal state (5, 7).

Heuristic Function	Formula	Calculated Value for This Example	Best Used For
Manhattan Distance	|x₁−x₂| + |y₁−y₂|	|5−2| + |7−3| = 7	Grids with 4-direction movement (up, down, left, right)
Euclidean Distance	√((x₁−x₂)² + (y₁−y₂)²)	√(3² + 4²) = 5	Continuous space with movement in any direction
Chebyshev Distance	max(|x₁−x₂|, |y₁−y₂|)	max(3, 4) = 4	Grids with 8-direction movement, including diagonals, at equal cost
Octile Distance	max(dx, dy) + (√2 − 1) × min(dx, dy)	4 + (0.41 × 3) ≈ 5.24	Grids with 8-direction movement, where diagonal moves cost more than straight moves

The heuristic function itself influences the efficiency and effectiveness of the algorithm. The use of the heuristic function which is closer to the actual cost, but doesn’t exceed it, leads to the smaller number of states expansion and thus results in faster search.

Common Problems Heuristic Functions Solve

Heuristic functions are used to solve various kinds of search problems, namely path-finding, constraint satisfaction, optimization, and game-playing.

• Path-finding problems. Path-finding problems involve the process of finding the way from one point to another point. These problems may include maze navigation, routing by means of GPS, and robot movement planning.
• Constraint satisfaction problems. Constraint satisfaction problems involve assigning values to certain variables according to the set of rules. These problems include Sudoku, exam scheduling, and assignment of resources to a given number of people.
• Optimization problems. Optimization problems involve the search for the optimal solution. These problems include Traveling Salesman Problem, delivery routing problem, and portfolio selection with a given budget.
• Game-playing problems. Game-playing problems include the selection of the strongest move among all others. These problems include moves’ evaluation in chess, checkers, and Go.

Real-World Applications of Heuristic Functions

The following are the four major areas in which heuristics can be applied to artificial intelligence: navigation systems, game playing systems, robotics and natural language processing.

1. In GPS navigation systems, heuristic functions like the straight-line distance are used to estimate the travel time from the present location to the destination prior to computing the total route. Through estimation, the GPS system will be able to evaluate only those road segments that can take it close to the destination rather than evaluate all the roads.
2. In game playing systems, heuristic functions are used to determine the scores for different board configurations in games such as chess and Go. The heuristic function in chess can consider factors such as pieces count, control of the board and safety of the king among others, and give an overall numerical value for the same.
3. Robotics uses heuristic functions in order to plan the paths for physical robots. In the case of a robot traversing the warehouse, the heuristic function computes the distance to the shelf and avoids any obstacle detected by sensors.
4. Natural language processing uses heuristic functions while performing tasks such as machine translation and text summarization when the evaluation of all the possible output is computationally infeasible. The heuristic function ranks candidate outputs by estimated quality, allowing the system to select a strong result without generating every possible option.

Frequently Asked Questions

Key Takeaways

• The heuristic function gives an estimation of the cost to the goal state that will be left, h(n). Heuristic functions in search algorithms guide on which nodes need to be examined.
• A* combines the g(n) and h(n) functions to ensure an optimal path if the heuristic function is admissible; Greedy Best-First Search and Hill-Climbing use h(n) only and don’t ensure an optimal path.
• Admissibility means that the heuristic function should not overestimate the actual cost left to the goal node, while consistency is even stronger in that it does not allow faster estimations of costs than actual steps.
• The named heuristic functions such as Manhattan distance, Euclidean distance, Chebyshev distance, and octile distance are applied in different movement rules in the search problem.
• Heuristic functions solve pathfinding, constraint satisfaction, optimization, and game-playing problems and are used in navigation systems, game-playing systems, robotics, and natural language processing.