Tractable Inquiry in Information-Rich Environments

Barbara Dunin-Keplicz, Alina StrachockaIJCAI 2015

In the field of multi-agent systems, a fundamental challenge is enabling autonomous agents to solve problems collectively when their information is incomplete, messy, or contradictory. Traditional logical models, typically rooted in 2-valued (True/False) logic, often fail in these "information-rich" environments. A single contradiction can lead to logical trivialization, and many existing dialogue models are too computationally expensive for real-time applications. This paper, presented at IJCAI 2015, proposes a formal framework for tractable inquiry dialogues designed to overcome these hurdles.

The 4QL Logic Framework

To handle real-world uncertainty, the authors move beyond binary logic to a 4-valued logic system known as 4QL. This system treats ignorance and inconsistency as first-class citizens by introducing two additional truth values: Unknown (u) and Inconsistent (i).

Truth tables for the 4-valued logic (4QL) operators.

By utilizing 4QL, agents can explicitly reason about what they do not know or where their data sources disagree. The framework is implemented using a Datalog-like query language that allows for negation in both premises and conclusions. This flexibility is essential for handling conflicts without breaking the underlying reasoning engine, all while ensuring that evaluations remain within polynomial time.

Dialogue Management and Strategies

The proposed system manages conversations through two primary mechanisms:

  1. Commitment Store (CS): An evolving 4QL program that accumulates all facts and rules shared during the dialogue.
  2. Query Store (QS): A repository of active, unresolved questions that drive the backward-chaining process.

The researchers define four distinct inquiry strategies—narrow-minded, pragmatic, forgetful, and open-minded—distinguished by how they open and close inquiry threads as new information is introduced. The paper specifically differentiates between Inquiry-WHAT (discovery of unknown values) and Inquiry-THAT (proving or refuting a specific hypothesis).

Comparative Analysis and Complexity

A key contribution of the paper is the formal proof of the "Open-minded" strategy's superiority. It is the only strategy demonstrated to be both sound and complete, meaning it will always reach the same conclusion as a single hypothetical "super-agent" with access to all agents' private databases.

Comparative analysis of inquiry strategies and their computational properties.

As shown in the comparison above, while "narrow-minded" strategies may seem efficient, they are neither sound nor complete because they risk closing inquiry threads prematurely, potentially ignoring critical conflicting evidence. In terms of complexity, the framework achieves a communication complexity of $O(nM)$ and a computational complexity for obtaining conclusions of $O(N^k)$, matching the efficiency of standard recursive SQL.

Conclusion

By restricting logic to a rule-based 4QL system, the authors provide a pathway for expressive yet tractable multi-agent communication. While current models assume cooperative agents and static internal beliefs, future work aims to introduce "challenge" locutions and hybrid forward-backward chaining to further enhance the flexibility of these inquiry dialogues in dynamic environments.

Summary updated

BibTeX
@inproceedings{duninkeplicz2015tractable,
  author = {Barbara Dunin-Keplicz and Alina Strachocka},
  title = {{Tractable Inquiry in Information-Rich Environments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure