Clustering Results

In this experiment EUREKA selects the optimal number of clusters to use for each problem instance. By combining the features of distributed tree search and parallel window search, it is possible to achieve better performance than when each approach is used in isolation.

The clustering algorithm is tested using 1, 2, and 4 clusters on 64 processors of an nCUBE 2 for the fifteen puzzle, robot motion planning, and SNLP domains, and using 1 and 2 clusters for the fifteen puzzle domain on a distributed network of 8 PCs. Test results for the clustering algorithm are presented in Table 5.

 

Table 5: Clustering Speedup Results

Approach	15Puzzle	Fil-15P	RMP	Fil-RMP	Planning	PVM-15P
1 Cluster	52.02	65.21	60.01	62.75	108.46	7.69
2 Clusters	57.04	64.97	80.09	79.98	145.0	7.03
4 Clusters	56.83	49.57	162.86	153.17	129.15	--
C4.5-nCUBE	58.90	86.76	126.32	164.96	195.19	7.72
Combined-C4.5	73.90				--

 

Table 5 demonstrates that EUREKA's automatic strategy selection using C4.5 outperforms any fixed strategy in almost all domains, and always performs best when the filtered data sets are used. The table also indicates that the optimal number of clusters on average varies from one domain to another, thus reinforcing the need for automatic selection of this parameter. In the PVM experiments, because only eight processors are available we experimented with 1 or 2 clusters for each problem instance. The combined results are again collected from the test cases for the fifteen puzzle and robot arm motion planning domains.

 

Table 6: Clustering Classification Results

Approach	15Puzzle	Fil-15P	RMP	Fil-RMP
1 Cluster	.5556 (.04)	.4595 (.00)	.7540 (.11)	.7778 (.01)
2 Clusters	.6956 (.32)	.6738 (.00)	.9048 (.04)	.7778 (.02)
4 Clusters	.7489 (.18)	.8667 (.00)	.3413 (.11)	.4444 (.01)
C4.5	.6756	.2333	.4921	.1481

 

The classification results for choice of number of clusters are shown in Table 6. On the filtered data set, C4.5 outperforms all fixed strategies at a significance level of p$\leq$0.02.