Logical planning in Temporal Defeasible and Dynamic Epistemic Logics: the case of t-DeLP and LCC
Pere Pardo · TDX (Tesis Doctorals en Xarxa) · 2013
En esta tesis, estudiamos sistemas de planificacion basados en logicas, para los casos particulares de las logicas Temporal Defeasible Logic Programming t-DeLP y Logics of Communication and Change LCC. Un problema de planificacion consiste en construir un plan cuya ejecucion lleve de un estado inicial a un estado objetivo. La motivacion para el presente estudio, en el area de la logica, consiste en obtener sistemas de razonamiento practico (que debe hacer un agente para conseguir un objetivo) a partir de ciertas logicas para sistemas multi-agente. Des del punto de vista de la inteligencia artificial, la motivacion consiste en extender el lenguaje y la logica subyacente a los sistemas de planificacion clasicos, de modo que el planificador pueda tambien razonar con ciertos conceptos (causalidad, conocimiento, etc.) utilizando una logica apropiada para este fin. De este modo, los objetivos del planificador pueden consistir en expresiones (formulas) de esta logica. La primera parte de la tesis contiene un estudio de t-DeLP en esta direccion. t-DeLP es un sistema no-monotonico de programacion logica temporal basada en herramientas de argumentacion computacional. Esta logica pretende modelizar distintos tipos de razonamiento causal de un modo no-monotonico, pero utilizando para este fin conceptos naturalmente inspirados en el razonamiento humano (razonamiento basado en argumentacion). t-DeLP es una adaptacion temporal del sistema logico DeLP propuesto por Garcia y Simari. En t-DeLP, una base de conocimiento viene dada por un conjunto de reglas y hechos temporales, que se combinan formando argumentos (derivaciones minimales) para hechos temporales derivados (conclusiones). El lenguaje admite dos tipos de reglas: estrictas y rebatibles. Las primeras se comportan clasicamente, de modo que las derivaciones estrictas son monotonicas, mientras que las derivaciones que utilizan una regla rebatible pueden ser canceladas por otros argumentos constructibles. Para solventar las posibles inconsistencias temporales entre argumentos, se propone un criterio basado en una preferencia por argumentos basados en mas hechos (mas informacion), o en un menor uso de reglas de persistencia temporal. Se puede demostrar que este sistema logico satisface distintas propiedades de consistencia y clausura, exigibles a cualquier sistema argumentativo. Para definir un sistema de planificacion en t-DeLP, se introducen las acciones como pares de precondiciones y efectos. Combinando estas acciones con la relacion de consecuencia logica de t-DeLP, se define un sistema de transiciones de estado, sobre el que se basa el sistema de planificacion. Distintos algoritmos de busqueda (centralizada) resultan correctos y completos al respecto. Tambien se estudia el caso descentralizado, donde un grupo de agentes cooperativos deben construir un plan conjunto para sus objetivos comunes. Se propone para este caso un protocolo de dialogos que define un algoritmo de busqueda de planes. Este algoritmo tambien resulta ser correcto y completo. La segunda de las logicas estudiadas, LCC, es una familia de logicas dinamicas epistemicas propuestas por van Benthem et al. que captura gran parte de las logicas existentes de la misma clase. LCC es un clase de logicas modales que contiene operadores epistemicos para multiples agentes o grupos, asi como de conocimiento comun (common knowledge). Tambien contiene operadores para la ejecucion de acciones epistemicas (comunicaciones, observaciones) o fisicas. Estas logicas, ademas, se pueden extender con constructores para modelizar acciones no-deterministas. Se propone una simple extension axiomatica de LCC en este sentido y se demuestra su correccion y completitud. Estas logicas permiten el estudio de sistemas de planificacion deterministas (LCC) y no-deterministas (LCC extendida). En esta tesis, demostramos que los correspondientes algoritmos de busqueda de tipo Breadth First Search son correctos y completos en el espacio de planes dado por una logica y un problema de planificacion. Bilbiografia: A. Garcia and G. Simari. Defeasible logic programming: An argumentative approach. Theory and Practice of Logic Programming, 4(1+2):95-138, 2004 J. van Benthem, J. Van Eijck and B. Kooi. Logics of communication and change. Information and Computation, 204: 1620-2662, 2006 M. Ghallab, D. Nau, and P. Traverso. Automated Planning: Theory and Practice. Morgan Kaufmann, 2004