Understanding Heuristic Search and Admissible Heuristics in AI

Heuristic search algorithms are a key part of Artificial Intelligence (AI) used to find solutions to problems by exploring a state space. Unlike uninformed search methods that explore systematically without extra knowledge, heuristic search uses a heuristic function, denoted as \(h(n)\), to estimate the cost from a given node \(n\) to the goal node. This estimate guides the search towards promising states, making the search more efficient.

What is an Admissible Heuristic?

A heuristic \(h(n)\) is considered admissible if it never overestimates the true cost to reach the goal from node \(n\). Let \(h^*(n)\) be the actual minimum cost from node \(n\) to the goal. An admissible heuristic satisfies the condition:

\(h(n) \le h^*(n)\) for all nodes \(n\).

Admissibility is a desirable property, especially for algorithms like A* search. If the heuristic used in A* is admissible, A* is guaranteed to find an optimal solution (a solution with the minimum cost) provided the step costs are non-negative.

Combining Multiple Admissible Heuristics

Consider a scenario where we have a collection of \(m\) different admissible heuristics: \(h_1(n), h_2(n), \ldots, h_m(n)\) available for a problem. Each of these individual heuristics \(h_i(n)\) is admissible, meaning \(h_i(n) \le h^*(n)\) for all \(i\) and all nodes \(n\). The question states that none of these heuristics dominates any of the others, meaning for any two heuristics \(h_i\) and \(h_j\), there is at least one node where \(h_i\) is better (closer to \(h^*\)) and another node where \(h_j\) is better.

We need to combine these individual admissible heuristics into a single heuristic function \(h(n)\) that is also admissible and, ideally, as informed as possible (meaning it provides the tightest possible estimate without overestimating).

Analyzing the Options for Combining Heuristics

Let's evaluate the given options for combining the admissible heuristics \(h_1, \ldots, h_m\):

1. \(h(n) = \max\{h_1(n), \ldots, h_m(n)\}\)

   If each \(h_i(n) \le h^*(n)\), then the maximum of these values will also be less than or equal to \(h^*(n)\). Specifically, \(\max\{h_1(n), \ldots, h_m(n)\} \le h^*(n)\) because every element in the set \(\{h_1(n), \ldots, h_m(n)\}\) is less than or equal to \(h^*(n)\). Therefore, the maximum function \(h(n) = \max\{h_1(n), \ldots, h_m(n)\}\) is admissible.

   Furthermore, the maximum function takes the largest value among all \(h_i(n)\) for a given node \(n\). This value is greater than or equal to any individual \(h_i(n)\), providing a more informed estimate (a larger lower bound) towards \(h^*(n)\) while still being admissible. A more informed admissible heuristic generally leads to exploring fewer nodes in algorithms like A*, making the search more efficient.

2. \(h(n) = \min\{h_1(n), \ldots, h_m(n)\}\)

   If each \(h_i(n) \le h^*(n)\), then the minimum of these values will also be less than or equal to \(h^*(n)\). So, \(h(n) = \min\{h_1(n), \ldots, h_m(n)\}\) is also admissible.

   However, the minimum function takes the smallest value among all \(h_i(n)\). This estimate will be less than or equal to any individual \(h_i(n)\), making it less informed than the maximum function. While admissible, a less informed heuristic can result in exploring more nodes compared to using the maximum function.

3. \(h(n) = \text{avg}\{h_1(n), \ldots, h_m(n)\}\)

   The average function is calculated as \(h(n) = \frac{1}{m} \sum_{i=1}^m h_i(n)\). While the average of admissible heuristics might seem reasonable, it is not guaranteed to be admissible. Consider a case with two admissible heuristics, \(h_1\) and \(h_2\), and \(m=2\). If for a node \(n\), \(h_1(n)\) is a good estimate but slightly overestimates \(h^*(n)\) for some reason (this would mean \(h_1\) isn't strictly admissible everywhere), or if step costs are involved in a way not captured by the simple definition, the average could easily exceed \(h^*(n)\) even if individual heuristics are admissible in the strict sense. A common scenario where average fails is when one heuristic is a significant underestimate and another is a significant overestimate (though individual admissibility means none *significantly* overestimates, summing or averaging can accumulate errors or dependencies).

4. \(h(n) = \text{sum}\{h_1(n), \ldots, h_m(n)\}\)

   The sum function is calculated as \(h(n) = \sum_{i=1}^m h_i(n)\). If each \(h_i(n) \ge 0\) (which is typical for heuristic estimates of cost) and each \(h_i(n) \le h^*(n)\), then their sum \(h(n)\) will almost certainly be greater than \(h^*(n)\) unless \(m=1\) or all but one heuristic evaluate to 0 for that node. Therefore, the sum function is not admissible in general.

Conclusion

Given a collection of admissible heuristics \(h_1, \ldots, h_m\), where none dominates the others, we want to choose a combined heuristic that is both admissible and provides the most informed estimate. From the analysis above:

• \(h(n) = \min\{h_1(n), \ldots, h_m(n)\}\) is admissible but less informed.
• \(h(n) = \text{avg}\{h_1(n), \ldots, h_m(n)\}\) is generally not admissible.
• \(h(n) = \text{sum}\{h_1(n), \ldots, h_m(n)\}\) is generally not admissible.
• \(h(n) = \max\{h_1(n), \ldots, h_m(n)\}\) is admissible and provides a more informed estimate than the minimum or average (when average is admissible). By taking the maximum, we are essentially picking the estimate that is 'closest' to the true cost \(h^*(n)\) from the admissible ones available at node \(n\), thus making the heuristic function as informed as possible while retaining admissibility.

Therefore, to maintain admissibility and gain the most informed estimate from a set of non-dominating admissible heuristics, the maximum function should be chosen.

Revision Table: Key Concepts in AI Heuristic Search

Additional Information on AI Heuristic Search Strategies

• Consistent Heuristic: A stronger condition than admissibility. A heuristic \(h(n)\) is consistent if for every node \(n\) and every successor \(n'\) of \(n\) with step cost \(c(n, n')\), we have \(h(n) \le c(n, n') + h(n')\). Consistency implies admissibility.
• A* Search: This algorithm uses \(f(n) = g(n) + h(n)\), where \(g(n)\) is the cost from the start node to node \(n\), and \(h(n)\) is the estimated cost from \(n\) to the goal. A* is optimal if the heuristic \(h(n)\) is admissible. If \(h(n)\) is consistent, A* is also optimally efficient (expands no more nodes than any other optimal search algorithm using the same heuristic).
• Generating Admissible Heuristics: Admissible heuristics can often be derived from relaxed versions of the problem, where some constraints are removed. For example, in pathfinding on a grid, the Manhattan distance or Euclidean distance are admissible heuristics if diagonal moves are restricted or allowed, respectively, and costs are uniform.
• Non-Dominating Heuristics: When multiple admissible heuristics exist and none is strictly better than all others for all states, combining them using the maximum function leverages the strengths of each heuristic at different states, resulting in a stronger overall heuristic.