Michael Jones, PhD

page 13. The heurstic generating function is not admissible because g^h can be satisfied in one step if g and h are satisfied by the change of a single variable. The heuristic generating function for g^h returns the cost of satisfing g plus the cost of satisfying h. If g and h are satisfied by the same transition, then the heurstic over-estimates the cost and inadmissible.

page 16. A* "seems to work better with the Hf+U[formula-based heurstic plus user annotations] than the Hap [the active process based heurstic]. But best-first results for either heuristic are similar." And that's why the best-first results use Hap rather than Hf+U.

pages 17-19. A total of 20 data points are given for non-LTL properties in the paper. Of those 20 data points, BF finds the error at the same depth in 8, BF finds the error within 50% of A* in 12, BF generates 1/5th as many states as A* in 8, BF generates the same or fewer states in 14. There are notable exeptions both ways. In one problem (dining philosophers with 12 diners), BF found an error at almost twice the depth after expanding more than 7 times as many statses. In another problem, BF found an error at the same depth after expanding less than 1/300th as many states. Including path costs results in shorter paths to errors in just over 1/2 of the data points while requiring expanding 5 times as many states in 4/10 data points. While these results are hardly an endorsement of best first search, they are not a clear endorsement of A* search either.