Norm Monitoring under Partial Action Observability

Natalia Criado, Jose M. SuchIEEE Trans. Cybernetics 2015 · DOI · OpenReview

TL;DR

This paper tackles the challenge of monitoring norm compliance in multi-agent systems when not all agent actions are observable. They propose a novel approach that reconstructs unobserved actions to gain a more complete picture, leading to significantly improved detection of norm violations and fulfillments.

What Problem Does This Paper Address?

In multi-agent systems (MAS), norms are crucial for coordinating and regulating agent behavior. However, a significant practical challenge arises when a "Norm Monitor" (NM) cannot observe every action taken by every agent. This "partial action observability" can occur due to the cost of monitoring, or because illegal actions might have effects that are observable even if the action itself isn't. Existing approaches often assume full observability or try to adapt norms, which isn't always feasible. This paper addresses this gap by proposing a method to reconstruct these unobserved actions, thereby enhancing the NM's ability to accurately assess norm compliance.

Methods

The core contribution of this paper lies in its formalization of action reconstruction for norm monitoring. They introduce two main strategies:

  • Full Reconstruction: This method exhaustively searches for all possible sets of unobserved actions that are consistent with the observed actions and the system's state before and after the actions occurred. It aims to identify exactly what happened.
  • Approximate Reconstruction: This approach is designed for scalability. Instead of finding exact action sequences, it identifies actions that are likely to have occurred or are forbidden/mandatory, even if the specific action isn't known. This allows the NM to detect violations or fulfillments even with incomplete information.

Both methods involve defining formal languages for states, actions, and norms, and then developing algorithms to infer unobserved actions and update the NM's knowledge of the system state.

Datasets

Not discussed in the paper. The authors developed a Java simulator to evaluate their approach, creating scenarios based on parameters like the number of agents, offices, corridors, and cameras.

Key Insights and Ideas

  • Reconstruction is Key: The fundamental insight is that even with partial observability, we can infer a lot about unobserved actions by considering the observed actions and the system's state transitions. This significantly improves norm monitoring accuracy.
  • Two Flavors of Reconstruction: The distinction between "full" and "approximate" reconstruction is crucial. Full reconstruction offers higher accuracy but is computationally expensive, while approximate reconstruction sacrifices some precision for scalability, making it practical for larger systems.
  • Discovering Violations: The approximate reconstruction method is particularly interesting because it can detect norm violations even when the exact forbidden action isn't identified. This is valuable for identifying problematic norm designs or situations where agents are forced into violating norms.

Key Results

The paper presents empirical evaluations demonstrating the effectiveness of their approach:

  • Improved Detection: Both full and approximate reconstruction significantly increase the number of detected norm violations and fulfillments compared to traditional monitors that only consider observed actions.
  • Approximate vs. Full: In complex scenarios with multiple norms and concurrent actions, approximate reconstruction performed slightly worse than full reconstruction but was still substantially better than traditional methods.
  • Scalability: The approximate reconstruction method proved to be scalable, successfully handling scenarios with up to 500 agents, 128 actions, and 128 norms.

Limitations and Future Work

  • Computational Cost of Full Reconstruction: The paper acknowledges that full reconstruction is computationally expensive and becomes intractable for larger, more complex scenarios.
  • Domain-Specific Approximations: The authors suggest that future work could investigate domain-dependent approximations to further speed up action reconstruction.
  • Norm Design: While the paper focuses on monitoring, the ability to detect situations where agents are forced into violating norms could inform better norm design.

Summary updated

Abstract

In the context of using norms for controlling multi-agent systems, a vitally important question that has not yet been addressed in the literature is the development of mechanisms for monitoring norm compliance under partial action observability. This paper proposes the reconstruction of unobserved actions to tackle this problem. In particular, we formalise the problem of reconstructing unobserved actions, and propose an information model and algorithms for monitoring norms under partial action observability using two different processes for reconstructing unobserved actions. Our evaluation shows that reconstructing unobserved actions increases significantly the number of norm violations and fulfilments detected.
BibTeX
@article{criado2015norm,
  author = {Natalia Criado and Jose M. Such},
  title = {{Norm Monitoring under Partial Action Observability}},
  journal = {IEEE Trans. Cybernetics},
  year = {2015},
  doi = {10.1109/tcyb.2015.2513430},
}
Figure