When is a heuristic admissible but not consistent?

Admissible but Not Consistent: Understanding Heuristics in A* Search

Explore the nuanced relationship between admissibility and consistency in heuristic functions for A* search, and discover scenarios where a heuristic can be admissible but fail the stricter consistency test.

In the realm of artificial intelligence and pathfinding algorithms, heuristic functions play a crucial role in guiding search processes like A*. A well-designed heuristic can dramatically improve the efficiency of finding optimal paths. Two key properties define the quality of a heuristic: admissibility and consistency. While consistency implies admissibility, the reverse is not always true. This article delves into the conditions under which a heuristic can be admissible yet not consistent, providing practical examples and clarifying their implications for search algorithms.

Defining Admissibility and Consistency

Before we examine the differences, let's establish a clear understanding of each property:

• Admissibility: A heuristic function h(n) is admissible if, for every node n, the estimated cost to reach the goal from n is never greater than the true cost to reach the goal from n. Mathematically, h(n) <= h*(n), where h*(n) is the true cost from n to the goal. An admissible heuristic guarantees that A* search will find an optimal path.

• Consistency (or Monotonicity): A heuristic function h(n) is consistent if, for every node n and every successor n' of n, the estimated cost to reach the goal from n is no more than the cost of moving from n to n' plus the estimated cost to reach the goal from n'. Mathematically, h(n) <= c(n, n') + h(n'), where c(n, n') is the cost of the edge from n to n'. Consistency is a stricter condition than admissibility.

flowchart TD
    A[Heuristic Function h(n)]
    B{Is h(n) <= h*(n)?}
    C[Admissible]
    D{Is h(n) <= c(n, n') + h(n')?}
    E[Consistent]
    A --> B
    B -- Yes --> C
    B -- No --> F[Not Admissible]
    C --> D
    D -- Yes --> E
    D -- No --> G[Admissible but Not Consistent]
    E --> C

Relationship between Admissibility and Consistency

When Admissibility Doesn't Imply Consistency

The key to understanding a heuristic that is admissible but not consistent lies in the local property of consistency versus the global property of admissibility. Consistency requires that the heuristic estimate doesn't drop too sharply from a node to its successor, relative to the actual edge cost. Admissibility, on the other hand, only cares that the estimate is never an overestimate of the true cost to the goal.

Consider a scenario where the heuristic value for a node n is very low, but for one of its successors n', the heuristic value is significantly higher, and the edge cost c(n, n') is small. If h(n) > c(n, n') + h(n'), then the heuristic is not consistent. However, both h(n) and h(n') could still be less than or equal to their respective true costs to the goal (h*(n) and h*(n')), thus maintaining admissibility.

A Concrete Example: The Modified Manhattan Distance

Let's illustrate this with a grid-based pathfinding problem, similar to the 8-puzzle or a simple maze. We want to find the shortest path from a start node to a goal node.

Standard Manhattan Distance: This is a common admissible and consistent heuristic for grid maps where movement is restricted to horizontal and vertical directions. h(n) = |n.x - goal.x| + |n.y - goal.y|.

Modified Manhattan Distance (Inconsistent Version): Imagine we have a special 'fast lane' or 'teleport' tile on our grid. If a node n is on this fast lane, we might want to give it a very low heuristic value, reflecting its perceived proximity to the goal. However, if its successor n' is not on the fast lane, and the cost c(n, n') is 1, we could create an inconsistency.

Let's define a heuristic h(n):

• If n is the goal, h(n) = 0.
• If n is on a 'fast lane' tile, h(n) = 1.
• Otherwise, h(n) = ManhattanDistance(n, goal).

Assume the true cost h*(n) for a fast lane tile is indeed 1 (meaning the goal is just one step away via the fast lane). So, h(n) = 1 <= h*(n) = 1, making it admissible.

Now, consider a node n on the fast lane, and its successor n' is an adjacent tile not on the fast lane. The edge cost c(n, n') = 1. Let's say n' is 5 steps away from the goal via Manhattan distance, so h(n') = 5. The consistency check is:

h(n) <= c(n, n') + h(n') 1 <= 1 + 5 1 <= 6 (This holds, so it's consistent in this specific case)

However, what if the 'fast lane' heuristic is too optimistic for n? Suppose n is on the fast lane, but the true cost h*(n) is 3 (it's not that fast). We set h(n) = 1. This is still admissible because 1 <= 3. Now, let n' be a neighbor of n with c(n, n') = 1, and h(n') = 5. The true cost h*(n') is 4. So h(n') = 5 is not admissible here. This example shows how careful one must be.

Let's refine the example to ensure admissibility while breaking consistency:

Consider a graph where S is the start, G is the goal. Edges have cost 1.

• h(S) = 10 (True cost h*(S) = 10)
• h(A) = 1 (True cost h*(A) = 1)
• h(B) = 2 (True cost h*(B) = 2)
• h(G) = 0

Path: S -> A -> B -> G

Edge costs:

• c(S, A) = 1
• c(A, B) = 1
• c(B, G) = 1

All h(n) <= h*(n) are satisfied, so the heuristic is admissible.

Now check consistency for S -> A: h(S) <= c(S, A) + h(A) 10 <= 1 + 1 10 <= 2 (FALSE!)

Here, h(S) is admissible, but the heuristic is not consistent because the estimate drops too sharply from S to A relative to the edge cost. This can happen if h(n) is based on some global property that doesn't smoothly transition between adjacent nodes.

graph TD
    S[Start (h=10, h*=10)] -->|c=1| A[Node A (h=1, h*=1)]
    A -->|c=1| B[Node B (h=2, h*=2)]
    B -->|c=1| G[Goal (h=0, h*=0)]

Example Graph with Admissible but Inconsistent Heuristic

Implications for A* Search

The primary consequence of using an admissible but inconsistent heuristic in A* search is that the algorithm loses its guarantee of processing each node at most once. With a consistent heuristic, the g(n) value (cost from start to n) for any node n is finalized the first time it's expanded from the open list. This is because f(n) = g(n) + h(n) is non-decreasing along any path.

When the heuristic is inconsistent, f(n) can decrease along a path. This means A* might find a path to a node n, expand it, and later discover a cheaper path to n through a different route. In such cases, n would need to be re-added to the open list and re-expanded, leading to redundant work. While optimality is preserved (due to admissibility), efficiency can suffer significantly.

In summary, while admissibility is crucial for guaranteeing optimal solutions with A*, consistency offers additional benefits in terms of efficiency by preventing nodes from being re-expanded. Understanding the distinction helps in designing robust and efficient search algorithms for various AI problems.