Abstraction for Reasoning about Agent Behavior with Answer Set Programming

Recent advances in the field of AI aggravate the challenge of understanding the behavior of the designed agent and distinguishing the core elements in the designed model that plays a role in the behavior. A logic-based approach for designing AI agents is about representing their knowledge of the world as a mathematical model through a powerful representation language with precisely defined syntax and semantics, that describes the capabilities of the agent and allows it to reason about the next course of actions. The desire to develop such a representation language emerges the challenges of representing commonsense knowledge and the nonmonotonic nature of human reasoning, which has led to the invention of many formalisms in the field of Knowledge Representation and Reasoning. However, understanding the key elements in the behavior of an agent that is designed using such formalisms remains to be a challenging problem.

Answer Set Programming (ASP) is one such formalism which is recognized as a knowledge representation and reasoning paradigm, currently widely used in problem solving thanks to its expressive power and the availability of efficient solvers. One particular application area of ASP is the representation of agent behavior, as it offers an expressive setting which is convenient for representing and reasoning about actions and change. This makes ASP a desirable tool for reasoning about the behavior of the agent. There have been investigations on understanding how ASP programs work, which however may lead to obtaining explanations with too many details that prevent one from seeing the crucial parts of the behavior.

Abstraction is a process that is unwittingly used by humans for problem solving and figuring out the key elements. This observation has led to investigations of using abstraction in Computer Science and AI 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, by adding back further details only when necessary. Surprisingly, other than some simplification methods, abstraction has not been considered in the context of nonmonotonic knowledge representation and reasoning, and specifically not in ASP.

This thesis tackles the challenge of understanding the key elements in the behavior of an agent with an ASP perspective, by employing abstraction. We approach the challenge from two directions. First, we investigate the representation of an abstraction that preserves the behavior of the original program while getting rid of details irrelevant to the behavior. For this, we introduce a formal semantics for describing agent behavior following a designed policy by abstracting over the indistinguishable details, while preserving the behavior. Second, we make the initial step for employing abstraction in the context of Answer Set Programming, to be able to abstract over the irrelevant details of answer set programs. We focus on two approaches of abstraction: (1) abstraction by omission, and (2) domain abstraction, and introduce a method to construct an abstract program with a smaller vocabulary, by ensuring that the original program is over-approximated. We introduce an abstraction-&-refinement methodology that makes it possible to start with an initial abstraction and automatically achieve an abstraction with a concrete solution. The evaluations of the implemented tools of the methodology reveal the potential of the approach for problem analysis by focusing on the parts of the program that cause the unsatisfiability and by achieving concrete abstract answer sets that reflect relevant details only.