Abstract
Autonomous agents operating in open, dynamic environments frequently encounter situations where their pre-existing commitments conflict. Traditional approaches often fail by treating commitments as rigid or assuming conflicts can be designed away. This paper presents Coco, a formal framework for runtime reasoning that utilizes situation-dependent dominance rules to resolve conflicts. By leveraging Answer-Set Programming (ASP), Coco identifies a maximal set of nondominated commitments, providing a realistic model of compliance where agents prioritize the most critical obligations.
Introduction
In multi-agent systems, autonomous parties (principals) interact by entering into commitments—agreements to bring about specific states of affairs. However, the complexity of real-world environments often leads to the "damned if you do, damned if you don't" dilemma. For instance, a service robot might be committed to both a delivery deadline and assisting a person in distress. If these duties clash, the robot needs a principled way to decide which takes precedence.
Coco addresses this gap by focusing on runtime reasoning. Instead of attempting to foresee every possible conflict during the design phase, Coco allows agents to dynamically evaluate which commitment is "dominant" based on the current context.
Formalizing Commitments
The foundation of Coco lies in its formal representation of commitments. A commitment schema is defined as a template $(dbt, crd, \phi, \psi, t_d)$, where a debtor ($dbt$) owes a creditor ($crd$) a consequent ($\psi$) if an antecedent ($\phi$) occurs, typically within a deadline ($t_d$).
To manage these at runtime, Coco employs a set of schema and instance predicates that track the lifecycle of a commitment—from being detached (activated) to being satisfied or violated.
Resolving Conflicts with Dominance
The core innovation of Coco is the introduction of dominance relations. These are explicit, situation-dependent rules that define when one commitment instance supersedes another. These relations form a strict partial order, allowing the system to prune conflicting obligations.
Consider a scenario where a guardian (Bob) is committed to working during specific hours but also to caring for a sick child (Alice). When Alice falls ill, the commitment to her healthcare "dominates" the commitment to work.
As shown in Figure 1, the framework tracks these states over time. At time 10, the "sick" event detaches a guardian commitment ($gCom$). At time 11, a work commitment ($wCom$) is also detached. Coco identifies the conflict and applies the dominance rule, ensuring that the agent is considered compliant if it satisfies the nondominated commitment ($gCom$), even if the dominated one ($wCom$) is eventually violated.
Computational Framework and ASP
Coco translates the current world state, active commitments, and dominance rules into an Answer-Set Programming (ASP) program. The system then computes "stable models" to identify the maximal set of nondominated commitments. This approach ensures that the agent always pursues the most important, consistent set of goals.
The authors demonstrate that finding this set is computationally tractable, with complexity equivalent to finding stable models in ASP. Furthermore, verification of liveness (reaching desirable states) and safety (avoiding prohibited states) within Coco is shown to be PSPACE-complete, aligning with standard model-checking benchmarks.
Key Insights
- Contextual Compliance: Coco redefines compliance. An agent is not a "violator" simply because it missed a deadline; it is compliant if it prioritized the most important duties in a given context.
- Efficiency through Runtime Resolution: By deferring conflict resolution to runtime, the system avoids the combinatorial explosion of trying to map every possible conflict at design-time.
- Partial Ordering: A total ranking of all possible commitments is unnecessary. A partial order is sufficient to make consistent decisions in complex environments.
Conclusion and Future Work
Coco provides a robust theoretical and practical framework for autonomous agents to navigate social and legal obligations. Future research aims to handle potential cycles in dominance relations and to incorporate higher-level legal principles, such as Lex Superior (authority-based precedence) and Lex Posterior (recency-based precedence), to automatically generate dominance rules from organizational contexts.
Summary updated