Par-KAP: a Knowledge Acquisition Tool for Building Practical Planning Systems
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Planning and Scheduling. Pages 1246-1252.
© 1997 International Joint Conferences on Artificial Intelligence
Abstract
Recently, attention has b ee n focused on providing Knowledge Acquisition (KA) support for building practical planning systems. Such support is needed to guide a knowledge engin ee r in selecting planning methods, as well as for building and validating th e planning knowl edge-base for a given practical domain . Following current practice in knowledge acquisition, developing KA tools for planning requir es that a number of planning knowledge components are made explicit. This includ es explicating (i) a planning domain onto logy, (ii) a library of problem-solving methods (PSMs) used in planning, and (iii) a set of domain requirements that are used to select a suitable PSM. In this paper, we summariz e the planning knowledge components which we have identified in previous work , and, based on these , present an implementation (Par-KAP) that can exp loit th ese models to aid knowledge engineers in constructing practical planning systems.
- Andersen et a/. , 1 994]
- W . Andersen, J. Hendler, M . Evett, and B. Ketter. Massive parallel m atching of knowledge structures. In H. Kitano and J. Hendler, editors , Massively Parallel Artificial Intellig en ce . AAAI/MIT Press , 1994.
- [Benjamins et a/., 1996] V. Richard Ben- jamins, Leliane Nunes de Barros , and Andre Valente. Constru cting planners through problem-solving meth- ods. In Knowledge Acquisition Workshop -KA W '96 (Banff) , 1996.
- V. R . Ben]amins. Problem-solving methods for diagnosis and their role in knowledge ac- quisition. International Journal of Expert Systems: Resea rch and Applications, 8(2):93-120 , 1995.
- [Breuker and van de Vel de, 1994] J. Breuker and W. van de Velde , editors. CommonKADS Library for Expertise Modeling. lOS Press , Amsterdam , The Netherlands, 1994.
- [Chandrasekaran, 1990] B. Chandrasekaran. Design problem solving: A task analysis. AI Magazin e, 11 :59- 71 , 1990 . .
- [Chapman , 1987] D. C hapman . Planning for conjunc- tive goals. AI, 32:333-377, 1987.
- [Chien , 1996] Steve A. Chien. Knowledge acquisition , validation and m aintenan ce in a planning system for automated image processing . In KA W'96. Banff, 1996 .
- [Cottam and Shadbolt , 1996] Hugh Cottam a nd Nigel Shadbolt. Knowledge acquisition for search and res- cue. In KA W '96. Banff, 1996.
- [de Ba rros et a/. , 1996] L. Nunes de Barros , A. Valente, and V . R . Benj a mins . Modeling planning tasks. In AIPS-96, pages 11-18, 1996.
- Hendler and McDermott , forthcoming] J. Hen dler and D . McDermott. AI Planning S yst ems, chapt ers circu- lated for review. Morgan Kaufma nn , for t hcoming.
- [McAllester and Rosenblitt , 1991] D. McAllester and D. Rosenblitt. Systematic nonlinear planning. In Proc. of AAA I-91 , pages 634-639, Ana heim , CA , 1991.
- [M cCart hy and Hayes, 1969] J. McCarthy an d P. J. Hayes. Some philosophical problems from the stand- point of a rtifi cial intelligence. In Machin e Int ellig ence 4, 1969.
- [Orsvarn, 1996] K . Orsvarn. Principles for libraries of task decomposition methods -conclusions from a case-study. In N. Shadbolt , K. O 'Hara, and G. Schreiber , editors , Lecture Notes in Artificial In- t ellig ence, 1076, EKA W-96 , pages 48-65. Springer- Verlag, 1996.
- [Schreiber et a/., 1994] A. Th. Schreib er , B. J. Wielinga, R . de Hoog , J. M. Akkermans , and W . Van de Velde. CommonKADS: A comprehensive m ethodology for KBS development. IEEE Expert, 9(6):28-37, Decem- ber 1994.
- [Tate et a/., 1990] A. T ate, J. Hendler , and M. Drum- mond. Readings in planning, 1990.
- [Tate, 1996] A . Tate , editor. Advanced planning t echnol- ogy -t echnological achieve ments of th e ARPA/Rome Planning Initiative. AAAI Press, 1996.
- [Tu and Musen , 1996] Samson W . Tu and Mark A . Musen . Episo di c refinment of episodic skeletal plan refinment. In KA W '96. Banff, 1996.
- [Valente, 1995] A. Valente. Knowledge level analysis of planning . SIGART Bulletin , 6(1):33-41, 1995 .
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
Constructing a planner for a particular application is a difficult job, for which few knowledge acquisition tools currently exist. Due to an increasing need for the build ing of planning systems that can handl e real world ap plications, knowledge engineering efforts need to focus on the following questions:
- Is a particular practical planning system from the literature suitable for a given domain?
- What type of domain knowledge is required for the application and how can it be represented?
*This research was supported in part by grants from ONR (N00014-J-91-1451), ARPA (N00014-94-1090, DAST-95C003, F30602-93-C-0039) , and the ARL (DAAH049610297). Dr. Hendler is also affiliated with the UM Institute for Sys tems Research (NSF Grant NSF EEC 94-02384).Leliane is also supported by CNPq,a Brazilian Research Grant.
1 Author is supported by the Netherlands Computer Sci ence Research Foundation with financial support from the Netherlands Organisation for Scientific Research (NWO), and by the European Commission through a Marie Curie Research Grant (TMR).
In previous work , we have presented different parts of the library: knowledge roles and domain models [Va lente, 1995), basic methods and the task-method decom position structure [de Barros et al., 1996], and suitability criteria [Benjamins et al., 1996]. In this paper, we fo cus on the extension of these methods to control knowl edge, and on the implementation of a KA system for supporting the development of planners. In Section 2, we briefly summarize our past work on a KA framework for planning and on how it is extended for control knowl edge. This is followed in Section 3 with a discussion of Par-KAP, an implemented KA prototype that uses our framework. In Section 4 we give examples of how Par KAP supports the construction of planning systems. It should be noted that the aim of this work is not to cover all existing planning methods in the AI literature 1 , but to show how an extendible library can help to construct planners for particular application domains by providing a high-level, abstract synthesis of the available planning methods.
2 A library of PSMs for planning
In this section we present an overview of our previous work and discuss the extension to control knowledge for planning.
2.1 A domain ontology for planning
One of the critical elements in the analysis of a plan ning method is specifying the different roles that do main knowledge plays during the planning process. In the planning literature, domain knowledge is defined as static knowledge about the world which is only consulted during planning, but not manipulated. However, from a KA perspective, we must consider how this same knowl edge is used by the planner itself in defining its dynam ically changing "model" of the world. Thus, we iden tify two roles for domain knowledge: static and dynamic [Schreiber et al. , 1994].
Static knowledge roles in planning
Figure 1 shows the hierarchical organization of static knowledge roles for planning [Valente, 1995]. The leaves of the hierarchy of static roles are associated with the types of domain knowledge (domain models) 2 that can play these roles (through the "plays" relation).
The plan model role defines what a plan is and what it is made of. It consists of two parts: a world description and a plan description.
The world description role describes the world in which planning occurs. It is comprised of two sub-roles. (1) The state description role, which contains the knowl edge necessary . to represent or describe the state of the world (for example, a set of first order predicates as in STRIPS or a set of fluents from the Situation Calculus [McCarthy and Hayes, 1969]). (2) The state changes role explicates the information connected to the specification of changes in the state of the world (e.g., STRIPS-like operators or hierarchical task networks (HTNs)).
1 In particular, we concentrate on what are known as "classical" planners as defined in [Hendler and McDermott, forthcoming].
2 0ur use of the term domain models for this knowledge is based on the use of the term "model" in KA, as opposed to in planning.

