In many real-world problems, most actions consume resources, while there are special actions that increase the levels of resources. Since checking whether the level of a resource is sufficient for allowing the execution of an action is similar to checking the predicate preconditions, one obvious approach is to adjust the relaxed plan by including actions that provide that resource-related condition to the relaxed plan. However, for many reasons, it turns out to be too difficult to decide which actions should be added to the relaxed plan to satisfy the given resource conditions (Do & Kambhampati, 2001, gives a more detailed discussion of these difficulties). Therefore, we introduce an indirect way of adjusting the cost of the relaxed plan to take into account the resource constraints.

We first pre-process the problem specifications and find for each resource R an action AR that can increase the amount of R maximally. Let ∆R be the amount by which AR increases R, and let C(AR) be the cost value of AR. Let **Init**(R) be the level of resource R at the state S for which we want to compute the relaxed plan, and Con(R), **P ro**(R) be the total consumption and production of R by all actions in the relaxed plan. If Con(R) **> Init**(R) + **P ro**(R), then we increase the cost by the number of production actions necessary to make up the difference. More precisely:

$$C\gets C+\sum_{R}\left[\frac{(C o n(R)-(I n i t(R)+P o(R)))}{\Delta_{R}}\right]*C(A_{R})$$

We shall call this the adjusted cost heuristic. The basic idea is that even though we do not know if an individual resource-consuming action in the relaxed plan needs another action to support its resource-related preconditions, we can still adjust the number of actions in the relaxed plan by reasoning about the total resource consumption of all the actions in the plan. If we know the resources R consumed by the relaxed plan and the maximum production of those resources possible by any individual action in the domain, then we can infer the minimum number of resource-increasing actions that we need to add to the relaxed plan to balance the resource consumption. In our ongoing example, if the car rented by the students at *Tucson* does not have enough fuel in the initial state to make the trip to Phoenix, LA, or Las Vegas, then this approach will discover that the planner needs to add a *refuel* action to the relaxed plan.

Currently, our resource-adjustment technique discussed above is limited to simple consumption and production of resources using addition and subtraction. These are the most common forms, as evidenced by the fact that in all metric temporal planning domains used in the competition, actions consume and produce resources solely using addition (increase) and subtraction (decrease). Modifications are needed to extend our current approach to deal with other types of resource consumption such as using multiplication or division.

## 6. Post-Processing To Improve Temporal Flexibility

To improve the makespan and execution flexibility of the plans generated by Sapa, we post-process and convert them into partially ordered plans. We discuss the details of this process in this section. We will start by first differentiating between two broad classes of plans. Position and Order constrained plans: *A position constrained plan (p.c.) is a plan where the* execution time of each action is fixed to a specific time point. *An order constrained (o.c.) plan is a* plan where only the relative orderings between the actions are specified.

Note that the p.c. vs. o.c. distinction is orthogonal to whether or not concurrency is allowed during execution. Indeed, we can distinguish two subclasses of p.c. plans–serial and parallel. In