Agents that Work in Harmony by Knowing and Fulfilling their Obligations

AAAI 1998

TL;DR

This paper introduces a novel framework for multi-agent systems that allows agents to understand and manage complex social obligations and interdictions. By representing these "social laws" as deontic constraints and using a constraint propagation mechanism, agents can reason about conflicts, negotiate, and coordinate their actions effectively, leading to more robust and harmonious multi-agent interactions.

What Problem Does This Paper Address?

Building intelligent agents that can collaborate effectively in complex environments is a significant challenge. Real-world social interactions are governed by a web of rules, obligations, and prohibitions that are often contradictory and require agents to make difficult choices. Existing models, like the Cohen-Levesque account of teamwork, often oversimplify this by assuming a single, implicit obligation towards a common goal. This paper tackles the problem of how agents can manage multiple, potentially conflicting, social obligations and interdictions to achieve coordinated behavior, especially when there's no perfect solution and some constraints must be violated. The authors aim to create agents that can not only understand these social laws but also reason about them to decide which actions to take, and crucially, which obligations to break when necessary, all while respecting the authority and priorities of others.

Methods

The core of the paper's contribution lies in its novel approach to representing and reasoning about obligations, permissions, and interdictions (OPIs).

  • Deontic Logic Foundation: The OPIs are semantically founded on dynamic deontic logic, specifically using Meyer's reduction of deontic logic to dynamic logic. This provides a formal basis for reasoning about actions and their consequences in terms of obligations and interdictions.
  • Constraint Propagation: A key innovation is the use of a constraint propagation mechanism. This algorithm, based on theorems derived from the deontic logic foundation, allows agents to infer applicable obligations and interdictions by traversing networks of goals and subgoals.
  • Violation Costs: To handle conflicting situations, the model incorporates violation costs. When an agent cannot fulfill all obligations, it can rationally choose to violate less important ones (those with lower associated costs) to satisfy more critical ones. This allows for quantitative or qualitative comparisons of costs.
  • Action Scheduling: Beyond deontic reasoning, the paper addresses action scheduling. Agents need to plan and sequence actions, considering time windows, resource usage, and action durations. A constraint-based scheduler is used to produce a complete ordering of actions consistent with all constraints.
  • Coordination Language: These mechanisms are integrated into a practical agent development language. This language allows for defining organizations, roles, agents, and their associated OPIs, conversations, and coordinated behaviors.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and its implementation, illustrating its use with a telecommunications feature interaction problem.

Key Insights and Ideas

  • Social Laws as Constraints: The paper frames social interaction not just as shared goals but as a system of explicit social laws (obligations and interdictions) that constrain agent behavior. This provides a more nuanced and realistic model of multi-agent systems.
  • Rational Violation of Obligations: The introduction of violation costs is crucial. It moves beyond a binary "fulfill or fail" paradigm to allow agents to make rational decisions about which obligations to break when faced with unavoidable conflicts, based on predefined costs or priorities.
  • Negotiation through Deontic Exchange: A significant consequence of the approach is its support for negotiation. Agents can exchange deontic constraints (obligations and interdictions) to reach agreements, allowing them to resolve conflicts by adjusting these constraints.
  • Integration of Reasoning and Action: The paper successfully integrates deontic reasoning (what should be done) with action planning and scheduling (how and when to do it), creating a more complete agent architecture.

Key Results

The paper demonstrates the feasibility of its approach through a detailed explanation of the framework and its integration into a coordination language. While specific quantitative results are not the primary focus, the paper illustrates the system's capability through:

  • Successful Deontic Propagation: The paper shows how the constraint propagation mechanism can infer obligations and interdictions from initial assertions, even in complex networks with choices and parallel compositions.
  • Conflict Resolution with Costs: Examples demonstrate how violation costs enable agents to resolve conflicts by selecting the least costly obligation to violate or by identifying the only viable option when others are forbidden.
  • Application to Feature Interaction: The framework is illustrated with a practical example of resolving feature interactions in telecommunications, showing how agents can negotiate and coordinate to avoid undesirable outcomes.

Limitations and Future Work

  • Handling of Authority and Priorities: While the paper mentions authority, the detailed mechanisms for how authority influences the resolution of conflicting obligations and interdictions could be further explored.
  • Extreme Cases of Violation: The paper notes that it does not deal with extreme cases where agents might try to modify social laws themselves.
  • Integration of Time and Planning: The authors suggest further work on the direct integration of time into the deontic propagation process, allowing for obligations and interdictions over specific time intervals, and integrating this with classical planning and scheduling for a more complete architecture.
  • Negotiation Strategies: The authors are exploring negotiation strategies based on deontic constraint exchange, particularly in limiting information disclosure during exchanges.
  • Global Supply Chain Management: The approach is being applied to global supply chain management, which involves managing complex horizontal and vertical interactions.

Summary updated

BibTeX
@inproceedings{1998agents,
  title = {{Agents that Work in Harmony by Knowing and Fulfilling their Obligations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}
Figure