Proposal

Classifying Constraints | Temporal and Resource Models | Commitment Function | Mutual Support Function | HAI Mechanisms | Back

Classifying Constraints

A way to understand the planning process is via the elements that have influence on it. Considering that each of such elements is represented as a set of constraints Ci, we have the scenario illustrated below:

According to this figure, we can identify the following sets of constraints:

  • C0: represents the set of constraints imposed by the environment such as weather conditions or the state of world objects;

  • C1: represents the set of constraints that restricts the planning process in adding new activities into the agent's plan (agenda). This set is specified via the temporal model according to Requirement 1;

  • C2: represents the capabilities and internal state of agents that, together, restrict the kind and amount of activities that they can perform. C2 of subordinate agents also restrict the creation of plans by its superior. This set is specified via the resource model according to Requirement 2;

  • C3: represents the constraints associated with the process of commitment. Each delegated activity has one constraint C3, whose value indicates if a specific agent is committed to the performance of such an activity. The value of C3 is generated via the commitment function F1, which is specified according to Requirements 3 and 4;

  • C4: represents the set of constraints used by humans to control/customise the behaviour of agents, according to the Requirement 8;

  • C5: represents the set of constraints that restricts the options of the human user. Its definition is in accordance with Requirement 7;

  • C6: represents the set of constraints associated with activities of other agents. The function F2 acts on C6 to discover possible inconsistencies in such a set, so that agents can mutually support each other according to Requirement 5;

  • C7: represents the set of all constraints monitored by the function F3, which accounts for generating explanations in accordance with Requirement 9;

  • C8: represents the set of constraints that accounts for providing a declarative manner of restricting the autonomy of the planning process, according to Requirement 6.

The definition of such sets is based on the <I-N-C-A> constraint definition. A RELAX NG Schema for complete <I-N-C-A> plans, including constraints, can be seen here.


Temporal and Resource Models (C1 and C2)

A temporal model, based on the explicit timeline approach, indicates that each activity should have an associated constraint I, expressing its interval, with initial (Ii) and final (If) moments. In addition the model also must provide constraints on temporal relations between activities. These ideas are expressed by the constraint definition in follow:

    KNOWN-CONSTRAINT ::=
      <constraint type="temporal" relation="TEMP-TYPE" sender-id="NAME">
        <parameters><list>TEMPORAL-PA</list></parameters>
        <annotations><map>MAP-ENTRY</map></annotations>
      </constraint>

    TEMP-TYPE ::= interval | TEMPORAL-RELATION

    TEMPORAL-RELATION ::= before | equal | meets | during | meets | during | overlaps | finishes

    TEMPORAL-PA ::= TEMPORAL-INTERVAL-PA | TEMPORAL-RELATION-PA

    TEMPORAL-INTERVAL-PA ::=

      <temporal-interval-pa>
        <pattern><list>
          <name>NODE-ID</name>
        </list></pattern>
        <value>TEMPORAL-PA</value>
      </temporal-interval-pa>

    TEMPORAL-RELATION-PA ::=

      <temporal-relation-pa>
        <pattern><list>
          <name>NODE-ID</name>
          <name>NODE-ID</name>
        </list></pattern>
      </temporal-relation-pa>

The definition of a resource constraint type aims to provide information that enables reasoning on resources and their capabilities. In this way, while activity pattern can provide a simple high-level description of the capability required by the plan, constraints can provide a more granular way to characterise or restrict the use of such capability.

    KNOWN-CONSTRAINT ::=
      <constraint type="resource" relation="RESOURCE-TYPE" sender-id="NAME">
        <parameters><list>PATTERN-ASSIGNMENT</list></parameters>
        <annotations><map>MAP-ENTRY</map></annotations>
      </constraint>

    RESOURCE-TYPE ::= reusable | consumable

Considering a hierarchical coalition, superior agents can keep only the high-level description of their subordinate agents, mainly because such descriptions are stable. However, if they need more information, a query can be performed so that subordinates return their current resource attributes and respective values.


Commitment Function (C3 and F1)

The commitment function allows the extension of an activity-oriented planning so that it also considers the idea of activity commitments and execution reports. The principal idea is to provide a general rather than a specfic task-based solution, also keeping the planning process independent of such extensions.

