Answer set based design of highly autonomous, rational agents

Abstract

Answer set programming is a knowledge representation methodology that combines a high level of abstraction and direct computability. This dissertation shows how complex rational agents can be built with the answer set programming methodology and the associated languages. We describe the design of agents capable of fairly sophisticated reasoning, including planning, diagnosis, inductive learning. More precisely, we show reasoning algorithms that, given a formal description of the domain, allow the agent to: * generate plans, expected to achieve the agent's goal under reasonable assumptions; * monitor the execution of actions and detect unexpected observations; * explain unexpected observations by: - hypothesizing that some event occurred, unobserved, in the past; - modifying the original description of the domain to match the observations.

The reasoning approach is model-based, with the domain model written in action language AL, and shared by all the reasoning components. The ability to use a single model for all the types of reasoning demonstrates the flexibility deriving from the use of answer set programming. Moreover, having a single model increases the ease of development, update and reuse of the domain description.

For the actual computation, the domain model is translated into A-Prolog using a novel encoding from AL into A-Prolog. The encoding differs from the previous ones in that it extracts, from the model in AL, information that support not only planning and diagnosis, but also learning.

Two sets of reasoning components are presented. The first set is developed using A-Prolog. We demonstrate that the components in this set are capable of fairly sophisticated reasoning. Next, we show how the approach can be extended to substantially improve the quality of reasoning. For this, we develop CR-Prolog, a language in which A-Prolog is augmented by consistency-restoring rules (cr-rules) and preferences. The new constructs allow the encoding of qualitative preferences on the solutions of reasoning problems. The second set of reasoning components is obtained by extending the basic ones to allow the specification of preferences. This allows to reason, for example, about plans satisfying, if at all possible, a collection of requirements, about most likely diagnoses, and about most reasonable modifications of domain models. We demonstrate how the quality of reasoning performed by this set of components is substantially higher than that of the basic ones.

Since the reasoning techniques sometimes depend on whether the domain model is deterministic or non-deterministic, we also present a sufficient condition for the determinism of action descriptions. We show that the condition can be checked in polynomial time, and describe an A-Prolog program that performs the test.