Data-Driven Revision of Conditional Norms in Multi-Agent Systems (Extended Abstract)

Davide Dell'Anna, Natasha Alechina, Fabiano Dalpiaz, Mehdi Dastani, Brian LoganIJCAI 2023 · OpenReview

TL;DR

This paper introduces DDNR, a novel data-driven approach to automatically revise conditional norms in multi-agent systems (MASs). By learning from observed agent behavior, DDNR creates more accurate norms that adapt to changing system objectives and dynamic environments, outperforming manually designed norms in a traffic simulation.

What Problem Does This Paper Address?

In multi-agent systems (MASs), norms are crucial for guiding agent behavior towards desired system-level objectives. However, designing effective norms is challenging due to the inherent dynamics of MASs, where agent behaviors can be unpredictable, agents can join or leave the system, and system objectives can evolve over time. Traditional norm design often relies on static assumptions about agent behavior and system goals, making existing norms quickly become ineffective or even counterproductive. This paper addresses the need for a mechanism to automatically adapt and revise these norms based on real-world system execution data, ensuring they remain aligned with evolving objectives.

Methods

The core contribution is the DDNR (Data-Driven Norm Revision) approach. DDNR operates in two main steps:

  1. Synthesis: Given a dataset of labeled traces (observed agent behaviors annotated with their alignment to system objectives), DDNR synthesizes potential revised norms. This synthesis process can result in three types of revisions:
  2. Weakening: Making the norm less restrictive (prohibiting fewer behaviors).
  3. Strengthening: Making the norm more restrictive (prohibiting more behaviors).
  4. Alteration: Modifying the norm's condition, target state, or deadline to prohibit a different set of behaviors. The synthesis is data-driven, meaning it doesn't require prior knowledge of the MAS's internal workings or the specific mapping between norms and objectives, only the labeled traces.

  5. Selection: From the set of synthesized revised norms, DDNR selects the one that best aligns with the system objectives. This selection is based on maximizing the accuracy of the norm on the provided dataset, measured by how well the norm's classification of traces (compliant vs. violating) matches the ground truth labels from the MAS objectives evaluator.

Datasets

The paper uses a dataset generated from a traffic simulation using the SUMO simulator. This dataset consists of finite traces representing vehicle journeys on a highway. Each trace is labeled as either "positive" (contributing to MAS objectives like low emissions and travel time) or "negative" (detrimental to objectives). The authors do not introduce a new benchmark dataset but rather use a realistic simulation to generate data for evaluating their approach.

Key Insights and Ideas

  • Norms as Adaptive Mechanisms: The paper highlights that norms in MASs shouldn't be static. They need to be dynamic and adaptable, much like social norms in human societies, to remain effective in complex and changing environments.
  • Data-Driven is Key: The core idea is that observed behavior is the most reliable source of information for revising norms, especially in open MASs where internal agent logic is unknown. This bypasses the need for explicit causal models between norms and objectives.
  • Beyond Simple Compliance: The evaluation metric (accuracy) goes beyond just checking if a norm is violated. It assesses how well the norm's classification of behavior aligns with the actual impact on system objectives, even if the norm's language differs from the objective's language (e.g., speed limits vs. CO2 emissions).
  • Types of Revision Matter: The study shows that different types of revisions (weakening, strengthening, alteration) have varying impacts on norm effectiveness, suggesting that the system can intelligently choose the best revision strategy.

Key Results

The DDNR approach demonstrated significant improvements in norm accuracy:

  • Weakening: Led to a negligible improvement in accuracy (dCohen = 0.087), suggesting original norms were already too weak.
  • Strengthening: Improved accuracy by approximately 20% (dCohen = 1.115).
  • Alteration: Achieved the highest improvement, around 24% (dCohen = 1.275).
  • Overall, revised norms showed an average accuracy improvement of about 30% on the training data and 13% on unseen traces.
  • The study found that half of the revised norms had an accuracy higher than 76%, and 25% exceeded 89%.

Limitations and Future Work

  • Boolean Evaluation: The current DDNR approach relies on a binary (positive/negative) labeling of traces. The authors suggest extending this to more fine-grained evaluations of traces with respect to objectives.
  • Single Objective: The current framework focuses on a single system objective. Future work aims to support multiple system objectives.
  • Runtime Integration: The authors plan to embed DDNR into a runtime supervision framework to continuously monitor system execution and suggest norm revisions proactively.
  • Generalization: While some generalization was tested, further investigation into how well revised norms generalize to unseen traces is a direction for future work.
  • Relative Importance: Incorporating the relative importance of different states and propositions in the revision process is another avenue for future research.

Summary updated

Abstract

In multi-agent systems, norm enforcement is a mechanism for steering the behavior of individual agents in order to achieve desired system-level objectives. Due to the dynamics of multi-agent systems, however, it is hard to design norms that guarantee the achievement of the objectives in every operating context. Also, these objectives may change over time, thereby making previously defined norms ineffective. In this paper, we investigate the use of system execution data to automatically synthesise and revise conditional prohibitions with deadlines, a type of norms aimed at preventing agents from exhibiting certain patterns of behaviors. We propose DDNR (Data-Driven Norm Revision), a data-driven approach to norm revision that synthesises revised norms with respect to a data set of traces describing the behavior of the agents in the system. We evaluate DDNR using a state-of-the-art, off-the-shelf urban traffic simulator. The results show that DDNR synthesises revised norms that are significantly more accurate than the original norms in distinguishing adequate and inadequate behaviors for the achievement of the system-level objectives.
BibTeX
@inproceedings{dellanna2023data,
  author = {Davide Dell'Anna and Natasha Alechina and Fabiano Dalpiaz and Mehdi Dastani and Brian Logan},
  title = {{Data-Driven Revision of Conditional Norms in Multi-Agent Systems (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=veOHSyefDE},
}

Loading related content...

Figure