We consider a particular subclass of normal programs that we call simple guess-and-check (SGC) programs. SGC programs consist of guess rules (i.e. rules without positive body atoms) and arbitrary constraints. Many simple combinatorial problems such as graph coloring can be encoded via SGC programs. Moreover, constraint-free SGC programs are known to have a close relation to abstract argumentation frameworks. Our main result shows that for SGC programs the notions of strong and uniform equivalence coincide (in contrast to general normal programs), but do not amount to classical equivalence (as is the case of positive programs). Moreover, we study the characteristics of SE-models for SGC programs; this allows to check whether an arbitrary program (part) can be equivalently formulated within the simpler class of SGC programs. Finally, we briefly discuss our results in relation to other classes of programs.

The ability to abstract is important in AI systems and in problem solving, as generalizing over irrelevant details facilitates finding solutions. In the context of Answer Set Programming (ASP), abstraction has been recently investigated with a focus on the omission of unnecessary details, which is related to forgetting, as well as on clustering vocabulary of similar concepts into a common abstract representation. In the latter case, a characterization has been provided that identifies when such abstraction is possible without affecting the answer sets under the addition of any set of facts, in the spirit of uniform equivalence and aligned with the ASP methodology where a general problem encoding is used with varying instances. However, when this characterization fails, no abstraction is possible, and even if it succeeds, computing an abstracted program syntactically is only possible for a limited subclass of programs. In this paper, we consider that not all kinds of facts are required to be added in general, and investigate under which conditions such abstraction is indeed always possible as well as when and how to compute abstracted programs, generalizing at the same time (compared to related work) to a larger class of programs with wider applicability.

In the study of logic programming, notions of equivalence play a significant role. This is due to the fact that under common nonmonotonic semantics, like answer-set programming, two programs sharing the same models (answer sets) does not necessarily yield that they are equivalent in all contexts. Whether this context concerns other program modules or just different data, distinguishes strong from uniform equivalence. We introduce a new notion of equivalence for logic programs under the answer-set semantics that allows to precisely compare and simplify programs that receive input from different sources (i.e., over different alphabets); a setting that previous equivalence notions have not considered, but has some interesting use cases, like data integration or belief merging. Our notion further generalizes relativized equivalence, where equivalence is only required over a parameterized context, and has the core concepts of strong and uniform equivalence as corner cases. We provide a model-theoretic characterization in the spirit of SE-models and establish some theoretical properties including a thorough complexity analysis. Furthermore, using our notion, we can pinpoint the known complexity gap between strong and uniform equivalence, giving insight into why the latter is harder than the former.

Answer Set Programming (ASP) is a prominent rule-based language for knowledge representation and reasoning with roots in logic programming and non-monotonic reasoning. The aim to capture the essence of removing (ir)relevant details in ASP programs led to the investigation of different notions, from strong persistence (SP) forgetting, to faithful abstractions, and, recently, strong simplifications, where the latter two can be seen as relaxed and strengthened notions of forgetting, respectively. Although it was observed that these notions are related, especially given that they have characterizations through the semantics for strong equivalence, it remained unclear whether they can be brought together. In this work, we bridge this gap by introducing a novel relativized equivalence notion, which is a relaxation of the recent simplification notion, that is able to capture all related notions from the literature. We provide the necessary and sufficient conditions for relativized simplifiability, which shows that the challenging part is for when the context programs do not contain all the atoms to remove. We then introduce an operator that combines projection and a relaxation of SP-forgetting to obtain the relativized simplifications. We furthermore provide complexity results that complete the overall picture.

Approaches to computational argumentation provide foundational ways to reason argumentatively within Artificial Intelligence (AI). The underlying formal approaches can oftentimes be classified into structured argumentation and abstract argumentation. The former prescribe rigorous workflows, starting from knowledge bases to finding arguments in favour and against claims under scrutiny, and drawing conclusions. Abstract argumentation provides formal semantics operating on arguments whose internal structure is hidden and only relations are kept for reasoning, resulting in so-called argumentation frameworks (AFs). In this work, we apply a form of existential abstraction on the prominent structured approach of assumption-based argumentation (ABA), leading to an interactive way of simplifying argumentation scenarios by abstracting irrelevant details, towards supporting explainability. Existential abstraction was shown to be promising in many areas of AI, including a recent work on AFs. We lift this approach to the structured level---which is, as we show, both not direct from AFs and can benefit from utilization of the internal structure of arguments. Among our contributions, we introduce existential abstraction on ABA via clustering assumptions, develop semantics on clustered ABA frameworks for reasoning on such clusterings, show differences to the level of AFs, and provide a prototype interactive tool that obtains faithful clusterings that do not lead to any spurious reasoning.

