AIAI O-Plan

<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

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


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":

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>

O-Plan Index
AIAI Page maintained by oplan@aiai.ed.ac.uk, Last updated: Tue Nov 28 19:47:14 2006