A Critical Look at Critics in HTN Planning
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Planning. Pages 1592-1597.
© 1995 International Joint Conferences on Artificial Intelligence
Abstract
Detecting interactions and resolving conflicts is one of the key issues for generative planning systems. Hierarchical Task Network (HTN) planning systems use critics for this purpose. Critics have provided extra efficiency and flexibility to HTN planning systems, but their procedural -and sometimes domain-specificnature has not been amenable to analytical studies. As a result, little work is available on the correctness or efficiency of critics . This paper describes a principled approach to handling conflicts, as implemented in UMCP 1 , an HTN planning system. Critics in UMCP have desirable properties such as systematicity, and the preservation of soundness and completeness.
- [Allen et al. , 1990] Allen , J .; Hendler, J . and Tate, A. editors. Readings in Planning. Morgan-Kaufmann , San Mateo, CA, 1990.
- [Chapman, 1987] Chapman, D. Planning for conjunc- tive goals. Artificial Intelligence, 32:333-378 , 1987.
- [Collins and Pryor, 1992] Collins, G. and Pryor, L. Achieving the functionality of filter conditions in a partial order planner In Proc. AAAI-92, 1992, pp. 375-380.
- [Dean, 1983] Dean, T . Time map maintenance. Techni- cal Report 289, Yale University, October 1983.
- [Drummond, 1985] Drummond, M. Refining and Ex- tending the Procedural Net. In Proc. IJCAI-85, 1985. IJCAI
- [Erol et al., 1994a] Erol, K.; Hendler, J. and N au, D. Semantics for Hierarchical Task Network Plan- ning. CS-TR-3239, UMIACS-TR-94-31 , ISR-TR- 95-9 , University of Maryland, March 1994.
- [Erol et al. , 1994b] Erol, K.; Hendler, J . and Nau, D. Complexity results for hierarchical task-network planning. To appear in Annals of Mathematics and Artificial Intelligence Also available as Technical re- port CS-TR-3240, UMIACS-TR-94-32 , ISR-TR-95- 10 Computer Science Dept. , University of Mary- land, March 1994.
- [Erol, 1995] Erol, K. HTN Planning: Formalization , Analysis, and Implementation. Ph.D . Dissertation, Computer Science Dept ., University of Maryland, 1995. In preparation.
- [Fikes and Nilsson, 1971] Fikes, R. E. and Nilsson , N. J . STRIPS : a new approach to the application of the- orem proving to problem solving . Artificial Intelli- gence, 2(3/4):189-208, 1971. IJCAI
- [Kambhampati and Hendler , 1992] Kambhampati , S. and Hendler, J. "A Validation Structure Based 1698 PLANNING Theory of Plan Modification and Reuse" Artificial Intelligence , May, 1992.
- [Kambhampati, 1992] Kambhampati, S. "On the utility of systematicity: understanding trade-offs between redundancy and commitment in partial-ordering planning," unpublished manuscript, Dec ., 1992.
- [Kambhampati et al., 1995] Kambhampati, S.; Knoblock, C. and Yang, Q. Planning as refinement search: A unified framework for evaluating design tradeoffs in partial order planning . To appear in Ar- tificial Intelligence, Special Issue on Planning. [Kanal and Kumar, 1988] Kanal , L. and Kumar, V. Search in Artificial Intelligence, Springer-Verlag, 1988.
- [McAllester and Rosenblitt, 1991] McAllester, D. and Rosenblitt, D. Systematic nonlinear planning. In Proc. AAAI-91, 1991.
- [Minton et al., 1991] Minton, S.; Bresina, J . and Drum- mond, M. Commitment strategies in planning. In Proc. IJCAI-91, 1991.
- [Sacerdoti, 1977] Sacerdoti, E. D. A Structure for Plans and Behavior, Elsevier-North Holland. 1977.
- [Sussman , 1990] Sussman , G.J ., HACKER: a compu- tational model of skill acquisition, MIT AI Lab Memo 1973, also in Allen, 1990, Readings in Plan- ning. Morgan Kaufmann.
- [Tate et al., 1990] Tate, A.; Hendler, J . and Drummond, D. AI planning: Systems and techniques. AI Magazine , (UMIACS-TR-90-21, CS-TR-2408) :61- 77, Summer 1990
- [Tate, 1977] Tate, A. Generating Project Networks In Proc. IJCAI-77, 1977. pp . 888-893 . IJCAI
- [Tate et al., 1994] Tate, A.; Drabble, B. and Dalton, J. The Use of Condition Types to Restrict Search in an AI Planner . Proc. AAAI-94. pp . 1129-1134.
- [Vere, 1983] Vere, S. A. Planning in Time: Windows and Durations for Activities and Goals . IEEE Transactions on Pattern Analysis and Machine In- telligence, PAMI-5(3) :246-247, 1983.
- [Wilkins, 1988] Wilkins, D. Practical Planning: Extend- ing the classical AI planning paradigm, Morgan- Kaufmann , CA. 1988.
- [Yang, 1990] Yang, Q. Formalizing planning knowledge for hierarchical planning Computational Intelli- gence Vol.6 ., 12-24, 1990.
- [Yang et al., 1993] Yang, Q.; Nau, D.S .; and Hendler, J . Merging separately generated plans with re- stricted interactions. Computational Intelligence, 9(1), February 1993.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Detecting interactions and resolving conflicts is one of the key issues for planning systems. The importance of this issue was realized as long ago as the 1970s in early AI planning systems such as STRIPS [Fikes and Nilsson, 1971] and HACKER [Sussman, 1990] . The in troduction of task networks and task decomposition in NOAH [Sacerdoti, 1977] provided an even richer set of interactions and resolution methods, and a component of NOAH called the critic mechanism was designed for han dling these interactions. Critics helped prune the search space by detecting dead ends in advance and by resolving many types of conflicts as soon as they appeared. Crit ics could also draw upon domain-specific information to do their job more efficiently. The power of the critic mechanism was quickly realized and adopted by hierar chical task network (HTN) planning systems [Tate, 1977; Vere, 1983; Wilkins, 1988].
*This work was supported in part by NSF Grants DDM9201779, IRI-9306580 and NSF EEC 94-02384, AFOSR (F49620-93-1-0065), the ARPA/Rome Laboratory Planning Initiative (F30602-93-C-0039), and ONR grant N00014-91-J1451. Any opinions, findings, and conclusions or recommen dations expressed in this material are those of the authors and do not necessarily reflect the views of the National Sci ence Foundation or ONR.
1 Universal Method-Composition Planner
Some of the critics identified by Sacerdoti [1977] (based in part on Sussman's [1990] earlier work) include:
- Resolve Conflicts. The conflicts handled by this critic, later referred to as "deleted-condition" inter actions, have received the bulk of the attention in the literature.
- Eliminate redundant preconditions. This critic both handled "phantom" conditions and found cases where two different procedural networks added the same primitive prior to usage.
In addition to the interactions handled by these critics, several other situations that can arise in planning have been identified in the literature:
- For his DEVISER system, Vere [1983] has discussed temporal interactions between the times at which actions must occur. 2 He has used temporal window ing and performed an analysis thereof to eliminate possible reductions.
- Wilkins' SIPE system [Wilkins, 1988] has added sev eral different mechanisms for recognizing resource interactions and for allowing user preferences to be considered when making a choice among reductions.
- Yang, Nau, and Hendler [Yang et al., 1993] have discussed a general "action-precedence" interaction that, while less general than deleted-condition in teractions, can be exploited in some planning situ ations. They also have discussed a "simultaneous action" interaction that arises in some domains .
- To handle iteration in plans, Drummond [1985] has proposed several extensions to the procedural net, and an extension to Sacerdoti's Resolve-conflicts critic.
- NONLIN [Tate, 1977] and O-Plan2 [Tate et al., 1994] provide various condition types which can be used to reduce the search space. In O-Plan2, Con straint Managers support decision making of the planner by providing complete information about the constraints they are managing.
- A number of special-purpose "domain dependent" planning systems have identified interactions occur ring only in the particular domain for which the sys-
2See also [Dean, 1983].
tern is being developed. Typically special-purpose heuristics are introduced to exploit this knowledge.
As can be seen, the many interactions which need to be handled during planning go beyond the (relatively) well-understood deleted-condition interaction. To han dle these interactions, implemented planning systems usually use critics or similar mechanisms. Unfortunately it is difficult for a user to exploit these planning sys tems effectively (i.e. reasonably efficiently and correctly) without an in-depth understanding of the implementa tion details of the critic mechanisms . To reason about analytical properties of such mechanisms (i.e. system aticity, soundness, completeness) , a general model of in teractions and critics is clearly needed.
The work described in [Erol et al., 1994a; 1994b] presents a formal model for HTN planning, which pro vides a constraint-based representation for interactions among t.asks and enables principled approaches to con flict detection and handling in HTN planning. This pa per presents conflict management and constraint han dling techniques based on that framework. Among the properties of .these techniques are soundness, complete ness and systematicity. These techniques have been im plemented in UMCP, an HTN planning system.
2 An Overview of HTN planning
Here is a brief informal description of HTN planning. For a precise formal description, see [Erol et al., 1994a; 1994b] .
HTN planning representations for actions and states of the world are similar to those used in STRIPS-style planning. 3 Each state of the world is represented by the set of atoms true in that state. Actions , which in HTN planning are usually called primitive tasks, correspond to state transitions ; i.e., each action is a partial mapping from the set of states to the set of states.
The primary difference between HTN planners and STRIPS-style planners is in what they plan for , and how they plan for it. In STRIPS-style planning, the objec tive is to find a sequence of actions that will bring the world to a state that satisfies certain conditions or "at tainment goals." Planning proceeds by finding operators that have the desired effects and by making the precon ditions of those operators into subgoals. In contrast , HTN planners search for plans that accomplish task net works, which can include things other than just attain ment goals; and they plan via task decomposition and conflict resolution, which shall be explained shortly.
A task network is a collection of tasks that need to be carried out, together with constraints on the order in which tasks can be performed, the way variables are instantiated, and what literals must be true before or after each task is performed. Unlike STRIPS-style plan ning, the constraints may or may not contain condi tions on what must be true in the final state. For-
3 The term "STRIPS-style" planning is used to refer to any planner (either total- or partial-order) in which the planning operators are "STRIPSoperators" (i.e., operators consisting of three lists of atoms: a precondition list, an add list , and a delete list) .

mally, a task network is a syntactic construct of the form [(nt :at) ... (nm : am),¢>], where
- each a ; is a task;
- n; is a label for a; (to distinguish it from any other occurrences of a; in the network) ;
- ¢> is a boolean formula constructed from variable binding constraints such as (v = v') and (v = c), ordering constraints such as ( n -< n'), and state constraints such as (initially /), (n , l), (I, n), and (n, l, n'), where v, v' are variables, l is a literal, c is a constant, and n, n' are node labels. 4 Intu itively, (n-< n') means that the task labeled with n must precede the one labeled with n'; (n , l) , (1 , n) and (n, l, n') mean that l must be true in the state immediately after n, immediately before n, and in all states between n and n', respectively. (initially l) means that l must be true in the initial state. Both negation and disjunction are allowed in the constraint formula.
As an example, Fig. 1 shows a blocks-world task net work and its graphical representation. In this task net work there are three tasks: clearing Vt, clearing v2, and moving v1 to v2. The task network also includes the constraints that moving v1 should be done last , v1 and v2 should remain clear until we move Vt , and that the variable v3 is bound to the location of v1 before v1 is moved.
A task network that contains only primitive tasks is called a primitive task network. Such a network might occur, for example, in a scheduling problem. In this case, an HTN planner would try to find a schedule (task ordering and variable bindings) that satisfies all the con straints.
In the more general case, a task network can contain non-primitive tasks, which the planner needs to figure out how to accomplish. Non-primitive tasks cannot be
4 We also allow node labels in the constraints to be of the form first[n;,nj, ... ] or last[n;,nj, ... ] so that we can refer to the task that starts first and to the task that ends last among a set of tasks, respectively.
- Input a planning problem P.
- If P contains only primitive tasks, then resolve the conflicts in P and return the result . If the conflicts cannot be resolved, return failure.
- Choose a non-primitive task t in P.
- Choose an expansion for t.
- Replace t with the expansion.
- Use critics to find the interactions among the tasks in P , and suggest ways to handle them.
- Apply one of the ways suggested in step 6.
- Go to step 2.
Figure 2: The Standard HTN Planning Procedure.
executed directly, because they represent activities that may involve performing several other tasks. For example the task of traveling to New York can be accomplished in several ways, such as flying, driving or taking the t~ain . Flying would involve tasks such as making reservatwns, going to the airport , buying ticket, boarding the plane; and flying would only work if certain conditions were satisfied: availability of tickets, being at the airport on time, having enough money for the ticket , etc.
Ways of accomplishing non-primitive tasks are repre sented using constructs called methods. A method is a syntactic construct of the form (a, d) where a is a non primitive task, and d is a task network. It states that one way to accomplish the task a is to achieve all the tasks in the task network d without violating the con straints in d. For example, the task network in Figure 1 presents one possible way of accomplishing on( VI, v2) , thus ( achieve[on( VI, v2)], d) is a method for Blocks world domain, where d is the task network in Figure 1.
An HTN problem is represented as a triple P = (d I D) where d is the task network we need to plan ' ' ' for, I is the initial state, and 1) is the set of operators and methods associated with the planning domain.
A number of different systems that use heuristic algo rithms have been devised for HTN planning [Tate, 1977; Vere, 1983; Wilkins, 1988], and several recent papers have tried to provide formal descriptions of these algo rithms [Yang, 1990; Kambhampati and Hendler, 1992] . Figure 2 presents the essence of these algorithms: HTN planning works by expanding tasks and resolving con flicts iteratively, until a conflict-free plan can be found that consists only of primitive tasks.
Expanding or reducing each non-primitive task (steps 3-5) is done by finding a method capabl.e of accom plishing the non-primitive task, and replacmg the non primitive task with the task network produced by the method. Details of how to do the task expansion is pre sented in [Erol et al., 1994a; 1994b].
The task network produced in Step 5 may contain con flicts caused by the interactions among tasks . The job of finding and resolving such interactions is performed by critics. This is reflected in Steps 6 and 7 of Figure 2: after each reduction, a set of critics is checked so as to recognize and resolve interactions between this and any
- Input a planning problem P =< d, I, 1) >.
- Initialize OPEN-LIST to contain only d.
- If OPEN-LIST is empty, then halt and return "NO SOLUTION."
- Pick a task network tn from the OPEN-LIST.
- If tn is primitive, its constraint formula is TRUE, and tn has no committed-but-not-realized constraints, then return tn as the solution.
- Pick a refinement strategy R for tn .
- Apply R to tn and insert the resulting set of task networks into OPEN-LIST.
- Go to step 3.
Figure 3: High-level Refinement-Search in UMCP
other reductions. Thus, critics provide a general mecha nism for detecting interactions early, so as to reduce the amount of backtracking.
3 Planning in UMCP
One way of finding solutions to HTN planning prob lems is to generate all possible expansions of the input task network to primitive task networks, then generate all possible ground instances (assignment of constants to variables) and total orderings of those primitive task networks and finally output those whose constraint for mulae evaluate to true. However, considering the size of the search space, it is more appropriate to try to take advantage of the structure of the problem, and prune large chunks of the search space by eliminating in ad vance some of the variable bindings, orderings or meth ods that would lead to dead-ends. To accomplish this UMCP uses a branch-and-bound approach [Kanal and Kumar, 1988].
A task network can be thought of as an implicit rep resentation for the set of solutions for that task network. UMCP works by refining a task network into a set of task networks, whose sets of solutions together make up the set of solutions for the original task network. Those task networks whose set of solutions are determined to be empty are filtered out . In this aspect, UMCP nicel~ fits into the general refinement search framework descnbed in [Kambhampati et al., 1995].
Figure 3 contains a sketch of the high-level search al gorithm in UMCP. Search is implemented by keeping an OPEN-LIST of task networks in the search space that are to be explored; by altering how task networks are picked from the OPEN-LIST and how they are in serted, depth-first, breadth-first , best-first and various other search techniques can be employed. Step 5 checks whether tn is a solution node; if all tasks in tn are prim itive the constraint formula is the atom TRUE, and the list ~f constraints that have been committed to be made true but not yet made true is empty, then all task order ings and variable assignments consistent with the aux iliary data structures associated with tn are plans for the original problem. 5 Those plans can be easily enumerated. If tn is not a solution node, then it is refined by some refinement strategy R, and the resulting task networks are inserted back into the OPEN-LIST.
5 Constraints and the data structures will be discussed in
Three types of refinement strategies used in UMCP are task reduction, constraint refinement, and user-specific critics. Task reduction involves retrieving the set of methods associated with a non-primitive task in tn, ex panding tn by applying each method to the chosen task and returning the resulting set of task networks. User specific critics is one of the places where UMCP can be tailored for specific domains. If a domain-specific refine ment strategy is available, it can be used to improve the performance of the planner. This paper will focus on constraint refinement.
4 Constraint Handling in UMCP
4.1 Overview
This section contains an overview of the constraint han dling mechanisms in UMCP, which serve as domain in dependent critics. They are designed to preserve sound ness, completeness, and systematicity. Details for each type of constraint are summarized in the next section. For a full description, see [Erol, 1995).
The three types of decisions in HTN planning are the choice of method for each non-primitive task, the choice of constant to assign to each variable, and the orderings of tasks. Of those three, the choice of method is directly reflected in the task network (i .e. in the list of tasks and the constraint formula). Auxiliary data structures are required for the other two. Thus, along with each task network, UMCP keeps a list of possible values for each variable values until the size of the list exceeds a threshold, and a partial order graph of task nodes. Both of those structures will be referred to as commitments. Dealing with some constraints might not be possible at the current level of detail in a task network; dealing with those constraints has to be postponed until the task net work is refined further . Until then, those constraints are stored in a list called the Promissory List (the list of constraints the planner has committed to make true, but has not done so yet).
The four phases of constraint refinement in UMCP are constraint selection, constraint update, constraint prop agation and constraint simplification, which are carried out sequentially.
Constraint selection involves deciding which con straints in the constraint formula or in the commit ments to work on. Constraint selection returns a list of constraint formulae, where each formula is a conjunct of atomic constraints. The list of constraint formulae is selected in such a way that (a) the formulae in the list are mutually inconsistent in the presence of com mitments (in order to preserve systematicity), and (b) the list covers all possibilities (in order to preserve com pleteness). Some examples of constraints that may be selected include (i) an atomic constraint 6 and its nega tion, (ii) a conjunct of unit clauses from the constraint formula, or (iii) a set of possible constraints for a vari able - i.e. if the set of possible values for a variable v are { truck1 , truck2, truck3} , UMCP may branch out on the constraints (v = truckt), (v = truck2), (v = truck3) .
detail in the next 'section.
6 An atomic constraint refers to any instance of the types of constraints discussed in Section 2.
For each constraint formula in the list computed in the constraint selection phase, the constraint update phase computes a task network for every possible way of mak ing the selected formula true by further restricting the commitments of the task network. For each atomic con straint in the selected constraint formula, the following steps are executed: first it is evaluated; if it evaluates to true , it can be ignored, if it evaluates to false, the task network fails , otherwise further restrictions are placed on the commitments (variable bindings, orderings etc.) to make the constraint necessarily true in all further re finements of the task network. There might be multiple possible ways of accomplishing that , thus even atomic constraint update computes a list of task networks rather than a single task network. However, UMCP does con straint update in such a way that there is no overlap among the set of solutions to the task networks in this list. For some constraints, at the current level of detail in the task network, it might not be possible via restric tions on commitments to ensure that the constraint will be true in all further refinements. Those constraints are simply recorded in the Promissory List.
In the constraint propagation phase, UMCP evaluates and simplifies the constraints in the Promissory List of each task network produced during the constraint up date phase. If any of those constraints evaluate to false , the task network fails; those that evaluate to true are removed from the Promissory List. Constraint update is performed on the remaining simplified constraints if possible at the current level of detail in the task net work. This phase is repeated until no more propagation is possible.
UMCP contains evaluation and simplification routines for every type of constraint , as described in the next sec tion. These routines are used in the constraint simplifi cation phase to evaluate and simplify the constraint for mulae of the task networks produced during the propa gation phase. For instance if part of a conjunct evaluates to true, that part is dropped, if it evaluates to false, the whole conjunct evaluates to false . Disjuncts are treated analogously. Those task networks whose constraint for mulae evaluate to false are pruned.
4.2 Details
This section describes how constraint evaluation and up date is done for each type of constraint. Update always involves evaluating the constraint and it fails whenever the constraint evaluates to false. This is omitted from the explanations below for brevity.
Variable Binding Constraints
Type: (v =a)
Evaluation: Return true if constant a is the only pos sible value for variable v ; return false if a is not a possible value for v; return ( v =a) otherwise.
Update: To make it true, set the possible value list for v to a, replace v with a throughout the task network. To make it false, remove a from the possible value list for v. If v has only one possible value left, substitute that value for v throughout the task network.
Type: Cv1 = v2)
Evaluation: Return true if both v1 and v2 have the same one possible value; return false if they do not have any common possible values or if negation of the con straint is in the Promissory List; return the constraint itself otherwise.
Update: To make it true, set the possible value list for v2 to the intersection of possible values for v1 and v2, set the possible value list for v1 to v2, and replace v1 with v2 throughout the task network. To make it false, insert its negation in the Promissory List.
Ordering Constraints
Ordering constraints are handled by querying and mod ifying the partial order graph. They are of the form (node-expression ~ node-expression).
A node-expression can be in either of the 2 forms: first[n1, n2, ... , nk], or last[n1, n2, ... , nk]. Thus, a to tal of four types of ordering constraints need to be considered. 7
Let A; = { n;1, ... , n;k} be lists of node labels for i = 0, 1. Recall that first[Ao] and last[Ao] refer to the node which is ordered to be the first and the last among the nodes in the expansion of nodes { no1, ... , nok}, re spectively.
Let's define 0;, I; ~ A; as the nodes that are not or dered after (respectively before) any node in Ao U A1.
Let's define B;, C; ~ A; as the nodes that are not ordered after (respectively before) some node in A; and are not ordered after(respectively before) all nodes in A(i+1) mod 2·
Type: (first[Ao] ~ first[A1])
Evaluation: Return true if 0 1 is empty; return false if Oo is empty; return (first[Oo] ~ first[01]) otherwise. Update: If Oo contains a single primitive task put links from the node in Oo to each node in 0 1 in the partial order graph; otherwise insert (first[Oo] ~ first[Ot]) into the Promissory List.
Type: (first[Ao] ~ last[A1])
Evaluation: Return false if Bo or C1 is empty; return true if some node in Bo is ordered before one in C1; otherwise return (first[Bo] ~ last[Ct]).
Update: If both B0 and C1 contain single primi tive tasks, put a link between them, otherwise insert (first[Bo] ~ last[C1]) into the Promissory List.
Evaluations and updates of (last[Ao] ~ first[A1]) and (last[Ao] ~ last[A1]) are done analogously.
State Constraints
The set of atoms in the initial state are stored in a dis crimination tree for fast querying. Negative literals need not be stored due to the closed world assumption. Note that "...., (initially /)" and "(initially --,/)" have the same meaning.
7 Ordering constraints which contain negation or refer to single node labels can be converted to one of those four forms.
Type: (initially l)
Evaluation: Return true if all ground instances of l that are consistent with possible values lists in com mitments are in initial state; return false if none of the ground instances of l that are consistent with possible values lists are in initial state.
Update: To make it true (false) do the following: If l has only one variable, restrict that variable to values for which l is true (false) in the initial state. If l con tains k > 1 variables, for each combination of values for the first k - 1 variables, output a task network by as signing those variables the corresponding constants, and restricting the value of the last variable so as to make l true (false) in the initial state. Combinations of val ues for which this is not possible need not be considered. For example, in order to make (initially type[v,truck]) true in transport logistics domain, it suffices to restrict possible values for v to constants of type truck.
The state constraints of the form (I, n) are evaluated and updated by computing the effectors. An effector of l is either (i) a primitive task with an effect that can unify with l or ....,[, (ii) the initial state, (iii) a compound task whose expansion might contain such a primitive task, or (iv) a committed-to state constraint that is stored in the Promissory List whose literal can unify with l or ....,[. Those effectors that are ordered after n or shadowed by 8 some other effector of l are ignored. If all effectors of l are positive then (/, n) is true, if all are negative than it is false, otherwise it is unknown yet. Update is delayed if some of the positive effectors are compound tasks, and the constraint is recorded in the Promissory List. Oth erwise for each positive effector e a new task network is created where e is the establisher of 1 with added con straints (preserve l e n) 1\ (preserve ....,[ e n )preventing any action between e and n from denying or asserting /, respectively.
Evaluating and/or updating constraints of the form ( n, l) is delayed until n refers to a single primitive task symbol. In that case ( n, 1) evaluates to true if the action labeled by n asserts l, it evaluates to false if that action denies/, otherwise it evaluates to (/, n).
Constraints of the form ( n, 1, n') are converted to ( n' -< n) V [(n ~ n') 1\ (n, /) 1\ (preserve l n n')] and handled as such.
4.3 Properties of Constraint Refinement
As discussed in Section 3, constraint refinement takes a task network tn as input, and returns a list of task networks R(tn). We can now demonstrate the properties of constraint refinement in UMCP:
- Soundness: Any solution to any task network in R(tn) is also a solution for tn. Thus constraint refinement does not introduce invalid solutions. UMCP satisfies this property because commitments in task networks grow monotonically, and con straints in the Promissory List are removed only as they become necessarily true.
8 An effector x shadows an effector y if x is ordered between y and n, and whenever an effect of y codesignates with 1, so does an effect of x.
- Completeness: Any solution for tn is also a solution for some task network in R(tn). Thus constraint refinement does not eliminate any valid solutions. UMCP satisfies this property because any time a constraint is selected in constraint selection phase, its negation is also selected (unless it contradicts with the commitments or the constraint formula), and all possible ways of making a constraint true are tried in the constraint update phase.
- Systematicity: The set of candidate solutions for each task network in R(tn) are mutually disjoint. Thus UMCP does not examine the same candidates multiple times. The way systematicity is accom plished in UMCP is by making sure (a) the branches in constraint selection are mutually exclusive (i.e. any two conjuncts have a common literal, positive in one, negated in the other); (b) there is no over lap among the solution sets to the task networks produced in update phase.
5 Related Work
Causal links are used by POCL planners such as SNLP [McAllester and Rosenblitt, 1991] to establish pre conditions and to detect threats. Causal links are also employed by UMCP in the form of special state con straints stored in the Promissory List. SNLP's threat removal process is similar to how UMCP handles those special constraints in its constraint propagation phase.
[Chapman, 1987] introduced the MTC (modal truth criterion) to tell whether a literal is true at a given point in a partially-ordered plan. In order to evaluate state constraints, UMCP uses an extended version ofthe MTC that also accounts for compound tasks. UMCP's ex tended MTC algorithm runs in quadratic time-and it is directly applicable for computing Chapman's MTC, for which the other known algorithms run in cubic time.
NOAH [Sacerdoti, 1977] employs its resolve conflicts critic to deal with deleted-condition interactions, which are explicitly represented by state constraints in UMCP. The constraint refinement techniques of UMCP guaran tees these interactions will be handled without sacrificing soundness or completeness.
UMCP evaluates each constraint before trying to make it true, and skips those constraints that are already true, and hence it emulates NOAH's eliminate redundant pre conditions critic.
HTN planners often allow several types of conditions in methods. How to deal with those conditions has been a topic of debate.
NONLIN [Tate, 1977] evaluates filter conditions as soon as they are encountered, using the QA (Question Answering) mechanism. QA returns false unless it can verify those conditions to be necessarily true, even if the conditions are possibly true. Thus, NONLIN often backtracks over filter conditions which would have been achieved by actions in later task expansions or by more ordering and variable binding commitments. As a result, NONLIN may fail to find a solution when a solution ex ists, or may miss a short and simple solution and do much more work to find a longer and more complicated solution.
At first glance, the problems such as these might seem to argue against the use of filter conditions: at one ex treme, using filter conditions immediately to prune the search space sacrifices completeness, and at the other extreme, postponing their use until the plan is complete (so as to preserve completeness) is inefficient. 9
Although the above argument is partially correct, it ignores a third possibility that lies between the two ex tremes. In general, to preserve completeness, a plan ner cannot use a filter condition to prune the search space unless the filter condition evaluates to "necessar ily false" -but this does not necessarily require that the task network has been expanded into a primitive and totally-ordered plan. Instead, UMCP simply records the filter conditions in the Promissory List and prunes the task network only when one of them becomes necessarily false.
More specifically, UMCP handles filter conditions and other constraints as follows:
- Some instances of variable binding, ordering, and state constraints can be dealt with immediately. For example, conditions (e.g., an object's type) that are not affected by the actions are represented by con straints of the form (initially 1). Such constraints can be evaluated at any time by querying the initial state, and they can be committed to by appropri ately restricting the possible values for the variables in l.lo
- Those constraints that cannot be dealt with imme diately are stored in the Promissory List, and are processed in the constraint propagation phases.
Constraints in UMCP go through three stages: they first appear in constraint formula; then possibly in the Promissory List if they cannot be dealt with at the time they are selected in constraint selection phase; and fi nally they are reflected in restrictions on possible values for variables and task orderings. This three-stage ap proach facilitates dealing with the disjunctions in the constraint formula, and by postponing its processing of some types of constraints, UMCP preserves complete ness without sacrificing efficiency.
6 Conclusion
Dealing with numerous types of interactions is an im portant aspect of planning systems. The work described in [Erol et al., 1994a; 1994b] has provided a formal frame work for representing interactions and conflicts via con straints, and in this paper we have introduced techniques for constraint handling as a means for detecting interac tions and resolving conflicts. Those techniques preserve soundness, completeness, systematicity, and they have been implemented in UMCP, an HTN planning system.
9 In fact, Collins and Pryor [1992] have made a similar argument against filter conditions in the context of planning with STRIPS-style operators.
10 SIPE [Wilkins, 1988] uses a "sort hierarchy" for this pur pose, the only difference in UMCP is that UMCP allows ar bitrary boolean formulae constructed from all types of con straints, instead of a conjunct of constraints as in SIPE.
By instantiating the constraint selection strategy in different ways, various commitment strategies discussed in the literature can be used by UMCP. For example, variable instantiation can be done before anything else (as in NONLIN) , all primitive tasks can be totally or dered as soon as they appear in task networks, or task expansions can be deferred until all conflicts have been resolved (least commitment) . Currently, we are design ing experiments to empirically evaluate these techniques.
UMCP's constraint-handling mechanism provides the capabilities of many domain-independent critics dis cussed in the literature, and UMCP's user-specific critics module can be used to incorporate domain-specific crit ics as well. The modular and formal nature of UMCP makes it readily extensible. We are currently exploring ways of extending UMCP's constraint-handling mecha nism to handle numerical and complex temporal con straints so that it can do deadline and resource man agement, and provide the capabilities of other domain independent critics.
@inproceedings{ijcai1995p205,
title = {A Critical Look at Critics in HTN Planning},
author = {Erol, Kutluhan and Hendler, James A. and Nau, Dana S. and Tsuneto, Reiko},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {1592--1597},
year = {1995},
note = {Planning},
url = {https://ijcai.org/proceedings/1995/205},
}
TY - CPAPER TI - A Critical Look at Critics in HTN Planning AU - Erol, Kutluhan AU - Hendler, James A. AU - Nau, Dana S. AU - Tsuneto, Reiko T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 1592 EP - 1597 UR - https://ijcai.org/proceedings/1995/205 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: