

![0_image_0.png](0_image_0.png)

The meaning of the above formula is that the two literals are mutex in all worlds S where all pairs of effects that support the literals in S are mutex in S.

## 4.4.3 Lug Heuristics

The heuristics computed on the LUG can capture measures similar to the MG heuristics, but there exists a new opportunity to make use of labels to improve heuristic computation efficiency. A single planning graph is sufficient if there is no state aggregation being measured, so we do not mention such measures for the LUG.

Positive Interaction Aggregation: Unlike MG heuristics, we do not compute positive interaction based relaxed plans on the LUG. The MG approach to measure positive interaction across each state in a belief state is to compute multiple relaxed plans and take their maximum value. To get the same measure on the LUG we would still need to extract multiple relaxed plans, the situation we are trying to avoid by using the LUG. While the graph construction overhead may be lowered by using the LUG, the heuristic computation could take too long. Hence, we do not compute relaxed plans on the LUG to measure positive interaction alone, but we do compute relaxed plans that measure overlap (which measures positive interaction).

Independence Aggregation: Like positive interaction aggregation, we need a relaxed plan for every state in the projected belief state to find the summation of the costs. Hence, we do not compute relaxed plans that assume independence.

State Overlap Aggregation: A relaxed plan extracted from the LUG to get the h LUG
RP heuristic resembles the unioned relaxed plan in the hMG
RP U heuristic. Recall that the hMG
RP U heuristic extracts a relaxed plan from each of the multiple planning graphs (one for each possible world) and unions the set of actions chosen at each level in each of the relaxed plans. The LUG relaxed plan heuristic is similar in that it counts actions that have positive interaction in multiple worlds only once and accounts for independent actions that are used in subsets of the possible worlds. The advantage of h LUG
RP is that we find these actions with a single pass on one planning graph.

We are trading the cost of computing multiple relaxed plans for the cost of manipulating LUG
labels to determine what lines of causal support are used in what worlds. In the relaxed plan we want to support the goal with every state in BSP , but in doing so we need to track which states in BSP use which paths in the planning graph. A subgoal may have several different (and possibly overlapping) paths from the worlds in BSP .

A LUG relaxed plan is a set of layers: {ARP
0, E
RP
0,L
RP
1**, ...,** ARP
b−1
, E
RP
b−1
, L
RP
b}, where ARP
r is a set of actions, E
RP
ris a set of effects, and L
RP
r+1 is a set of clauses. The elements of the layers are labelled to indicate the worlds of BSP where they are chosen for support. The relaxed plan is extracted from the level b = h LUG
level(BSi) (i.e., the first level where BSiis reachable, also described in Appendix A).

Please note that we are extracting the relaxed plan for BSiin terms of clauses, and not literals, which is different than the SG and MG versions of relaxed plans. Previously we found the