Logical planning in Temporal Defeasible and Dynamic Epistemic Logics: the case of t-DeLP and LCC

Abstract

In this thesis, we study planning systems based on logics, for two particular cases: Temporal Defeasible Logic Programming t-DeLP and the Logics of Communication and Change LCC. A planning problem consists in building a course of actions, or plan, whose execution leads from a given initial state to some goal state. The motivation for the present studies, from the point of view of Logic, is to obtain systems for practical reasoning (what an agent should do) from given logics oriented to multi-agent systems. From the Artificial Intelligence point of view, the motivation consists in extending the languages and logics underlying the well-known classical or temporal planning systems. This way, a planner can correctly reason about certain concepts (actions, causality, belief, etc.) using an appropriate logic to this end. In practice, the proposed methods permit a planner to aim for goals which can be expressed in the corresponding logical languages. The first part of the thesis contains a study of t-DeLP along these lines. The t-DeLP framework is a non-monotonic temporal logic programming system based on tools from computational argumentation. This logic system aimsto model different types of causal reasoning in a non-monotonic way, but using to this end natural concepts inspired by human reasoning and argumentation. The t-DeLP system is a temporal extension of the DeLP system proposed by García and Simari. In t-DeLP, a knowledge base is given by a set of temporal rules and facts, which combine into arguments (or consistent, minimal derivations) for further derived temporal facts (or conclusions). The language admits two types of rules: strict and defeasible. The former behave similarly to rules in monotonic logics, while derivations or arguments making use of some defeasible rules can be canceled by other existing arguments. To solve the temporal inconsistencies between conflicting arguments, we propose two criteria based on a preference for arguments using more strict facts (more basic information) or less persistence rules. It is shown that the resulting logic programming system satisfies different consistency and closure properties that any logic-argumentation system should obey.

In order to define a planning system based on t-DeLP, one can introduce temporal actions as pairs of preconditions and effects. These actions combine with the t-DeLP consequence relation, thus inducing a state transition system. Different search algorithms for centralized planning can be shown to be sound and complete for the class of planning problems definable in t-DeLP. We also study the decentralized case, where a group of planning agents cooperate in order to reach an agreement upon a joint plan for their shared goals. For this, we propose a protocol for argumenative dialogues that defines a plan search algorithm. This algorithm is also shown to be sound and complete, with respect to centralized planning.

The second part of the thesis focuses on the Logics of Communication and Change, or LCC. LCC is a family of dynamic epistemic logics proposed by van Benthem et al. Which capture a good deal of the existing dynamic epistemic logics in the literature. The class of LCC modal logics contain a rich class of epistemic operators for multiple agents or groups as well as operators for common knowledge or belief. They also contain dynamic operators for the execution of epistemic actions (communications, observations) or physical actions. The actions of either type can also be modelled with their epistemic effects, that is, how the action will appear to each of the agents. In this thesis, we also extend these logics with product and choice constructors in order to model non-deterministic actions and plans. We propose a simple extension of the axiom system along this line, and show its soundndess and completeness.

The proposed planning system based on these logics permit the study of deterministic and non-deterministic planning. In this thesis we show that the corresponding search algorithms based on Breadth First Search are correct and complete for backward planning in a given LCC logic. This is shown for both the deterministic case, and for strong non-deterministic planning.

En aquesta tesi, estudiem algorismes de planificació per a dues lògiques enfocades a sistemes multi-agent. Amb més detall, estudiem problemes de planificació (com arribar a estats objectiu a partir de l'estat inicial i un conjunt d'accions disponibles), els elements dels quals es poden expressar en alguna de les dues lògiques. En la primera part de la tesi, proposem en primer lloc una extensió temporal de la programació lògica rebatible (temporal defeasible logic programming) t-DeLP. Aquest és un sistema de programació lògica no-monotònica basat en tècniques d'argumentació i orientat al raonament sobre les accions, i especialment dels seus efectes indirectes. En el llenguatge d'aquesta lògica, hom pot descriure accions temporals de l'estil de sistemes de planificació, i definir al seu temps un sistema de transicions d'estats. Finalment, això permet definir un sistema de planificació basat en aquesta lògica que combina accions i derivacions lògiques. Les contribucions principals al respecte són: l'estudi de les propietats argumentatives del sistema lògic, i de la correcció i completesa d'algorismes basats en Breadth First Search de cerca en l'espai de plans. En la segona part de la tesi, estudiem sistemes de planificació definits sobre una família de lògiques dinàmiques epistèmiques, conegudes com a Logics of Communication and Change. Aquestes lògiques permeten l'estudi formal de les creences de diversos agents, així com dels efectes epistemics i físics de diferents tipus d'accions. Entre aquestes, podem incloure diferents accions comunicatives (públiques, privades), observacions i les accions físiques habituals en planning. L'estudi del sistema de planificació definit per aquestes lògiques és dut a terme mitjançant algorismes de cerca basats en breadth first search. Les contribucions principals són l'extensió d'aquestes lògiques amb accions no-deterministes i composició d'accions, i la demostració de la correcció