Plan Ontology based on <I-N-OVA> Constraint Model of Activity

Austin Tate, 16-Oct-96

Introduction

An introduction to the <I-N-OVA> Constraint Model of Activity and papers concerning the model and the Ontology of Plans which it relates to are given here.

This page provides an object model of <I-N-OVA> and the Plan Ontology suggested by these papers. It is still under development.

The ontology is intended to act as a minimum core on which extensions can be made in a consistent, structured fashion. It is meant to support both the meta-level of reasoning about the activities involved in the planning process and the domain object level in which the plans are meant to be executed.

Core Model of Plans and Activity

The model sits within the real world in which behaviour can occur. Behaviour is the performance of one or more real world activities (a non-empty set of activities). A description of the behaviour possible in the real world may or may not be included in the model - with more or less accuracy if included. The environment is notionally considered to be the agent supplying the force behind any non-modelled behaviour or the cause of any difference between behaviour that actually occurs in the real world and that predicted by the model. The real world behaviour is shown in the diagrams as lighter coloured boxes which are not actually represented within the model itself.

Part of the space of behaviour is modelled more or less accurately by activities.

A plan consists of a set of constraints on the behaviour possible in the real world. The plan specifies, more or less accurately, a sub-set of real world behaviour.

An activity models, more or less accurately, a sub-set of real world behaviour.

An activity takes place over a period of time from its begin time point to its end time point. The begin of an activity is temporally before the end of the activity. The distance between the begin and end time points is referred to as the activity duration.

It is possible to provide more or less accurate models of activities which occur through the force of the environment, in this case the activities are termed events. For the avoidance of doubt, the notes below which refer to activities also refers to the more specialised events.

An activity may optionally be modelled at a more detailed level of description by one or more alternative sets of constraints on real world behaviour (in the same format as plans). There is a deliberate uniformity of representation of the detailed decomposition of an activity and a plan (sub-plan).

