Admissible Heuristic

The defining property of an admissible heuristic is that it never overestimates the true cost to reach the goal from any given state. Formally, for all states n, h(n) ≤ h*(n), where h*(n) is the true optimal cost from n to the goal. This property is critical because it ensures that algorithms like A* can safely prioritize promising paths without missing the optimal solution. If a heuristic overestimates, the algorithm may incorrectly prune the optimal path from consideration.

When used with the A search algorithm*, an admissible heuristic guarantees that the first solution found will be optimal (lowest cost), provided the heuristic is also consistent (monotonic). A* combines the actual cost from the start g(n) with the heuristic estimate h(n) (f(n) = g(n) + h(n)). Admissibility ensures f(n) never exceeds the true cost of the best path through n, allowing A* to systematically expand the most promising node without fear of overlooking a cheaper alternative.

While admissibility is required for optimality, the informativeness of the heuristic determines search efficiency. The most informative admissible heuristic is the exact optimal cost h*(n) itself. Common admissible heuristics are often simpler, less informed approximations:

• Zero Heuristic (h(n) = 0): Trivially admissible but uninformed, reducing A* to uniform-cost search.
• Manhattan Distance (for grid navigation): Admissible when movement cost is 1 per orthogonal step and no obstacles.
• Straight-Line Distance (Euclidean): Admissible for navigation when the cost is at least as great as the direct distance. The goal is to design a heuristic that is as close to h*(n) as possible without ever exceeding it.

A powerful method for creating admissible heuristics is to solve a relaxed version of the original planning problem, where some constraints or action costs are removed or reduced. The optimal cost of the relaxed problem is an admissible heuristic for the original, harder problem. Examples include:

• Ignore Delete Lists: A classic relaxation where actions only add facts, never delete them (used in the FF planner's heuristic).
• Ignore Preconditions: Making all actions always applicable.
• Decompose into Subproblems: Solve independent parts of the problem and sum the costs, which remains admissible if subproblems don't interact negatively.

Consistency is a stronger property than admissibility that is often required for efficient implementation. A heuristic is consistent if for every state n and its successor n' generated by action a with cost c(n, a, n'), the triangle inequality holds: h(n) ≤ c(n, a, n') + h(n'). This implies the heuristic is monotonic non-decreasing along any path. All consistent heuristics are admissible, but not all admissible heuristics are consistent. Consistency guarantees that A* will find a node's optimal path the first time it is expanded, allowing the use of a closed list without re-opening nodes.

Heuristics can be compared via dominance. If h2(n) ≥ h1(n) for all states n and both are admissible, then h2 dominates h1 and is more informed, leading to a more efficient A* search. A common technique to generate strong admissible heuristics is abstraction or pattern databases. This involves mapping the original state space to a smaller, abstract space, solving the abstract problem optimally, and using that cost as the heuristic for the concrete state. Since abstraction can only make the problem easier (or equal), the derived heuristic is guaranteed to be admissible.

A heuristic function, denoted h(n), is an estimate of the cost from a given state (n) to the goal state. It is the core mechanism for guiding search algorithms away from unpromising paths and toward solutions. In planning, common heuristics include:

• Relaxed Plan Heuristics: Estimate cost by solving a simplified version of the problem (e.g., ignoring delete effects).
• Landmark Heuristics: Use propositions that must be true at some point in every valid plan.
• Pattern Database Heuristics: Precompute exact costs for abstract subproblems and use them as estimates for the full problem. The accuracy of the heuristic directly impacts search efficiency; a perfect heuristic (h*(n)) would lead directly to the goal.

A search* is a best-first graph search algorithm that finds a least-cost path from a start node to a goal node. It combines two cost functions:

• g(n): The exact cost incurred from the start node to the current node n.
• h(n): The heuristic estimate of the cost from n to the goal. The algorithm expands nodes with the lowest f(n) = g(n) + h(n). The admissibility of h(n) is the critical property that guarantees A* will return an optimal solution if one exists. If h(n) is also consistent (monotonic), A* is optimally efficient.

A heuristic is consistent (or monotonic) if for every node n and every successor n' generated by action a with cost c(n, a, n'), the estimated cost of reaching the goal from n is no greater than the step cost plus the estimated cost from n': h(n) ≤ c(n, a, n') + h(n'). This is a stricter condition than admissibility. All consistent heuristics are admissible, but not all admissible heuristics are consistent. Consistency ensures that the f(n) value never decreases along any path from the root, which allows A* to efficiently find an optimal path without re-expanding nodes.

In automated planning and search, optimality refers to a solution plan (sequence of actions) that achieves the goal with the minimum possible total cost, as defined by the problem's cost function. An algorithm is optimal if it is guaranteed to find an optimal solution when one exists. The admissible heuristic is the key that unlocks optimality for informed search algorithms like A*. Without admissibility, algorithms like Greedy Best-First Search may find a solution faster but cannot guarantee it is the cheapest one.

A relaxed problem is a simplified version of the original planning problem created by removing constraints (e.g., ignoring the delete lists of actions). The cost of an optimal solution to the relaxed problem provides an admissible heuristic for the original problem—it never overestimates because the original problem has stricter constraints. This is the foundation for powerful heuristics like the h_add and h_ff heuristics used in the Fast Forward (FF) planner. Designing effective relaxations is a central technique for creating domain-independent admissible heuristics.

Given two admissible heuristics, h1 and h2, h1 dominates h2 if for all states n, h1(n) ≥ h2(n). A dominating heuristic provides a tighter (higher) estimate of the true cost to the goal, which is always better for A* search. A* using h1 will never expand more nodes than A* using h2, and typically expands fewer. The maximum of multiple admissible heuristics is also admissible and dominates each individual heuristic. This principle is used to combine simpler heuristics into a more powerful, informed guiding function.