CODEWITHSUNDEEP
artificial-intelligenceshortest-patha-star
LearningMath
LearningMath

Reputation: 861

A* with reopening when heuristics is only admissible but not consistent

The A* pseudocode I follow is given here: enter image description here

My question is: How are we sure that we can return when a goal state is found? As it is with all other CLOSED states, they could be reopened from new OPEN states. So, if I have a state that I got from OPEN and I see that I can take a better path to the CLOSED goal from that state, then I should update its value at least. Shouldn't we wait till all the states are closed?

Upvotes: 3

Views: 1528

Answers (3)

Kevin Chou
Kevin Chou

Reputation: 577

After reading dennis' answer, I would like to make a brief addition from my own understanding.

Let's imagine that there is another node in open_list, f(another) >= f(n). because f(n)=g(n)+h(n), n is goal node, so h(n) = 0, then f(another) >= g(n);

Then, let's recall admissible heuristic principle as below:

Heuristics are still admissible, meaning that the heuristic cost h(n) of a node n must always be less than or equal to the true (unknown) remaining cost h*(n): h(n) <= h*(n) for all n

Next, Let's imagine that there is path connecting anothernode and goal n' node, then f(another->n') = g(another->n') + h(n'), and h(n') = 0, so f(another->n') = g(another->n'). No doubt g(another->n') > g(another), because of positive path cost.

so we have:

condition:
1. g(another) + h(another) = f(another) >= f(n) = g(n);
2. f(another->n') = g(another->n') > g(another)
*important:  [admissible]
3. h(another) <= h*(another) = g(another->n') - g(another)

=>

conlusion:
f(another->n') >= f(another) >= f(n)

Therefore, the node n have already the min f. In fact, my above derivation is proof that admissible heuristic guarantees optimal. more info ref to: Admissible heuristic - Wikipedia

I hope I've made the issue clear for you.

Upvotes: 1

Kevin Chou
Kevin Chou

Reputation: 577

This question is a good one. I meet the same question. thanks to @LearningMath The received answers is almost right, thanks to @Dennis Soemers. But I find some mistakes from Dennis Soemers's comments , it troubles me for a long time.

If h is consistent you can 1) remove the first part inside the for-loop where you see if you've just found a more efficient path to a node that was already closed (you can just continue the for-loop instead if the new node already turns out to be in CLOSED), and 2) in all the lines that say put something on OPEN, you can first check if that something is the goal, and immediately return the path if it indeed turns out to be the goal, instead of first pushing it to OPEN and then continuing till it gets popped again.

The first part is true, but the second part is false; I won't prove this theoretically and completely, just show you a counterexample from CS 188 lecture pdf . In the other hand, if you search standard A* pesudo code from here, you'll find that goal_check execuate after be enqueued.

Upvotes: 1

Dennis Soemers
Dennis Soemers

Reputation: 8518

This works because:

  • Heuristics are still admissible, meaning that the heuristic cost h(n) of a node n must always be less than or equal to the true (unknown) remaining cost h*(n): h(n) <= h*(n) for all n.
  • You always pop the node n with the minimum total cost f(n) = g(n) + h(n) off of OPEN, where g(n) is the cost of the path traversed so far to reach n.

So, suppose you just popped a node n off of OPEN which turns out to be the goal state. You know for sure (due to the second point) that every single other node in OPEN has a greater or equal total f-score. Because of the first point, you also know that these f-scores of all these other nodes in OPEN are not overestimates; they'll certainly not get better. They're either precisely correct, or underestimates of the cost. You know for sure they'll never outright beat n anymore, so the path you've just found to n will at least be an optimal path (it might not be the only optimal path though).

Upvotes: 3

Related Questions