Planning is a challenging research area since the early days of Artificial Intelligence. The planning problem is the task of finding a sequence of actions leading an agent from a given initial state to a desired goal state. Whereas classical planning adopts restricting assumptions such as complete knowledge about the initial state and deterministic action effects, in real world scenarios we often have to face incomplete knowledge and non-determinism. Classical planning languages and algorithms do not take these facts into account. So, there is a strong need for formal languages describing such non-classical planning problems on the one hand and for (declarative) methods for solving these problems on the other hand.In this thesis, we present the action language Kc, which is based on flexible action languages from the knowledge representation community and extends these by useful concepts from logic programming.We define two basic semantics for this language which reflect optimistic and secure (i.e. sceptical) plans in presence of incomplete information or nondeterminism. These basic semantics are furthermore extended to planning with action costs, where each action can have an assigned cost value. Here, we address optimal plans as well as plans which stay within a certain overall cost limit.Next, we develop efficient (i.e. polynomial) transformations from planning problems described in our language Kc to disjunctive logic programs which are then evaluated under the so-called Answer Set Semantics. In this context, we introduce a general new method for problem solving in Answer Set Programming (ASP) which takes the genuine "guess and check" paradigm in ASP into account and allows us to integrate separate "guess" and "check" programs into a single logic program. Based on these methods, we have implemented the planning system DLVK. We discuss problem solving and knowledge representation in Kc using DLVK by means of several examples. The proposed methods and the DLVK system are also evaluated experimentally and compared against related approaches. Finally, we present a practical application scenario from the area of design and monitoring of multi-agent systems. As we will see, this monitoring approach is not restricted to our particular formalism. / Austrian Science Funds (FWF)

This thesis presents the Planning System DLVK, which supports the novel Planning Language K. The language allows to represent AI planning problems in a declarative way and is capable of representing incomplete knowledge as well as nondeterministic effects of actions.After explaining some basics, the syntax and semantics of this language will be formally described and some results on the computational complexity of our language will be given, proving that K is capable of expressing hard planning problems, possibly involving incomplete knowledge or uncertainty, such as secure (conformant) planning.A translation from various planning tasks specified in K to a logic programming framework will be shown subsequently. We have implemented a prototype of a planning system, DLVK, on top of the disjunctive logic programming system DLV, to show the practical use of our translation. This prototype will be presented in detail. Finally, examples and experimental results will be given, together with an outlook to further research. / Austrian Science Funds (FWF)

Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state and state transitions. While few practical problems are purely conformant, the ability to find conformant plans is needed in planning with observations where conformant situations are an special case and where relaxations into conformant planning yield useful heuristics. In this dissertation, we introduce new formulations for tackling the conformant planning problem with deterministic actions using translations. On the one hand, we propose a translation in propositional logic and two schemes for obtaning conformant plans for it, one based on boolean operations of projection and model counting, the other based on projection and satisfiability. On the other hand, we introduce translations of the conformant planning problem into classical problems that are solved by a modern and effective classical planner. We analyze the formal properties of the translations into classical planning and evaluate the performance of the resulting conformant planners. / La planificación conformante es el problema de encontrar una secuencia de acciones para lograr un objetivo en presencia de información incompleta sobre el estado inicial y en las transiciones entre estados. Aunque pocos problemas son de carácter puramente conformante, la posibilidad de encontrar planes conformantes es necesaria en planificación con observaciones, donde las situaciones conformantes son un caso particular, y donde las relajaciones a planificación conformante dan heurísticas útiles. En esta tesis atacamos el problema de la planificación conformante con acciones determinísticas mediante dos formulaciones basadas en traducciones. Por un lado, proponemos una traducción a lógica proposicional y dos esquemas para obtener planes conformantes a partir de ésta, uno basado en operaciones booleanas de projección y conteo de modelos, y otro basado en projección y satisfacción proposicional. Por otro lado, introducimos traducciones que permiten transformar un problema de planificación conformante en un problema de planificación clásica que es luego resuelto usando planificadores clásicos. También analizamos las propiedades formales de las traducciones y evaluamos el rendimiento de los planificadores obtenidos.

Artificial Intelligence Planning is about acting in order to achieve a desired goal. Under incomplete information, the task of finding the actions needed to achieve the goal can be modelled as a search problem in the belief space. This task is costly, as belief space is exponential in the number of states, which is exponential in the number of variables. Good belief representations and heuristics are thus critical for scaling up in this setting. The translation-based approach to automated planning with incomplete information deals with both issues by casting the problem of search in belief space to a search problem in state space, where each node of the search space represents a belief state. We develop plan synthesis tools that use translated versions of planning problems under uncertainty, with partial or null sensing available. We show formally under which conditions the introduced translations are polynomial, and capture all and only the plans of the original problems. We study empirically the value of these translations. / La Planificación es la disciplina de Inteligencia Artificial que estudia los procesos de razonamiento necesarios para conseguir las acciones que logren un objetivo dado. En presencia de información incompleta, el problema de planificación puede ser modelado como una búsqueda en el espacio de estados de creencia, cada uno de ellos representando un conjunto de estados posibles. Este problema es costoso ya que el numero de estados de creencia puede ser exponencial en el número de estados, lo cual es exponencial en el número de variables del problema. El uso de buenas representaciónes de los estados y de heurísticas informadas resultan cruciales para escalar en este espacio de búsqueda. En esta tesis se presentan traducciones para planificación con información incompleta, que transforman el problema de búsqueda en el espacio de estados de creencia, en búsqueda en espacio de estados, donde cada nodo representa un estado de creencia. Hemos desarrollado herramientas para la generación de planes para el problema traducido, ya sea con percepción parcial o nula. A su vez, demostramos formalmente bajo qué circunstancias las traducciones son polinómicas, completas y correctas. La evaluación empírica remarca el valor de dichas traducciones