Test results are obtained for the two alternative distribution approaches. The fifteen puzzle, the robot arm motion planning problem, and the artificial search space serve as problem domains. Experimental results are shown in Table 2. For each domain, the control variable is indicated under the ``Approach'' column.
The breadth-first distribution performs slightly better than C4.5 for the fifteen puzzle data set; however, the C4.5 recommendations outperform the breadth-first approach for the robot motion problem domain. The row labeled Combined-C4.5 is the result of merging the fifteen puzzle results with the robot motion planning results and running the combined data set through C4.5. The performance is better than for the fifteen puzzle but slightly worse than for the robot motion planning domain.
Note that using the filtered 15 puzzle data, EUREKA achieves a speedup of 79.17 although the number of processors used is only 64. These parallel search algorithms can produce superlinear speedup (speedup greater than the number of processors) because the parallel algorithms do not completely imitate the serial algorithm. For example, using distributed tree search individual subtrees are assigned to separate processors. If a goal node is located on the far left side of the rightmost subtree in the search space, the processor searching this subtree will quickly find the goal node, thus terminating search after only a few node expansions. In contrast, the serial algorithm in a left-to-right search will completely search all other subtrees to the cost threshold before searching and finding the goal node in the rightmost subtree. Thus the serial algorithm will perform disproportionately more search than all processors combined using the parallel algorithm. Each type of parallel search approach described in this paper can yield superlinear speedup under certain conditions. Some algorithms more closely imitate serial search, but at a potential loss of overall performance [17].
EUREKA's selection of strategies in the fifteen puzzle domain does not perform consistently better than using some of the strategies in isolation. One reason for this disappointing performance is the nature of the training data. Although we use the strategy that achieves the best run time as the correct ``classification'' for a given problem instance, there does not always exist a clear winner for each problem instance. On some problem instances one strategy dramatically outperforms the others. On other problem instances two or more strategy selections perform almost equally well.
This problem is exacerbated by the fact that there is some noise inherent in the collected run times. To demonstrate the amount of error that can be present in the timings we select twelve instances of the fifteen puzzle problem (four small, four medium, and four large instances), and time five runs of each instance with identical strategy parameters on an nCUBE 2. We compute the standard deviation of the speedups for five runs of the same problem instance, and then divide the result by the sample mean to ensure the result is not affected by the magnitude of the speedup values. This coefficient of variation averaged over all problem instances in the category is listed in Table 3 along with the average speedup for the instances in the problem category. As shown, the amount of error present in the timings can be quite large, and when two strategies perform almost equally well, the winner for any given run can be almost arbitrary.
To account for such misleading data, we sort all problem instances in the fifteen puzzle domain by the amount of variance of the strategy timing results. Those problem instances that yield a clear strategy winner are placed at the top of the list. We then filter the data set to keep only the top third of the sorted problem instances. The instances in the top third of this filtered data set are duplicated in the training set. The results of EUREKA's performance on this filtered training set is shown for each experiment in the Fil-15P column. We perform a similar filtering step to the robot arm motion planning domain data.
This approach can be used in each domain in which problem instances do not always yield a clear strategy winner. For example, problem instances drawn from the planning domain and artificial domain all demonstrate high variance of strategy timings, thus all problem instances are utilized. For any given domain, the number and type of test cases to use as training data can be selected based on the amount of variance of strategy results. The disadvantage of the filtered-data method is that cases in which two strategies yield similar timings may be discarded, even when the two strategies perform much better than other possible strategies.
The results in Table 3 verify that EUREKA can automatically select parallel search strategies that yield greater speedup than using any single strategy for all problem instances pulled from the filtered data sets. However, this table does not indicate how well the machine learning component is performing at the classification task. One danger in listing only speedup results is that the numbers may be biased by the magnitude of several large problem instances in which EUREKA correctly picks the best strategy.
In Table 4 we measure how well the system classifies each new test
problem. Once again we perform ten-fold cross validation and show mean
classification error for each approach. The fixed strategies (Kumar and Rao,
Breadth-first) always pick the correct classification of a problem instance as
their own, and C4.5 uses its decision tree to pick the classification of
the problem instance. Significance values are gathered using a paired student
t-test and are shown in parentheses following the mean error.
In each of the filtered data sets, C4.5 significantly outperforms
either fixed approach (p
0.03) when predicting the correct
classification of unseen problem instances.