

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

$$\delta e^{i p a c t a g c_{2},p a t a c_{1},e t g g A_{1},e t g g C_{1}}$$

of the search. Consider the example of the Logistics domain illustrated in Figure 9. In this example, we need to move two packages from cityA to **cityB** and **cityC** and there are two airplanes
(plane1**, plane**2) at **cityA** that can be used to move them. Moreover, we assume that **plane**1 is 1.5 times faster than **plane**2 and uses the same amount of resources to fly between two cities. There are two relaxed plans

$=\;1\,^{III}$
$$\partial U(p a c t a y c_{1},p a t c_{1},c t e y A,c t e y B),m a$$
P1 = {move(package1, plane1, cityA, cityB), move(package2, plane1**, cityA, cityC**)}

$P_{2}=\{move(package_{1},plane_{1},cityA,cityB),move(package_{2},plane_{2},cityA,cityC)\}$
that both contain two actions. The first one uses the same plane to carry both packages, while the second one uses two different planes. The first one has a shorter makespan if mutexes are ignored. However, if we consider the mutex constraints, then we know that two actions in P1 can not be executed concurrently and thus the makespan of P1 is actually longer than P2. Moreover, the static mutex relations also show that even if we order the two actions in P1, there is a violation because the first action cuts off the causal link between the initial state and the second one. Thus, the mutex information helps us in this simple case to find a better (consistent)
relaxed plan to use as a heuristic estimate. Here is a sketch of how the relaxed plan P2 can be found. After the first action A1 = move(package1, plane1**, cityA, cityB**) is selected to support the goal at(package1**, cityB**), the relaxed plan is RP = A1 and the two potential actions to support the second goal at(package2**, cityC**) are A2 = move(package2, plane1**, cityA, cityC**) and A′2 = move(package2, plane2**, cityA, cityC**). With mutex information, we will be able to choose A′2 over A2 to include in the final relaxed plan.

## 5.2 Using Resource Information To Adjust The Cost Estimates

The heuristics discussed in Section 4 have used the knowledge about durations of actions and deadline goals but not resource consumption. By ignoring the resource related effects when building the relaxed plan, we may miss counting actions whose only purpose is to provide sufficient resourcerelated conditions to other actions. In our ongoing example, if we want to drive a car from Tucson to LA and the gas level is low, by totally ignoring the resource related conditions, we will not realize that we need to *refuel* the car before *drive*. Consequently, ignoring resource constraints may reduce the quality of the heuristic estimate based on the relaxed plan. We are thus interested in adjusting the heuristic values discussed in the last two sections to account for the resource constraints.