Communicating Answer Set Programs

Kim Bauters, Jeroen Janssen, Steven Schockaert, Dirk Vermeir, Martine De CockICLP (Technical Communications) 2010 · OpenReview

TL;DR

This paper explores the expressiveness of Answer Set Programming (ASP) when multiple ASP programs can communicate. They demonstrate that simple ASP programs communicating with each other can achieve the same expressive power as normal ASP programs with negation-as-failure. Furthermore, they introduce a "focused" communication mechanism that allows simple programs to simulate disjunctive ASP programs.

What Problem Does This Paper Address?

Answer Set Programming (ASP) is a powerful declarative programming paradigm for solving complex problems. While existing work has explored how multiple ASP programs (agents) can cooperate, the specific impact of communication on the expressiveness of these systems, particularly when using simple ASP programs (those without negation-as-failure), has not been thoroughly investigated. This paper aims to fill this gap by systematically studying how communication mechanisms affect the problem-solving capabilities of ASP.

Methods

The authors introduce a formal framework for "communicating answer set programs." This framework allows individual ASP programs (components) to communicate by querying each other's literals. They define a semantics for these communicating programs and then explore their expressiveness through transformations.

Key methodological contributions include:

  • Simulating Negation-as-Failure: They propose a transformation that converts a communicating normal ASP program (which can use negation-as-failure) into an equivalent communicating simple ASP program (without negation-as-failure). This transformation involves introducing auxiliary "world" components to simulate the non-monotonic behavior of negation-as-failure.
  • Focused Communicating Programs: They extend the communication mechanism by introducing the concept of "focusing" on a single component program. This allows for analyzing the answer sets of a specific agent within the network, effectively treating it as a leader or primary decision-maker. This focused approach is then used to simulate disjunctive ASP programs.

Datasets

Not discussed in the paper. The paper focuses on theoretical expressiveness and formalisms rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Communication as a Substitute for Negation-as-Failure: The most striking insight is that the ability for simple ASP programs to communicate (ask questions to each other) is as expressive as adding negation-as-failure to individual programs. This suggests that distributed reasoning can compensate for the lack of certain logical constructs within individual components.
  • Focusing for Disjunction Simulation: The introduction of "focused" communicating programs is a clever way to handle disjunction. By designating one component as the focus, the system can effectively simulate the choice inherent in disjunctive rules by leveraging the communication and negation-as-failure simulation techniques.
  • Complexity Implications: The paper connects these expressiveness results to computational complexity. Simulating normal ASP programs with communicating simple programs implies that solving communicating simple programs is at least NP-hard. The focused communication mechanism, by simulating disjunctive programs, pushes the complexity to $\Sigma_2^P$.

Key Results

  • Communicating simple ASP programs have the same expressiveness as communicating normal ASP programs (i.e., they can simulate negation-as-failure).
  • Focused communicating programs can simulate positive disjunctive ASP programs.
  • The problem of finding answer sets for communicating simple programs is NP-hard.
  • Deciding whether a Q-focused communicating program with two or more components has an answer set containing a specific literal is $\Sigma_2^P$-hard.

Limitations and Future Work

  • Complexity of Comparison: The authors note that while their work complements existing research on multi-context systems, direct comparisons can be complicated by differences in definitions of communicating ASP and minimality.
  • Parameter-less Communication: The paper focuses on parameter-less communication, where the truth of a situated literal doesn't depend on parameters passed to it. Future work could explore more complex communication patterns.
  • Empirical Evaluation: The paper is primarily theoretical. Future work could involve implementing these mechanisms and evaluating their performance on practical problems.
  • Further Complexity Analysis: While complexity results are presented, further exploration of the precise complexity classes for various forms of communicating ASP could be beneficial.

Summary updated

Abstract

Answer set programming is a form of declarative programming that has proven very successful in succinctly formulating and solving complex problems. Although mechanisms for representing and reasoning with the combined answer set programs of multiple agents have already been proposed, the actual gain in expressivity when adding communication has not been thoroughly studied. We show that allowing simple programs to talk to each other results in the same expressivity as adding negation-as-failure. Furthermore, we show that the ability to focus on one program in a network of simple programs results in the same expressivity as adding disjunction in the head of the rules.
BibTeX
@inproceedings{bauters2010communicating,
  author = {Kim Bauters and Jeroen Janssen and Steven Schockaert and Dirk Vermeir and Martine De Cock},
  title = {{Communicating Answer Set Programs}},
  booktitle = {ICLP (Technical Communications)},
  year = {2010},
  url = {https://openreview.net/forum?id=2Zyz1tLev2b4},
}
Figure