Reviving Partial Order Planning

1 Introduction

Most recent strides in scaling up planning have centered around two dominant themes - heuristic state space planners, exemplified by UNPOP[20], HSP-R[3], and CSP-based planners, exemplified by Graphplan[2] and SATPLAN [14] . This is in stark contrast to planning research up to five years ago, when most of the efforts were focused on scaling up partial order planners[19; 27; 15; 23; 11; 13]. Despite such efforts, the partial order planners continue to be extremely slow and are not competitive with the fastest state search-based and CSPbased planners. Indeed, the recent advances in plan synthesis have generally been (mis)interpreted as establishing the supremacy of state space and CSP-based approaches over POP approaches.

Despite its current scale-up problems, partial order planning remains attractive over state space and CSP-based planning for several reasons. The least commitment inherent in partial order planning makes it one of the more open planning frameworks. This is evidenced by the fact that most existing architectures for integrating planning with execution, information gathering, and scheduling are based on partial order planners. In

A3 This research is supported in part by the NSF grant IRI-9801676, AFOSR grant F20602-98-1-0182 and the NASA grants NAG2-1461 and NCC-1225. We thank David Smith, Malik Ghallab, Austin Tate, Dan Weld, Terry Zimmerman, Biplav Srivastava, Minh B. Do, and the IJCAI referees for critical comments on the previous drafts of this paper.

BD UCPOP [27] AX UNPOP [20] AX REPOP. REPOP's source code is available from http://rakaposhi.eas.asu.edu/repop.html.

[25], Smith argues that POP-based frameworks offer a more promising approach for handling domains with durative actions, and temporal and resource constraints as compared to other planning approaches. In fact, most of the known implementations of planning systems capable of handling temporal and durative constraints -including IxTET [6] as well as NASA's RAX [10]-are based on the POP algorithms. Even for simpler planning domains, partial order planners search for and output partially ordered plans that offer a higher degree of execution flexibility. In contrast, none of the known state space planners can find parallel plans efficiently [8], and CSP planners such as Graphplan only generate a very restricted class of parallel plans (see Section 5).

The foregoing motivates the need for improving the efficiency of POP algorithms. We show in this paper that the insights and techniques responsible for the advances in plan synthesis made in the recent years in the context of state-based and CSP-based planners are largely adaptable to POP algorithms. In particular, we present novel methods for adapting distance based heuristics, reachability analysis and disjunctive constraint processing techniques to POP algorithms. Distancebased heuristics are used as the basis for ranking partial plans and as flaw selection methods. The other two techniques are used for efficiently enforcing the consistency of the partial plans-by detecting implicit conflicts and resolving them.

Our methods help scale up POP algorithms dramaticallymaking them competitive with respect to state space planners, while preserving their flexibility. We present empirical studies showing that REPOP, a version of UCPOP [27] enhanced by our ideas, can perform competitively with other existing approaches in many planning domains. In particular, REPOP appears to scale up much better than Graphplan in the parallel domains we tried. More importantly, the solutions REPOP generates are generally shorter in length, and provide significantly more execution flexibility [25].

The paper is organized as follows. In the next section we will briefly review the basics of the POP algorithm. Section 3 describes how distance based heuristics can be adapted to rank partial plans. Section 4 shows how unsafe links flaws can be generalized and resolved efficiently. Section 5 reports empirical evaluations of the techniques that have been described. Section 6 discusses related work, and Section 7 summarizes the contributions of this work.

2 Background on Partial Order Planning

In this paper we consider the simple STRIPS representation of classical planning problems, in which the initial world state
, goal state BZ and the set of deterministic actions AA are given. Each action CP BE AA has a precondition list and an effect list, denoted respectively as  D6CTCRB4CPB5BN BXCU CU B4CPB5. The planning problem involves finding a plan that when executed from the initial state
will achieve the goal BZ.