An agent may hold purposes of two types: requirements (defined as hard constraints on a behaviour in the real world if the agent's requirements are to be satisfied) and preferences (desirable or soft constraints which may be partially satisfied). An agent may also adopt plans to relate to their requirements and preferences.

Each constraint is added to a plan by an agent. This may be because the agent is setting the requirements (task, aim or objectives) on the plan by including the agent's requirements or preferences directly. Or the agent may be part of the planning process and add a constraint on real world behaviour in a way which supports the executability and relevance of a plan. The agent adding the constraint will provide an indication of the hard or soft nature of the constraint. Its is likely that objective functions or other evaluation criteria will be given which can allow the degree of satisfaction of a soft constraint to be measured.

Organisational Context

Agents may also have relationships with other agents, which can express organisational and authority relationships.

This simple model forms a basis for extensions while allowing some context to be provided for the relationships between agent's requirements, preferences, adopted plans and constraints added into plans.

Entities Used in Various Places

A time point represents a specific, instantaneous, point along a time line which is an infinite sequence of time points. It is possible to associate one or more calendars with the time line, and to specify the minimum resolution of the distance between any two such points. A time point is considered to have a finite duration of epsilon, which is below the finest resolution available in the model. Informally, a time point therefore has two "sides" (a "before" "in" side, and an "after" or "out" side).
A node represents an activity or an other node. An other node is an entity within the plan which is used to facilitate the description of the plan logic and temporal ordering relationships. The inclusion of dummy nodes in plans may simplify the writing of other constraints.
Recall that an activity is associated with two time points, representing its begin and end time points. The begin and end time points of any node can be referred to in plan temporal relationships and other plan logic. An other node may be a dummy node which is associated with a single time point (actually its begin time point and its end time point are associated with a single time point). Examples may include start of plan, finish of plan, or-split, or-join, and-split and and-join. There is no sub-plan associated with such a dummy node.
An other node may also represent a conditional if/then/else within the plan. Such a conditional will have two associated sub-plans for the alternative branches. An alternative that might have been used in the model for conditionals could have specified two separate end points for the then and the else branches (hence using three distinct time points in the encapsulation). This latter approach may be more flexible, but would not allow reasoning about conditionals as a block by systems that may not be able to deal with the conditional logic in detail. An other node may also represent an encapsulation of an iteration or for-each which is associated with two time points. Such an encapsulation will have an associated sub-plan which is the object of the encapsulation.
An entity variable allows reference to an entity without naming the specific entry. An entity variable is a virtual entity which anticipates a deferred real entity.

Defining Constraints

The content of a constraint is represented by any one of a range of different constraint types. These are:

Include Activity which says that a given activity should be included in any real world behaviour specified by the plan.
Issue which is an outstanding aim, objective, preference, task, flaw or other issue which remains to be addressed by the plan. Issues provide implied constraints on the real world behaviour specified by the plan.
Issues are represented by a verb, zero, one or more noun phrases and zero, one or more qualifiers. An issue expressed a "to-do" item which may act upon the parameters expressed as noun phrases, and which is scoped or restricted by any qualifiers given. Noun phrases and qualifiers are stated as expressions involving other entities associated with the planning process or plan.
Other Constraint which says that one of a range of different constraints types should be satisfied in the real world behaviour specified by the plan.

Include Activity and Issue constraints are separated out as they are so important to the reasoning methods normally associated with the planning and enactment processes. They also relate very strongly to defining the sub-space of real-world behaviours which are referred to by a plan. The rest of the constraints can be seen as further filtering the sub-space principally defined by the include activity and issue constraints.

Each of the other constraints includes an expression, nominally in first order logic, which specifies an assertion that can be evaluated with respect to a plan as "something that may or may not hold for behaviour performed in the real world". The format of this expression is different for each of the various other constraint types.

The terms of an expression may include:

node - as well as the specific "Include Activity" constraints, other constraints on activities and other nodes with respect to a plan are possible, e.g.,
- do not include a given activity
- limit the activity in some way (e.g., activity should be performed by a specified agent)
- include a node other than an activity node (i.e. "other node") to describe plan ordering, conditionals, etc. This can include:
  - dummy nodes, plan start and finish nodes, or-split, or-join, and-split, and-join
  - iterate, for-each
  - conditional (if/then/else)
agent - it is possible to specify that an agent should be the performer of any given activity.
time point - it is possible to specify temporal relationships directly between time points, and, through the association of time points with the begin and end of an activity, between activities themselves. Constraints involving terms which are all time points are termed time point constraints to differentiate them from more general "temporal constraints" involving other terms as well as time points. E.g., time points constraints include:
- before(tp1,tp2)
- not-between(tp1,tp2,tp3)
- interval-not-during-interval(tp1,tp2,tp3,tp4)
However, time points also play a large part in expressions for other types of constraint concerning statements involving other entities associated with a plan which have temporal scope. These temporal constraints may be:
- metric temporal constraints - involving one time points - to relate a given time point to an actual time or calendar reference.
- input temporal constraints - involving one time point - the constraint should hold immediately before the given time point.
- output temporal constraints - involving one time point - the constraint should hold immediately after the given time point.
- range temporal constraints - involving two time points - the constraint should hold at all times between the two given time points.
- other temporal constraints - involving one or more time points.
entity variable - it is possible to specify entity variable relationships directly between variables, and, through the implied association between variables and the deferred real entity to which it refers, between other entities. E.g.,
- equal(var1,var2)
- not-equal(var1,var2)
However, entity variables also play a large part in expressions for other types of constraint concerning statements involving other entities associated with a plan which are only partially specified.
other entity - all other domain entities not specifically defined elsewhere. E.g.,
- Resources or tools
- documents and other artifacts being manipulated by real world behaviour.
expression - an expression may itself refer to other expressions.

Suggestions for Using the Representation

The following sections give ideas for ways in which the plan representation may be used, and are based upon the experience of using plan representations within the O-Plan project, and other planning systems and aids developed by AIAI.

Always Plan -- Representing Domain Constraints which "Always" Hold

A description of the invariant constraints on behaviour in the real world may or may not be included in the model - with more or less accuracy if included. The set of constraints which always hold may be held as a single Always Plan. Notionally, the planning process and plan reasoning should consider the constraints in the Always plan as a basis for all other plans in the domain. They need not be explicitly added to any plan - since they (more or less accurately) hold anyway. Usually, only those parts of the invariant constraints on behaviour in the real world which are analysed as possibily impacting upon the plans under consideration will be explicitly represented. Note that distribution of the "always" constraints to only those parts of the reasoning systems which need to make use of specific parts of the model is possible.

External Event and Process Models

It is possible to use the same representation to describe events and processes which are beyond the control of the agents which can perform activities which can be included in plans. The set of constraints which which represents these "external" events and processes may be held as a single External Event and Processes Plan (as is done in the DEVISER planner (Vere, JPL). Notionally, the planning process and plan reasoning should consider the constraints in the External Event and Processes Plan as a basis for all other plans in the domain. They need not be explicitly added to any plan - since they (more or less accurately) hold anyway. Usually, only those parts of the external events and processes which are analysed as possibily impacting upon the plans under consideration will be explicitly represented. Note that distribution of the "external events and processes" constraints to those parts of the reasoning systems which need to make use of parts of the model is possible.

Initial Plan -- Task Assignments, Options, Phases and Plans

In O-Plan, an Initial Plan is created which describes the mistask assignment to the O-Plan planner.

O-Plan allows for a task assigner to associate various meaningful names with different variants of task assignments (called options and sub-options). O-Plan also allows a task assigner to associate names with various phases and levels of a task assignment or plan. This can help in mixed initiative working between users and the planning system.

Cases, Plans, Process Models, Activities and Sub-activities

The plan representation allows for a uniform representation of case libraries and plans manipulated by a planning system. This can be useful for generalising plans for re-use in future, and for selecting from a case library to create an "Initial Plan" which the planner can be given as its task assignment.

Likewise, activities, the combination of them into Process Models, or the decomposition of them into sub-activities all can employ a common representation.

PlanWorld Views

The plan representation can support multiple types of user view. O-Plan differentiates technical plan structure oriented views (called Plan Views) and world or domain related views (called World Views). Plan Views may include such presentations as:

activity/sub-activity breakdown structures
PERT Charts
Gantt Charts
Workflow wavefront and to-do lists
Role/activity diagrams and state charts
Justifications

World Views may include such presentations as:

Simulations and animations
Explanations

Planning Annotations and Dependencies

The plan representation allows for direct recording of the agent which added each constraint and inter-constraint dependencies are recorded in key instances within the the expressions representing the constraints (e.g. in O-Plan, the "contributor" activities which provide world state effects which satisfy condition requirements on other activities are recorded explicitly in the goal structure expressions for each condition).

However, there are cases where other information about the planning process and the decision taken must be maintained. O-Plan provides a Notepad for this (this was called the Jotter in the earlier NONLIN planner. The entries on the Notepad are called notes and are handled in the same way as any other constraint. The notepad can be used in O-Plan to keep track of the approach being taken in different plan options and to provide guidance to the user by way of reminder notes about ways in which issues should be addressed within the approach adopted.

Plan Quality and Evaluations

It is possible to incorporate quality statements within a plan. These would be stored as miscellaneous constraints if they were described in a fixed syntax or could be kept as more informal "notes" in the "notepad" otherwise. Plan quality analysis functions could utilise these constraints or notes to add information to the plan for communication to other agents or system components.

Mixed Initiative Planning

The plan representation is intended to form a basis for links between planning agents, scheduling agents and enactment systems, where people and systems are working in a mixed initiative fashion. The model of mixed initiative planning supported is that is mutually constraining the space of behaviour.

Attributes of the Objects in the <I-N-OVA> Model

Plan

constraints: zero, one or more Constraint objects.

Constraint

addedBy: an Agent object corresponding to the agent which caused this constriant to be added to a plan.
softHardInformation: a description of whether the constraint is one which must be enforced (termed a "hard" constraint), or is a preference (termed a "soft" constraint). This specification is deemed to be specified by the "addedBy" agent and thus the reponsibility of that agent. Details of the criteria for evaluating the degree to which a soft constraint is satisfied may be provided.
constraintContent: one of three types of specialised constraint object represented by an Issue object, an Include Activity object or the general OtherConstraint object

OtherConstraint

expression: an Expression object which gives a description of the constraint.

HandleIssue

verb: symbol.
nounPhrases: one or more Expression objects.
qualifiers: zero, one or more Expression objects.

An Issue object is considered to be a specialised type of Constraint with a prespecified structure for some of the terms in that constraint. This allows for more regularity in handling.

IncludeActivity

activity: a Node object representing the activity to be included.

An IncludeActivity object is considered to be a specialised type of Constraint with a prespecified structure for some of the terms in that constraint. This allows for more regularity in handling.

Expression

terms: one or more terms which may be symbols or other Expression objects.

Node

beginTimePoint: optionally, a TimePoint object may be associated with the begin of the node. It need only be explicitly named if there are to be constraints specified that refer to the time point.
endTimePoint: optionally, a TimePoint object may be associated with the end of the node.
subPlans: zero, one or more descriptions of the node at a greater level of detail.

Notionally, all nodes have an implied begin and end TimePoint object associated with them. They need only be explicitly provided if there are to be constraints specified that refer to such time points. Expression object terms which include beginTimePoint(Node) or endTimePoint(Node) are understood to stand in for these TimePoint objects.

Agent

hasRequirements: zero, one or more Constraint objects describing the requirementss (hard constraints) which the agent wishes to have satisfied.
hasPreferences: zero, one or more Constraint objects describing the preferences (soft constraints) which the agent wishes to have satisfied to a greater or lesser degree.
hasPlans: zero, one or more Plan objects referring to the Plans which the agent has adopted. These will usually be adopted against one or more Requirements and Preferences.

EntityVariable

No attributes are defined in the basic <I-N-OVA> model.

TimePoint

No attributes are defined in the basic <I-N-OVA> model, though it will be usual to add specifications of minimum and maximum times along some time line which can be related to one or more calendars.

OtherEntity

No attributes are defined in the basic <I-N-OVA> model.

AgentRelationship

relationship: symbol representing the relationship between the agents.
agents: two or more agents involved in the named relationship.

O-Plan Index | <I-N-OVA> Home Page

Page maintained by oplan@ed.ac.uk, Last updated: Fri Nov 12 10:03:00 1999