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.
 |
and 
to optimal plan length. Rv = Rovers, L =
Logistics, B = BT, BC = BTC, C = Cube Center, R = Ring.