DARPA Rome Lab. Planning Initiative
Shared Planning and Activity Representation - SPAR

Part of the DARPA/Rome Laboratory Planning Initiative (ARPI)
Watch Out - Under Rapid Initial Development
This is an initial draft of the SPAR Document.
Some parts of this document are not yet complete.
Responsibility for parts under development are indicated by [...].
"Getting as far as we can is the best that we can do"
(Edward Witten, Princeton University, investigator of superstring theory)

Sections remaining to complete for version 0.1 by 22-Oct-97:

  1. TG - Program manager perspective on SPAR for introduction.
  2. SP - References to expand to (author,year) format and add NIAM acronym expansion and references.
  3. SP - Requirements section to provide.
  4. AP - Model overview sentences for event, etc to provide.
  5. AP - Object Model section to provide.
  6. BS - Language section to provide.
  7. KM - Discussion, Clarification and Issues section to provide.
  8. AP - More detail of entity attributes to provide.
  9. BS - Suitable "placeholder" text for the language appendix.
  10. AP - Suitable "placeholder" text for 3 appendices.
  11. KM - Suitable "placeholder" text for the formal theory appendix.
  12. SP - Check all URLs work and Correct Spelling.
  13. SP - Complete Abbreviations and Acronym appendix.

Version: 0.0a
Date: 6-Oct-97
Status: Draft
Request for Comments by: not set
E-mail: spar-core@isi.edu
WWW: http://www.aiai.ed.ac.uk/~arpi/spar/

Requirements | Model | Discussion | Participants | Appendices

Introduction and Aims

It is important that information about processes, plans and activities are sharable within and across organisations. Cooperation and coordination of the planning, monitoring and workflows of the organisations can be assisted by having a clear shared model of what comprises plans, processes and activities. The Shared Planning and Activity Representation (SPAR) is intended to contribute to a range of purposes including domain modelling, plan generation, plan analysis, plan case capture, plan communication, behaviour modelling, etc. By having a shared model of what constitutes a plan, process or activity, organisational knowledge can be harnessed and used effectively.

Program Manager perspective on need for SPAR [TG]

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 than SPAR - e.g., using pure logic [ref] or all constraint [ref, ref] bases. Even where the structure of SPAR itself is not suitable as a basis for novel research or products, the intention is that the content of SPAR Representations 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.

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.

History

The AI planning community has used explicit domain description languages and plan definitions for more than 25 years [Ref, Ref]. As long ago as the late 1960s, work on the STRIPS operator representation of actions [Ref] was used to practical effect for planning and control of the SRI Shakey robot. This early application was based upon more theoretical roots in the QA3 theorem prover [Ref] and situation calculus [Ref]. There is now a wealth of experience of defining plan representations from both theoretical studies and practical planning. In 1992, under the DARPA/Rome Laboratory Planning Initiative (ARPI) [ref], a number of participants created the KRSL plan language [ref]. Although this has been used for some transfers of information between planning components within the ARPI (in particular an Integrated Feasibility Demonstration called IFD-2 [ref]), it has not had the widespread impact desired. Its structure was too rigid and KRSL excluded much that was already being done within AI planning research. However, it did establish a range of entities which needed to be in a plan representation and was an influence on subsequent work.

In 1994, a group was formed to approach the creation of an ontology for plans using new insights gained over the last few years in the knowledge-sharing community in the US [ref, ref, ref] and Europe [ref]. This led to an outline plan model [ref]. However, this work was not brought to a conclusion.

