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 failures⁸. 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.

Figure 3: Histogram of times, in seconds, for planner F to fail.