Heuristic Function

An admissible heuristic never overestimates the true cost to reach the goal from any given node. Formally, for all nodes n, h(n) ≤ h*(n), where h*(n) is the true optimal cost to the goal. This is the critical property guaranteeing that the A* search algorithm will return an optimal solution. A common example is using the straight-line Euclidean distance as a heuristic for pathfinding on a map, as it is always less than or equal to the actual road distance.

A consistent heuristic satisfies the triangle inequality. For every node n and its successor n' generated by action a with cost c(n, a, n'), the heuristic must obey: h(n) ≤ c(n, a, n') + h(n'). This implies that the estimated cost to the goal from n is no greater than the step cost to its successor plus the estimated cost from there. Consistency is a stronger condition than admissibility; all consistent heuristics are admissible, but not all admissible heuristics are consistent. Consistency guarantees that A* finds the optimal path without needing to re-expand nodes.

Given two admissible heuristics h1 and h2, h2 dominates h1 if for all nodes n, h2(n) ≥ h1(n). A dominating heuristic provides a tighter, more accurate estimate of the true cost. For A* search, a dominating heuristic will typically expand fewer nodes, making the search more efficient, while still guaranteeing optimality. For example, in the 8-puzzle, the Manhattan distance heuristic dominates the misplaced tiles heuristic, as it always provides a higher (and thus more informative) estimate.

Informedness refers to the accuracy of a heuristic's estimate. A more informed heuristic is closer to the true cost h*(n) on average. While admissibility ensures optimality, informedness drives efficiency. The most informed admissible heuristic would be h*(n) itself, which would lead the search directly to the goal. In practice, designers balance the computational cost of calculating a highly informed heuristic against the search time it saves. Techniques for creating informed heuristics include:

• Relaxing problem constraints (e.g., allowing tiles to move through each other).
• Using pattern databases that store exact costs for subproblems.
• Learning heuristics from experience or data.

The computational overhead of evaluating the heuristic function h(n) must be significantly less than the cost of expanding the node. A perfect but computationally expensive heuristic can be counterproductive, as the time spent calculating it for every node may outweigh the search space reduction it provides. Effective heuristic design involves a trade-off: a slightly less informed heuristic that is extremely fast to compute (e.g., a simple lookup or linear calculation) is often preferable to a highly informed one that requires solving a complex sub-problem. This property is crucial for real-time applications like game AI or robotics.

A heuristic is inherently tied to the domain knowledge of the specific problem being solved. Unlike general-purpose search algorithms, the heuristic function encodes an understanding of the problem's structure to guide the search intelligently. For example:

• Pathfinding/Navigation: Euclidean or Manhattan distance to target.
• Puzzle Solving (8-puzzle): Manhattan distance of tiles or linear conflict count.
• Theorem Proving: Number of unmatched premises or depth of the proof tree.
• Machine Learning (for model selection): Akaike Information Criterion (AIC) or Bayesian Information Criterion (BIC) as heuristics for model quality. This property means that designing an effective heuristic requires deep insight into the state space and goal of the application.

An admissible heuristic is one that never overestimates the true cost to reach the goal from any given node. This property is critical for guaranteeing the optimality of algorithms like A* Search.

• Key Property: For all nodes n, h(n) ≤ h*(n), where h*(n) is the true optimal cost to the goal.
• Guarantee: If a heuristic is admissible, A* Search is guaranteed to find the least-cost path.
• Example: In a grid-based pathfinding problem, the straight-line Euclidean distance to the goal is admissible if movement cost is distance, as it's the shortest possible path (a straight line).

A consistent heuristic satisfies the triangle inequality property: the estimated cost from a node to the goal is no greater than the step cost to a successor plus the estimated cost from that successor to the goal. Formally, for every node n and its successor n' generated by action a with cost c(n, a, n'), the heuristic must satisfy: h(n) ≤ c(n, a, n') + h(n').

• Implication: Consistency implies admissibility (for finite graphs).
• Benefit: Ensures A* Search finds the optimal path without needing to re-expand nodes, making it more efficient.
• Practical Use: Most well-designed heuristics for pathfinding, like Manhattan distance on a grid with unit-cost moves, are consistent.

An evaluation function, often denoted f(n), is the total function used by a search algorithm to assign a priority or value to a node n. It typically combines the cost incurred so far with a heuristic estimate of the remaining cost.

• Classic Form: In A* Search, f(n) = g(n) + h(n), where g(n) is the actual cost from the start to node n, and h(n) is the heuristic estimate from n to the goal.
• Role: This function determines the order in which nodes are expanded from the frontier.
• Variants: Different algorithms use different evaluation functions. Greedy Best-First Search uses f(n) = h(n), while Uniform-Cost Search uses f(n) = g(n).

Search algorithms are categorized by their use of problem-specific knowledge.

• Informed (Heuristic) Search: Uses a heuristic function h(n) to estimate proximity to the goal. This guides the search intelligently, making it far more efficient in large state spaces. Examples: A* Search, Greedy Best-First Search.
• Uninformed (Blind) Search: Uses no domain knowledge beyond the problem definition (successor function, start state, goal test). It explores systematically but often inefficiently. Examples: Breadth-First Search, Depth-First Search, Uniform-Cost Search.
• Trade-off: The power of a heuristic function is measured by its ability to reduce the effective branching factor of the search, transforming an intractable problem into a solvable one.

A relaxed problem is a simplified version of the original search problem, created by removing one or more constraints. The optimal solution cost to a relaxed problem provides an admissible heuristic for the original, more complex problem.

• Methodology: This is a systematic way to derive heuristics. For example, in the 8-puzzle, a relaxed problem might allow tiles to move anywhere (ignoring other tiles), yielding the Manhattan distance heuristic.
• Optimality: The cost of the optimal solution to the relaxed problem is guaranteed to be less than or equal to the cost of the optimal solution to the original problem, ensuring admissibility.
• Automated Generation: This principle can be automated to create heuristics from a formal problem description, a key technique in classical AI planning.

Given two admissible heuristics h1 and h2, h2 dominates h1 if, for all nodes n, h2(n) ≥ h1(n). A dominating heuristic provides a tighter (higher) estimate of the true cost without overestimating.

• Consequence: A* Search using a dominating heuristic (h2) will expand no more nodes than when using the dominated heuristic (h1), and often far fewer, because its f(n) values are more accurate, focusing the search more sharply.
• Example: For the 8-puzzle, the Manhattan distance heuristic dominates the number of misplaced tiles heuristic.
• Goal: The ideal is to use the most accurate (highest-valued) admissible heuristic available, as it yields the most efficient search.