Generalization is an important ability that allows humans to tackle complex problems by identifying common problem structures and omitting irrelevant details. Whereas such ability comes naturally to humans, it has proved challenging to establish within AI systems. Although different research communities have tackled this challenge, their focus has usually been set on developing efficient algorithms for concrete problems, and a general theoretical understanding of the generalization ability is still lacking. In the context of Answer Set Programming (ASP), a well-established knowledge representation and reasoning paradigm for solving highly combinatorial search problems, research on generalization has primarily focused on forgetting and projection, two related operations that aim at the omission of irrelevant details, while abstraction, an operation that aims at providing a higher-level view on the common solution and problem structures, has largely been overlooked. In this paper, we develop the theoretical foundation for generalized reasoning through abstraction in ASP, focusing on the notion of abstraction through vocabulary clustering. We formally characterize when abstraction is possible, semantically define the desired result, investigate syntactic operators to obtain such abstractions, and study the computational complexity of this problem.

Recently forms of abstraction have been proposed for both logic programs (LPs) under the answer set semantics (ASP) and for the related formalism of assumption-based argumentation (ABA), e.g., via clustering of atoms or assumptions, in order to simplify a given LP or ABA framework. In both approaches after clustering the original answer sets and assumption sets are over-approximated, with the aim of avoiding spuriousness. In contrast, in ASP a given LP is syntactically modified to achieve over-approximation, while on ABA the framework is minimally modified and the semantics is abstracted. In this work we follow the latter approach and provide a novel semantical abstraction for LPs and for ABA frameworks corresponding to LPs.

Simplification of logic programs under the answer-set semantics has been studied from the very beginning of the field. One natural simplification is the removal of atoms that are deemed irrelevant. While equivalence-preserving rewritings are well understood and incorporated in state-of-the-art systems, more careful rewritings in the realm of strong or uniform equivalence have received considerably less attention. This might be due to the fact that these equivalence notions rely on comparisons with respect to context programs that remain the same for both the original and the simplified program. In this work, we pursue the idea that the atoms considered irrelevant are disregarded accordingly in the context programs of the simplification, and propose novel equivalence notions for this purpose. We provide necessary and sufficient conditions for these kinds of simplifiability of programs, and show that such simplifications, if possible, can actually be achieved by just projecting the atoms from the programs themselves. We furthermore provide complexity results for the problems of deciding simplifiability and equivalence testing.

Abstraction is a powerful technique that has not been considered much for nonmonotonic reasoning formalisms including Answer Set Programming (ASP), apart from related simplification methods. We introduce a notion for abstracting from the domain of an ASP program that shrinks the domain size and over-approximates the set of answer sets, as well as an abstraction-&-refinement methodology that, starting from an initial abstraction, automatically yields an abstraction with an associated answer set matching an answer set of the original program if one exists. Experiments reveal the potential of the approach, by its ability to focus on the program parts that cause unsatisfiability and by achieving concrete abstract answer sets that merely reflect relevant details.

Argumentation in Artificial Intelligence (AI) builds on formal approaches to reasoning argumentatively. Common to many such approaches is to use argumentation frameworks (AFs) as reasoning engines, with AFs being composed of arguments and attacks between arguments, which are instantiated from knowledge bases in a principle-based manner. While representing what can be argued for in an AF provides a conceptually clean way, this process can face challenges arising from generating a large number of arguments, which can act as a barrier to explainability. Inspired by successful approaches to model checking where the state explosion is mitigated by applying existential abstraction, we study an adaption of existential abstraction in form of clustering arguments in an AF to address an associated "argument explosion". In this paper, we provide a foundational investigation of this form of existential abstraction by defining semantics of the resulting clustered AFs, which balance two inherent aspects of existential abstractions: abstracting from concrete AFs and not permitting too much spuriousness (i.e., conclusions that hold on the abstraction but not on the original AF). Moreover, we show properties of clustered AFs, including complexity results, discuss use of clusterings for explaining results of reasoning tasks, and employ the recently introduced methodology of abstraction in answer set programming (ASP) for obtaining and reasoning over clustered AFs.

Abstraction is an important technique utilized by humans in model building and problem solving, in order to figure out key elements and relevant details of a world of interest. This naturally has led to investigations of using abstraction in AI and Computer Science to simplify problems, especially in the design of intelligent agents and automated problem solving. By omitting details, scenarios are reduced to ones that are easier to deal with and to understand, where further details are added back only when they matter. Despite the fact that abstraction is a powerful technique, it has not been considered much in the context of nonmonotonic knowledge representation and reasoning, and specifically not in Answer Set Programming (ASP), apart from some related simplification methods. In this work, we introduce a notion for abstracting from the domain of an ASP program such that the domain size shrinks while the set of answer sets (i.e., models) of the program is over-approximated. To achieve the latter, the program is transformed into an abstract program over the abstract domain while preserving the structure of the rules. We show in elaboration how this can be also achieved for single or multiple sub-domains (sorts) of a domain, and in case of structured domains like grid environments in which structure should be preserved. Furthermore, we introduce an abstraction-&-refinement methodology that makes it possible to start with an initial abstraction and to achieve automatically an abstraction with an associated abstract answer set that matches an answer set of the original program, provided that the program is satisfiable. Experiments based on prototypical implementations reveal the potential of the approach for problem analysis, by its ability to focus on the parts of the program that cause unsatisfiability and by achieving concrete abstract answer sets that merely reflect relevant details. This makes domain abstraction an interesting topic of research whose further use in important areas like Explainable AI remains to be explored.

