In heuristic search algorithms in Artificial Intelligence (AI), if a…

Short answer: Choose h(n) = max{h1(n), ..., hm(n)}.

Reason: If each heuristic hi is admissible (never overestimates the true cost to a goal), then for every node n the maximum value maxi hi(n) is also never greater than the true cost, so the maximum is admissible. Because the maximum is pointwise at least as large as every individual heuristic, it dominates them and gives a tighter (more informed) admissible estimate. Tight admissible heuristics typically reduce the number of node expansions in informed search algorithms such as A*.

• Max preserves admissibility and dominates each individual heuristic: for all n, max{h1(n),…,hm(n)} ≥ hi(n).

• Minimum and average remain admissible but are typically weaker (they underestimate more) and do not dominate the best heuristic.

• Summing heuristics can lead to overestimation and thus break admissibility unless the heuristics refer to strictly disjoint subproblems; therefore sum is not safe in general.

Note: If all hi are consistent, the maximum is also consistent.