The heuristics that account for overlap in the possible worlds should be more accurate than the heuristics that make an assumption of full positive interaction or full independence. To check our intuitions, we compare the heuristic estimates for the distance between the initial belief state and the goal belief state for all the heuristics used in conformant problems solved by . Figure 11 shows the ratio of the heuristic estimate for to the optimal serial plan length in 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 and heuristics are very close to , confirming our intuitions. Interestingly, and are both close to 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 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 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 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, and are very accurate in many domains, but suffer in Ring and Cube Center because they can be costly to compute.