A Framework for Problem Solving Activities in Multi-Agent Systems

AAAI 1999

TL;DR

This paper proposes a novel framework for multi-agent systems (MAS) that integrates organization design, coordinated planning, and plan execution. By enabling agents to reason about their own activities and select appropriate strategies at each phase, this framework enhances flexibility and responsiveness in dynamic environments.

What Problem Does This Paper Address?

Building effective multi-agent systems (MAS) is complex due to the interconnected nature of core research issues like problem decomposition, task distribution, communication, plan synthesis, coordination, conflict resolution, and organization design. Existing approaches often struggle to integrate solutions for these issues seamlessly. This paper addresses the need for a unified framework that guides MAS designers in selecting and integrating appropriate techniques, allowing agents to adapt to changing environments and operating conditions through meta-level reasoning about their activities.

Methods

The proposed framework decomposes problem-solving activities into three phases:

  1. Organization Design: Agents (or designers) determine how agents will interact, leading to static or dynamic organizational structures (e.g., master-slave, peer-to-peer, command-driven, independent).
  2. Coordinated Planning: This phase involves three tasks:
  3. Plan Generation: Agents select actions to achieve goals, potentially using any planning algorithm.
  4. Task Allocation: Agents assign responsibility for tasks to individual agents.
  5. Plan Integration: Agents coordinate subtask solutions to prevent conflicts, integrating partial plans, scheduling actions to avoid resource conflicts, and preventing "clobbering" of plans.
  6. Plan Execution: Agents monitor the execution of their actions to ensure intended effects and observe environmental states and other agents' behaviors to maintain cooperation and resource availability. If plans become unachievable, agents can restart planning at an earlier phase.

A key aspect is meta-level reasoning, allowing agents to reason about their actions, strategies, and strategic decision-making, thereby increasing flexibility and responsiveness. Coordination across all phases is achieved through communication.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Meta-level Reasoning for Adaptability: The core idea is that agents reasoning about their own activities (actions, strategies, and strategic decisions) allows them to adapt dynamically to changing environments and operating conditions, a crucial feature for robust MAS.
  • Integrated Framework: By structuring problem-solving into distinct but interconnected phases (organization design, coordinated planning, plan execution) with defined sub-tasks, the framework provides a clear roadmap for MAS development and integration.
  • Flexibility through Strategy Selection: Empowering agents to select appropriate strategies for each phase (e.g., planning, task allocation) enhances their ability to handle diverse situations and organizational structures.
  • Communication as the Glue: Explicitly stating that communication is the mechanism for coordination across all phases highlights its critical role in MAS functionality.

Key Results

The paper presents a conceptual framework and does not report quantitative results from experiments. However, it highlights the framework's utility in aiding the design of MAS like Sensible Agents (SA). SA, which utilize Dynamic Adaptive Autonomy (DAA) for organization design and can choose between hierarchical planning and operator search strategies, are cited as an example benefiting from this framework. The ongoing development and testing of SA capabilities in the Sensible Agent Testbed are mentioned as evidence of the framework's practical application.

Limitations and Future Work

The paper acknowledges that the framework is a conceptual aid and does not detail specific implementation challenges or empirical validation. Future work likely involves further development and testing of the proposed framework within MAS architectures like Sensible Agents, particularly in refining the integration of strategies for conflict resolution (negotiation, arbitration, self-modification) and enhancing the overall capabilities of agents within dynamic environments.

Summary updated

BibTeX
@inproceedings{1999framework,
  title = {{A Framework for Problem Solving Activities in Multi-Agent Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure