Coalitions | Problem Definition | Hierarchical Organisations | Back


Coalition, from Latin coalescere (co-, together + alescere, to grow) is a type of organisation where joint members work together to solve mutual goals. The principal feature of a coalition is the existence of a global goal, which motivates the activities of all coalition members. However, normally such members are not directly involved in the resolution of this goal, but in sub-tasks associated with it. Typical features of a task scenario that requires the deployment of a coalition are:
  • The nature of the problem demands a set of different abilities;

  • Participants need to collaborate because they have limits in abilities and knowledge;

  • The task requires a structure of command and control that coordinates the activities of participants. Coordination is also essential to avoid conflict and improve the use of time and resources;

  • There is the problem of integrating heterogeneous systems belonging to multiple organisations with distinct doctrines and operational rules.

Examples of Coalition Scenarios

Urban disaster relief domains require the union of agents that support activities related to search and rescue. This coalition instance (left-hand side) is based on the RoboCup Rescue Simulator . Agents are represented by fire brigades, ambulances, police forces, fire stations, ambulance centres, police offices and a search and rescue command centre. The scenario could represents a real part of Kobe City (Japan).
The next figure (right-hand side) illustrates an example of a military domain where multinational forces integrate abilities during operations of peacekeepers, such as in the Iraq scenario. Agents are represented by the head country's Department of Defence, local operational agents and several military units. Multinational coalitions are a typical example of coalitions that require the development of shared representations reflecting different cultures, doctrines and languages. Groups such as the Multinational Planning Augmentation Team (MPAT) work in this direction, trying to develop and become familiar with Standard Operating Procedures (SOP), which represent well-founded and tried plans to be applied in specific situations.
The last figure illustrates a futuristic scenario where robots and astronauts collaboratively work in interplanetary missions, such as a Mars Mission. Agents are represented by the Earth Mission Control Centre, Mars Habitats and units of astronauts and robots. A real example in this context is the Aurora Exploration Programme , a long-term effort of the European Space Agency (ESA) that aims to send a team like that to Moon in 2024 and to Mars in 2033.

Problem Definition

This thesis, in particular, is concerned with the role of intelligent planning in coalition support systems. Planning can bring several advantages to coalition operations such as prediction of failures, resource allocation, conict identication and so on. The planning process in coalitions is naturally distributed because each coalition member is a decision-maker.

We are delivering planning mechanisms to users via assistant agents. In this approach each participant has an agent that supports his/her tasks, providing for example, planning information and options to carry out activities. This approach is powerful because while users have the ability to take decisions based on their past-experience (case-base reasoning), agents are able to generate and compare a significant number of options, showing both positive and negative points of such options. Agents that support coalition members at different levels of decision-making must be customised so that they are able to support the planning activities carried out at each level. From a practical perspective, this customisation means that agents must provide activity handlers (e.g. pathfinder, load balancing, etc.) to support a specific set of activities (see figure below). Such handlers work on a planning representation, which expresses, for example, notions of environment, time, resources, priority, activity, state, etc.

However, when agents are performing as part of a coalition, the complexity of the planning process increases due to the number of requirements that must be considered. Requirements associated with collaboration, distributed planning, coordination and user interaction are interrelated and the design of such one can inuence others. Thus the implementation of individual solutions for each set of requirements is not a good practise. Part II of this thesis analyses in details such requirements and their role inside the planning representation.

The principal claim of this work is that we can integrate distinct groups of requirements (multiagent planning, collaboration and human interaction), associated with the development of hierarchical coalition support agents, via a unied framework provided by a constraint-based ontology and related functions. We argue and demonstrate that such framework brings several advantages for the agents' development, such as: well-known environment to represent and build plans; transparent way to incorporate collaborative concepts, which complement the planning abilities; opportunities for the development of more advanced human-agent mechanisms, and; support to an easy customisation of activities handlers. In brief, we have the following goals:

  • Formalisation of hierarchical coalitions (members, relations and rules among them) so that we can use the structural features of this kind of organisation for the development of command and control mechanisms (coordination);

  • Investigation and categorisation of requirements that have inuences on the development of models and processes used by agents operating in hierarchical structures;

  • Specification of a unified representation of planning and collaboration that enables an easy customisation of activity handlers and an appropriate basis for the incorporation of requirements associated with human-agent interaction;

  • Development of practical applications that demonstrate the real advantages of this approach and also stress its generality.

Hierarchical Organisations

The use of hierarchies facilitates the deployment of coordination mechanisms because such mechanisms can exploit the hierarchical organisational structure. This is because such an organisation implicitly denes the agents responsibilities, capabilities, connectivity and control flow. In addition hierarchies also have the following advantages:
  • They are compatible with the divide-and-conquer idea. The process of splitting a problem into smaller subproblems is repeated at each level;

  • Hierarchical levels may deal with different granularities of knowledge so that each level does not need to have all the details about the problem;

  • It is possible to enclose problems to be dealt with by local subteams, instead of spreading it over the coalition.
Hierarchical organisation can be classified into three levels of decision-making: strategic, operational and tactical. This hierarchical arrangement is a common practise in military models of command and control and consistent with knowledge engineering work. Furthermore, this classification also highlights the need of customising planning processes at each of these levels.
  • The strategic level accounts for developing plans in a high-level of abstraction, or "what-to-do" plans. In other words, the level specifies what must be done, but it does not give details about how something must be done. In this way, the principal tasks are related to analysis, directions and comparison of courses of actions.

  • The operational level accounts for refining the plans produced at the strategic level, mainly providing the logistical resources for them via processes of resource scheduling and load balancing. Thus, knowledge about the operation environment is more detailed and limited coalition groups will be affected by the decisions.

  • The tactical level is where the execution of operations actually takes place. For this reason the degree of knowledge of tactical components is very specialised on the domain that they are operating, and their decisions are generally taken on sets of atomic activities. As the components are performing inside a dynamic and unpredicted environment, their reactive capabilities and speed of response are very important so that the use of pre-dened procedures could be useful alternative. The result of this level are atomic activities or set of atomic activities that are commonly executed by the own components.
A formal specification and definition for the hierarchical coalitions that we are work with can be seen here.
AIAI Artificial Intelligence Applications Institute
Centre for Intelligent Systems and their Applications
School of Informatics, The University of Edinburgh
Page maintained by, Last updated: Tue Oct 18 23:59:50 2005