Abstract
Designing the complex rules, or norms, that govern multi-agent systems is a manual and error-prone process. This paper introduces a semi-automatic framework that utilizes Inductive Logic Programming (ILP) to debug and refine these rules by learning from example behavior traces. By treating norm design as an iterative, data-driven process, the framework helps designers move from incomplete specifications to robust normative systems, bridging the gap between intended behavior and formal logic.
Introduction
In both human society and autonomous software systems, "norms"—rules regarding permissions, obligations, and violations—are essential for coordination. However, as systems grow in complexity, it becomes nearly impossible for a human designer to foresee every edge case. A rule that seems logical in isolation might lead to unintended deadlocks or allow "cheating" behavior in practice. Currently, designers must manually identify where their rules fail and figure out how to patch them. This paper addresses the need for automated design support, framing norm design as an iterative process where the system suggests revisions based on "disfunctional traces"—behaviors that deviate from the designer's intent.
Methodology
The proposed framework combines two powerful logic-based paradigms to facilitate norm refinement:
- Answer Set Programming (ASP): The authors use AnsProlog to model the normative framework. This allows for the representation of the world state through "fluents" (dynamic facts) and "events" (actions that trigger state changes).
- Inductive Logic Programming (ILP): Specifically, the system employs TAL. Unlike statistical machine learning, ILP learns actual logical rules.
As illustrated in Figure 1, the workflow is a closed loop. The designer provides "use cases"—sequences of events paired with expected outcomes. If the current rules fail to produce the expected outcome, the TAL system performs an abductive search to find a set of new rules (a hypothesis) that satisfies the use cases when added to the background knowledge. This approach is non-monotonic, allowing it to handle "negation as failure," which is crucial for modeling permissions that exist only in the absence of specific violations.
Evaluation and Results
The framework was evaluated using a custom Reciprocal File Sharing scenario involving two agents, Alice and Bob. The rules were designed to ensure reciprocity: downloading a block revokes permission for further downloads until a block is shared in return. The authors deliberately removed specific rules and tasked the TAL system with re-learning them from event traces.
Key results include:
- Rule Induction: The system successfully learned "Initiate" and "Terminate" rules, correctly identifying conditions for granting or revoking permissions.
- Complexity Handling: The framework could induce valid hypotheses even when multiple rules were missing simultaneously and successfully learned "counts-as" rules (e.g., Action A counts as a violation under Condition B).
- Efficiency: Despite the complexity of logical induction, the TAL system computed suggested revisions in 30 to 500 milliseconds.
Discussion and Conclusion
A core insight of this work is framing normative design as a software engineering problem where use cases serve as unit tests for social rules. By mapping ASP to ILP, the authors bridge the gap between observed traces and formal rules. While the system provides a powerful "human-in-the-loop" assistant, limitations remain regarding the user interface—which currently requires raw logic syntax—and the need for better heuristics to filter out semantically nonsensical (though logically valid) rules.
Future work will focus on scaling the search space for larger scenarios and moving toward "on-line" norm evolution, where systems might adapt their own rules in real-time as they observe new agent behaviors.
Summary updated