Since 1995, there have been a number of initiatives to standardise terminology related to enterprise processes in PIF (the Process Interchange Format [ref]); workflow International Workflow Management Coalition [ref]); CASE systems data modelling exchange in CDIF [Ref, [Ref]; manufacturing processes (NIST's Process Specification Language [ref]); the Object Modeling Working Group's CPR (Core Plan Representation - [ref]); and in the US military planning research community [ref, ref]. These initiatives have involved academic, government and industry participants.

In August 1997, DARPA and Rome Laboratory Programme Managers for ARPI proposed a renewed effort to tap into this accumulated expertise, and to create a shared plan representation suitable for use in ARPI and on applied research programmes in their communities. This effort is called the Shared Planning and Activity Representation (SPAR).

SPAR Roots

SPAR has drawn on a wide range of previous work. Plan ontologies and representations created by participants of ARPI-related projects include:

  1. ARPI KRSL 2.0.2 [ref] as noted above.
  2. ARPI KRSL-Plans ontology [ref] as noted above.
  3. SRI International ACT language from the Cypress project [ref].
  4. Edinburgh O-Plan Task Formalism [ref,ref] and the related <I-N-OVA> constraint model of activity [ref,ref].
  5. CMU OZONE scheduling ontology [ref].
  6. The Planning Domain Definition Language (PDDL) [Ref] created by a community of researchers wanting to exchange planning challenge problems. PDDL draws on work on expressive planner operator languages in ADL [Ref] and hierarchical task network planning [Ref].
  7. Process Interchange Format (PIF) standard being worked on by a number of projects interested in exchanging process information [ref].
  8. USC/ISI work on the SENSUS ontology and lexicon, and its recent application to the Joint Forces Air Component Commander (JFACC) plan representation at DARPA [ref].
  9. Edinburgh and ISX Corporation work on process models and grammars for describing the actions and products flowing for US Air Campaign Planning [ref].
It has drawn on the ontologies created on collaborative projects related to Enterprise Modelling and Integration including:
  1. Enterprise Ontology (Edinburgh, Lloyds Register, Logica, IBM UK and Unilever) [ref, ref] and the report of the Enterprise Project workshop on "Content, Form and Methods for Ontologies" in May 1994 [ref]. that were provided to the KRSL-Plans, PIF and other communities.
  2. TOronto Virtual Enterprise (TOVE) ontology [ref].
In addition, there is relevant work on Structured Analysis and Design Techniques (e.g., SADT [ref]), Issue-Based Design Methods (e.g., IBIS [ref]), Process Management Models and Methods (e.g., IDEF [ref]), Entity-Relationship Modelling [ref], Object-Role Modelling (e.g., NIAM [ref]), Process Workflow Support, etc.

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:

  1. Object Modeling Working Group (OMWG) Core Plan Representation (CPR) [ref].
  2. National Institute of Standards and Technology (NIST) Process Specification Language (PSL) [ref], [ref].
  3. Workflow Management Coalition work in standardising workflow systems and process terminology via their Glossary of Workflow terms [ref] and their interface 1 - the Workflow Process Definition Language (WPDL).
  4. CASE Data Interchange Format (CDIF [Ref]) group of the Electrical Industries Association who are standardising data model exchanges between CASE systems in a number of areas including the Project Management, Planning and Scheduling Subject Area [Ref].

A common model of processes and activity has emerged from this work and has been used as the basis for SPAR.

Development, Refinement and Review Process

SPAR will be developed in the following way:
  1. The SPAR Core Group has merged existing plan ontology work into a solid core representation as a starting point and will present this at the November 1997 ARPI Workshop.
  2. Via three panels, the Core Group will seek input to the SPAR work, reviews of the representation proposed, and issues raised by it. The panels are:
  3. The Core Group will take the lessons learned in 2 to refine 1, and repeat the process.
  4. The Core Group and others will Communicate the work in progress and the promote the availability of the representation to the potential user, technical and standards communities.
  5. The research community will collect experience in the use of SPAR and use lessons learned to refine the representation.
  6. The research community will publish a report on the representation and experience gained.

[Suggestion from AT - to be confirmed by Core Group] [AT]

The Core Group has decided to prioritise the areas of planning and activity representation which it will seek to address in SPAR during its initial development and request for comment review cycles:

  1. Key Plan, Objective, Activity and Agent relationships.
  2. Detailed temporal, resource and actor constraints for scheduling support.
  3. World state or situation descriptions and state of activity execution.
  4. Planning process, workflow, planning capability and problem solving methods representation (sometimes referred to as the "meta-level").
  5. Plan, Plan/Activity Library and Case Library annotations for human and system communication and indexing for retrieval in systems.
  6. Explicit representation of probabalistic uncertainty.
  7. Soft constraints or preferences, non-boolean evaluation criteria.
  8. Design rationale, issues, argumentation, and decision recording in plans [ref].
  9. Other factors.

[Comments on this prioritisation are sought from reviewers.] [AT]

Requirements

Section here on requirements. Should mention NIST PSL Requirements Phase 1 and Phase 2 document comparing these requirements against ARPI created representations. Give reference. [SP]

Initial work in providing a classified list of requirements is at:

SPAR Model

Scope

The principal scope of SPAR is to represent past, present and possible future activity and the command, planning and control processes that create and execute plans meant to guide or constrain future activity.

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 [ref] or EXPRESS [Ref] for product interchange in manufacturing. Examples of organisational and agent relationships models can be found in the Enterprise Models [ref, ref], the ORDIT Organisational Model [ref], and the work on classifications of agents and their relationships by Doyle at MIT [ref].

SPAR allows for extensions. Within the SPAR structure it is possible to specialise the representation through the provision of application, domain or technology specific extensions via Plug-in 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. This may draw on standard representations being adopted in the community such as PDDL [Ref].

Concurrent use of multiple such extensions is allowed for to achieve the objective of SPAR to support large scale, distributed representation of plans at multiple levels of detail.

Design Principles

The SPAR design has adopted a small number of guiding principles. It seeks to use these principles in a consistent manner.

[Possibly some of these principles will only relate to specific reference models - such as the object model or reference language BNF. [AT]

  1. 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 is possible to create an extension used within that community using a mechanism such as the PIF "Partially Shared Views" (PSVs) [ref].

    It is possible that a process for communicating and registering Partially Shared View extensions to a broader community could be provided by a suitable standards body (as is intended for PIF [ref]).

  2. SPAR may be expressed or represented in a wide variety of ways. This document provides reference designs and implementations for a number of those which will be mostly commonly useful. KIF [ref], Conceptual Graphs [ref], LOOM [ref], CDIF [Ref] or other representations of SPAR are possible.

  3. Conceptually, entities contain properties or attributes of the single entity, relationships are separate entities in their own right rather than being incorporated into attributes of the entities related. For efficiency of reasoning, an implementation may choose to represent some roles played by entities in common relationships into the attributes of the entities playing those roles.

  4. A number of conceptual entities are provided which cluster other entities into classes (Such as Constraint, ActivityConstraint, etc.) These are convenient for explanation of the model, to improve its communication and translatability to other standards, to improve its modularity, and to allow for some measure of flexibility should detailed parts of the representation be amended in future. An implementation may choose to leave out these conceptual entities.

Entities, Relationships, Functions, Attributes, Values and Roles

Entity is a fundamental thing in the domain being modelled. An Entity may participate in Relationships with other entities. A Relationship is an association between two or more entities. It has a specialisation Function, and in turn that can be specialised to Property. A Property of an entity is also referred to as an Attribute of that entity. An entity that participates in a relationship plays a "role" in that relationship. E.g., the object or agent that participates in the relationship performs(activity,agent) plays the role of being the "performing actor".

World and Environment

The "Real World" is "the domain in which activity takes place". The "World Model" describes, in more or less detail and with more or less accuracy, the "Real World". Part of the space of real world activity is modelled more or less accurately by specifications of "actions" and "events". Activity is the performance of one or more real world actions or events (a non-empty set of actions or events). A specification of the activity possible in the real world may or may not be included in the model - with more or less accuracy if included.

An "Environment" contains the world model, including the descriptions of activity that model includes whether that activity can be planned for or not (i.e. the domain modelled may contain agents whose activity is not directly specifiable). Plans are contained within an environment.

SPAR Model Overview

Activity and State

Activity is an important building block in SPAR. A Plan contains a specification of activity but also has a specification of objectives (themselves related to the agents which hold those objectives).

Activity takes place across an interval defined by its begin and end time points (which may be underspecified) and involving a number of activity-related "objects" (which may be both physical or more abstract). A Plan (or plan templates and cases) is defined as a specification of activity associated with one or more objectives. An agent may hold objectives and/or perform activities.

Primitive Activity is defined from the perspective of any agent to be an activity whose specification in the model available to that agent does not contain any sub-activities. This allows for more detailed models to be available to some agents than others.

The terminology used to describe past, present and future activity and world state is as follows:

Past StatePresent StatePossible Future State
Past ActivityPresent ActivityPossible Future Activity

Model Overview

The starting point for the SPAR model of planning and activity are the following statements. The first 14 sentences were taken from KRSL-Plans (version dated 20-Sep-96 ). This was a refinement of an earlier version dated 2-Feb-95 (published in [ref]). It was used to provide ARPI participants input to the development of the OMWG Core Plan Representation (CPR [ref]). The remaining sentences are adapted from OMWG CPR and other sources. [square brackets are used to indicate phases or options still under discussion].
  1. A PLAN is a SPECIFICATION of ACTIVITY to meet one or more OBJECTIVES.
  2. A SPECIFICATION of ACTIVITY denotes or describes one or more ACTIVITIES.
  3. An ACTIVITY may change the WORLD-STATE.
  4. WORLD-STATE is something that can be evaluated as holding or not.
  5. An AGENT can perform ACTIVITIES and/or hold OBJECTIVES.
  6. An OBJECTIVE may have one or more EVALUATION-CRITERIA.
  7. An EVALUATION-CRITERIA is an ASPECT of [past, present or possible future] WOLRD-STATE or an ASPECT of [one or more] PLANS.
    [Replace ASPECT with FUNCTION? - Aspect is not defined. [AT]]
  8. An EVALUATION is a predicate (holds/does not hold) or a preference ranking on [one or more] EVALUATION-CRITERIA.
  9. An ACTIVITY takes place over a TIME-INTERVAL identified by its two ends, the BEGIN-TIME-POINT and the END-TIME-POINT. The BEGIN-TIME-POINT is temporally before the END-TIME-POINT.
  10. An ACTIVITY-SPECIFICATION may have ACTIVITY-CONSTRAINTS associated with it and its TIME-INTERVAL.
  11. An ACTIVITY-SPECIFICATION may include one or more SUB-ACTIVITIES.
  12. SUB-ACTIVITY: Sub-activities are the constituent activities designated in any ACTIVITY-SPECIFICATION.
  13. PRIMITIVE ACTIVITY is an ACTIVITY whose ACTIVITY-SPECIFICATION contains no (further) ACTIVITIES.
  14. ACTIVITY CONSTRAINTS can be stated with respect to none, one or more than one time point. They express things which are required to hold. They are evaluable with respect to a specific PLAN as holding or not holding.
  15. [EVENT - definition to be added - AP]

Ontology

The following top level model for SPAR reflects the statements above.

SPAR Model

Entity Types

The top level types in SPAR are Activity, TimePoint, Object (and its special sub-type Agent) and Relationship (and its special sub-type Constraint).

SPAR Types Overview

[Invite panel members comments - Are self referents desirable for Objective, ActivitySpecification, ActivityConstraint and WorldStateConstraint? See issues 0018 and 0021] [AT]

In more detail the SPAR types are as follows (leaving out the basic types needed for values of attributes of the SPAR entities for the moment):

SPAR Types

Value Types

The basic types used to specify values of attributes of SPAR entities are:

SPAR Basic Types

The following framework is adapted from the PIF 1.1 Document [Ref] with the permission of Jintae Lee, University of Hawaii (jl@hawaii.edu).

A SPAR description consists of a set of entity definitions which may be described in a variety of ways - including in an object-oriented style of in an ASCII language.

Each entity definition refers to an entity instance and is typed (e.g. ACTIVITY, OBJECT, TIMEPOINT) and they form a class hierarchy. An entity definition has a particular set of attributes defined for it. Each of the attributes describes some aspect or property of the entity. For example, a PERFORMS definition has Actor and Activity attributes that specify which Object (or its specialization Agent) is performing which activity. The instance of an entity definition has all the attributes of all of its superclasses, in addition to its own attributes. For example, all the instances of ACTIVITY have the Name attribute, since ENTITY, which is a superclass of ACTIVITY, has the Name attribute.

When an attribute of one entity has a value that refers to another entity, the attribute represents a relationship between the two instances that the two entities refer to. For example, if the BeginTimePoint attribute of ACTIVITY-1 takes TIMEPOINT-32 as its value, then the BeginTimePoint attribute represents a relationship between the ACTIVITY-1 and TIMEPOINT-32 instances. The value of a given attribute in SPAR holds independent of time.

An attribute in a SPAR entity can have as its value the following, and only the following: a literal value of a SPAR basic value type; or an expression that represents such a value type. The SPAR basic value types are primitive or composite value types.

The SPAR primitive value types consist of:

The SPAR composite value types consist of: The Reference Language BNF Language Appendix describes SPAR's recommended syntax, including the syntax of the SPAR basic value type primitive literals as well as the composite value types.

The attribute value of a SPAR entity holds independent of time (i.e. no temporal scope is associated with an attribute value in SPAR). Any property of an entity which can change over time, should be represented by a RELATION that links the property to a TimePoint (perhaps indirectly).

An EXPRESSION may include variables, quantifiers, and the Boolean operators for expressing conditions or constraints. A STATEMENT (specialization of EXPRESSION) is used in the Constraint attribute of ENTITY, and in a range of ActivityConstraints attributes of ACTIVITY.

An entity variable is a sub-type of expression of the form: entity-name[.attribute-name]*, which refers to either the entity named or the entity which is the value of the named attribute of that entity (recursively).

A variable in an expression may have several different scopes. All such variables with the same name within the same scope are bound to a single entity, whereas that is not necessarily so if the variables occur in different scopes.

  1. An entity.
  2. An ActivitySpecification
  3. A Plan or Process
  4. A World Model
  5. An Environment

Plug-in Domain Grammars and Lexicons

The specification of a number of entities within the SPAR model are dependent on the application domain within which the model is used. A variety of decisions can be taken as to the level of modelling of the domain, what is to be included and excluded, and the level of accuracy to be built into the model. SPAR provides the ability to define the domain dependent aspects via a number of syntaxes (or grammars) which specify the restrictions on legal statements for a number of SPAR value types (of the attributes of entities). The terminal tokens of the syntax or grammar must be legitimate symbols understood in the domain, or they may be symbols further defined (unambiguously) in any one of a number of domain lexicons associated with a grammar.

The SPAR entities which can be defined by one or more domain specific grammars which can be plugged into SPAR are:

  1. ActivityPattern of an Activity - The grammar specifying legal activity-expressions has the following top level structure: (verb [noun phrase]* [qualifier]* ).
  2. ConstraintSyntax - including the specialisations for:

  3. AgentCapabilitySyntax - which has no minimum requirements and may be an empty definition. It could define capabilities or skills of agents in a way that allows for selection of appropriate agents to perform activity.
  4. EvaluationCriterionSyntax - which has no minimum requirements and may be an empty definition. It could define evaluations and their boolean (holds/does not hold) or preference ranking (measures of merit for soft constraints).
  5. AnnotationSyntax - which will have a small minimum set of requirements still to be decided. It could define annotations such as the 20 or so required headers for process descriptions in the Workflow Management Coalition's WPDL (interface 1).
  6. ProjectedTimeSpecificationSyntax - which has no minimum requirements and may be an empty definition. It could define ways in which probabalistic time specifications, or other time specifications were to be handled.
  7. LocationSpecificationSyntax - which has no minimum requirements and may be an empty definition. It could define ways to define spatial regions, points in space, geographical locations (GEOLOCS), etc.
  8. CalendarSyntax - for which there will be a default StandardCalendarSyntax.

Concurrent Use of Multiple Domain Terminologies

The shared planning and activity representation provides a generic framework in which one or more specific application domain syntax and lexicons can be used for defined items.. It is intended that SPAR support concurrent use of any number of several different disjoint or partially overlapping domain models while still allowing simple models to be created. It will do this by having a single default for each specified syntax associated with the "Environment" entity that encloses all information within the SPAR model or for the "Specification" entities ("ActivitySpecification" and "WorldModel").

To simply exposition in early versions of SPAR and to ensure its adoption in today's simpler applications requiring SPAR, this feature will not be fully elaborated. This will mean that the enclosing "Environment" (or an override via any "ActivitySpecification" or "WorldModel") will define the legal domain syntax and lexicon for enclosed entities. However, in future versions (hopefully in an upward compatible way), any named syntax (and associated lexicons) will be able to be specified for use in the value type of any entity which allows CalendarSyntax entries.

Object Model

Object Model introduction [AP]
Detail in Appendix.
CPR Meta-model Diagram

Language

Language introduction [BS]
Detail in Appendix.
See related issue 0020

Discussion, Clarification and Issues

Overview of this section and motivate need for discussion of some specific non-obvious uses of the SPAR model. [KM]

Previous and Current Issues

The previous and current issues for SPAR are listed at http://www.aiai.ed.ac.uk/~arpi/spar/#issu. A summary of those outstanding at a specific date are included in each published version of the SPAR document. See Appendices for Issues Addressed in this Version and Current Issues in this Version. An initial SPAR model version 0.0 was created on 25-Sep-97 at the initial meeting of the SPAR Core Group. It was created using the common elements from the ARPI Plan Ontology Constructor Group (POCG) work on KRSL-Plans (20-Sep-96 version), PIF 1.1, and recent discussions on NIST PSL. Details were added using experience from SRI's ACT, the Edinburgh <I-N-OVA> constraint model of activity and O-Plan TF; the CMU OZONE scheduling ontology; OMWG's CPR version 2 and recent experience of applying it to the JFACC C2 Schema requirements; and USC/ISI work on grammars to describe actions for the JFACC domain.

Subsequent discussions have led to the current version which is open for comment and for issues to be raised.

IDEF Models

IDEF (Integration DEFinition) methods were originally created in the early 1980s at the Wright-Patterson Air Force Base for system modelling purposes. The IDEF family of methods [ref] are now widely used within business and government organisations internationally. Therefore, in some organisations, there exist IDEF process models created in the IDEF-0 function modelling method or in the more appropriate IDEF-3 method which was specifically design for process modelling. There are advantages to be gained in terms of capturing planing and process knowledge for organisations, if it is possible to translate in a straightforward way IDEF models into SPAR.

SPAR provides the framework for doing this. As in IDEF-0, SPAR activities have decompositions through the ability to give each an activity specification in terms of sub-activities and the constraints on those activities. IDEF-0 inputs and outputs can be modelled as Objects in SPAR or more sophisticated input and output models can use the WorldStateConstraints in SPAR. The mechanisms of IDEF-0 map directly to the Resources (through ResourceConstraints) and the Objects (normally of subtype Agent which play the role of Performing the Activity (through ActorConstraints). The controls of IDEF are mmodelled in SPAR as AuthorityConstraints.

Workflow Management Coalition - Workflow Process Description Language (IDEF)

The Workflow Management Coalition's WPDL specifies interface 1 of a range of standards being established by this international consortium of workflow vendors, consultants, users and researchers. It is intended to allow today's workflow tools to interoperate through exchanging information close to that used in current technology workflow support systems. A workshop held by the PIF Group and attended by a representative of Working Group 1 of the Workflow Management Coalition Coalition [ref] in July 1996 compared PIF to the WPDL. This showed that although different terminology was used, the basic Activity, Object, Agent, Temporal Constraint, and other Relationships model in PIF (and SPAR) mapped straightforwardly to the draft WPDL available at that time. Some changes in the details of WPDL have taken place since that date.

The main area in which PIF and WPDL differed was the level of specified documentation annotations for processes and other WPDL structures. WPDL has a small number of required annotations and a long list of optional ones. These reflect the documentation attributes used in current workflow tools on the market.

It is anticipated that SPAR will provide a sample WPDL compliant AnnotationSyntax base to be used for expansion for specific uses - called WPDLAnnotationSyntax.

Acknowledgements

The SPAR Project is a part of the Defense Advanced Research Projects Agency (DARPA) and U.S. Air Force Rome Laboratory Planning Initiative (ARPI). The work is supported by ARPI and other participants, and by their host organizations.

The U.S. Government is authorised to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of DARPA, Rome Laboratory or the U.S. Government.

Credits for Text

Some parts of this document have been derived largely from existing specifications or ontologies. References are given to the major sources of the design of SPAR in the References section of this document. Extracts from documents of the Core Group Members are extensive and are not specifically credited.

The description of value types in SPAR is adapted from the PIF 1.1 Document [Ref] with the permission of Jintae Lee, University of Hawaii (jl@hawaii.edu). A section of the draft NIST PSL's core theory is included in the Formal Theory Appendix with the permission of Christopher Menzel, Texas A&M University (cmenzel@tamu.edu) and KBSI (cmenzel@kbsi.com).

Participants

Participants have been chosen to be familiar with the issues of plan representation and to be able to reflect specific concerns for their "constituency".

Note that an individual's initials are used in SPAR documents to track issues relating to the development of SPAR.

The list of active participants will be included in published versions of this document. [AT]

The current list of participants is available at http://www.aiai.ed.ac.uk/~arpi/spar/#part.

References

Allen, J., Towards a General Theory of Action and Time, Artificial Intelligence 23, pp. 123-154, North-Holland, 1984.

Allen, J., Hendler, J. and Tate, A. (eds.), Readings in Planning, Morgan Kaufmann, 1990.

Burstein, M.H., Schantz, R., Bienkowski, M.A., desJardins, M.E. and Smith, S.F., The Common Prototyping Environment -- A Framework for Software Technology Integration, Evaluation and Transition, IEEE Expert, Vol. 10, No. 1, pp. 17-26, February 1995, IEEE Comp. Soc. http://arpi.isx.com

Ernst, J., Introduction to CDIF, CASE Data Interchange Format Division, Electronic Industries Association, May 1997. http://www.cdif.org

Doyle, J., Rich agent models Reference, MIT. Reference and URL to include. To be completed [AT].

Erol, K., Hendler, J. and Nau, D., UMCP: A Sound and Complete Procedure for Hierarchical Task Network Planning, in Proceedings of the Second International Conference on AI Planning Systems (AIPS-94), pp. 249-254, Chicago, IL, USA, 1994.

Etherington, D., CSP Constraint Representations for Scheduling, Paper and URL to be nominated as a reference. [DE].

Fikes, R.E. and Nilsson, N., STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving, Artificial Intelligence, 5(2), North-Holland, 1971.

Green, C., Applications of Theorem Porving to Problem Solving, Proceedings of the First International Joint Conference on Artificial Intelligence (IJCAI-69), pp. 741-747, Morgan Kaufmann, 1969.

Fowler, N., Cross, S.E. and Owens, C. The ARPA-Rome Knowledge-Based Planning and Scheduling Initiative, IEEE Expert, Vol. 10, No. 1, pp. 4-9, February 1995, IEEE Comp. Soc. http://arpi.isx.com

Fraser, J. and Tate, A., The Enterprise Tool Set -- An Open Enterprise Architecture, Proceedings of the Workshop on Intelligent Manufacturing Systems, International Joint Conference on Artificial Intelligence (IJCAI-95), Montreal, Canada, August 1995. http://www.aiai.ed.ac.uk/project/enterprise/ontology.html

Fox, M.S., Chionglo, J.F. and Fadel, F.G., A Common-Sense Model of the Enterprise, Proceedings of the Second IERC. Department of Industrial Engineering, University of Toronto. http://www.ie.utoronto.ca/EIL/tove/toveont.html

Genesereth, M. and Fikes, R., Knowledge Interchange Format Reference Manual. http://www-ksl.stanford.edu/pub/knowledge-sharing/papers/kif.ps.

Gruber, T., Ontolingua: A Translation Approach to Providing Portable Ontology Specifications, Knowledge Acquisition, 5(2), pp. 199-200, 1993. http://www-ksl.stanford.edu/pub/knowledge-sharing/papers/ontolingua-intro.ps.

Gruninger, M., Situation Calculus Descriptions of Processes and Activity in TOVE. Paper and URL to be nominated as a reference. [MG].

Khambhampati, R. (1997) Refinement Planning, AI Magazine, Summer 1997. To be checked and URL added [AT].

Kingston, J.K., Griffiths, A. and Lydiard, T.J., Multi-Perspective Modelling of the Air Campaign Planning Process, Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan, August 1997. http://www.aiai.ed.ac.uk/~arpi

Lee, J. and Malone, T., Partially Shared Views: A Scheme for Communicating between Groups Using Different Type Hyerarchies, ACM Transactions on Information Systems, 8(1), pp. 1-26., 1990. http://soa.cba.hawaii.edu/pif/

Lee, J. (editor), Gruninger, M., Jin, Y., Malone, T., Tate, A., Yost. G., and other members of the PIF Working Group, Process Interchange Format and Framework, Version 1.1, MIT Center for Coordination Science, Working Paper No. 194, 1996. http://soa.cba.hawaii.edu/pif/

Lehrer, N. (ed.), ARPI KRSL Reference Manual 2.0.2, February, 1993. ISX Corporation. http://isx.com/pub/ARPI/ARPI-pub/krsl/krsl-info.html

MacGregor, R., et. al. LOOM Reference Manual, Information Sciences Institute, University of Southern California, 1997. To be checked and URL added [AT] http://www.isi.edu/loom-not-yet

McCarthy, J. and Hayes, P.J., Some Philosophical Problems from the Standpoint of Artificial Intelligence, Machine Intelligence 4, (eds. Meltzer, B. and Michie, D.), pp. 463-502, Edinburgh University Press, 1969.

McDermott, D., et. al., PDDL - The Plan Domain Definition Language, Computer Science, Yale University,1997. http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/mcdermott.html

Moralee, S., Notes from Enterprise Project Workshop on "Content, Form and Methods for Ontologies", May 1994 IBM(UK) Offices, Nottingham, UK, Dated 25-Nov-94. http://www.aiai.ed.ac.uk/~bat/ontology-may94.html.

Navarro, T., 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, March 1996. http://www.cdif.org/overview/ProjectManagement.html

Neches, R., Fikes, R., Finin, T., Gruber, T., Patil, R., Senator, T. and Swartout, W.R., Enabling Technology for Knowledge Sharing, AI Magazine, 12(3), pp. 36-56, 1991. Reference and URL to be checked [AT]. http://www-ksl.stanford.edu/pub/knowledge-sharing/.

Pease, R.A. and Carrico, T.M., Object Modeling Working Group (OMWG) Core Plan Representation - Request for Comment, version 2, 24 January 1997, Defense Advanced Research Projects Agency. http://www.teknowledge.com/CPR2/

Pednault, E., ADL: Exploring the Middle Ground between STRIPS and te Situation Calculus", in Proceedings of the First International Conference on the Principles of Knowledge Representation and Reasoning, pp. 324-332, 1989.

Polyak, S. and Tate, A., Rationale in Planning: Causality, Dependencies and Decisions, Knowledge Engineering Review, Cambridge University Press, 1997. To be checked [SP]

Schlenoff, C. (editor), Knutilla, A., and Ray, S., Unified Process Specification Language: Functional Requirements for Modeling Processes, National Institute of Standards and Technology, Gaithersburg, Maryland, July 1996. http://www.nist.gov/psl/

Smith, S.F. and Becker, M., An Ontology for Constructing Scheduling Systems, Working Notes from 1997 AAAI Spring Symposium on Ontological Engineering, Stanford, CA, March, 1997 (AAAI Press). http://www.cs.cmu.edu/afs/cs/project/ozone/www/AAAI_Symp_On_Ontol_97/abstract.html

Swartout, W.R., Valente, A. and Gil, Y., Reference for work on JFACC Objectives and Activity Grammar. Not yet correct [BS]. http://www.isi.edu

Tate, A., A Plan Ontology - a Working Document - October 31, 1994, in the Proceedings of the Workshop on Ontology Development and Use, 2nd - 4th November 1994, La Jolle, CA. ftp://ftp.aiai.ed.ac.uk/pub/documents/1994/94-ont-plan-ontology.ps

Tate, A., O-Plan Task Formalism Manual, Version 2.3, July 12, 1995. Artificial Intelligence Applications Institute, University of Edinburgh. ftp://ftp.aiai.ed.ac.uk/pub/documents/ANY/oplan-tf-manual.ps

Tate, A. (editor), 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", Vol. 9. No. 1, pp.19-26, March 1996. A shorter version of [ref]. ftp://ftp.aiai.ed.ac.uk/pub/documents/1996/96-aiia-plan-ontology.ps

Tate, A., Representing Plans as a Set of Constraints -- the <I-N-OVA> Model, Proceedings of the Third International Conference on Planning Systems (AIPS-96), pp. 221-228, Edinburgh. Scotland, May 1996, AAAI Press. http://www.aiai.ed.ac.uk/~oplan/inova.html

Tate, A., (reporter) and the PIF Working Group, PIF and the Workflow management Coalition WPDL, Report of session at the PIF Workshop, Stanford University, 11-Jul-96. To be checked and get PIF-WfMC report online for URL [AT]. http://soa.cba.hawaii.edu/pif/

Tate, A., Drabble, B. and Kirby, R.B., O-Plan2: an Open Architecture for Command, Planning and Control, in Intelligent Scheduling (eds. Fox, M. and Zweben, M.), Morgan Kaufmann, 1994. http://www.aiai.ed.ac.uk/~oplan/

Tate, A., Hendler, J. and Drummond, M., A Review of AI Planning Techniques, in Allen, J., Hendler, J. and Tate, A. (eds.), Readings in Planning, pp. 26-49, Morgan Kaufmann, 1990.

Uschold, M.F., Filby, I.M. and Georges, M., EuroKnowledge - concepts and terminolopgy for Knowledge Sharing, Knowledge Engineering Review, Special Issue on Ontologies, 1998. To be completed [MFU]. http://www.aiai.ed.ac.uk/project/euroknow

Uschold, M.F., Moralee, S., King, M. and Ziorgios, Y., The Enterprise Ontology, Knowledge Engineering Review, Special Issue on Ontologies, Cambridge University Press, 1998. http://www.aiai.ed.ac.uk/project/enterprise/ontology.html

Wilkins, D.E. and Myers, K.L., A Common Knowledge Representation for Plan Generation and Reactive Execution, SRI International Artificial Intelligence Center. Journal of Logic and Computation, 1995. http://www.ai.sri.com/~act/act-formalism.html

Workflow Management Coalition Glossary -- A Workflow Management Coalition Specification, November 1994. http://www.aiai.ed.ac.uk/WfMC/

EXPRESS Information Modelling Language, ISO WD 10303-11. http://www.eurpc2.demon.co.uk/part11.html IDEF Reference to include. To be completed [SP]. http://www.idef.com

IBIS Reference and URL to include. To be completed [SP].

Entity-Relationship Modelling Reference and URL to include. To be completed [SP].

NIAM Reference and URL to include. To be completed [SP].

SADT Reference and URL to include. To be completed [SP].

Conceptual Graphs Reference and URL to include. To be completed [SP].

ISO STEP Reference and URL to include. To be completed [SP].

ORDIT Reference and URL to include. See Enterprise Ontology Paper. To be completed [AT].

Entities | Language | Object Model | CORBA IDL | Java | Formal Theory | Previous Issues | Current Issues | Revision History | Top of Document

Appendices

Detailed Entity Definitions

ENTITY

Parent Classes: None
Attribute NameValue TypeNo. of ValuesDefaults
NameSymbol0..1 
AnnotationAnnotationSyntax0..N 
ConstraintsEntityConstraintExpression0..N 

Attribute Descriptions:

Notes on Usage:
  1. Entity is the root of the all types. It provides the ability to specify Name, Annotations and Constraints for any entity in SPAR.
  2. Constraints: No reference to other entities is allowed - that is done through specific relationships - including the specialisation to Constraint and ActivityConstraint in particular. If more than one Constraint expression is provided it is treated as a conjunct of the expressions.
  3. EntityConstraintExpression [Issue 0007 relates to this]
Efficiency and Implementation Issues:
  1. There can be 0..N constraints. An implementation could insist that there was always a single EntityConstraintExpression which could be a logical expression wheer a conjunct was required. This might regularise handling of entity constraints in suitable constraint manager implementations.

ACTIVITY

Parent Classes: Entity
Attribute NameValue TypeNo. of ValuesDefaults
ActivityPatternActivityPatternSyntax1 
BeginTimePointTimePoint0..1A notional TimePoint entity that can only be referred to by <timepoint>.BeginTimePoint
EndTimePointTimePoint0..1A notional TimePoint entity that can only be referred to by <timepoint>.BeginTimePoint
ActivitySpecificationActivitySpecification0..1 

Attribute Descriptions:

Notes on Usage:
  1. ActivitySpecification may be absent for primitive activities, but if present for a primitive activity, no sub-activities may be included in that specification.
Efficiency and Implementation Issues:
ACTION

Parent Classes: Activity -> Entity
Attribute NameValue TypeNo. of ValuesDefaults

Attribute Descriptions:

Notes on Usage:
  1. Action is an abstract class to differentiate activity where the performing agent can be planned for (action) and activity where it cannot (event). It is provided to assist in clarity of modelling.

Efficiency and Implementation Issues:

  1. An implementation could conjoin activity, action and event.

EVENT

Parent Classes: Activity -> Entity
Attribute NameValue TypeNo. of ValuesDefaults

Attribute Descriptions:

Notes on Usage:
  1. Event is an abstract class to differentiate activity where the performing agent can be planned for (action) and activity where it cannot (event). It is provided to assist in clarity of modelling.

Efficiency and Implementation Issues:

  1. An implementation could conjoin activity, action and event.

TIMEPOINT

Parent Classes: Entity
Attribute NameValue TypeNo. of ValuesDefaults
UsesCalendarCalendar0..1Calendar nearest in scope
MinimumTimeTimeUnit0..1-Omega
ProjectedTimeExpression in ProjectedTimeSpecificationSyntax0..1 
MaximumTimeTimeUnit0..1+Omega

Attribute Descriptions:

Notes on Usage:

Efficiency and Implementation Issues:

  1. Note that minumum and maximum times are maintained as timeunits. They are directly relatable to a calendar time token or string, but these are not used in the entity attributes themselves. It is normal to convert to a TimeUnit on inout and to a CalendarTime token or string only on output to a user.
  2. There has been much work on the efficient engineering of time constraint handling in AI planners and beyond. An implementation could insist that the MinimumTime and the MaximumTime are always present (cardinality 1) and that a real value is always available even where an expression defines time. Such implementations could add another two attributes for the IntegerMinimumTime and IntegerMaximumTime, or use the ProjectedTime for the expression bearing attributes.

OBJECT

Parent Classes: Entity
Attribute NameValue TypeNo. of ValuesDefaults

Attribute Descriptions:

Notes on Usage:
  1. A primitive of the representation. Its attributes if defined are outside of the scope of SPAR. They may for example be defined by a product interchange specification such as ISO STEP [Ref].
  2. Specific types of defined object are Agent and Location.

Efficiency and Implementation Issues:

AGENT

Parent Classes: Object -> Entity
Attribute NameValue TypeNo. of ValuesDefaults
CapabilityAgentCapabilitySyntax0..N 

Attribute Descriptions:

Notes on Usage:
  1. An object may be used anywhere where a perform(activity,object) relationship may be specified. Agent only specialises object in that a capability description is available for agent.

Efficiency and Implementation Issues:

LOCATION

Parent Classes: Object -> Entity
Attribute NameValue TypeNo. of ValuesDefaults
LocationSpecificationLocationSpecificationSyntax1Universe

Attribute Descriptions:

Notes on Usage:
  1. Location entities would normally be used along with an "AtLocation" SpatialConstraint, itself a specialisation of ObjectConstraint.
  2. Note that its attribute is optional, but that the default of "Universe" has the not specifying any SpatialConstraint on the object.

Efficiency and Implementation Issues:

RELATIONSHIP

Parent Classes: Entity
Attribute NameValue TypeNo. of ValuesDefaults

Attribute Descriptions:

Notes on Usage:
  1. Relationship is an abstract parent class for more specific relationships such as Plan, Calendar, etc.

Efficiency and Implementation Issues:

  1. An implementation could omit the abstract class.

ACTIVITYCONSTRAINT

Parent Classes: Relationship -> Entity
Attribute NameValue TypeNo. of ValuesDefaults

Attribute Descriptions:

Notes on Usage:
  1. ActivityConstraint is an abstract parent class for more specific constraints such as ObjectConstraint, TimeConstraint, etc.

Efficiency and Implementation Issues:

  1. An implementation could omit the abstract class.

<constraint-type>CONSTRAINT

Parent Classes: ActivityConstraint -> Relationship -> Entity
Attribute NameValue TypeNo. of ValuesDefaults
ConstraintSpecification<constraint-type>ConstraintSyntax1 

Attribute Descriptions:

Notes on Usage:
  1. ConstraintSpecification: states the constraint in a form that is compatible with the appropriate syntax. The cardinality of the attribute is 1 indicating that a single expression is the value of the attribute. It could easily be 1..N meaning that the constraints were a conjunction of the set given. But there are other mechanisms to specify this. It cannot be cardinality 0 as that would negate the reason to have the entity present at all.
  2. Note that Constraint Managers and Domain Description language compilers used in planning systems may be able to use the grammars provided.

Efficiency and Implementation Issues:

  1. An implementation could provide further struture to implement specific syntaxes provided for the constraints.
  2. An implementation might choose not to provide the entity at all, since the expression of the constraint could be added to the higher level entities which add these constraints.

ENVIRONMENT

Parent Classes: Relationship -> Entity
Attribute NameValue TypeNo. of ValuesDefault
SPARVersionString0..1"Current Version"**
ActivityPatternSyntaxGrammar0..1MinimumActivityPatternSyntax**
ConstraintSyntaxGrammar0..1MinimumConstraintSyntax**
AgentCapabilitySyntaxGrammar0..1MinimumAgentCapabilitySyntax**
EvaluationCriterionSyntaxGrammar0..1MinimumEvaluation
CriterionSyntax**
AnnotationSyntaxGrammar0..1MinimumAnnotationSyntax**
ProjectedTime SpecificationSyntaxGrammar0..1MinimumProjectedTimeSpecificationSyntax**
LocationSpecificationSyntaxGrammar0..1MinimumLocationSpecificationSyntax**
DefaultCalendarCalendar0..1StandardCalendar**
OtherCalendarsCalendar0..N **

Attribute Descriptions:

Notes on Usage:
Efficiency and Implementation Issues:
  1. Note that all entity attributes are optional. In an implementation which uses fixed syntaxes for the various plug-ins, the environment entity could be omitted.
  2. It is possible to create additional entity structures in an implementation for some of the attributes of existing SPAR entities which are specified by a grammar, rather than processing them internally as an expression in the defined syntax.

WORLDMODEL

Parent Classes: Relationship -> Entity
Attribute NameValue TypeNo. of ValuesDefaults
SubWorldModelsWorldModel0..N 
ProcessesProcess0..N 
WorldStateConstraintWorldStateConstraintSyntax0..N 

Attribute Descriptions:

Notes on Usage:
Efficiency and Implementation Issues:

PLAN

Parent Classes: Relationship -> Entity
Attribute NameValue TypeNo. of ValuesDefaults
HasEnvironmentEnvironment0..1Environment nearest in scope
HasObjectivesObjective1..N 
HasActivitySpecificationActivitySpecification1..N 

Attribute Descriptions:

Notes on Usage:
  1. Plan is a relationship between one or more objectives and one or more (conjunctively) specification(s) of activity.

Efficiency and Implementation Issues:

PROCESS

Parent Classes: Relationship -> Entity
Attribute NameValue TypeNo. of ValuesDefaults
HasEnvironmentEnvironment0..1Environment nearest in scope
HasActivitySpecificationActivitySpecification1..N 

Attribute Descriptions:

Notes on Usage:

Efficiency and Implementation Issues:

  1. An implementation could conjoin ActivitySpecification and Process, so long as annotation and indexing facilities were provided in the way expected of a process.

OBJECTIVE

Parent Classes: Relationship -> Entity
Attribute NameValue TypeNo. of ValuesDefaults
HasEnvironmentEnvironment0..1Environment nearest in scope
HasEvaluationCriteriaEvaluationCriterion0..N 
HasObjectiveSpecificationActivitySpecification1..N 

Attribute Descriptions:

Notes on Usage:
  1. SPAR is deliberately designed such that the specification of objectives and the specification of activity (including the storage of case plans) is uniform.

Efficiency and Implementation Issues:

EVALUATIONCRITERION

Parent Classes: Relationship -> Entity
Attribute NameValue TypeNo. of ValuesDefaults
EvaluationCriterionSpecificationEvaluationCriterionSyntax0..N 

Attribute Descriptions:

Notes on Usage:

Efficiency and Implementation Issues:

SPECIFICATION

Parent Classes: Relationship -> Entity
Attribute NameValue TypeNo. of ValuesDefaults

Attribute Descriptions:

Notes on Usage:
  1. Specification is an abstract parent class for more specific relationships such as ActivitySpecification.

Efficiency and Implementation Issues:

  1. An implementation could omit the abstract class.

ACTIVITYSPECIFICATION

Parent Classes: Specification -> Relationship -> Entity
Attribute NameValue TypeNo. of ValuesDefaults
HasEnvironmentEnvironment0..1Environment nearest in scope
SubActivities:Activity0..N 
HasConstraintsActivityConstraint0..N 

Attribute Descriptions:

Notes on Usage:
  1. ActivitySpecification is an important entitysince it is the common point at which descriptions of processes, the activity related to a plan, the description of plan cases, plan library schemas and operators, etc is provided.

Efficiency and Implementation Issues:

  1. An implementation could omit the abstract class.

CALENDAR

Parent Classes: Entity
Attribute NameValue TypeNo. of ValuesDefault
CalendarNameSymbol1 
UnitsOfTimeSymbol0..1Second
BeginTimeCalendarTimeSyntax0..1"BeginOfTime"
EndTimeCalendarTimeSyntax0..1"EndofTime"

Attribute Descriptions:

Notes on Usage:
  1. TimeUnit are considered as integers. CalendarTimes are strings. Either representation may be used to specify calendar times for TimePoints or other metric time quantities in SPAR.
  2. A number of conversion routines are provided for calendars:
  3. Standard calendars will usually provided for calendar dates set to a particular start date (year, date and time relative to year 0, day 0, 00:00hrs) and times down to the level of a chosen time unit (days, hours, minutes, seconds or some decimal fraction of a second).
  4. As well as the StandardCalendar, other Calendars can be provided for project periods, calendar months from project start time (as date zero), shift periods, etc. A syntax convention will be adopted that allows the StandardCalendar times to be given simply with specific Calendars being able to be named in an upward compatible syntax..
  5. Concurrent use of more than one Calendar is supported in SPAR.
Efficiency and Implementation Issues:
  1. It would be usual to limit the internal representation of a plan or activity in a computer system to use only the integer TimeUnit representation throughout. Conversion to the string form being done on entry to the system, or when an external representation was needed, e.g. for human communication.
GRAMMAR

Parent Classes: Entity
Attribute NameValue TypeNo. of ValuesDefaults
BNFSyntaxStructure?1 

Attribute Descriptions:

Notes on Usage:

Efficiency and Implementation Issues:

Reference Language BNF

BNF convention used elsewhere in the document is:

The SPAR Language Design has not yet been started. However, some notes here from the PIF 1.1 language description [ref] are included to provide some initial ideas.

PIF 1.1 Language Notes

A number of domain specific grammars can be plugged into SPAR. The language design for these grammars has yet to be defined. However, a set of standard and minimum grammars for the definition of entities are provided (as defaults if no specific syntax is given), and to act as a basis for the development of domain specific grammars. These resources could be made available on-line for developers.

There are some predefined entity instances and constants of the basic types:

TypeStandard InstanceDefinition
ActivitySyntaxMinimumActivitySyntax Default ActivitySyntax to be determined.
ConstraintSyntaxMinimumConstraintSyntax A description of the <constraint-type> specific syntaxes included. By default this is the MinimumTimeConstraintSyntax and the MinimumObjectConstraintSyntax.
TimeConstraintSyntaxMinimumTimeConstraintSyntax Default TimeConstraintSyntax includes Before (TimePoint, TimePoint), Interval (TimePoint, TimePoint), Duration (Timepoint, Timepoint, TimeUnit) and CalendarTimeConstraint (CalendarTime, TimePoint [,Calendar]). PIF Successor (activity-1, activity-2) can be stated as Before (activity-1.EndTime, activity-2.BeginTime).
TimeConstraintSyntaxAllenTimeConstraintSyntax Allen temporal logic relationships [Ref]
ObjectConstraintSyntaxMinimumObjectConstraintSyntax Default Object ConstraintSyntax includes equal, not-equal and the MinimumActorConstraintSyntax
ActorConstraintSyntaxMinimumActorConstraintSyntax Default ActorConstraintSyntax includes perform
<other-constraint-type>SyntaxMinimum
<other-constraint-type>Syntax
Defaults for other <constraint-type>Syntaxes are empty
AgentCapabilitySyntaxMinimumAgentCapabilitySyntax Default AgentCapabilitySyntax is empty.
ProjectedTime
SpecificationSyntax
MinimumProjectedTime
SpecificationSyntax
Default ProjectedTimeSpecificationSyntax is empty.
LocationSyntaxLocationSyntax Default LocationSpecificationSyntax is empty.
EvaluationCriterionSyntaxMinimum
EvaluationCriterionSyntax
Default EvaluationCriterionSyntax is empty.
AnnotationSyntaxMinimumAnnotationSyntax Default AnnotationSyntax is empty.
AnnotationSyntaxWPDLAnnotationSyntax A Syntax for entity annotations which is compatible with the required and optional Workflow Management Coalition WPDL documentation structures.
AnnotationSyntaxWWWRDFAnnotationSyntax A Syntax for entity annotations which is compatible with the metadata descriptors from the WWW Consortium RDF Metadata format.
CalendarStandardCalendar Default Calendar
TimeUnitEpsilon Smaller than any other TimeUnit in any possible Calendar
TimeUnitOmega Larger than any possible TimeUnit in any possible Calendar (infinity)
SymbolYearTo specify a time unit of one year
SymbolMonthTo specify a time unit of one month
SymbolWeekTo specify a time unit of one week
SymbolDayTo specify a time unit of one day
SymbolHourTo specify a time unit of one hour
SymbolMinuteTo specify a time unit of one minute
SymbolSecondTo specify a time unit of one second
SymbolMillisecondTo specify a time unit of one millisecond
SymbolNanosecondTo specify a time unit of one nanosecond
Symbol...To specify a time unit of one ...
SymbolUniverseTo specify a Location that has no SpatialConstraints (yet)

Reference Object Model

As an example of the level at which the Reference Object Model will be provided, see the current OMWG Core Plan Representation Request For Comment document.

CPR Meta-model Diagram with Methods

OMWG Core Plan Representation - Request for Comment

Reference CORBA IDL

Not included in the current version of the SPAR Document.

Reference Java Implementation

Not included in the current version of the SPAR Document.

Formal Theory

As an example of the level at which the formal theory and semantics of SPAR may be expressed, a section of the draft NIST PSL's core theory is included here. From Christopher Menzel, Texas A&M University (cmenzel@tamu.edu) and KBSI (cmenzel@kbsi.com)

Part of the NIST PSL Core - Draft Theory

Previous Issues

The previous and current issues for SPAR are listed at http://www.aiai.ed.ac.uk/~arpi/spar/#issu. Issues addressed in this version and current issues are included in the appendices here.

Source:

Issue No. Version Date Source Raised By Core Handler Others Involved Aim to Resolve Resolved Version
00010.097-09-25CATATAP,BS,KM,SP,TC0.0a0.0a

Topic: Initial SPAR model
Related Issues: None
Further Details: None

An initial SPAR model version 0.0 for discussion at meeting 1 of the SPAR Core Group on 25-Sep-97 was created using the common elements from the ARPI Plan Ontology Constructor Group (POCG) work on KRSL-Plans (20-Sep-96 version), PIF 1.1, and recent discussions on NIST PSL. Details were added using experience from SRI's ACT, the Edinburgh <I-N-OVA> constraint model of activity and O-Plan TF; the CMU OZONE scheduling ontology; OMWG's CPR version 2 and recent experience of applying it to the JFACC C2 Schema requirements; and USC/ISI work on grammars to describe actions for the JFACC domain. A number of immediate points were made that needed change to create an initial model. These changes have been made in version 0.0a.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00020.097-09-25CATATAP,BS,KM,SP,TC0.0a0.0a

Topic:Explicit inclusion of Resource, Actor/Agent, Space/Location
Related Issues: None
Further Details: None

The subtypes of Constraint for space/location, resource and actor/agent are ontologically unnecessary as these three are specialized types of the fundamental entities in SPAR. All refer to "objects" in the domain. However, they are considered useful to aid modellers. This ontological relationship will be preserved by making spatial, resource and actor constraints be subtypes of object constraint.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00070.0a97-09-30CATATAP0.2 

Topic: Restriction on use of constraints attribute of Entities
Related Issues: None
Further Details: None

To reflect the design principle of attributes of entities only relating to properties/attributes of those entities and using separate entities to represent relationships between entities, it is desirable to clearly separate EntityConstraintExpression from the Constraint relationship expression (limited to expressions in the ActivityConstraintSyntax).

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00080.097-09-25CATAT 0.0a0.0a

Topic: Explicit inclusion of Authority/Control Constraints
Related Issues: None
Further Details: None

A constraint for authority (or a control in IDEF-0 parlance) to perform an action is not included in SPAR 0.0. A direct mapping from IDEF process descriptions to SPAR ones would be facilitated by the explicit inclusion of authority specifications. SPAR 0.0a includes AuthorityConstraint.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00170.097-09-25CKMATAP,KM,BS0.0a0.0a

Topic:Exclusion of Generic Node Type
Related Issues: None
Further Details: None

It was suggested that we only allow activities to be stated in an activity specification rather than allowing a more general class of nodes (activities and a range of "non-activity related" entities such as dummy nodes, and control nodes for split/join, etc). It was also suggested that DummyNode may be able to be handled by constraints among Activities where there are arbitrary hierarchies of Activities.

A dummy node as used in project management systems and so on is effectively a "do nothing" which is a perfectly valid "verb ..." expression anyway. Special version of these like "start" and "finish" are already in a verb like form "start the execution", "finish the execution".

Dropping Node does make the explanation of SPAR easier - which will be a good thing for earlier versions anyway. If we find problems later with node like objects we can always come back with a node based scheme. There are some consequences for other related design decisions. It would be wise to allow an activity pattern to be just a verb with no parameters - so "start" would be a legal action, as would "split", "join", "finish". a dummy would be "do nothing".

The 0.0a model drops Node.

Current Issues

The previous and current issues for SPAR are listed at http://www.aiai.ed.ac.uk/~arpi/spar/#issu. Issues addressed in this version and current issues are included in the appendices here.

0003, 0004, 0005, 0006, 0009, 0010, 0011, 0012, 0013, 0014, 0015, 0016, 0018, 0019, 0020, 0021, 0022, 0023, 0024, 0025, 0026, 0027, 0028, 0029, 0030, 0031, 0032, 0033, 0034, 0035,

Source:

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00030.0a97-09-30CATATAP0.2 

Topic: Explicit inclusion of issues remaining in a plan
Related Issues: 0009
Further Details: None

Issues remaining in plans and process descriptions are not explicitly included. They could be available as an attribute of plan or could be contained in the execution record of the meta-plan - the plan which describes the planning process.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00040.0a97-09-30CAPBSAP,AT0.2 

Topic:Representing evaluation criteria
Related Issues: None
Further Details: None

Evaluation criteria can be boolean (holds/does not hold) or provide a (preference) ranking (better/worse). Suitable ways to represent such criteria in SPAR are needed. Not sure that we need anything in the object model beyond the notion of Objective, EvaluationCriterion (a function on an Objective) and an Evaluation (which is the relation of a WorldState to an EvaluationCriterion), where the Evaluation may yield an arbitrary result from boolean to partial order to total order.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00050.0a97-09-30CATATKM,TC,AP0.1 

Topic: Better term for Plan to reflect range of uses
Related Issues: None
Further Details: None

Is there a better term for "Plan" in the ontology to reflect that it is used for storing partial-plans, fully worked out plans, case-library plans, sub-plan templates, primitive activity descriptions, etc. All relate objectives to an activity-specification.

AP adds - I agree for the need to minimize creating new concepts but think that this might be necessary. For example, I believe that plans have imprecision but not uncertainty. The execution record of a plan may have uncertainty. Plan templates have constraints on slot fillers. The difference is not so much in the definition of the different types of plans themselves but rather on the information which fills out the different types of plans. How that is modeled however is an open question.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00060.0a97-09-30CAPAPAT0.2 

Topic: Explicit inclusion of structure for uncertainty
Related Issues: None
Further Details: here

Uncertainty needs to be represented explicitly within the model. AP suggests that we need a base structure which gives "possible worlds" or consistent hypothesis sets. We'll also need a structure that coexists with the less formal structure. The more formal model will be Bayes Nets that can update the hypotheses according to a mathematical model.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00090.0a97-09-25CTCATTC,BS,AP0.2 

Topic: Planning process level representation - meta-level or workflow level
Related Issues: 0003
Further Details: None

How Evaluation (and other planning tasks/functions) fit into the model needs to be explained. These are actions in the "planning process". As well as the more usual representation of a specific plan domain in which actions take place as directed by the plan itself, SPAR can represent the planning process (either generically or for some specific domain planning specialization). It then uses suitable planning process activity verbs (such as "evaluation", "generate", "review", "execute", "schedule") and planning domain objects (such as an "air tasking order", a "plan document", etc). Different domain grammars for activity-expression are in use concurrently in such cases. SPAR must support multiple concurrent use for different domain grammars for activity-expression to allow for process vs. product level uses, and for multiple modelling levels, and structured use of non-shared or partially-shared models.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00100.097-09-25CSPSPAT,KM,BS,AP0.3 

Topic:Explicit representation of Plan (or Operator) Design Rationale
Related Issues: None
Further Details: None

Plan design rationale is not allowed for directly in SPAR - other than the hook of allowing annotations. At least structured use of such annotations will be necessary.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00110.0a97-09-25CKMKMSP,AT,BS0.3 

Topic: Selection criteria and indexing of Plans (also Cases and Operators)
Related Issues: None
Further Details: None

Selection criteria, indexing information and advice for retrieval or use of activity templates, cases, plans, etc are not allowed for directly in SPAR - other than the hook of allowing annotations. At least structured use of such annotations will be necessary.
Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00120.0a97-09-25CKMKMAT0.2 

Topic: Clearer description of how activity hierarchies are represented
Related Issues: None
Further Details: None

Better explanation is needed of how hierarchies of activities and their parental derivation are visible in the plan representation.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00130.0a97-09-25CKMKMAT0.3 

Topic: World State descriptions and constraints - open and closed world semantics
Related Issues: None
Further Details: None

Issues related to whether certain types of world state descriptions (and the conditions and effects that utilize those) used close or open world assumptions.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00140.097-09-25CAPAPAT0.2 

Topic: Details needed for World Model description
Related Issues: None
Further Details: None

The issue of a world model and past, present and future state (static, dynamic and domain events/processes, etc). is underdeveloped in the work to date.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00150.097-09-25CATATBS0.3 

Topic: Alternative description framework for the SPAR document
Related Issues: None
Further Details: None

It may be desirable to use a LOOM-like descriptive logic rather than specific types and sub-type in the SPAR document.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00160.097-09-25CKMATKM,BS0.2 

Topic: Should an activity specification have at least one activity included
Related Issues: None
Further Details: None

Should it be mandatory to include at least one activity in an activity specification (1..N rather than the current 0..N in SPAR version 0.0a).

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00180.0a97-09-25CAPAPAT0.1 

Topic: ActivitySpecification and/or Process may be superfluous
Related Issues: None
Further Details: None

ActivitySpecification may be superfluous. It is possible to combine Process and ActivitySpecification so long as annotation/documentation and indexing facilities are provided on the conjoined entity.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00190.0a97-09-25CAPAP 0.2 

Topic: Sub-types of Plan and plan information
Related Issues: None
Further Details: None

We need some appropriate labeling of plans.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00200.0a97-09-25CATBSAT0.2 

Topic: Two SPAR Language Presentations
Related Issues: None
Further Details: None

There are two possible routes (at least) for the SPAR language. One would be to take the object/attribute/relation style structure and to simply flatten it. This has some merits for systems that use internal data structures (say an object model) that is close to the SPAR entity definition. The disadvantage of this approach is that reified structures are created which do not structure things in any natural way for human consumption. It also can lead to very large descriptions to say very simple things. KRSL 2.0.2 has such an approach.

An alternative is to use the the main semantic entities themselves as a basis for the language structure. Things like activity, process, plan, objective, world model, agent, etc. This has the advantage that the descriptions are much more meaningful to humans, and can be readily used in (constraint supporting) editors and the like. This approach is taken in O-Plan TF and SRI's ACT.

A possibility is to allow for both of these languages in SPAR. This would be compatible with the NIST PSL and CDIF standards notion that multiple "presentations" are possible to communicate a single underlying model. [Issue being considered by BS]

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00210.0a97-10-01CATATAP0.2 

Topic: Possible sub-structures for a range of SOAR entities
Related Issues: None
Further Details: None

Should Objective, ActivitySpecification, ActivityConstraint and WorldStateConstraint have an attribute Sub-XXX to themselves. This would allow very simple merging of such specifications and constraint descriptions. The semantics is simple (conjunction of all the constraints in the specifications). But there are other ways to describe this conjunction in the representation already. Is such redundancy desirable?

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00220.0a97-10-03CATAT 0.2 

Topic: Clarification of relationship, function, property, Attribute and Role
Related Issues: None
Further Details: None

The following paragraph could add detail to the section on Terminology. A more detailed description of the same thing is available in the Enterprise Ontology if alternative text is required [ref].

Some means to regularise the terminology used to associate functional or truth values with some relationships is also required. The following three definitions seek to do this in a general and minimum commitment way.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00230.0a97-10-03CATBSKM,AT,AP0.3 

Topic: Temporally Scoped Relationships - such as Activity Status
Related Issues: None
Further Details: None

It is possible to add temporally scoped versions of some relevant static attributes to SPAR as new RELATIONSHIPS. In this case, the original static attributes specified in SPAR still hold true for all time. ACTIVITY-STATUS is an example of a relationship between a time specification and an activity).

An example of one such RELATIONSHIP in SPAR is ACTIVITY-STATUS which is used to represent the status (e.g. COMPLETED, DELAYED, PENDING) of an ACTIVITY at different times. ACTIVITY-STATUS is one example of a dynamic property of those entities commonly used in process modeling and workflow systems and modelled in SPAR.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00240.0a97-10-03CATBSKM,AT,AP0.3 

Topic: Soft Constraints
Related Issues: None
Further Details: None

Soft constraints are yet to be explicitly provided for.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00250.0a97-10-04CATAT 1.0 

Topic: Extension Mechanism and Registration Process
Related Issues: None
Further Details: None

A mechanism for extension of SPAR structure beyond the plug-in grammars should be considered.

A mechanism to register such extensions and have them made available should be considered.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00260.0a97-10-05CATAT 0.2 

Topic: AuxiliaryConstraints
Related Issues: None
Further Details: None

An entity type called AuxiliaryConstraints could be introduced to cluster all the ActivityConstraints other than Object and TimePoint Constraints which are more fundamental to the model, and which have an influence on the other constraints through object correspondences and temporal relationships. There are specific minimum requirements on Object and TimePoint Constraints whereas the other constraints have no minimum requirements. Clustering them under a single type could make modularity of the structure more easily preserved as advances take place in the unification of approaches to handling constraints in planners and schedulers.

The terminology of Auxiliary Constraints arises from the treatment of constraints in refinement style planners [Khambhampati, 1997]

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00270.0a97-10-05CATAP 1.0 

Topic: Translatability to CDIF
Related Issues: None
Further Details: None

It could be worth ensuring that SPAR language syntax can be represented in and communicated through CDIF (http://www.cdif.org).

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00280.0a97-10-05XOLAP 1.0 

Topic: WWW Consortium RDF for metadata description for publishing SPAR plans on the WWW
Related Issues: None
Further Details: None

OL = Ora Lassila of the WWW Consortium

Relating to the actual (physical) distribution of plans, ontologies etc., we (the World Wide Web Consortium) have on 3-Oct-97 released the first public draft of a standard proposal for distributed WWW-based metadata. The system could be a basis for building actual knowledge representation systems for the web.

This could be relevant to SPAR in two ways:

  1. The linearization is very concise and also human-readable - a good model for the SPAR language.
  2. It is relevant for how we might want to think about presenting plans to people and putting plans on web pages. The issue then would be how to aggregate plan information in meaningful ways for web presentation. AP believes that translating a SPAR plan description into RDF itself wouldn't be that hard. He will consider a "publishing" service for the design of the SPAR reference implementation which would present plans as web pages and tag the pages with RDF.

SPAR could provide a plug in grammmar for annotations that allows for markup of a plan for publishing in WWW RDF format (WWWRDFAnnotatonSyntax).

http://www.w3.org/Press/RDF

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00290.0a97-10-05CSKBSAT1.0 

Topic: Use of PDDL as a base for detailed activity and world state models
Related Issues: None
Further Details: None

SK = Subarrao Khambhampati. Also raised by DW = Drew McDermott.

The SPAR framework may be able to use PDDL [Ref] to provide the recommended detailed models for actions constraints (based on HTN - UMCP [Ref]) and for situations/state (based on ADL [Ref]).

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00300.0a97-10-06CAPAP 1.0 

Topic: Possible presentation in UML
Related Issues: None
Further Details: None

It could be an advantage to have a clear mapping to the Unified Modelling Language (UML).

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00310.0a97-10-06CBSBSAT0.3 

Topic: More detailed model for SPAR Object entity
Related Issues: None
Further Details: None

It may be an advantage to use a more expressive object representation in SPAR. There could be benefits in using more sophisticated KR systems, and a lot could be gained by closer coupling between the KR and planning communities. Candidates we should consider would include KIF, Ontolingua, Loom and PowerLoom. All of these are well-documented and widely used representations, so they would providing an existing basis to build upon. Furthermore, using any one of them would help make the SPAR effort more connected with the various ontology efforts that DARPA is supporting. We need to think through what the tradeoffs are in using a more sophisticated representation.

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00320.0a97-10-06C??BSAT0.2 

Topic: Explicit inclusion of variables
Related Issues: None
Further Details: None

Variables can be used at entity level (by being used inexpressions in attributes, including the Properties extension attribute. Variables may also be associated with any Environment. Variables lists including variable names, restrictions and values may be stated. Shoudl these be separate entities, declared only in plug in syntaxes thta use variables (for flexibility), or inlcuded as fixed attributes of entity (EntityVariables 0..N) and the environment entity (EnvironmentVariables 0..N).

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00330.0a97-09-25C????   

Topic:
Related Issues: None
Further Details: None

Issue No. Version Date Source Raised By Core Handler Others Involved Target to Resolve Resolved Version
00xx0.0a97-09-25C????   

Topic:
Related Issues: None
Further Details: None

Acronyms and Abbreviations

Acronym and ReferenceMeaning
CDIFCASE Data Interchange Format
IDEFIntegrated DEFinition
<I-N-OVA>Issues, Nodes, Orderings/Variables/Auxiliary Constraint Model of Activity
O-PlanOpen Planning Architecture
......

Revision History

Version NumberVersion DateDocument
0.025-Sep-97 Initial model diagram from SPAR Core Group Meeting 1
0.0a06-Oct-97 Initial SPAR document prepared by Austin Tate
0.0b?? Current Working Copy
1.031-Oct-97 First published version

ARPI Home Page | SPAR Home Page | Top of Document
AIAI Page maintained by Austin Tate (a.tate@ed.ac.uk), Last updated: Fri Apr 28 14:03:14 2000
Please make contact if you have any comments on these pages or the SPAR Project.