SAT Encodings for Distance-Based Belief Merging Operators

Sébastien Konieczny, Jean-Marie Lagniez, Pierre MarquisAAAI 2017 · DOI

Abstract

Belief merging is a critical task in multi-agent systems where conflicting information from multiple sources must be reconciled under integrity constraints. While distance-based merging operators offer a robust framework, their high computational complexity ($Θ_2^P$ or $Δ_2^P$) has historically limited their application to small-scale problems. This paper presents a novel approach that leverages the "SAT revolution" by translating belief merging into Boolean Satisfiability (SAT) problems. By employing a two-step compilation process involving Weighted Partial MAXSAT solvers, we demonstrate that distance-based merging can scale to hundreds of variables, making it practical for complex real-world scenarios for the first time.

Introduction

In multi-agent environments, agents often hold divergent beliefs. The goal of belief merging is to synthesize these individual "belief bases" into a single, consistent base that respects a set of global "integrity constraints." Distance-based merging is a prominent approach where the resulting merged base consists of models that satisfy the integrity constraints and minimize a collective distance to the agents' profiles.

Despite its theoretical elegance, implementing these operators is challenging. Previous state-of-the-art methods relied on Ordered Binary Decision Diagrams (OBDDs), which typically fail when the number of variables exceeds twenty. This work addresses this scalability bottleneck by proposing efficient SAT encodings for various distance metrics and aggregation functions.

Methods

The proposed methodology utilizes a two-step compilation process to transform a merging problem into a standard Conjunctive Normal Form (CNF) formula:

  1. Optimization Step: A Weighted Partial MAXSAT solver identifies the minimum distance ($min$) between the integrity constraints and the collective agent profile.
  2. Encoding Step: A CNF formula is generated to represent all worlds that satisfy the integrity constraints and achieve exactly this minimum distance.

The authors developed specific encoding schemes for distances such as Drastic and Hamming distance, and aggregators including $\Sigma$ (summation), GMax (leximax), and GMin (leximin). For GMax and GMin, sophisticated constraints were implemented to sort distance vectors within the logic formula.

Example of distance-based merging with different aggregators

As shown in Figure 1, different aggregators can lead to different preferred models ($ω$) depending on how individual distances to belief bases ($K_1, K_2, K_3$) are combined.

Experimental Evaluation

To evaluate the scalability of the SAT-based approach, the authors created a benchmark based on a university time-tabling problem. This problem involves hard integrity constraints (e.g., no teacher can be in two places at once) and soft preferences from multiple curricula. The dataset included 150 instances with up to 15 belief bases and hundreds of variables.

Results

The experimental results demonstrate a significant leap in performance over previous methods. While OBDD-based implementations failed on all non-trivial benchmarks, the SAT-based approach successfully handled instances with hundreds of variables.

Experimental results for various merging operators and problem sizes

Figure 2 details the performance across different operators and problem sizes (defined by the number of belief bases $K^k$). The $\Sigma$ aggregator proved to be the most efficient, with most instances solved in under 100 seconds. While GMax and GMin were more computationally demanding due to the complexity of sorting encodings, they remained solvable for the majority of instances within a 900-second timeout. Furthermore, the generated SAT encodings were found to be polynomial in size, ensuring efficient representation of the merged base.

Conclusion

This work marks a significant advancement in the practical application of belief merging. By reducing a $\Delta_2^P$ problem to a series of SAT calls, the authors have enabled the processing of large-scale multi-agent coordination problems. Future work will explore encoding additional logical distances and applying these techniques to domains such as robot swarm planning and legal reasoning.

Summary updated

BibTeX
@inproceedings{konieczny2017sat,
  author = {Sébastien Konieczny and Jean-Marie Lagniez and Pierre Marquis},
  title = {{SAT Encodings for Distance-Based Belief Merging Operators}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10681},
}

Loading related content...

Figure