According to the function, the activity of a superior agent is only valid if its subordinate agents commit on the performance of such activity's subnodes. Thus, a commitment setting is, in fact, a conditional constraint to the activity, and can be speficied as in follow:

    KNOWN-CONSTRAINT ::=
      <constraint type="commitment" relation="COMMIT-TYPE" sender-id="NAME">
        <parameters><list>COMMITMENT-PA</list></parameters>
        <annotations><map>MAP-ENTRY</map></annotations>
      </constraint>

    COMMIT-TYPE ::= nil

    COMMITMENT-PA ::=

      <commitment-pa>
        <pattern><list>
          <name>NODE-ID</name>
          <name>AGENT-ID</name>
        </list></pattern>
        <value>
          <boolean>true/false</boolean>
        </value>
      </commitment-pa>

The principal advantage of this approach is that commitments are naturally considered during the constraint processing. In other words, the failure in a commitment is interpreted as a problem in satisfying a constraint, which will trigger a common process of recovery (e.g., replanning).


Mutual Support Function (C6 and F2)

The principal idea behind mutual support is to enable that one agent has knowledge about the needs of other agents. In our approach, in particular, this implies that each agent agi must share its conditional constraints C (Ccorresponds to C6 in our model) with the agents of its sub-coalition. The function in follow is applied by agents that receive C from agi:

We argues that such a function brings three advantages to the process of planning and collaboration: (1) a better information sharing because the sending of information is guided by the constraint-based knowledge that each agent has of the activities of its partners; (2) mutual activity support because agents have the capability of creating new activities to support their patners; and (3) conflict detection because agents know which conditions they should respect during their our planning process.


Human-Agent Interaction Mechanisms (C4, C5, C7, C8 and F3)

An alternative to decrease the impact of human delays in this process is to define contexts where agents choose by themselves the option to be performed. Such an approach is very suitable because contexts can be redefined by users so that they are still in control of the situation. We define contexts associated with activities so that if such a context is true, a degree of autonomy is applied avoiding or allowing agents to take autonomous decisions. The specification of constraints C8 that implement this idea is showed below:

    KNOWN-CONSTRAINT ::=
      <constraint type="autonomy" relation="DEGREE" sender-id="NAME">
        <parameters><list>PATTERN-ASSIGNMENT</list></parameters>
        <annotations><map>MAP-ENTRY</map></annotations>
      </constraint>

    DEGREE ::= permission | in-control

On the other hand, we are also characterising a group of constraints (C5) that restrict the decision processes of humans. This group is represented by constraints whose source is an external component such as the superior agent, or other team member. Based on this idea, the whole set of constraints can be divided into two classes:

  • Internal constraints, which users can manipulate (read/write) and that are generally created by themselves during the process of customisation of solutions;

  • External constraints, which users cannot change (read-only) because they are assigned by other components. This class represents (C5).
The definition of preference type constraints (C4) is important to relax the restricitions of external constraints and also as an alternative to stand preferencial, but not obrigatory, ways to perform activities.

    KNOWN-CONSTRAINT ::=
      <constraint type="preference" relation="PREF-TYPE" sender-id="NAME">
        <parameters><list>PREFERENCE-PA</list></parameters>
        <annotations><map>MAP-ENTRY</map></annotations>
      </constraint>

    PREF-TYPE ::= world-state | temporal | resource | instantiation

    PREFERENCE-PA ::= PATTERN-ASSIGNMENT | INSTANTIATION-PA

    INSTANTIATION-PA ::=
      <instantiation-pa>
        <pattern><list>PATTERN</list></pattern>
        <value>OBJECT</value>
      </instantiation-pa>

The last aspect is associated with the of explanations. The idea here is to define a function (F3) that produces explanations based on specific events triggered during the constraint processing. In this case the set of constraints (C7) represents all constraints that are being monitored by F3.

We are using <I-N-C-A> annotations to keep the explanations for activities. As annotations can be set for every component, the explanation function could be extended to automatically create several explicative forms of annotations to other components.


AIAI Artificial Intelligence Applications Institute
Centre for Intelligent Systems and their Applications
School of Informatics, The University of Edinburgh
Page maintained by c.siebra@ed.ac.uk, Last updated: Fri Sep 9 15:59:50 2005