Abstract
Designing normative frameworks for multi-agent systems is a complex, error-prone task. This paper introduces a semi-automatic, iterative methodology that leverages Inductive Logic Programming (ILP) and Answer Set Programming (ASP) to assist designers. By treating desired behaviors (use cases) as constraints, the system identifies discrepancies in the rule set and suggests minimal revisions. A case study in reciprocal file sharing demonstrates the approach's effectiveness in debugging logic, handling exceptions, and synthesizing new rules.
Introduction
In "virtual institutions" and multi-agent systems, designers must establish robust sets of norms—permissions, obligations, and penalties—to regulate agent behavior. However, as with legal code or software, creating these frameworks is prone to errors, such as missing edge cases or conflicting rules. While software engineering benefits from automated testing, normative design has historically lacked tools to bridge the gap between high-level requirements and low-level logical implementations. This paper addresses this gap by proposing an automated mechanism to validate and revise normative rules based on intended social outcomes.
Methodology
The proposed methodology centers on a "Theory Revision" approach, utilizing two primary logical components: Answer Set Programming (ASP) and Inductive Logic Programming (ILP).
The normative framework is formalized as a logic program under ASP, which is ideal for modeling social norms due to its non-monotonic nature—allowing new information to retract previous conclusions. The core learning engine, ASPAL (ASP Abductive Learning), treats the revision task as an abductive reasoning problem. When a normative theory fails to satisfy a provided use case, ASPAL searches for the "minimal revision"—the smallest set of additions or deletions—required to align the theory with the desired behavior.
As shown in the formalization above, the framework defines fluents, events, and initiation/termination rules. The iterative workflow involves the designer providing event traces and desired outcomes. If the current ruleset is insufficient, the system suggests revisions, which the designer then reviews and integrates.
Case Study: Reciprocal File Sharing
The methodology was evaluated using a reciprocal file-sharing scenario. In this system, agents are required to share file blocks to earn the right to download new ones. The test case involved a sequence of seven events, including a "VIP" agent who should be exempt from standard restrictions. The objective was to determine if the learning tool could automatically correct a flawed initial ruleset to accurately identify violations and misuse based on these traces.
Results
The evaluation demonstrated that the system could effectively:
- Correct Typos: It identified a variable name error in a rule governing downloads.
- Handle Exceptions: It automatically introduced conditions (e.g.,
not isVIP(X)) to accommodate privileged users. - Synthesize Rules: It suggested new rules for "misuse" events that were present in use cases but undefined in the logic.
- Performance: Revisions were generated in approximately 23 seconds on standard hardware, indicating practical feasibility.
Conclusion
This research provides a powerful tool for normative designers, shifting the focus from manual debugging to high-level requirement specification. By prioritizing minimal revisions, the system preserves the designer's original intent while ensuring logical consistency. Future work will focus on improving scalability for larger rule sets and developing heuristics to help designers choose between multiple valid revision suggestions.
Summary updated