Planning Threads

HTN Planning + Constraint Posting | Teamwork Theories | Human-Agent Interaction | Back

HTN Planning and Constraint Posting

Hierarchical Task Network (HTN) planning is an abstraction-based plan representation that allows an agent to successively refine planning decisions. As the name itself suggests, HTN planning is the natural choice for planning performance in hierarchical organisations because such approach distinguishes actions and goals of different degrees of abstraction and importance for each level.

We are joining the HTN ideas with an underlying constraint-based representation of plans. In this way, the planning framework can employ powerful problem solvers based on search and constraint reasoning methods, and still retain human intelligibility of the overall process and plans that are created. Constraints have several interesting properties, some of them complementary to the abilities of HTN planning:
  • They efficiently describe problems that incorporate resources and time. For example, the problem of preventing overlaps of a number of tasks with specific durations that share a resource. Note that in classical HTN, issues associated with the resources and priorities are ignored, and time is represented implicitly by means of instant transitions in a transition graph;

  • While global constraints allow an easy representation of inherent disjunction in the non-overlap problem (e.g., activity A may precede activity B or activity B may precede activity A), HTN provides a natural way to stipulate global constraints on plans;

  • Constraints are declarative so that they specify what relationship must hold without specifying a computational procedure to enforce that relationship. Thus users only state the problem while the computer solves it. Taking advantages of this property, users can declare set of constraints for each HTN task that control its decomposition (if it is non-primitive) or execution (if it is primitive);

  • In addition, constraints may specify partial information (they need not uniquely specify the values of its variables), they are additive (the order of imposition does not matter), and they are heterogeneous (relations can be defined between variables with different domains).

The constraint posting approach based on additions and retractions of constraints during the planning process, where constraint satisfaction is used as an add-on function to check the satisfaction of restrictions such as availability of resources or temporal intervals. One particularly relevant feature of constraint posting is its abilities to plan hierarchically by introducing new constraints and variables. In fact, using this approach, the CSP graph can be built stepwise so that only specific subproblems are covered within the constraint solving process at each level. Thus, upper level agents only need to deal with constraints that are necessary to dene a plan according to the degree of abstraction required by their levels. The work of refining a plan, with additional constraints, is left to lower level agents.

Requirements for Planning in Coalitions

We have introduced constraint posting as an approach for planning performance. However, there are different ways that we can use constraints to describe a plan model, depending on the requirements of a particular set of problems that we want to handle. This work, in particular, discusses the likely requirements for planning, considering its application in coalition scenarios. The focus is on two principal models (temporal and resource models) that, together, account for supporting several processes associated with planning such as conflict resolution, task allocation and loading balancing.

Requirement 1: the temporal planning model must be based on an explicit timeline approach, which must enable the representation of both quantitative and qualitative temporal references as well as relations between them.

Requirement 2: the resource planning model must support the tasks of localising services/agents that provide specified capabilities, and also provide information that enables reasoning on such capabilities.

Teamwork Theories

 The complexity of problems associated with coalitions, such as disaster relief operations or military missions, requires that the planning and execution activities of coalition members be performed in a collaborative way. Pure planning approaches support the operations of distributing tasks and synchronising their performances. Thus, there is a coordination of activities so that conflicts and redundant tasks can be avoided. However, these operations still do not ensure collaborative behaviour.

The Teamwork research encloses a set of ideas that support the implementation of a collaborative framework. In fact, teamwork has become the most widely accepted metaphor for describing the nature of multiagent collaboration. Investigating the principal proposals for teamwork (Joint Intention, SharedPlans, Joint Responsabilities and Planned Team Activites), we can list the following requirements to be considered:

Requirement 3: the collaborative model must consider the establishment of commitments to joint activities, enabling consensus on plans or their constituent parts.

Requirement 4: the collaborative model must provide ways to the dissemination of information associated with progress, completion and failure of activities.

Requirement 5: the collaborative model must underline the idea of mutual support, providing ways to the specification of useful information sharing mechanisms and creation of supportive activities.

Note that, as discussed in previous works, collaboration between different problem-solving components, such as planning agents, must be designed into systems from the start. It cannot be patched on. In this way, coalition planning processes need to be designed on a collaborative framework that ensures commitments of individual components in carrying out their activities, considering the global coalition objective.

Human-Agent Interaction

 The use of teamwork ideas supports the performance of collaborative planning activities by agents of a coalition, however they do not consider situations where agents interact with human users. Two principal problems could be raised in such situations:
  • Agent inaction while waiting for a human response can lead to potential miscoordination with other coalition members;
  • Local decisions taken by a coalition member can seem appropriate for her/him, but may be unacceptable to the team.
Such problems respectively enforce the consideration of the requirements in follow:

Requirement 6: the human-agent model must enable the definition of adjustable methods that complement the decision making process of human users.

Requirement 7: the human-agent model must provide ways to restrict user options in accordance with the global coalition decisions.

These requirements can be seen as a problem of finding a suitable level of autonomy to the agents. Depending on this level of autonomy, agents can only carry out user commands or, at the other extreme, replace human reasoning, making all necessary decisions. If the agents' autonomy is adjusted to a correct degree, this will allow them to exploit human abilities to improve their performance, but without becoming overly dependent or intrusive in their human interaction. Research in adjustable autonomy considers this idea, encompassing the strategies by which an agent selects the appropriate entity such as itself, a human user, or another agent, to make a decision at key moments when an action is required. These strategies can vary the level of autonomy of agents so that they require a different level of guidance depending on the current situation.

There are two different directions to formulate adjustable autonomy: agent-based and user-based approaches. In the agent-based approach to adjustable autonomy, each agent explicitly reasons by itself about whether and when to transfer decision-making control to another entity. In the agent-based approach each agent explicitly reasons by itself about whether and when to transfer decision-making control to another entity. Differently, the user-based approach to adjustable autonomy explores a human-centred perspective, so that the central issue for this approach is the design of mechanisms by which an user can dynamically modify the scope of autonomy for an agent.

Analysing projects such as TRAINS/TRIPS and O-Plan, we can note that they use the concept of Mixed-Initiative to implement mechanisms to transfer control between agents and humans. Such mechanisms are a key aspect of the adjustable autonomy process so that mixed-initiative interaction can be used to adjust the degree of agents' autonomy. The implementation of adjustable autonomy on the mixed-initiative perspective is a suitable alternative because research in mixed-initiative has also been investigating two fundamental requirements of human-computer interaction, which can be expressed as:

Requirement 8: the human-agent model must support the definition of mechanisms that intensify the human user control and enable the customisation of solutions.

Requirement 9: the human-agent model must support the generation of explanations about autonomous decisions, clarifying the reasons why they were taken.

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