A tutorial introduction to POP algorithms can be found in [27]. We will provide a brief review here. Most POP algorithms can be seen as searching in the space of partial plans. A partial plan is a five-tuple:  BP B4BTBNBN BNBVBN CDB5, where BTAI AA is a set of (ground) actions, BE  is a set of ordering constraints over BT, and  is a set of causal links over BT. BF A causal link is of the form CP CX D4 A0AX CP CY , and denotes a commitment by the planner that the precondition D4 of action CP CY will be supported by an effect of action CP CX . BV is a set of open conditions, and CD is a set of unsafe links. An open condition is of the form B4D4BN CPB5, where D4 BE  D6CTCRB4CPB5 and CP BE BT, and there is no causal link CQ D4 A0AXCP BE . Loosely speaking, the open conditions are preconditions of actions in the partial plan which have not yet been achieved in the current partial plan. A causal link CP CX D4 A0AXCP CY is called unsafe if there exists an action CP CZ BE BT such that (CX) BMD4 BE BXCUCUB4CP CZ B5 and (CXCX) CJCUCP CX AU CP CZ AU CP CY CV is consistent. In such a case, CP CZ is also said to threaten the causal link CP CX D4 A0AX CP CY . Open conditions and unsafe links are also called flaws in the partial plan. Therefore a solution plan can be seen as a partial plan with no flaws (i.e., BV BP BN and CD BP BN).

The POP algorithm starts with a null partial plan  and keeps refining it until a solution plan is found. The null partial plan contains two dummy actions CP BC AU CP BD where the preconditions of CP BD correspond to the top level goals of the problem, and the effects of CP BC correspond to the conditions in the initial state. The null plan has no causal links or unsafe link flaws, but has open condition flaws corresponding to the preconditions of CP BD (top level goals).

A refinement step involves selecting a flaw in the partial plan , and resolving it, resulting in a new partial plan. When the flaw chosen is an open condition B4D4BN CPB5, an action CQ needs to be selected that achieves D4. CQ can be a new action in AA, or an action that is already in BT. The sets BV, ,  and CD also need to be updated with respect to CQ. Secondly, when the flaw chosen is an unsafe link CP CX D4 A0AX CP CY that is threatened by action CP CZ , it can be repaired by either promotion, i.e adding ordering constraint CP CZ AU CP CX into , or demotion, i.e adding CP CY AU CP CZ into .

The efficiency of POP algorithms depends critically on the way partial plans are selected from the search queue, and the strategies used to select and resolve the flaws. In Section 3 we present several distance-based heuristics for ranking partial plans in the search queue. Section 4 introduces the disjunctive constraint representation for efficiently handling unsafe link flaws, and reachability analysis for generalizing the notion of unsafe links to include implicit conflicts in the plan.

3 Heuristics for ranking partial plans

In choosing a plan from the search queue for further refinement, we are naturally interested in plans that are likely to lead to a solution with a minimum number of refinements

BE Although partial order planners are capable of handling partially instantiated action instances, we restrict our attention to ground action instances.

BF Strictly speaking BT should be seen as a set of "steps", where each step is mapped to an action instance [15].

(flaw resolutions). As we handle the unsafe links in a significantly different way than standard UCPOP (see Section 4), the only remaining category of flaws to be resolved are open condition flaws. Consequently one way of ranking plans in the search queue is to estimate the minimum number of new actions needed to resolve all the open condition flaws.

Definition 1 (h*) Given a partial plan , let CW A3 B4B5 denote the minimum number of new actions that need to be added to  to make it a solution plan.

CW A3 B4B5 can be seen as the number of actions that, when executed from the initial state
in some order, will achieve the set of subgoals CB BP CUD4CYB4D4BN CPB5 BE BVCV. In this sense, this is similar to estimating the number of actions needed to achieve a state from the given initial state in state search planners [3; 21], but for two significant differences: (i) the propositions in CB are not necessarily in the same world state and (ii) the set of actions that achieve CB cannot conflict with the set of actions and causal links already present in .

A well-known heuristic for estimating CW A3 involves simply counting the number of open conditions in the partial plan [13].

Heuristic 1 (Open conditions heuristic) CW D3CR B4B5BP CYBVCY

