

![0_image_0.png](0_image_0.png)

several problems. The points below the line (where the ratio is one) are under-estimates, and those above are over-estimates. Some of the problem instances are not shown because no optimal plan length is known.

We note that in all the domains the h LUG
RP and hMG
RP U heuristics are very close to h
∗, confirming our intuitions. Interestingly, hMG
s−RP and hMG
m−RP are both close to h
∗in Rovers and Logistics; whereas the former is close in the BT and BTC problems, and the latter is close in CubeCenter and Ring. As expected, assuming independence (using summation) tends to over-estimate, and assuming positive interaction (using maximization) tends to under-estimate. The h SG
RP heuristic tends to under-estimate, and in some cases (CubeCenter and Ring) gives a value of zero (because there is an initial state that satisfies the goal). The h**card** heuristic is only accurate in BT and BTC,
under-estimates in Rovers and Logistics, and over-estimates in Cube Center and Ring.

The accuracy of heuristics is in some cases disconnected from their run time performance. For instance h**card** highly overestimates in Ring and Cube Center, but does well because the domains exhibit special structure and the heuristic is fast to compute. On the other hand, h LUG
RP and hMG
RP U