next up previous
Next: Performance Metrics Up: Planners Previous: Planner Assumption 2: Do

Planner Assumption 3: Are Time Cut-offs Unfair?

Planners often do not admit to failure. Instead, the planner stops when it has used the allotted time and not found a solution. So setting a time threshold is a requirement of any planner execution. In a comparison, one might always wonder whether enough time was allotted to be fair - perhaps the solution was almost found when execution was terminated.

To determine whether our cut-off of 30 minutes was fair, we examined the distribution of times for declared successes and failures8. Across the planners and the problem set, we found that the distributions were skewed (approximately log normal with long right tails) and that the planners were quick to declare success or failure, if they were going to do so. Table 10 shows the max, mean, median and standard deviation for success and failure times for each of the planners. The differences between mean and median indicate the distribution skew, as do the low standard deviations relative to the observed max times. The max time shows that on rare occasions the planners might make a decision within 2 minutes of our cut-off.


Table 10: Max, mean, median and standard deviations (Sd) for the computation times to success and failure for each planner.
  Successes Failures
Planner Max Mean Median Sd Max Mean Median Sd
A 667.9 34.0 1.3 98.7 1116.4 44.9 4.9 128.8
B 1608.5 38.5 0.5 182.8 1692.0 45.6 17.8 96.8
C 1455.4 89.9 1.6 244.6 1.4 0.4 0.13 0.4
D 481.0 17.8 1.1 77.4 713.6 26.3 1.1 122.6
E 1076 26.2 0.1 126.8 1622.8 286.9 260.6 189.1
F 1282.4 44.4 0.1 126.8 1188.4 22.3 0.2 104.8
G 1456.2 44.6 0.7 188.5 1196.5 43.8 16.7 78.5
H 657.7 29.58 1.4 80.6 1080.6 93.8 1.4 162.1
I 1713.8 115.4 0.2 303.1 50.6 5.1 4.9 6.3
J 1596.5 43.6 4.3 127.4 1796 11.0 11.0 57.9
K 1110.5 31.0 0.32 121.8 1298.8 27.7 12.1 65.2
L 1611.9 54.4 2.0 180.9 847.1 124.1 68.4 164.8
M 1675.3 53.4 1.45 196.5 1.6 0.9 0.8 0.4


What this table does not show, but the observed distributions do show, is that very few values are greater than half of the time until the cut-off. Figures 2 and 3 display the distributions for planner F, which had means in the middle of the set of planners and quite typical distributions. Consequently, at least for these problems, any cut-off above 15 minutes (900 seconds) would not significantly change the results.

Figure 2: Histogram of times, in seconds, for planner F to succeed.
\begin{figure}
\setlength{\epsfxsize}{5.0in}
\centerline{\epsffile{success-ipp.epsi}}
\end{figure}

Figure 3: Histogram of times, in seconds, for planner F to fail.
\begin{figure}
\setlength{\epsfxsize}{5.0in}
\centerline{\epsffile{fail-ipp.epsi}}
\end{figure}


next up previous
Next: Performance Metrics Up: Planners Previous: Planner Assumption 2: Do
©2002 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.