This estimate is neither admissible nor informed in many domains, because it treats every open condition equally. In particular, it is ineffective when some open conditions require more actions to achieve than others.

We would like to have a closer estimate of CW A3 function without insisting on admissibility. To do this, we need to take better account of subgoal interactions[21]. Accounting for the negative interactions in estimating CW A3 can be very tricky, and is complicated by the fact that the subgoals in CB may not be in the same state. Thus we will start by ignoring the negative interactions. This has three immediate consequences: (i) the set of unsafe links CD becomes empty. (ii) the actions needed in achieving a set of subgoals CB will have no conflicts with the set of actions BT and and the causal links  already present in . and (iii) a subgoal D4 once achieved from the initial state can never become untrue. Given these consequences, it does not matter much that the subgoals in CB are not necessarily present in the same world state, since the minimum number of actions needed for achieving such a set of subgoals in any given temporal ordering is the same as the minimum cost of achieving a state comprising all those subgoals.

The foregoing justifies the adaptation of many heuristic estimators for ranking the goodness of states in state search planners. Most of the early heuristic estimators used in state search not only ignore negative interactions, but also make the stronger assumption of subgoal independence[3; 20]. A few of the recent ones, [21; 9] however account for the positive interactions among subgoals (while still ignoring the negative interactions). It is this latter class of heuristics that we focus on for use in partial order planning. Specifically, to account for the positive interactions, we exploit the ideas for estimating the cost of achieving a set of subgoals CB using a serial planning graph. BG

Specifically, we build a planning graph starting from the initial state
. Let D0CTDAB4D4B5 be the index of the level in the planning graph that a proposition D4 first appears, and D0CTDAB4CBB5 be the index of the first level at which all propositions in CB appear. Let D4 CB be the proposition in CB such that D0CTDAB4D4 CB B5 BP D1CPDC D4 CX BECB D0CTDAB4D4 CX B5.

BG We assume that the readers are familiar with the planning graph data structure, which is used in Graphplan algorithm[2].

D4 CB will possibly be the last proposition in CB that is achieved during execution. Let CP CB be an action in the planning graph that achieves D4 CB in the level D0CTDAB4D4 CB B5. We can achieve D4 CB by adding CP CB to the plan. Introduction of CP CB changes the set of goals to be achieved to CB BC BP CB B7  D6CTCRB4CP CB B5 A0 BXCU CU B4CP CB B5. We can express the cost of CB in terms of the cost of CP CB and CB BC :

where CRD3D7D8B4CP CB B5 BP BD if CP CB BPBE BT and 0 otherwise. Since D0CTDAB4D6CTCRB4CP CB B5B5 is strictly smaller than D0CTDAB4D4 CB B5, recursively applying Equation 1 to its right hand side will eventually express CRD3D7D8B4CBB5 in terms of CRD3D7D8B4
B5 (which is zero), and the costs of actions CP CB . The process is quite efficient as the number of applications is bounded by D0CTDAB4CBB5.

Heuristic 2 (Relax heuristic) CW D6CTD0CPDC B4B5 BP CRD3D7D8B4CBB5, where CB BP CUD4CYB4D4BN CPB5 BE BVCV, and CRD3D7D8B4CBB5 is computed using the recurrence relation 1.

Given such a heuristic estimate, plans in the search queue are ranked with the evaluation function: CUB4B5BP CYBTCYB7DB A3 CWB4B5. The parameter DB is used to increase the greediness of the heuristic search and is set to 5 by default.

4 Enforcing consistency of partial plans

The consistency of a partial plan is ensured through the handling of its unsafe links. In this section we describe two ways of improving this phase. The first involves posting disjunctive constraints to resolve unsafe links. The second involves detecting implicit conflicts (unsafe links) using reachability analysis.

4.1 Disjunctive representation of ordering constraints

