The values of the first 3 terms are automatically derived from the expression defining the plan metric for the problem (Gerevini et al., 2003). The coefficient for the fourth new term of E (αD)
is automatically set during search to a value proportional to d/δa(**p, p**0), where p is the current partial plan under construction. The general idea is to dynamically increase the value of αD
according to the number of plans n that have been generated so far: if n is much higher than k, the search process consists of finding many solutions with not enough diversification, and hence the importance of the last E-term should increase.

4.2.2. Making LPG Return a Set of Plans In order to compute a set of k d-distant plans solving a dDISTANCEkSET problem, we run the LPG search multiple times, until the problem is solved, with the following two additional changes to the standard version of LPG: (i) the preprocessing phase computing mutex relations and other reachability information exploited during the relaxed plan construction is done only once for all runs; (ii) we maintain an incremental set of valid plans, and we dynamically select one of them as the reference plan p0 for the next search. Concerning (ii), let P = {p1**, ..., p**n} be the set of n valid plans that have been computed so far, and *CPlans*(pi) the subset of P containing all plans that have a distance greater than or equal to d from a reference plan pi ∈ P.

The reference plan p0 used in the modified heuristic function E is a plan pmax ∈ P which has a maximal set of diverse plans in P, i.e.,

$\left.\right)\left|\downarrow\right\rangle$ . 
pmax = ARGMAX{pi∈P} {|**CPlans**(pi)|} . (13)
The plan pmax is incrementally computed each time the local search finds a new solution.

In addition to being used to identify the reference plan in E, pmax is also used for defining the initial state (partial plan) of the search process. Specifically, we initialize the search using a
(partial) plan obtained by randomly removing some actions from a (randomly selected) plan in the set *CPlans*(pmax) ∪ {pmax}.

The process of generating diverse plans starting from a dynamically chosen reference plan continues until at least k plans that are all d-distant from each other have been produced. The modified version of LPG to compute diverse plans is called LPG-d. 4.2.3. Experimental Analysis with LPG-d Recall that the distance function δa, using set-difference, can be written as the sum of two terms:

$$\delta_{a}(p_{i},p_{j})=\frac{|A(p_{i})-A(p_{j})|}{|A(p_{i})\cup A(p_{j})|}+\frac{|A(p_{j})-A(p_{i})|}{|A(p_{i})\cup A(p_{j})|}\tag{14}$$

The first term represents the contribution of the actions in pito the plan difference, while the second term indicates the contribution of pj to δa. We experimentally observed that in some cases the differences between two diverse plans computed using δa are mostly concentrated in only one of the δa components. This asymmetry means that one of the two plans can have many more actions than the other one, which could imply that the quality of one of the two plans is much worse than the quality of the other plan. In order to avoid this problem, we can parametrize δa by imposing the two extra constraints δ A
a ≥ d/γ and δ B
a ≥ d/γ