<I-N-OVA> Constraint Model of Activity
and its successsors <I-N-CA> and <I-N-C-A>
Work is described which seeks to use a common representation of tasks,
plans, processes and activities based on the notion that these are all
``constraints on behaviour''. This representation can form a basis for
mixed initiative user/system agents working together to mutually
constrain task descriptions and plans and to coordinate the
task-oriented enactment of those plans. It is well suited to an
incremental refinement approach to planning as is found in many modern
planners. It forms a potentially useful bridge between practical work
on planning, theoretical descriptions of planning, constraint
management, and work in other fields such as workflow and process
management.
The <I-N-OVA> (Issues - Nodes - Orderings/Variables/Auxiliary)
Model is a means to represent plans as a set of constraints. By having
a clear description of the different components within a plan, the
model allows for plans to be manipulated and used separately from the
environments in which they are generated. The underlying thesis is
that plans can be represented by a set of constraints on the
behaviours possible in the domain being modelled and that plan
communication can take place through the interchange of such
constraint information.
<I-N-OVA> is intended to act as a bridge to improve dialogue
between a number of communities working on formal planning theories,
practical planning systems and systems engineering process management
methodologies. It is intended to support new work on automatic
manipulation of plans, human communication about plans, principled and
reliable acquisition of plan information, and formal reasoning about
plans.
Constraint Types
I - Issues (Implied Constraints)
N - Node (Activity) Constraints
- include node constraints
- other node constraints
OVA - Detailed Constraints
O - Ordering Constraints
V - Variable Constraints
A - Auxiliary Constraints
- Authority Constraints
- World State Constraints
- Resource Constraints
- Spatial Constraints
- Miscellaneous Constraints
The node constraints (these are often of the form ``include
activity'') in the <I-N-OVA> model set the space within which
a plan may be further constrained. The I (issues) and OVA constraints
restrict the plans within that space which are valid. Ordering
(temporal) and variable constraints are distinguished from all other
auxiliary constraints since these act as critical constraints
or cross constraints, usually
being involved in describing the others -- such as in a resource
constraint which will often refer to plan objects/variables and to
time points or intervals.
Mutually Constraining Plans for Mixed Initiative Planning and
Control
The model of Mixed Initiative Planning that can be supported by the
approach is the mutual constraining of behaviour by refining a set of
alternative partial plans. Users and systems can work in harmony
though employing a common view of their roles as being to constrain
the space of admitted behaviour. Further detail is given in
Tate (1994).
Workflow ordering and priorities can be applied to impose specific
styles of authority to plan within the system. One extreme of user
driven plan expansion followed by system ``filling-in'' of details, or
the opposite extreme of fully automatic system driven planning (with
perhaps occasional appeals to an user to take predefined decisions)
are possible. In more practical use, we envisage a mixed initiative
form of interaction in which users and systems proceed by mutually
constraining the plan using their own areas of strength.
Documents
- Representing Plans as a Set of Constraints - the <I-N-OVA>
Model - Austin Tate - Proceedings of the Third International
Conference on Artificial Intelligence Planning Systems (AIPS-96) -
Edinburgh, May 1996 -
113K
ps file.
This is a more detailed version of a paper that first appeared in
SIGART Newsletter January 1995.
- Towards a Plan Ontology - Austin Tate - Newsletter of the Association
for Italian Artificial Intelligence (AIIA) - 1996 -
98K ps file.
This is an updated version of a document giving input to the Workshop
on Ontology Development and Use, 2nd - 4th November 1994, La Jolle, CA
- Mixed Initiative Planning in O-Plan2 - Austin Tate - 1994 -
150K ps file -
Proceedings of the ARPA/Rome Laboratory Planning Initiative Workshop,
pp. 512-516, (Burstein, M., ed.), Tucson, Arizona, USA, Morgan
Kaufmann.
Plan Ontology and Object Model
An object model of a Plan Ontology based on <I-N-OVA> and
suggested by these papers is available
(here).
It is still under development.
<I-N-OVA> Rationale
Information which motivates the use of the different types and
sub-types of constraint within the <I-N-OVA> model is described
here.
Planning is the taking of planning decisions (I) which selects the
activities to perform (N) which creates, modifies or uses the plan
objects or products (V) in the correct time (O) within the authority,
resources and other constraints specified (A).
The node constraints (these are often of the form ``include
activity'') in the <I-N-OVA> model set the space within which
a plan may be further constrained. The I (issues) and OVA constraints
restrict the plans within that space which are valid.
The Issues (I constraints, sometimes called "flaws" in earlier
planning work) are the items on which selection of Plan Modification
Operators is made in agenda based planners.
Others have recognised the special nature of the inclusion of
activities into a plan compared to all the other constraints that may
be described. Subbarao Khambhampati and Biplav Srivastava in
"Unifying Classical Planning Approaches" (Arizona State University ASU
CSE TR 96-006, July 1996) differentiates PMOs into progressive
refinements which can introduce new actions into the plan, and
non-progressive refinements which just partitions the search
space with existing sets of actions in the plan. They call the former
genuine planning refinement operators, and think of the latter as
providing the scheduling component.
If we consider the process of planning as a large constraint
satisfaction task, we may try to model this as a Constraint
Satisfaction Problem (CSP) represented by a set of variables to which
we have to give a consistent assignment of values. In this case we can
note that the addition of new nodes ("include activity" constraints in
<I-N-OVA>) is the only constraint which can add variables
dynamically to the CSP.
Issues can be categorised as to whether
they will, may or will never add a "node":
I - Issues (Implied Constraints)
- will add or may add an "include node" constraint
- will not add an "include node" constraint
Clearly the I constraints which can lead to
the inclusion of new nodes are of a different nature in the planning
process to those which cannot.
Ordering (temporal) and variable constraints are distinguished from
all other auxiliary constraints since these act as or cross constraints, usually being involved in
describing the others -- such as in a resource constraint which will
often refer to plan objects/variables and to time points or
intervals.
Sorted First Order Logic Base
<I-N-OVA> is meant as a conceptual model which can underly any
of a range of languages which can describe activities, plans and
processes. For example, O-Plan uses the
Task Formalism domain description language which has a simple
keyword introduced syntax (see examples here).
It is anticipated that any <I-N-OVA> model in whatever language
or format it is expressed can be reduced to a conjunctive set of
statements in first order logic with strong requirements on the type
of the terms involved in each statement - i.e. a Sorted First Order
Logic. Such representations are being studied by others as a
general interlingua between planning and scheduling systems (for example
in joint work between AIAI and David Joslin while at CIRL, University of Oregon
http://www.cirl.uoregon.edu/).
Joslin, D., Planner/Scheduler Interface Proposal, Draft,
CIRL, University of Oregon, 17-May-96.
joslin-sorted-fol.ps.
Placed here with permission of David Joslin. Please do not distribute
further.
A use of Sorted First Order Logic to describe <I-N-OVA> is
provided in the following paper.
Polyak, S.T. and Tate, A., A Common Process Ontology for
Process-Centred Organisations, Knowledge Based Systems, 2000. unavailable. Earlier
version published as University of Edinburgh Department of Artificial
Intelligence Research paper 930, 1998. 804KB ps
file
Use Beyond Plan and Activity Representation - <I-N-CA>
As well as for planning, we have related the same approach to design
and configuration tasks with I, N, CA components - where C are the
"critical constraints" in that particular domain - much as certain O
and V constraints are in a planning domain. We believe that the
approach is valid in design and other synthesis tasks more generally -
we consider planning to be a limited type of design activity.
<I-N-C-A>
The most recent rendering of the representation is <I-N-C-A>
- Issues
- Nodes
- Constraints
- Annotations
Page maintained by oplan@aiai.ed.ac.uk,
Last updated: Tue Nov 28 19:47:14 2006