Normally, an unsafe link CP CX D4 A0AX CP CY that is in conflict with action CP CZ is resolved by either promotion or demotion, that is, splitting the current partial plan into two partial plans, one with the constraint CP CZ AU CP CX , and the other with the constraint CP CY AU CP CZ . A problem with this premature splitting is that a single failing plan gets unnecessarily multiplied into many descendant plans poisoning the search queue significantly. A much better idea, first proposed in [16], is to resolve the unsafe link by posting a disjunctive ordering constraint that captures both the promotion and demotion possibilities, and incrementally simplify these constraints by propagation techniques. This way, we can detect many failing plans before they get selected for refinement.

Specifically, an unsafe causal link CP CX D4 A0AX CP CY that is in conflict with action CP CZ can be resolved by simply adding a disjunctive ordering constraint B4CP CZ AU CP CX B5CNB4CP CY AU CP CZ B5 to the plan.

We use the following procedure for simplifying the disjunctive orderings. Whenever an open condition B4D4BN CPB5 is selected and resolved by either adding a new action or reusing an action CQ in the partial plan, we add a new ordering constraint CQ AU CP to , followed by repeated application of the constraint propagation rules below:

• AF B4CP BD AU CP BE B5 BE CMB4CP BE AU CP BF B5 BE B5AW CJB4CP BD AU CP BF B5
• AF B4CP BD AU CP BE B5 BE  CMB4CP BE AU CP BD B5 BE B5False
• AF B4CP BD AU CP BE B5 BE CMB4CP BE AU CP BD CN CP BF AU CP BG B5 BE B5  AW  CJB4CP BF AU CP BG B5  AW  A0B4CP BE AU CP BD CN CP BF AU CP BG B5

The first two propagation rules are already done as part of POP algorithm to ensure the transitive consistency of ordering constraints. The third rule is a unit propagation rule over ordering constraints. This propagation both reduces the disjunction and detects infeasible plans ahead of time. When all the open conditions have already been established and there are still disjunctive constraints left in the plan, the remaining disjunctive constraints are then split into the search space [16].

4.2 Detecting and Resolving implicit conflicts through reachability analysis

Although the unsafe link detection and resolution steps in the POP algorithm are meant to enforce consistency of the partial plan, often times they are too weak to detect implicit inconsistencies. In particular, the procedure assumes that a link CP CX D4 A0AX CP CY is threatened by an action CP only if CP has an effect BMD4. Often CP might have an effect D5 (or precondition D6) such that no legal state can have D4 and D5 (or D4 and D6) true together. Detecting and resolving such implicit interactions can be quite helpful in weeding out inconsistent partial plans from the search space.

In order to do implicit conflict detection as described above, we need to have (partial) information about the properties of reachable states. Interestingly, such reachability information has played a significant role in the scale-up of state space planners, motivating the development of procedures for identifying mutex constraints, state invariants and memos etc. [2; 7; 5] (we shall henceforth use the term mutex to denote all these types of reachability information). One simple way of producing reachability information is to expand Graphplan's planning graph structure, armed with mutex propagation procedure [2]. The mutexes present at the level where the graph levels off are state invariants [21].

Exploiting the reachability information to check consistency of partial plans requires identifying the feasibility of the world states that any eventual execution of the partial plan must pass through. Although partial order plans normally do not have explicit state information associated with them, it is nevertheless possible to provide partial characterization of the states their execution must pass through. Specifically, we define the general notion of cutsets as follows:

Definition 2 (Cutsets) Pre- and post- cutsets, BV A0 and BV B7 of an action CP CZ in a plan  are defined as BV A0 B4CP CZ B5 BP  D6CTCRB4CP CZ B5CJ B4CP CZ B5, and BV B7 B4CP CZ B5 BP BXCUCUB4CP CZ B5 CJ B4CP CZ B5, where B4CP CZ B5 is the set of all conditions D4 such that there exists a link CP CX D4 A0AX CP CY where CP CX is necessarily before CP CZ , and CP CY is necessarily after CP CZ

The pre- and post-cutsets of an action can be seen as partial description of world states that must hold before and after the action CP CZ . If these partial descriptions violate the properties of the reachable states, then clearly the partial plan cannot be refined into an executable solution.

Proposition 1 If there exists a cutset that contains a mutex, then the partial plan is provably invalid and can be pruned from the search queue.

