Consistent Heuristic

In artificial intelligence, particularly in the context of path-finding and search algorithms, a consistent heuristic, also known as a monotonic heuristic, is a function used to estimate the lowest cost of reaching a goal from a given node. The consistency condition ensures that the estimated cost to reach the goal from the current node is always less than or equal to the actual cost of moving to a neighbor node plus the estimated cost from that neighbor to the goal.

This property guarantees that the heuristic is not overoptimistic about the cost of reaching the goal, which is crucial for the efficiency and accuracy of search algorithms like A*. A consistent heuristic ensures the optimality of the solution found by such algorithms and often leads to more efficient searches, as it prevents the algorithm from unnecessarily expanding paths that are already more expensive than the best solution found so far.

‍

Consider a navigation system that uses a map with cities as nodes and roads as edges. A consistent heuristic for finding the shortest path from one city to another might use the straight-line distance (as the crow flies) between cities as the heuristic estimate.

Since the actual road distance between two cities cannot be less than the straight-line distance (ignoring the possibility of tunnels or similar shortcuts), this heuristic is consistent. It ensures that the search algorithm, like A*, can efficiently find the shortest road path between the two cities without exploring unnecessary routes.

‍