
| Median of makespan   | Median of cost   |       |       |       |       |
|----------------------|------------------|-------|-------|-------|-------|
| Domain               | Distribution     | S > H | H > S | S > H | H > S |
| uniform              | 3                | 17    | 16    | 4     |       |
| ZenoTravel           | w02              | 6     | 12    | 14    | 4     |
| w08                  | 6                | 13    | 13    | 6     |       |
| uniform              | 6                | 11    | 7     | 11    |       |
| DriverLog            | w02              | 10    | 8     | 8     | 10    |
| w08                  | 10               | 7     | 9     | 9     |       |
| uniform              | 9                | 8     | 9     | 7     |       |
| Depots               | w02              | 7     | 9     | 5     | 9     |
| w08                  | 11               | 7     | 7     | 11    |       |

Since the quality of a plan set depends on how the two features makespan and plan cost are optimized, and how the plans "span" the space of time and cost, we also compare Sampling and Hybrid approaches in terms of those two criteria. In particular, we compare plan sets returned by the two approaches in terms of (i) their *median* values of makespan and cost, which represent how "close" the plan sets are to the origin of the space of makespan and cost, and (ii) their standard deviation of makespan and cost values, which indicate how the sets span each feature axis.

Table 9 summarizes for each domain, distribution and feature the number of problems in which each approach (either Sampling or Hybrid) generates plan sets with better median of each feature value (makespan and plan cost) than the other. There are 60 problems across 3 different distributions, so in total, 180 cases for each feature. Sampling and Hybrid return plan sets with better makespan in 40 and 62 cases, and with better plan cost in 52 and 51 cases (respectively),
which indicates that Hybrid is slightly better than Sampling on optimizing makespan but is possibly worse on optimizing plan cost. In ZenoTravel domain, for all distributions Hybrid likely returns better plan sets on the makespan than Sampling, and Sampling is better on the plan cost feature. In DriverLog domain, Sampling is better on the makespan feature with both non-uniform distributions, but worse than Hybrid with the uniform. On the plan cost feature, Hybrid returns plan sets with better median than Sampling on the uniform and w02 distribution, and both approaches perform equally well with the w08 ditribution. In Depots domain, Sampling is better than Hybrid on both features with the uniform distribution, and only better than Hybrid on the makespan with the distribution w08.

In terms of spanning plan sets, Hybrid performs much better than Sampling on both features across three domains, as shown in Table 10. In particular, over 360 cases for both makespan and plan cost features, there are only 10 cases where Sampling produces plan sets with better standard deviation than Hybrid on each feature. Hybrid, on the other hand, generates plan sets with better standard deviation on makespan in 91 cases, and in 85 cases on the plan cost.

These experimental results support our arguments in Section 5.1 about the limits of sampling idea. Since one single plan could be optimal for a wide range of weight values, the search in Sampling approach with different trade-off values may focus on looking for plans only at the same region of the feature space (specified by the particular value of the weight), which can reduce the chance of having plans with better value on some particular feature. On the opposite side, the Hybrid approach tends to be better in spanning plan sets to a larger region of the space, 30