[Back]


Doctor's Theses (authored and supervised):

A. Polleres:
"Advances in Answer Set Planning";
Supervisor, Reviewer: T. Eiter, G. Gottlob; Institut für Informationssysteme, 2003.



English abstract:
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 shown, this monitoring approach is not restricted to our particular formalism.

German abstract:
Seit den Anfaengen der Forschung im Bereich der Kuenstlichen Intelligenz ist Automatisches Planen ein wichtiger Forschungsgegenstand. Als das "klassische Planungsproblem" bezeichnet man hier das Auffinden einer Folge vordefinierter Aktionen um von einem gegebenen Anfangszustand in einen gewuenschten Zielzustand zu gelangen. Neben der Suche nach konkreten Algorithmen zur Loesung solcher Planungsprobleme spielen auch formale Sprachen zur Beschreibung von Aktionen und Planungsdomaenen eine ganz wesentliche Rolle. Flexible Aktionsbeschreibungssprachen aus dem Bereich der Wissensrepraesentation erweisen sich als nuetzlich, sobald es darum geht, nicht-klassisches Planen unter unvollstaendigem Wissen zu modellieren. Allerdings bringt die hohe Ausdrucksstaerke dieser Aktionsbeschreibungssprachen auch eine hohe Komplexitaet bei der Berechnung von Plaenen mit sich. Hier bieten sich deklarative Problemloesungsmethoden an, beispielsweise Methoden der deklarativen logischen Programmierung. Die vorliegende Dissertation geht auf diese Problemstellungen in mehrerlei Hinsicht ein. Zu Beginn wird die deklarative Planungssprache Kc eingefuehrt, die auf bestehenden Aktionsbeschreibungssprachen basiert und diese um Konzepte aus dem Bereich der deklarativen Logikprogrammierung erweitert. Nach der Definition der Syntax von Kc werden verschiedene Semantiken fuer das Planen unter unvollstaendigem Wissen eingefuehrt: optimistische Plaene sind Aktionsfolgen, die den Zielzustand nur moeglicherweise erreichen, waehrend sichere Plaene das Erreichen des Zielzustandes unter allen Umstaenden garantieren. Weiters wird auf die Erweiterung dieser beiden Semantiken um Aktionskosten eingegangen. Hier spielt einerseits die Berechnung von kosten-optimalen sowie Plaene, die bestimmte Kostenlimits einhalten, eine Rolle. Bei der Untersuchung dieser Aspekte wird besonders auf die theoretische Analyse der beschriebenen Semantiken der Sprache Kc Wert gelegt. Anschliessend wird die Uebersetzung von Planungsproblemen in disjunktive logische Programme beschrieben, welche unter der sogenannten Answer Set Semantik (Antwort-Mengen Semantik) ausgewertet werden koennen. Zunaechst wird auf allgemeine Methoden zur Problemloesung mit Hilfe des "guess and check" Paradigmas der Answer Set Programmierung eingegangen. Dabei wird ein Programm in zwei Komponenten eingeteilt, wobei die eine Loesungen raet (guess), und die andere diese Loesungen verifiziert (check). Eine neu entwickelte Methode zur Generierung von integrierten Answer Set Programmen aus separaten "guess" und "check" Teilen wird vorgestellt, die zur Loesung komplexer Planungsprobleme, wie beispielsweise der Berechnung sicherer Plaene verwendet werden kann. Anhand der beschriebenen, theoretischen Methoden wurde basierend auf dem am Institut entwickelten Answer Set Programmierungssystem DLV ein Planungssystem implementiert. Nach einer genauen Beschreibung des Systems DLVK wird naeher auf die experimentelle Evaluierung der vorgestellten Methoden eingegangen, wobei sich DLVK als durchaus konkurrenzfaehig gegenueber vergleichbaren Planungssystemen erweist. Ein weiterer Abschnitt der Arbeit widmet sich der Wissensrepraesentation in der Sprache Kc. Dabei wird die Modellierung von Planungsproblemen in Kc anhand zahlreicher Beispiele erlaeutert. Abschliessend wird ein praktisches Anwendungsszenario zur Verwendung von Planungsmethoden im Bereich der Ueberwachung und des Designs von Multi-Agenten-Systemen behandelt.

Created from the Publication Database of the Vienna University of Technology.