Normative design using inductive learning

Domenico Corapi, Alessandra Russo, Marina De Vos, Julian A. Padget, Ken Satoh

TL;DR

This paper introduces a semi-automatic, iterative methodology for designing the "laws" (normative frameworks) that govern open digital systems. By combining Inductive Logic Programming (ILP) with Answer Set Programming (ASP), the authors created a system that takes desired behaviors—expressed as use cases—and automatically suggests new rules or revisions to existing ones to ensure the system behaves as intended.

What Problem Does This Paper Address?

In multi-agent systems and "virtual institutions," designers must create complex sets of rules (norms) to regulate behavior, such as permissions, obligations, and penalties. Much like writing legal code or software, this process is highly error-prone. It is easy for a designer to miss a crucial edge case, create a rule that contradicts another, or fail to account for how a rule should change when a specific condition (like a "VIP" status) is met.

The authors identify a gap: while software engineering has robust tools for testing and debugging, normative design lacks an automated mechanism to validate that a set of rules actually yields the desired social outcomes. They aim to bridge the gap between high-level requirements and the low-level logic implementation.

Methods

The authors propose a "Theory Revision" approach powered by two main logical pillars:

  1. Answer Set Programming (ASP): The normative framework is modeled as a logic program under ASP. ASP is particularly well-suited for this because it is non-monotonic—meaning that adding new information (like an exception to a rule) can retract previous conclusions, which is exactly how legal and social norms function.
  2. Inductive Logic Programming (ILP) via ASPAL: The core "learning" engine is a tool called ASPAL (ASP Abductive Learning). Instead of learning a system from scratch, the designer provides an initial "revisable theory." When the system fails to meet a use case, ASPAL treats the learning task as an abductive reasoning problem. It searches for the "minimal revision"—the smallest number of additions, deletions, or modifications to the rules—required to satisfy the use cases.

The workflow is iterative: the designer provides a trace of events and a desired outcome (a use case). If the current rules don't produce that outcome, the learning tool suggests revisions. The designer reviews these, selects the best fit, and repeats the process.

Datasets

The paper does not use a standard large-scale dataset, as the focus is on a methodology for custom design. Instead, they evaluate their approach using a Reciprocal File Sharing case study.

  • The Scenario: Agents must share a file block before they are allowed to download a new one.
  • The Use Case: A sequence of seven events (downloads and shares) involving different agents, including a "VIP" agent who should be exempt from certain restrictions.
  • The Goal: To see if the system can automatically fix a buggy initial rule set to correctly identify "violations" and "misuse" based on these traces.

Key Insights and Ideas

  • Use Cases as Constraints: Rather than just being examples, use cases act as hard constraints. If the logic solver cannot find an "answer set" that satisfies the use case, it proves the current theory is broken.
  • Minimal Revision Distance: The system is biased toward making the fewest changes possible. This prevents the AI from "over-fixing" the problem by deleting the entire rule set and starting over; it tries to preserve the designer's original intent.
  • Debugging the "Law": The system can catch subtle errors that humans often miss, such as typographical errors in variable names (e.g., using the wrong variable in a download rule) or failing to account for how a "misuse" event should terminate an agent's power to act.

Key Results

The case study demonstrated that the system could successfully:

  • Correct a Typo: It identified a variable name error in a rule governing downloads.
  • Handle Exceptions: It automatically added a not isVIP(X) condition to a rule to ensure privileged users weren't penalized.
  • Synthesize New Concepts: It suggested a brand-new rule for a "misuse" event that the designer had mentioned in the use case but hadn't yet defined in the logic.
  • Performance: The revision for the case study was generated in 23 seconds on a standard 2011-era iMac, suggesting the approach is computationally feasible for practical design tasks.

Limitations and Future Work

  • Scalability: The authors acknowledge that as the number of rules, time steps, and possible events increases, the search space for revisions grows significantly.
  • Heuristics for Selection: Currently, the system might suggest multiple valid revisions. The authors suggest that future work should include "crucial literals" or "levels of confidence" to help the system automatically pick the "most likely" or "best" revision among several candidates.
  • Human-in-the-Loop: The process is semi-automatic. It still relies heavily on the designer's ability to provide comprehensive and accurate use cases. If the use cases are incomplete, the suggested rules might be technically correct but logically undesirable.

Summary updated

Abstract

In this paper we propose a use-case-driven iterative design methodology for normative frameworks, also called virtual institutions, which are used to govern open systems. Our computational model represents the normative framework as a logic program under answer set semantics (ASP). By means of an inductive logic programming approach, implemented using ASP, it is possible to synthesise new rules and revise the existing ones. The learning mechanism is guided by the designer who describes the desired properties of the framework through use cases, comprising (i) event traces that capture possible scenarios, and (ii) a state that describes the desired outcome. The learning process then proposes additional rules, or changes to current rules, to satisfy the constraints expressed in the use cases. Thus, the contribution of this paper is a process for the elaboration and revision of a normative framework by means of a semi-automatic and iterative process driven from specifications of (un)desirable behaviour. The process integrates a novel and general methodology for theory revision based on ASP.
BibTeX
@article{corapi2011normative,
  author = {Domenico Corapi and Alessandra Russo and Marina De Vos and Julian A. Padget and Ken Satoh},
  title = {{Normative design using inductive learning}},
  journal = {Theory Pract. Log. Program},
  year = {2011},
  doi = {10.1017/s1471068411000305},
}
Figure