An Implementation of Consistency-Based Multi-agent Belief Change Using ASP

Paul Vicol, James P. Delgrande, Torsten SchaubLPNMR 2015 · DOI

TL;DR

This paper introduces Equibel, a software system that implements a consistency-based framework for multi-agent belief change. It leverages Answer Set Programming (ASP) to efficiently find maximal agreements between agents' beliefs, enabling them to share information and update their knowledge bases without compromising their core beliefs.

What Problem Does This Paper Address?

In multi-agent systems, agents often possess individual belief bases and need to incorporate information from their peers. A key challenge is how agents can share information and update their beliefs in a way that is both consistent with their existing knowledge and maximizes the shared understanding. Traditional approaches often focus on merging entire belief bases or employ iterated processes. This paper addresses the need for a system that can handle belief sharing in arbitrary network topologies, allowing agents to incorporate as much consistent information as possible from their neighbors in a single step.

Methods

Equibel is built with a two-layer architecture:

  • ASP Layer: This core component uses Answer Set Programming (ASP) to perform the computationally intensive task of finding "maximal fits." A fit is a set of equivalences between propositional atoms of different agents that allows for a consistent assignment of truth values to all atoms, respecting the agents' original beliefs. "Maximal fits" are those that cannot be extended further. The ASP programs eq_sets.lp and translate.lp are used to generate candidate equivalence sets, test their consistency, and translate beliefs between agents based on these equivalences.
  • Python Layer: This layer acts as a wrapper and interface. It manages the ASP solver (clingo), processes the output from the ASP layer (combining results from different maximal fits), and provides both a programmatic interface for developers and an interactive command-line interface (CLI) for users. The Python component handles the "one-shot" belief sharing by taking the disjunction of translated beliefs across all maximal equivalence sets. It also supports belief revision and merging operations by constructing implicit graph topologies.

Datasets

Not discussed in the paper. The paper focuses on a general framework and its implementation, using a motivating example with propositional atoms to illustrate the concepts.

Key Insights and Ideas

  • Consistency-Based Belief Sharing: The core idea is that agents should incorporate information that is consistent with their existing beliefs. This is achieved by finding maximal sets of equivalences between agents' propositional atoms.
  • ASP for Maximization: Answer Set Programming proves to be a powerful tool for efficiently finding these maximal equivalence sets, which are crucial for determining how agents can agree on information.
  • Two-Layered Architecture: The separation of concerns between the ASP layer (for core computation) and the Python layer (for interface and post-processing) provides a flexible and scalable system.
  • "One-Shot" Belief Sharing: The system implements a single-step belief sharing mechanism, which is distinct from iterated approaches and can be more efficient in certain scenarios.
  • Implicit Graph Topologies: The system can handle belief revision and merging by implicitly constructing graph structures, making these operations accessible within the same framework.

Key Results

The paper demonstrates the implementation of a consistency-based belief change framework. While specific quantitative results are not presented, the paper highlights the system's ability to:

  • Model belief sharing in arbitrary network topologies.
  • Perform belief revision and merging operations.
  • Provide both programmatic and interactive interfaces for experimentation.
  • The motivating example illustrates how the system can determine updated beliefs for agents in a scenario involving drones searching for missing people.

Limitations and Future Work

  • Iterated Change: The current implementation focuses on a "one-shot" belief sharing mechanism. The authors mention that expanding the system to support iterated change is a future direction.
  • Agent Expertise: Incorporating agent expertise into the belief change process is another area for future work.
  • Performance on Large Networks: While ASP is efficient, the complexity of finding maximal equivalence sets can still be a challenge for very large or dense networks. This is implicitly acknowledged by the focus on "maximization" which aims to reduce the search space.

Summary updated

BibTeX
@inproceedings{vicol2015implementation,
  author = {Paul Vicol and James P. Delgrande and Torsten Schaub},
  title = {{An Implementation of Consistency-Based Multi-agent Belief Change Using ASP}},
  booktitle = {LPNMR},
  year = {2015},
  doi = {10.1007/978-3-319-23264-5\_40},
}
Figure