Problem Assumption 2: How Do Syntactic Representation Differences Affect Performance?

Although it is well known that some planners' performance depends on representation [Joslin Pollack 1994,Srinivasan Howe 1995], two recent developments in planner research suggest that the effect needs to be better understood. First, a common representation, i.e., PDDL, may bias performance. Some planners rely on a pre-processing step to convert PDDL to their native representation, a step that usually requires making arbitrary choices about ordering and coding. Second, an advantage of planners based on Graphplan is that they are supposed to be less vulnerable to minor changes in representation. Although the reasoning for the claim is sound, the exigencies of implementation may require re-introduction of representation sensitivity.

To evaluate the sensitivity to representation, ten permutations of each problem in the AIPS2000 set were generated, resulting in 4510 permuted problems. The permutations were constructed by randomly reordering the preconditions in the operator definitions and the order of the definitions of the operators within the domain definition.

We limited the number of problems in this study because ten permutations of all problems would be prohibitive. We selected the AIPS2000 problems for attention because this was the most recently developed benchmark set. Even within that set, not all of the domains were permuted because some would not result in different domains under the transformation we used. For the purposes of this investigation, we limited the set of modifications to permutations of preconditions and operators because these were known to affect some planners and because practical considerations limited the number of permutations that could be executed. Finally, for expediency, we ran the permutations on a smaller number of faster platforms because it expedited throughput and computation time was not a factor in this study.

To analyze the data, we divided the performance on the permutations of the problems into three groups based on whether the planner was able to solve all of the permutations, none of the permutations or only a subset of the permutations. If a planner is insensitive to the minor representational changes, then the subset count should be zero. From the results in Table 5, we can see that all of the planners were affected by the permutation operation. The susceptibility to permuting the problem was strongly planner dependent ( $\chi^2=1572.16$, $P<0.0001$), demonstrating that some planners are more vulnerable than others.

Table 5: The number of problems for which the planners were able to solve all, none or only a subset of the permutations.

Planner	All	None	Subset
A	65	315	30
B	70	295	45
C	318	74	18
D	202	169	39
E	111	132	167
F	112	138	160
G	70	295	45
H	91	290	29
I	109	134	167
J	150	124	136
K	60	305	45
L	112	284	14
M	212	148	50

By examining the number in the Subset column, one can assess the degree of susceptibility. All of the planners were sensitive to reorderings, even those that relied on Graphplan methodology. The most sensitive were E, F, I and J (which included some Graphplan based planners and in which 40% of the problems had mixed results on the permutations) with C and L being least sensitive (3-4% were affected).