While this proposition allows us to detect and prune inconsistent plans, it is often inefficient to wait until the plan becomes inconsistent. Detecting and resolving implicit conflicts is essentially a more active approach that prevents a partial plan from becoming inconsistent by this proposition. Specifically, we generalize the notion of unsafe links as follows:

Definition 3 An action CP CZ is said to have a conflict with a causal link CP CX D4 A0AX CP CY if (CX) CJCUCP CX AU CP CZ AU CP CY CV is consistent and (CXCX) either D6CTCRB4CP CZ B5 CJ CUD4CV or BXCUCUB4CP CZ B5 CJ CUD4CV contains a mutex. A causal link CP CX D4 A0AX CP CY is unsafe if it has a conflict with some action in the partial plan.

These notions of conflict and unsafe link subsume the original notions of threat and unsafe link introduced in Section 2, because BMD4 BE BXCUCUB4CP CZ B5 also implies that BXCUCUB4CP CZ B5 CJ CUD4CV is a mutex. Therefore the generalized notion of unsafe links result in detecting a larger number of (implicit) conflicts (unsafe links) present in a partial plan.

Once the implicit conflicts are detected, they are resolved by posting disjunctive orderings as described in the previous subsection. As we shall see later, the combination of disjunctive constraints and detection of implicit conflicts through reachability information leads to quite robust improvements in planning performance.

5 Empirical Evaluation

We have implemented the techniques introduced in this paper on top of UCPOP[27], a popular partial order planning algorithm. We call the resulting planner REPOP. As mentioned in Section 2, both UCPOP and REPOP are given ground action instances, and thus neither of them have to deal with variable binding constraints. Both UCPOP and REPOP use the LIFO as the order in which open condition flaws are selected for resolution. Our empirical studies compare REPOP to UCPOP as well as Graphplan[2] and AltAlt[21], which represent two currently popular approaches (CSP search and state space search) in plan synthesis. All these planners are written in Lisp. In the case of Graphplan, we used the Lisp implementation of the original algorithm, enhanced with EBL and DDB capabilities [17]. AltAlt [22] is a state-of-the-art heuristic regression state search planner, that has been shown to be significantly faster than HSP-R [3]. The empirical studies are conducted on a 500 MHz Pentium-III with 256MB RAM, running Linux. The test suite of problems were taken from several benchmark planning domains from the literature. Some of these, including gripper, rocket world, blocks world and logistics are "parallel" domains which admit solutions with loosely ordered steps, while others, such as grid world and travel world admit only serial solutions. Efficiency of Synthesis: In Table 1, we report the total running times for the REPOP algorithm, including the preprocessing time for computing the mutex constraints (using bilevel planning graph structures [18]). Table 1 shows that REPOP exhibits dramatic improvements from its base planner, UCPOP, in gripper, logistics and rocket domains-all of which are "parallel domains." For instance, REPOP is able to comfortably generate plans with up to 70 actions in logistics and gripper domains, a feat that has hither-to been significantly beyond the reach of partial order planners. More interesting is the comparison between REPOP and the non-partial order planners. In the parallel domains, REPOP manages to outperform Graphplan. Although REPOP still trails state search planners such as AltAlt, these latter planners can only generate serial plans.

Despite the impressive performance of the REPOP over parallel domains, it remains ineffective in "serial" domains including the grid, 8-puzzle and travel world, which admit only totally ordered plan solutions. We suspect that part of the reason for this may be the inability of our heuristics to adequately account for negative interactions. Indeed, we found that the normal open conditions heuristic CW D3CR is better than our relaxed heuristic on these problems. It may also be possible that the least commitment strategies employed by the POP algorithms become a burden in serial domains, since eventually all actions need to be ordered with respect to each other. One silverlining in this matter is that most of the domains where POP algorithms are supposed to offer advantages are likely to be parallel domains from the planner's perspective-either because the actions will have durations (making the serial/parallel distinction moot) or because we want solution output by the planner to offer some degree of scheduling flexibility.

