As shown in Section 3.4, macros added to a domain as new operators affect both the structure of the search space (the embedding effect) and the heuristic evaluation of states with relaxed graphplan (the evaluation effect). This section presents an empirical analysis of these.
Figure 24 shows results for Depots, Rovers and Satellite. For each domain, the chart on the left shows data for the original domain formulation, and the chart on the right shows data for the macro-enhanced domain formulation. For each domain formulation, the data points are extracted from solution plans as follows. Each state along a solution plan generates one data point. The coordinates of the data point are the state's heuristic evaluation on the vertical axis, and the number of steps left until the goal state is reached on the horizontal axis. The number of steps to a goal state may be larger than the distance (i.e., length of shortest path) to a goal state. The reason why states along solution plans were used to generate data is that for such states, both the heuristic evaluation, and the number of steps to a goal state are available after solving a problem.
The first conclusion from Figure 24 is that macros added to a domain improve the accuracy of heuristic state evaluation of relaxed graphplan. The closer a data point is to the diagonal, the more accurate the heuristic evaluation of the corresponding state.
Secondly, data clouds are shorter in macro-enhanced domains. This is a direct result of the embedding effect, which reduces the depth of goal states.
