![]() |
![]() |
Planning Initiative Shared Planning and Activity Representation - SPAR |
Title: Roots of SPAR - Shared Planning and Activity Representation
Author: Austin Tate, AIAI, University of Edinburgh
Date: 17-Nov-97
This article describes the previous work which has been used to create the initial SPAR representation. Key examples of the work drawn upon are published in the Knowledge Engineering Review Special Issue on Ontologies [Uschold & Tate, 1998]. The paper provides a comprehensive bibliography and related world wide web resources for work in the area of plan, process and activity representation.
SPAR is now being subjected to refinement during several review cycles by a number of expert and user panels.
The design of SPAR provides structure where there is a consensus on the key entities and relationships amongst those creating and using planning and activity representations. It specifies the structure to a level of detail judged to relate to the needs of the majority of potential users of the representation. However, planning and activity representations are the subject of active research. Some of the current approaches are conceptually simpler or more uniform than SPAR is intended to be - e.g., using pure logic or all constraint [Joslin, 1996; Tate, 1996a] bases. Even where the structure of SPAR itself is not suitable as a basis for novel research or applications, the intention is that the semantics of the SPAR Representation should be clearly defined such that it can be translated to alternative representations. This also provides the important capability that SPAR-represented information will be able to be communicated to future representational frameworks as and when those are adopted in a widespread way.
Within the SPAR structure it is possible to specialise the representation through the provision of application, domain or technology specific extensions via Plug-in Ontologies or Grammars with their associated Lexicons of the terms used. This is the level at which current and novel representations of activity and the constraints on activity will be attached. The plug in ontologies or grammars may draw on standard representations being adopted in the AI planning research community such as PDDL [McDermott et. al., 1997] or more constrained grammars may be specified for practical use in today's applications.
Where further shared structure can be agreed in future within a sufficiently broad community, it could be included in a future revision of SPAR. Where more limited communities representing vendors, specific sector users or research interest groups agree on a shared representation, it may be possible to create an extension used within that community using a mechanism such as the PIF "Partially Shared Views" (PSVs) [Lee & Malone, 1990].
Any practical use of a planning and activity representation naturally will relate to more detailed models of the objects involved or the organisational relationships between the people or agents included. It is not intended that SPAR itself prescribes structure for detailed object models or for detailed organisation or agent relationship models. SPAR can co-exist with one or more such models which can therefore be chosen to reflect standards established elsewhere. An example of a detailed object description standard is that established by International Standards Organisation's STEP [ISO, 1995] or EXPRESS [Express, 1995] for product interchange in manufacturing. Examples of organisational and agent relationships models can be found in the Enterprise Models [Fraser & Tate, 1995; Fox et. al., 1993] and the ORDIT Organisational Model [Blyth et. al., 1993].
SPAR may be expressed or represented in a wide variety of ways. It is intended that reference designs and implementations for a number of those which will be mostly commonly useful will be provided. KIF [Genesereth & Fikes, 1992], CommonKADS Conceptual Modelling Language [Schreiber et. al., 1994], Conceptual Graphs [Sowa, 1984], LOOM [Brill, 1993], CDIF [Ernst, 1997] or other representations of SPAR are possible.
In 1994, a group was formed to create an ontology for plans, using new insights gained over the last few years in the knowledge-sharing community in the US [Neches et. al., 1991; Genesereth & Fikes, 1992; Gruber, 1993] and Europe [Uschold, 1998; Breuker & van de Velde, 1994]. This led to an outline plan model called KRSL-Plans [Tate, 1996b]. However, this work was not brought to a conclusion though it did feed into subsequent work.
Since 1995, there have been a number of initiatives to standardise terminology in the subject area of activities and plans. These include enterprise processes in PIF (the Process Interchange Format [Lee et. al., 1996]); workflow (International Workflow Management Coalition [WfMC, 1994]); CASE systems data modelling exchange in CDIF [Ernst, 1997; Navarro, 1996]; manufacturing processes (NIST's Process Specification Language [Schlenoff et. al., 1996]); and the Object Model Working Group's CPR (Core Plan Representation - [Pease & Carrico, 1997]). These initiatives have involved academic, government and industry participants.
In the US military planning research community and beyond, there has been work to use verb/noun phrase grammars to represent plan objectives and activities [Valente et al., 1996; Hess, 1996; Kingston et. al., 1997; Drabble et. al., 1997].
In August 1997, DARPA and the Air Force Research Laboratory (Rome) Programme Managers for ARPI proposed a renewed effort to tap into this accumulated expertise, and to create a shared plan representation suitable for practical use in ARPI and on applied research programmes in their communities. The representation is expected to be considerably more detailed than the more conceptual ontology efforts which have gone before it.
SPAR is drawing on this wide range of previous work.
Plan ontologies and representations created by participants of ARPI-related projects include:
Since 1994, work within ARPI on plan representations has proceeded in parallel with pre-standards work on process interchange and representation. ARPI researchers have been involved in these activities, and others have supported the continuing ARPI work - including helping in the development and review of SPAR. The relevant standards activities that have been jointly pursued are:
A common model of processes and activity has emerged from this work and has been used as the basis for the initial version of SPAR.
Then at a second level of detail, the statements are:
The model is expected to develop from this base.
An initial version of SPAR has been produced utilising the wide range of previous work on plan, process and activity ontologies and representations. This is being subjected to review and refinement through a number of Request For Comment documents involving technical specialists and application-oriented user panels. Following these reviews, the intention is to publish a first version in mid 1998 and then to collect experience in the application of the representation.
It is intended that a process for sharing experiences of using SPAR will be established and continuing design issues tracked. A collected volume of papers describing SPAR and relating experience in using, adapting or extending the representation is planned in the medium term.
Thanks to the many people who have provided input to the planning, process and activity ontologies which have provided the roots for the work on SPAR and enabled rapid progress to be made in its initial development. Special thanks to Steve Polyak for helping to complete the extensive set of references in this paper. Thanks to Paul Krause, Simon Parsons, Steve Polyak and Mike Uschold for reviewing the text.
Allen, J.F., 1984. "Towards a General Theory of Action and Time" Artificial Intelligence 23 123-154.
Blyth A.J.C., Chudge, J., Dobson, J.E. and Strens, M.R., 1993. "ORDIT: A new methodology to assist in the process of eliciting and modelling organisational requirements" In Proceedings on the Conference on Organisational Computing Systems, November, San Jose, CA, USA. http://www.twente.research.ec.org/esp-syn/text/2301.html
Breuker, J., van de Velde, W., 1994. The CommonKADS Library for Expertise Modelling: Reusable Components for Artificial Problem Solving, IOS Press. http://www.swi.psy.uva.nl/projects/CommonKADS/home.html.
Brill, D., 1993. "LOOM Reference Manual v.2.0", Information Sciences Institute, University of Southern California. http://www.isi.edu/isd/LOOM/LOOM-HOME.html
Burstein, M.H., Schantz, R., Bienkowski, M.A., desJardins, M.E. and Smith, S.F., 1995. "The Common Prototyping Environment -- A Framework for Software Technology Integration, Evaluation and Transition" IEEE Expert 10(1) February 17-26, IEEE Comp. Soc. http://arpi.isx.com
Drabble, B., Lydiard, T. and Tate, A., 1997. "Process Steps, Process Products and System Capabilities", Artificial Intelligence Applications Institute, University of Edinburgh, Technical Report ISAT-AIAI/TR/4 Version 2, April 14, 1997. http://www.aiai.ed.ac.uk/~arpi/ACP-MODELS/ACP-PROCESS/97-APR/TEX-PS/isat-report4.pdf
Ernst, J., 1997. Introduction to CDIF, CASE Data Interchange Format Division Electronic Industries Association. http://www.cdif.org
EXPRESS Information Modelling Language, 1995. ISO WD 10303-11. http://www.eurpc2.demon.co.uk/part11.html
Fowler, N., Cross, S.E. and Owens, C., 1995. "The ARPA-Rome Knowledge-Based Planning and Scheduling Initiative" IEEE Expert, 10(1) February 4-9, IEEE Comp. Soc. http://arpi.isx.com
Fraser, J. and Tate, A., 1995. "The Enterprise Tool Set -- An Open Enterprise Architecture" In Proceedings of the Workshop on Intelligent Manufacturing Systems, International Joint Conference on Artificial Intelligence (IJCAI-95), Montreal, Canada. http://www.aiai.ed.ac.uk/~entprise/enterprise/ontology.html
Fox, M.S., Chionglo, J.F. and Fadel, F.G., 1993. "A Common-Sense Model of the Enterprise" In Proceedings of the Second Industrial Engineers Research Conference (IERC) Norcross, GA, Institute for Industrial Engineers. http://www.ie.utoronto.ca/EIL/tove/toveont.html
Genesereth, M.R. and Fikes, R.E., 1992. "Knowledge Interchange Format, Version 3.0 Reference Manual", Knowledge Systems Laboratory, KSL-92-86. http://ksl-web.stanford.edu/KSL_Abstracts/KSL-92-86.html.
Gruber, T., 1993. "Ontolingua: A Translation Approach to Providing Portable Ontology Specifications" Knowledge Acquisition 5(2) 199-200. http://ksl-web.stanford.edu/KSL_Abstracts/KSL-92-71.html.
ISO, 1995. "Product Data Representation and Exchange: Part 49: Integrated Generic Resources: Process Structure and Properties", ISO Standard 10303-49, International Standards Organization. http://www.nist.gov/sc4/www/stepdocs.htm
Joslin, D., 1996. "Planner/Scheduler Interface Proposal", Draft, CIRL, University of Oregon, 17-May-96. http://www.cirl.uoregon.edu/joslin/Papers/psi.ps.
Khambhampati, S, 1997. "Refinement Planning" AI Magazine, 18(2), pp. 67-97, Summer 1997.
Kingston, J.K., Griffiths, A. and Lydiard, T.J., 1997. "Multi-Perspective Modelling of the Air Campaign Planning Process" In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan. http://www.aiai.ed.ac.uk/~arpi
Knight, K. and S. Luk., 1994. "Building a Large Knowledge Base for Machine Translation". In Proceedings of the American Association of Artificial Intelligence Conference (AAAI-94), July 31, August 3, 1994, Seattle, WA. http://www.isi.edu/natural-language/resources/sensus.html#pubs
Lee, J. (ed.), Gruninger, M., Jin, Y., Malone, T., Tate, A., Yost. G., and other members of the PIF Working Group, 1996. "Process Interchange Format and Framework, Version 1.1", MIT Center for Coordination Science, Working Paper No. 194. http://ccs.mit.edu/pif
Lehrer, N. (ed.), 1993. "ARPI KRSL Reference Manual 2.0.2", ISX Corporation. http://isx.com/pub/ARPI/ARPI-pub/krsl/krsl-info.html
McDermott, D., 1997. "PDDL - The Plan Domain Definition Language", Computer Science, Yale University. http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/mcdermott.html
Moralee, S., 1994. "Notes from Enterprise Project Workshop on Content, Form and Methods for Ontologies", IBM(UK) Offices, Nottingham, UK, Dated 25-Nov-94. http://www.aiai.ed.ac.uk/~bat/ontology-may94.html.
Navarro, T., 1996. "CDIF - Integrated Meta-model - Project Management Planning and Scheduling Subject Area", Report EIA-PN3239, CDIF-DRAFT-PMPS-V04, CASE Data Interchange Format Division, Electronic Industries Association. http://www.cdif.org/overview/ProjectManagement.html
Neches, R., Fikes, R., Finin, T., Gruber, T.R., Patil, R., Senator, T. and Swartout, W.R., 1991. "Enabling Technology for Knowledge Sharing" AI Magazine 12(3) 36-56. http://ksl-web.stanford.edu/KSL_Abstracts/KSL-93-23.html.
NIST, 1993. "Integrated Definition for Function Modeling (IDEF0)", Federal Information Processing Standards (FIPS) Publication 183, National Institute of Standards and Technology, December 21, 1993. http://www.idef.com
Pease, R.A. and Carrico, T.M., 1997. "Object Model Working Group (OMWG) Core Plan Representation - Request for Comment", version 2, 24 January 1997, Defense Advanced Research Projects Agency. http://www.teknowledge.com/CPR2/
Schlenoff, C. (ed.), Knutilla, A., and Ray, S., 1996. "Unified Process Specification Language: Functional Requirements for Modeling Processes", National Institute of Standards and Technology, Gaithersburg, Maryland. http://www.nist.gov/psl/
Madni, A. and Mi, P., 1997. "IDEON™ Specification in CORBA IDL", Technical Memo ISTI-TM-7/97, July 17, 1997, Intelligent Systems Technology, Inc., Santa Monica, CA. http://www.intelsystech.com
Schreiber, G., Weilinga, B., Akkermans, H. and Van de Velde, W., 1994. "CML: The CommonKADS Conceptual Modelling Language" In L. Steels, G. Schreiber and W. Van de Velde (eds.) A future for knowledge acquisition: Proceedings of EKAW-94, Hoegaarden, Belgium, Springer-Verlag. http://www.swi.psy.uva.nl/projects/Kactus/toolkit/cml.html
Smith, S.F. and Becker, M., 1997. "An Ontology for Constructing Scheduling Systems" In Working Notes from 1997 AAAI Spring Symposium on Ontological Engineering, Stanford, CA, AAAI Press. http://www.cs.cmu.edu/afs/cs/project/ozone/www/AAAI_Symp_On_Ontol_97/abstract.html
Swartout, B. and Gil, Y., 1995. "EXPECT: Explicit Representations for Flexible Acquisition" In Proceedings of the Ninth Knowledge Acquisition for Knowledge-Based Systems Workshop, February 26-March 3, 1995. http://www.isi.edu/expect/expect-homepage.html
Tate, A., 1994. "A Plan Ontology - a Working Document - October 31, 1994" In Proceedings of the Workshop on Ontology Development and Use, 2nd - 4th November, La Jolle, CA. ftp://ftp.aiai.ed.ac.uk/pub/documents/1994/94-ont-plan-ontology.pdf
Tate, A., 1995. "O-Plan Task Formalism Manual", Version 2.3, July 12, 1995. Artificial Intelligence Applications Institute, University of Edinburgh. http://www.aiai.ed.ac.uk/project/ftp/pub/documents/ANY/oplan-tf-manual.pdf
Tate, A., 1996a. "Representing Plans as a Set of Constraints -- the <I-N-OVA> Model" In Proceedings of the Third International Conference on Planning Systems (AIPS-96), Edinburgh, Scotland, May 1996, AAAI Press, pp. 221-228. http://www.aiai.ed.ac.uk/~oplan/inova.html
Tate, A. (ed.), 1996b. "KRSL-Plans", Appendix of Tate, A, "Towards a Plan Ontology" AI*IA Notizie (Quarterly Publication of the Associazione Italiana per l'Intelligenza Artificiale), Special Issue on "Aspects of Planning Research" 9(1), pp. 19-26. A shorter version of [Tate, 1994]. http://www.aiai.ed.ac.uk/project/ftp/pub/documents/1996/96-aiia-plan-ontology.pdf
Tate, A (reporter) and the PIF Working Group, 1996. "PIF and the Workflow Management Coalition WPDL, Report of Session at the PIF Workshop", Stanford University, 11-Jul-96. http://ccs.mit.edu/pif
Tate, A., Drabble, B. and Kirby, R.B., 1994. "O-Plan2: an Open Architecture for Command, Planning and Control" In M. Fox and M. Zweben (eds.) Intelligent Scheduling, Morgan Kaufmann. http://www.aiai.ed.ac.uk/~oplan/
Uschold, M.F., 1998. "Concepts and Terminology for Knowledge Sharing" Knowledge Engineering Review, Special Issue on Ontologies, To appear, Cambridge University Press. http://www.aiai.ed.ac.uk/~euroknow
Uschold, M.F., Moralee, S., King, M. and Ziorgios, Y., 1998. "The Enterprise Ontology" Knowledge Engineering Review, Special Issue on Ontologies, To appear, Cambridge University Press. http://www.aiai.ed.ac.uk/~entprise/enterprise/ontology.html
Valente, A., Swartout, W. R. and Gil, Y., 1996. "A Representation and Library for Objectives in Air Campaign Plans". http://www.isi.edu/expect/inspect.html
Wilkins, D.E., 1988. Practical Planning Morgan Kaufmann.http://www.ai.sri.com/~sipe
Wilkins, D.E. and Myers, K.L., 1995. "A Common Knowledge Representation for Plan Generation and Reactive Execution" Journal of Logic and Computation 5(6) 731-761. http://www.ai.sri.com/~act/act-formalism.html
World Wide Web Consortium, RDF Metadata Format, Draft 3-Oct-97. http://www.w3.org/Press/RDF
Workflow Management Coalition, 1994. "Workflow Management Coalition Glossary", A Workflow Management Coalition Specification, November. http://www.wfmc.org
ARPI Home Page | SPAR Home Page |