Plan Quality: We also evaluated the quality of plans generated by REPOP, since plan quality is seen as an important issue favoring POP algorithms. To quantify the quality of plans generated, we consider three metrics: (i) the cumulative cost of the actions included in the plan (ii) the minimum time needed for executing the plan and (iii) the scheduling (execution) flexibility of the plan.

For actions with uniform cost, the action cost is equal to the number of actions in the plan. Table 1 shows that REPOP produces plans with lower action cost compared to both Graphplan and AltAlt in all but one problem (rocket-ext-b).

We measure the minimum execution time in terms of the makespan of the plan, which is loosely defined as the minimum number of time steps needed to execute the plan (taking the possibility of concurrent execution into consideration). Makespan for the plans produced by Graphplan is just the number of steps in the plan, while the makespan for plans produced by AltAlt (and other state space planners) is equal to the number of actions in the plan. For a partially ordered plan  generated by REPOP, the makespan is simply the length of the longest path between CP BC and CP BD . Specifically, D1CPCZCTD7D4CPD2B4B5 BP D1CPDC CPBE CTD7D8B4CPB5, where CTD7D8B4CPB5 is the earliest start time step for the (instantaneous) action CP. To compute CTD7D8, we can start by initializing CTD7D8 to 0 for all CP BE  . Next, we repeatedly update them until fixpoint using the following rule: For all B4CP CX AU CP CY B5 BE , CTD7D8B4CP CY B5 BMBP D1CPDCCUCTD7D8B4CP CY B5BN BDB7CTD7D8B4CP CX B5CV. Table 1 shows that the solution plans generated by REPOP are highly parallel, since the makespans of these plans are significantly smaller than the total number of actions. Graphplan's solutions have smaller makespans in several problems, but at the expense of having substantially larger number of actions.

Finally, we measure the execution flexibility of a plan in terms of the number of actions in the plan that do not have any precedence relations among them. The higher this measure, the higher the number of orders in which a plan can be executed ("scheduled"). Figure 1 illustrates a parallel plan  BD and a partially ordered plan  BE , which are generated by Graphplan and REPOP, respectively. Both plans have 4 actions and a makespan value of 2, but  BE is noticeably more flexible than

 BD , since  BD implies ordering constraints such as CP BD AU CP BG and CP BE AU CP BF , but  BE does not. To capture this flexibility, we define, for each action CP, CUD0CTDCB4CPB5 as the number of actions in the plan that do not have any (direct or indirect) ordering constraint with CP. CUD0CTDCB4B5 is defined as the average value of CUD0CTDC over all the actions in the plan. It is easy to see that for a serial plan , BK CPBE CUD0CTDCB4CPB5 = 0, and consequently CUD0CTDCB4B5 BP BC. In our example in Figure 1, CUD0CTDCB4CPB5 BP BD for all CP in  BD , and CUD0CTDCB4CPB5 BP BE for all CP in  BE . Thus, CUD0CTDCB4 BD B5 BP BD and CUD0CTDCB4 BE B5 BP BE. It is easy to see that  BE can be executed in more ways than  BD . Table 1 reports the CUD0CTDCB4B5 value for the solution plans. As can be seen, plans generated by REPOP have substantially larger average values of CUD0CTDC than Graphplan in blocks world and logistics, and similar values in gripper. Graphplan produces a more flexible plan in only one problem in the rocket domain.

Before ending the discussion on plan quality, we should mention that it is possible to use post-processing techniques to improve the quality of plans produced by state-space and CSP-based planners. However, such post-processing, in addition to being NP-hard in general [1], does not provide a satisfactory solution for online integration of the planner with other modules such as schedulers and executors [6; 25].

Ablation Studies: We now evaluate the individual effectiveness of each of the acceleration techniques, viz., heuristic functions for ranking partial plans (HP), and consistency enforcement (CE).Table 2 shows the number of partial plans generated and expanded in the search when each of these techniques is added into the original UCPOP. We restrict our focus to the parallel domains where REPOP seems to offer significant advantages.

In the logistics and rocket domains, the use of CW D6CTD0CPDC heuristic accounts for the largest fraction of the improvement from UCPOP. Interestingly, CW D6CTD0CPDC fails to help scale up UCPOP even on very small problems in the gripper domain. We found that the search spends most of the time exploring inconsistent partial plans for failing to realize that a left or right gripper can carry at most one ball. This problem is alleviated by consistency enforcement (CE) techniques through detection and resolution of implicit conflicts (e.g. the conflict between CRCPD6D6DDB4CQCPD0D0BDBN D0CTCUD8B5 and CRCPD6D6DDB4CQCPD0D0BEBN D0CTCUD8B5). As a result, REPOP can comfortably solve large gripper problems, such as gripper-20.

Among the consistency enforcement techniques, both reachability analysis and disjunctive constraint representation appear to complement each other. For instance, in problem logistics.d, if only reachability analysis is used with the heuristic CW D6CTD0CPDC , a solution can be found after generating 255K nodes. When disjunctive representation is also used, the number of generated nodes is reduced by more than 15 times to 16K.

6 RelatedWork

Several previous research efforts have been aimed at accelerating partial order planners (c.f. [11; 12; 13; 16; 23; 24; 6; 4]). While none of these techniques approach the current level of performance offered by REPOP, many important ideas separately introduced in these previous efforts are either related to or are complementary to our techniques. IxTeT [6] uses distance based heuristic estimates to select among the possible resolutions of a given open condition flaw (although no evaluation of the technique is provided). It is interesting to note that IxTeT's use of distance based heuristics precedes their independent re-discovery in the context of state-search planners by McDermott [20] and Bonet and Geffner [3]. In [4], Bylander describes the use of a relaxation heuristic based on linear planning for POP; it however seems not to be very effective. The idea of postponing the resolution of unsafe links by posting disjunctive constraints has been pursued by Smith and Peot in [23] as well as by Kambhampati and Yang in [16]. Our work shows that the effectiveness of this idea is enhanced significantly by generalizing the notion of conflicts to include indirect conflicts. The notion of action-proposition mutexes defined in Smith and Weld's work on temporal graphplan [26] is related to our notion of indirect conflicts introduced in Section 4. Finally, there is a significant amount of work on flaw selection strategies (e.g., the order in which open condition flaws are selected to be resolved) [11] that may be fruitfully combined with REPOP. The techniques for recognizing and suspending recursion ("looping") during search may also make a useful addition to REPOP [24].

7 Conclusion and Future Work

The successes in scaling up classical planning using CSP and state space search approaches have generally been (mis)interpreted as a side-swipe on the scalability of partial order planning. Consequently, in the last five years, work on POP paradigm has dwindled down, despite its known flexibility advantages. In this paper we challenged this trend by demonstrating that the very techniques that are responsible for the effectiveness of state search and CSP approaches can also be exploited to improve the efficiency of partial order planners dramatically. By applying the ideas of distance based heuristics, disjunctive representations for planning constraints and reachability analysis, we have achieved an impressive performance for a partial order planner, called REPOP, across a number of "parallel" planning domains. Our empirical studies show that not only does REPOP convincingly outperform Graphplan in parallel domains, the plans generated by REPOP have more execution flexibility. This is very interesting for two reasons. First of all, most of the real-world planning domains tend to have loose ordering among actions. Secondly, the ability for generating loosely ordered plans is very important in hybrid methods that involve on-line integration of planning with scheduling.

There are several avenues for extending this work. To begin with, our partial plan selection heuristics do not take negative interactions into account. This may be one reason for the unsatisfactory performance of REPOP in serial domains. One way to account for the negative interactions, that we are considering currently, involves using the partial state information provided by the pre- and post-cutsets of actions. Our work on AltAlt [22] suggests that the cost of achieving these partial states can be quantified in terms of the level in the planning graph at which the propositions comprising these states are present without any mutex relations. Another idea we are pursuing is to use n-ary state invariants (such as those detected in [5]) to detect and resolve more indirect conflicts in the plan. Finally, a more ambitious extension that we are pursuing involves considering more general versions of POP algorithmsincluding those that handle partially instantiated actions, as well as actions with conditional effects and durations.