CODEWITHSUNDEEP
artificial-intelligenceheuristics
Algo
Algo

Reputation: 91

Admissible heuristic function

I know that an admissible heuristic function underestimates the actual cost to a goal, but I want to conclude that a heuristic function h3 which is sum of two admissible heuristic functions(h1 and h2) can both be admissible and not if no further information on h1 and h2 is given. Do you think that is the right claim?

Thanks

Upvotes: 2

Views: 15093

Answers (2)

Prof.Chaos
Prof.Chaos

Reputation: 1045

I think the original question was not yet answered - also not in the comments of the previous answer.

If h1 and h2 are admissible, then h3 = h1 + h2 is in general NOT admissible although this could happen in special cases (i.e., the null heuristic is admissible and it can be added to another heuristic arbitrary many times without violating admissibility). This is very easy to see. Imagine a problem where all states are either goal states or they can be turned into a goal state with just one single action of cost 1. Thus, any heuristic that returns 0 for a goal state and 1 for a non-goal state is admissible. Let s be a non-goal state. Then, h1(s)=h2(s)=1 are both admissible, but h3(s)=2 is not.

Of course, taking the maximum of admissible heuristics is again admissible (this is also very easy to see), so h3 = max(h1,h2) would dominate h1 and h2 (i.e., it is at least as good as either of them) and still be admissible.

There are more elaborate ways than just taking the maximun of a set of admissible heuristics to combine them to a more accurate one. The most prominent technique that I am aware of is called cost partitioning: When ensuring that no action can contribute costs to both h1 and h2, it is safe to add their values. The basic idea to exploit this is (I think, check it yourself!) by creating n problem instances of the original problem (when aiming at n heuristics) and ensure that whenever an action has its original cost m in the problem number i (that is used for heuristic number i), then that very action has cost 0 in all other n-1 problems. That way, all problems/heuristics still have all actions available while summing their value is guaranteed to be non-overestimating, i.e. admimissible (given that all n heuristics are admissible as well). I think the article "Optimal admissible composition of abstraction heuristics" (http://www.sciencedirect.com/science/article/pii/S0004370210000652) explains that idea in detail.

Upvotes: 5

Johnny HD
Johnny HD

Reputation: 51

An admissible heuristic is one that never overestimates the cost of the minimum cost path from a node to the goal node. So, a heuristic is specific to a particular state space, and also to a particular goal state in that state space. It must be admissible for all states in that search space. To help remember whether it is “never overestimates” or “never underestimates”, just remember that an admissible heuristic is too optimistic. It will lead A* to search paths that turn out to be more costly that the optimal path. It will not prevent A* from expanding a node that is on the optimal path by producing a heuristic h value that is too high. A stronger requirement on a heuristic is that it is consistent, sometimes called monotonic. A heuristic h is consistent if its value is nondecreasing along a path. Mathematically, a heuristic h is consistent if for every node n of a parent node p,

Upvotes: 5

Related Questions