next up previous
Next: Interpretation of Results and Up: Performance Metrics Previous: Metric Assumption 1: Does

Metric Assumption 2: Do the Number of Plan Steps Vary?

Several researchers have examined the issue of measuring plan quality and directing planning based on it, e.g., [Perez 1995,Estlin MooneyEstlin Mooney1997,Rabideau, Englehardt, ChienRabideau et al.2000]. The number of steps in a plan is a rather weak measure of plan quality, but so far, it is the only one that has been widely used for primitive-action planning.

We expect that some planners sacrifice quality (as measured by plan length) for speed. Thus, ignoring even this measure of plan quality may be unfair to some planners. To check whether this appears to be a factor in our problem set, we counted the plan length in the plans returned in output and compared the lengths across the planners. Because not all of the planners construct parallel plans, we adopted the most general definition: sequential plan length. We then compared the plan lengths returned by each planner on every successfully solved problem.

We found that 11% of the problems were solved by only one planner (not necessarily the same one). The planners found equal length solutions for 62% of those that remained (493 problems). We calculated the standard deviation (SD) of plan length for solutions to each problem and then analyzed the SDs. We found that the minimum observed SD was 0.30, the maximum was 63.30, the mean was 2.43 and the standard deviation was 5.45. Thirteen cases showed SDs higher than 20. Obviously, these cases involved fairly long plans (up to 165 steps); the cases were for problems from the logistics and gripper domains.

To check whether some planners favored minimal lengths, we counted the number of cases in which each planner found the shortest length plan (ties were attributed to all planners) when there was some variance in plan length. Table 13 lists the results. Most planners find the shortest length plans on about one third of these problems. Planner F was designed to optimize plan length, which shows in the results. With one exception, the older planners rarely find the shortest plans.

Table 13: Number of plans on which each planner found the shortest plan. The data only include problems for which different length plans were found.
Planner Count
A 178
B 169
C 0
D 161
E 5
F 319
G 171
H 176
I 222
J 0
K 159
L 151
M 283

next up previous
Next: Interpretation of Results and Up: Performance Metrics Previous: Metric Assumption 1: Does
©2002 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.