The plan description role describes the structure and features of the plan being generated, and comprises two sub-roles: plan structure and the (optional) plan as sessment knowledge. (1) The plan structure role spec ifies how the parts of a plan (actions, sub-plans) are as sembled together. It has two sub-roles: (a) the plan com position role, which describes whether the plan composi tion is total or partial order, whether it includes iteration and/or conditional operators, and whether the composi tion is hierarchical (i.e. whether plans can be recursively decomposed into sub-plans). (b) The state change data role contains additional information about the plan such as interval constraints for binding the variables involved in the state changes. It is also possible to assign different resources to each state change or sub-plan. Two partic ularly important resources are agents and time. (2) The plan assessment knowledge role determines whether a certain plan (or sub-plan) is valid (hard assessment knowledge), or whether a plan is better than another (soft). Based on this knowledge, a plan can be modified or criticized. An example of hard plan assessment knowl edge is a rule-based-criterion which could be used to find out if a condition is true at some point in the plan (as in the modal truth criterion in TWEAK [Chapman, 1987]). Another example IS the causal-link knowledge used in SNLP [McAllester and Rosenblitt , 1991]. An example of soft assessment knowledge would be the user preferences which can guide planning in the .\S IPE planner [Tate et al., 1990].
Dynamic roles in planning
Dynamic knowledge roles characterize planning in terms of the relevant variables whose values are constantly up dated during the planning process. The dynamic roles include: (1) The current state role , which is initially filled by a description of the world at the beginning of the plan, but is subsequently modified to represent intermediary states in the plan. (2) The goal role, which describes the active goal or subgoal being worked on by the plan ner. The content of goal can be a set of conditions or a set of actions to be accomplished. Initially, this role points to the original goal, and during planning it may be updated with sub goals or decompositions of the orig inal goal. (3) The conflict role contains the result of checking the plan for inconsistencies with respect to its conditions. ( 4) The plan role is a composite role consist ing of (a) plan-steps, (b) ordering constraints over the plan-steps, (c) variable binding constraints, and (d) aux iliary constraints that represent temporal and truth con straints between plan-steps and conditions.
2.2 The tasks and methods for planning
Based on an analysis of many classical planning systems, we have identified relevant tasks and problem-solving methods. We organize these into a task-method de composition structure [Orsvarn , 1996] and show these in Figure 2 (where ellipses represent tasks and rectan gles methods). A method executes (solid lines) a num ber of subtasks and a (sub )task can be performed by alternative (dashed lines) methods. The leaves of the task-method tree are called primitive-methods and the tasks they perform, primitive-tasks. Methods have two additional types of knowledge associated with them (not shown in the figure: control knowledge (Section 2.3) and suitability criteria (Section 2.4).
The class of planners we are dealing with share a gen eral, high-level problem-solving method called propose critique-modify (PcM) [Chandrasekaran, 1990]3. That is, the planners all contain in one way or another these three basic tasks: (i) propose expansion, (ii) critique plan and (iii) modify plan. Planners differ in the problem solving methods (PSMs) ~hey use to perform these three tasks. These differences also reflect how planning knowledge is represented. For example, in Figure 2, the propose-! method consists of the three subtasks: select goal, pro pose expansion, and test for unachieved goals. The pro pose expansion task can, in its turn, be realized by three different methods: smart propose, goal achievement pro pose, and decomposition propose. For a detailed descrip tion of all tasks and methods involved, see [de Barros et al., 1996].
2.3 Control knowledge
The task-method decomposition discussed above, defines each method in terms of (sub )tasks. During planning, these subtasks can be executed in various ways by the ap plication of different control regimes. In fact, many plan ning systems from the literature differ from each other only with respect to their control knowledge. Therefore, we associate control knowledge with every PSM that can be decomposed into sub-tasks. Control knowledge in cludes the steps of a strategy, the order between them, conditions, loops , backtracking points, exit points, etc.
3 In the literature, planning algorithms are usually not de scribed in a common terminology. We have tried to choose fairly generic names that capture the whole array of these approaches.

The specification of control knowledge is important because it lets us relate the individual tasks and methods to specific planners. We do this by recognizing certain patterns of control as corresponding with well-known planners when possible. In some cases, we can recog nize a well-defined pattern corresponding to a planner from the literature, and recommend to a user the use of that algorithm (i.e., STRIPS, NONLIN, SIPE, SNLP, UCPOP, etc). In other cases, we can recommend certain control regimes that may be of use in implementing a planner for the specific application. We refer to the first of these cases as a match with a "fully-specified" control regime, and the second as matching a "partially-specified" con trol method.
As an example of a fully-specified control structure, the following would be the definition in our system of the SNLP planner [McAllester and Rosenblitt, 1991].
- test-for-unachieved-goals (method: agenda-based-test)
- if goal = empty then exit
- else select-goal (method: random-select)
- propose-expansion (method: goal-achievement propose); backtracking-point
- interaction-critique (method: causallink-based-critique)
- consistency-critique (method: constraint-propagation)
- if conflict i= empty then
- 8.
9.
- modify-plan (method: causal-link based-modify); backtracking-point
else
; recursive-invocation
Besides these fully defined algorithms, our analysis of classical planning systems shows that there are some other control features that are common between multiple algorithms. For example, in many planners a test-for unachieved-goals task is used as a termination-point, the propose-expansion task is a backtracking point, a select goa/task is always executed before the propose-expansion task, etc. We can exploit this by including these pieces of control knowledge in the KA system for making sug gestions when one of the known control regimes is not a perfect fit. An example of the specification of one of these partially-specified control structures is the method propose-critique-modify:
Tasks:
STEP-I. propose; isa backtracking-point and exit-point
STEP-2. critique; isa fail-point
STEP-3. modify; is a backtracking-point and
has-a cond: (conflict #empty)
Control ordering: STEP-2 is-before STEP-3
2.4 The suitability criteria
The use of suitability criteria for establishing the ap plicability of methods based on the domain specifica tion is an important part of knowledge acquisition [Ben jamins, 1995]. In our work, each planning method is as sociated with such criteria to specify constraints on the domain features used to fill a knowledge role. For exam ple, the decomposition propose method requires that the static role world description is fulfilled by the domain model HTN. The smart propose method requires the two role fillings plan composition= total order, and world description = STRIPS-like operators. Similarly, suitability criteria are used to establish the connection between the control structure of a method and the domain knowledge. A complete description of the suitability criteria we use is beyond the scope of this paper, but see [Benjamins et al., 1996] for a complete discussion .
3 Par-KAP: an implemented KA tool
As discussed in the introduction, the goal of defining a KA library such as the above one is to allow the imple mentation of aKA tool for developing planning systems. We have implemented a system called Par-KAP which uses the knowledge framework above for this purpose. In this section we briefly present implementation details and examples of the use of the system.
3.1 Implementation
Par-KAP (for Parka for Knowledge Acquisition in Plan ning) is implemented using the Parka knowledge repre sentation system developed at the University of Mary land [Andersen et a/., 1994]. Parka is a frame-based KR language which can be used to represent an ontol ogy consisting of classes, subclasses, and individuals and properties of these. Parka is implemented in C, using re lational databases to provide scaling to large knowledge bases. Par-KAP uses Parka's Application Programming Interface (API) but is itself implemented in Lisp, run ning on a Spare workstation. In the remainder of this section, we describe how the frame-language is used to represent the planning KA library.
Task method decomposition structure This struc ture is represented as a tree of methods and tasks, linked by two types of relations, executes and is-performed-by. A task is-performed-by a method (possibly by more than one), and a method executes a task (as shown in Fig ure 3) .

In Par-KAP, we have also defined a number of meth ods corresponding to well known planners (like STRIPS, NONLIN, SIPE, SNLP , UCPOP, etc.) which correspond to specific subtrees in the task-method decomposition de scribed previously. These methods are directly linked to their primitive-tasks and respective primitive-methods. An example is shown in Figure 4. These specialized methods are used during the KA process as described in Section 4 below.

Knowledge roles and domain requirements. In Par-KAP, knowledge roles are represented as an isa link (class/subclass) hierarchy. Individual domain models are represented as instances of the general class domain model, and these have plays links to the knowledge roles as was shown previously in Figure 1.
As discussed above, during KA the methods and knowledge roles are associated to each other by suit ability criteria. Suitability criteria are also used to link control knowledge with methods. Figure 5 illustrates how Par-KAP represents suitability criteria, using the example of recognizing that the decomposition-propose method can only be used if the world description is in the form of Hierarchical Task Networks.

Control-structure. Representing the control relation ships among the tasks is done by linking methods to con trol methods via the property controls. Control methods are defined in terms of steps, which are related to the (sub )tasks which are executed by the method. The con trol method provides ordering and algorithmic relations between these steps, using pointers to various control specific terms such as backtracking-point, exit-point, etc. Thus, the control information for the propose-critique modify method shown in Section 2.3 can be represented as shown in Figure 6. Methods can be associated with more than one control regime, and as we have mentioned before, domain requirements must be used as a criterion to select between them.

4 Knowledge acquisition
In this section, we provide two examples of how Par KAP supports knowledge acquisition in planning. The first example is to find a list of the domain requirements necessary for a given planning method to be applied. The second is to find a set of possible planning methods, given a domain specification.
Domain requirements. One use of Model-based Knowledge Acquisition tools is to find a set of domain requirements imposed by a particular problem solving methodology. For planning, Par-KAP can thus assist a knowledge engineer in identifying restrictions on the do main knowledge if a particular planning strategy is used. This could be used by a knowledge engineer to help build a planning knowledge base. Par-KAP assists the user by specifying what type of knowledge has to be acquired and how it should be represented.
The input to Par-KAP for this type of KA request is a planning strategy, which can be a well known strategy or a new one given by the user (defined in terms of a set of basic planning methods plus a control structure). Par KAP returns a list of domain requirements associated with each method involved in the input strategy, and also the requirements associated with the specified control structure.
A simple example of this use of Par-KAP is to input a known planning method. Par-KAP produces the in formation about how the plan is represented, assessed and composed. Thus, if the input is the known planner SNLP, the output is simply
state-changes = STRIPS-operators plan-assessment-knowledge = causal-link-protection plan-composition= partial-order
In a more complex example, the system could also output information about state descriptions , how state changes are tracked, and specific information about con trol regimes.
Planning strategy. Another use of such a KA tool is to help identify a problem solving strategy given a set of known domain features (expressed as domain modeling features as discussed in Section 2). In order to construct a planning strategy, Par-KAP takes as input a specifi cation from the knowledge engineer of what sorts of fea tures can be elicited from domain experts, literature, etc. Par-KAP then outputs either a known algorithm (if it covers all the features) or a set of techniques that would need to be combined to process this sort of domain.

To do this, Par-KAP uses the task-method decomposi tion structure shown previously in Figure 2. The system finds those tasks which are achieved by a method that could be applicable given ·the domain specification. A method is considered applicable if it meets two condi tions. First , all of its domain requirements (if any) must be satisfied within the given domain specification. Sec ond, for each of its subtasks, there exists at least one method which is applicable to perform that (sub )task. This essentially defines a recursion which bottoms out when it finds primitive methods matching the domain specification.
After generating a list of tasks and the correspond ing primitive-methods, Par-KAP has to select a suitable control regime for the application. As described in Sec tion 2.3 in Par-KAP, control knowledge can be fully specified or partially-specified.
A fully-specified control regime may be selected (i) when the list of selected primitive-methods match with the primitive-methods of a well known planner (as in Fig ure 4) and (ii) when all that planner 's domain require ments are satisfied by the domain specification. When none of the fully-specified control regimes can be se lected, Par-KAP suggests the partially-specified control regime associated to each of the applicable non-primitive methods. (A better result would be to allow the in terleaving or other complex composition of the control techniques suggested by Par-KAP. This sort of algorithm composition for planning is a topic of future research.)
. As an example;. suppose we give Par-KAP the follow mg domam specmcatwn:
state changes = HTN plan-assessment-knowledge = causal-link-protection plan-composition= partial-order state-change-data = resources state-description= logical-predicates
The system returns a list of how the high-level tasks can be decomposed into the primitive tasks shown in Figure 7. This figure also gives an example of one of the control structures that is returned for these inputs.
5 Conclusion
We have presented a knowledge-acquisition library with components, designed for constructing planning systems. The library is comprised of the essential ingredients needed for giving concrete support when building a plan ner: problem-solving methods including control knowl edge and a characterization of the domain knowledge used in planning. Suitability criteria, that form the connection between planning methods and both domain knowledge and control structure, are also included . A prototype KA tool for planning systems , Par-KAP has been implemented using this library.
Par-KAP shows that such a framework can provide concrete support to knowledge engineers building plan ning systems. In particular , Par-KAP gives two kinds of support: (1) given some planning strategy, sup port the (knowledge acquisition) process of building the knowledge-base to which to apply the problem-solving strategy; (2) given a characterization of a domain , gener ate a planning system strategy suitable for that domain. One feature of Par-KAP is that the planning frame work is represented using Parka, an efficient , frame based AI language. This allows easy inspection and maintenance of the knowledge. In future versions of Par KAP, we will introduce a user interface to the planning library, in order to allow the continuous update and re finement of the planning knowledge. We are also working to make the. Par-KAP tool available over the Internet to allow it to be remotely accessed and used.
@inproceedings{ijcai1997p180,
title = {Par-KAP: a Knowledge Acquisition Tool for Building Practical Planning Systems},
author = {de Barros, Leliane Nunes and Hendler, James A. and Benjamins, V. Richard},
booktitle = {Proceedings of the Fifteenth International Joint Conference on
Artificial Intelligence, {IJCAI-97}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Martha E. Pollack},
pages = {1246--1252},
year = {1997},
note = {Planning and Scheduling},
url = {https://ijcai.org/proceedings/1997/180},
}
TY - CPAPER TI - Par-KAP: a Knowledge Acquisition Tool for Building Practical Planning Systems AU - de Barros, Leliane Nunes AU - Hendler, James A. AU - Benjamins, V. Richard T2 - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97 PB - International Joint Conferences on Artificial Intelligence PY - 1997 SP - 1246 EP - 1252 UR - https://ijcai.org/proceedings/1997/180 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: