Algorithm 1: Incrementally find solution set P
1 **Input:** A planning problem with a solution space S; maximum number of plans required k; number of sampled trade-off values k0 (0 < k0 < k); time bound t; 2 **Output**: A plan set P (**|P| ≤** k);
3 **begin**
4 W ← sample k0 values for w; 5 P ← find good quality plans in S for each w ∈ W;
6 while |P| < k and search time < t do 7 Search for p s.t. ICP(P ∪ {p}) **< ICP**(P)
8 **P ← P ∪ {**p}
9 end 10 Return P
11 end Second, the values of the trade-off parameter w are sampled based on a given distribution, and independently of the particular planning problem being solved. As there is no relation between the sampled w values and the solution space of a given planning problem, sampling approach may return very few distinct solutions even if we sample a large number of weight values w. In our example, if all w samples have values w ≤ 0.67 then the optimal solution returned for any of them will always be p7. However, we know that P
∗ = {p1, p3, p7} is the optimal set according to the ICP measure. Indeed, if w ≤ 0.769 then the sampling approach can only find the set {p7} or {p3, p7} and still not be able to find the optimal set P
∗.

## 5.2. Icp Sequential Approach

Given the potential drawbacks of the sampling approach outlined above, we also pursued an alternative approach that takes into account the ICP measure more actively. Specifically, we incrementally build the solution set P by finding a solution p such that **P ∪ {**p} has the lowest ICP value. We can start with an empty solution set P = ∅, then at each step try to find a new plan p such that **P ∪ {**p} has the lowest ICP value.

While this approach directly takes the ICP measure into consideration at each step of finding a new plan and avoids the drawbacks of the sampling-based approach, it also has its own share of potential flaws. Given that the set is built incrementally, the earlier steps where the first "seed" solutions are found are very important. The closer the seed solutions are to the global lower convex hull, the better the improvement in the ICP value. In our example (Figure 5), if the first plan found is p2 then the subsequent plans found to best extend {p2} can be p5 and thus the final set does not come close to the optimal set P
∗ = {p1, p3, p7}.

## 5.3. Hybrid Approach

In this approach, we aim to combine the strengths of both the sampling and ICP-sequential approaches. Specifically, we use sampling to find several plans optimizing for different weights. The plans are then used to seed the subsequent ICP-sequential runs. By seeding the hybrid approach with good quality plan set scattered across the pareto optimal set, we hope to gradually expand the initial set to a final set with a much better overall ICP value. Algorithm 1 shows the pseudo-code for the hybrid approach. We first independently sample the set of k0 values (with 24