Abstract Abstraction is a well-known approach to simplify a complex problem by over-approximating it with a deliberate loss of information. It was not considered so far in Answer Set Programming (ASP), a convenient tool for problem solving. We introduce a method to automatically abstract ASP programs that preserves their structure by reducing the vocabulary while ensuring an over-approximation (i.e., each original answer set maps to some abstract answer set). This allows for generating partial answer set candidates that can help with approximation of reasoning. Computing the abstract answer sets is intuitively easier due to a smaller search space, at the cost of encountering spurious answer sets. Faithful (non-spurious) abstractions may be used to represent projected answer sets and to guide solvers in answer set construction. For dealing with spurious answer sets, we employ an ASP debugging approach to help with abstraction refinement, which determines atoms as badly omitted and adds them back in the abstraction. As a show case, we apply abstraction to explain unsatisfiability of ASP programs in terms of blocker sets, which are the sets of atoms such that abstraction to them preserves unsatisfiability. Their usefulness is demonstrated by experimental results.

Humans are capable of abstracting away irrelevant details or distinguishing the common properties when studying problems. This is especially noticeable for planning problems, as humans are able to disregard certain parts of the domain and focus on the key elements important for finding a plan. Recently, the notion of abstraction has been introduced for Answer Set Programming (ASP), a knowledge representation and reasoning paradigm widely used in problem solving, with the potential to understand the key elements of a program that play a role in finding a solution. This paper highlights the potential use of such an abstraction in getting to the essence of planning problems, expressed in ASP, by disregarding irrelevant details and computing abstract plans.

The recently introduced notion of ASP abstraction is on reducing the vocabulary of a program while ensuring over-approximation of its answer sets, with a focus on having a syntactic operator that constructs an abstract program. It has been shown that such a notion has the potential for program analysis at the abstract level by getting rid of irrelevant details to problem solving while preserving the structure, that aids in the explanation of the solutions. We take here a further look on ASP abstraction, focusing on abstraction by omission with the aim to obtain a better understanding of the notion. We distinguish the key conditions for omission abstraction which sheds light on the differences to the well-studied notion of forgetting. We demonstrate how omission abstraction fits into the overall spectrum, by also investigating its behavior in the semantics of a program in the framework of HT logic.

For reliable and fault tolerant operation of cognitive factories, we introduce an algorithm to monitor plan executions. According to this algorithm, when some changes or discrepancies are detected, appropriate decisions are given based on the causes of these changes or discrepancies. To identify these causes (e.g., broken robots or robot components), we introduce a novel diagnostic reasoning method which synergistically integrates hypothetical reasoning, geometric reasoning, and learning from earlier experiences. Based on these causes, if necessary, new hybrid plans (task plans integrated with feasibility checks) are computed to reach the manufacturing goals by allowing repairs of robots/components. The results of our experiments over reasonably-sized cognitive factory scenarios show the usefulness of (i) diagnostic reasoning for execution monitoring, (ii) allowing repair actions during replanning, and (iii) learning from experiences. We provide a video of dynamic simulation of our execution monitoring algorithm with Kuka youBots and a Nao humanoid robot as the supplementary material.

We consider multiple teams of heterogeneous robots, where each team is given a feasible task to complete in its workspace on its own, and where teams are allowed to transfer robots between each other. We study the problem of finding a coordination of robot transfers between teams to ensure an optimal global plan (with minimum makespan) so that all tasks can be completed as soon as possible by helping each other. We propose to solve this problem using answer set programming.

We consider cognitive factories with multiple teams of heterogenous robots, and address two key challenges of these domains, hybrid reasoning for each team and finding an optimal global plan (with minimum makespan) for multiple teams. For hybrid reasoning, we propose (i) modeling each team's workspace taking into account capabilities of heterogeneous robots, (ii) embedding continuous external computations into discrete symbolic representation and reasoning by combining different methods of integration, (iii) not only optimizing the makespans of local plans but also minimizing the total cost of robotic actions, where costs of actions can be defined in various ways. To find a global plan with minimum makespan, we propose a semi-distributed approach: we formulate the problem of finding an optimal coordination of teams that can help each other, prove its intractability, and describe how to solve this problem using existing automated reasoners. As a case study, we show applications of our hybrid reasoning and coordination approaches on a cognitive toy factory with dynamic simulations and physical implementation utilizing KuKa youBots and Lego NXT robots (supplementary video provided). We also present experimental results to discuss the scalability of these methods.

Abstract We study the problem of finding optimal plans for multiple teams of robots through a mediator, where each team is given a task to complete in its workspace on its own and where teams are allowed to transfer robots between each other, subject to the following constraints: 1) teams (and the mediator) do not know about each other's workspace or tasks (e.g., for privacy purposes); 2) every team can lend or borrow robots, but not both (e.g., transportation/calibration of robots between/for different workspaces is usually costly). We present a mathematical definition of this problem and analyze its computational complexity. We introduce a novel, logic-based method to solve this problem, utilizing action languages and answer set programming for representation, and the state-of-the-art ASP solvers for reasoning. We show the applicability and usefulness of our approach by experiments on various scenarios of responsive and energy-efficient cognitive factories.