0

I have a doubt about A* goal test.

As far as I know an early goal test is performed when a node (representing a certain state) is inserted in the frontier or, to conform with AIMA terminology, when is reached/generated.

Quoting AIMA 4ed:

(...) with a consistent heuristic, the first time we reach a state it will be on an optimal path, so we never have to re-add a state to the frontier, and never have to change an entry in reached.

With this piece of information I suppose that an early goal test is totally safe, but I wasn't able to find anything about it on the internet to confirm my hypothesis, so my second guess is that I am wrong about it.

Am I wrong? Did I misunderstood something?

nbro
  • 39,006
  • 12
  • 98
  • 176
InCrisis
  • 21
  • 2
  • Yes, you can. It's an extremely common optimization to early-exit like this in pathfinding code when you know for sure the heuristic will always be consistent. – BlueRaja - Danny Pflughoeft Mar 16 '22 at 19:07
  • Is early goal test ok even with multiple goal states? I think it is not. It is true that we can adapt a problem with multiple goal states to a problem with one goal state by connecting all goal states to an unique goal state, but this is equivalent to perform a late goal test with the original goal states in my opinion. – InCrisis Mar 24 '22 at 10:22

0 Answers0