- *Plan as a set of actions or causal links*: given a plan p, let A(p) and C(p) be the set of actions or causal links of p. The distance between two plans p and p
′can be defined as the ratio of the number of actions (causal links) that do not appear in both plans to the total number of actions (causal links) appearing in one of them:

$$\delta_{A}(p,p^{\prime})=1-\frac{|A(p)\cap A(p^{\prime})|}{|A(p)\cup A(p^{\prime})|}$$  $$\delta_{C L}(p,p^{\prime})=1-\frac{|C(p)\cap C(p^{\prime})|}{|C(p)\cup C(p^{\prime})|}$$

- *Plan as a sequence of states*: given two sequence of states(s0, s1**, ..., s**k) and (s
′0, s′1**, ..., s**′k′ )
resulting from executing two plans p and p
′, and assume that k
′ ≤ k. Since the two sequence of states may have different length, there are various options in defining distance measure between p and p
′, and we consider here two simple options. In the first one, it can be defined as the average of the distances between state pairs (si, s′i
) (0 ≤ i ≤ k
′),
and each state sk′+1,... sk is considered to contribute maximally (i.e. one unit) into the difference between two plans:

$$\delta_{S}(p,p^{\prime})=\frac{1}{k}\times[\sum_{i=1}^{k^{\prime}}\Delta(s_{i},s_{i}^{\prime})+k-k^{\prime}]$$

On the other hand, we can assume that the agent continues to stay at the goal state s
′
k′ in the next (k − k
′) time steps after executing p
′, and the measure can be defined as follows:

$$\delta_{S}(p,p^{\prime})=\frac{1}{k}\times[\sum_{i=1}^{k^{\prime}}\Delta(s_{i},s_{i}^{\prime})+\sum_{i=k^{\prime}+1}^{k}\Delta(s_{i},s_{k^{\prime}}^{\prime})]\tag{7}$$
$$(6)$$
$$({\boldsymbol{8}})$$

The distance measure ∆(**s, s**′) between two states s, s
′ used in those two measures is defined as

$$\Delta(s,s^{\prime})=1-\frac{s\cap s^{\prime}}{s\cup s^{\prime}}$$

Example: Figure 4 shows three plans p1, p2 and p3 for a planning problem where the initial state is {r1} and the goal propositions are {r3, r4}. The specification of actions are shown in the table. The action sets of the first two plans ({a1, a2, a3} and {a1, a2, a4}) are quite similar
(δA(p1, p2**) = 0**.5), but the causal links which involve a3 (a2 → r3 − a3, a3 → r4 − aG) and a4 (aI → r1 − a4, a4 → r4 − aG) make their difference more significant with respect to causallink based distance (δCL(p1, p2) = 47
). Two other plans p1 and p3, on the other hand, are very different in terms of action sets (and therefore the sets of causal links): δA(p1, p3**) = 1**, but they are closer in term of state-based distance ( 13 18 as defined in the equation 6, and 0.5 if defined in the equation 7).