Declarative Logic-Programming Components for Information Agents

Dissertation / Doktorarbeit von Michael Fink

Abstract:

At present, the World Wide Web faces several problems regarding the search for specific in formation, arising, on the one hand, from the vast number of information sources available, and, on the other hand, from their intrinsic heterogeneity. A promising approach for solving the complex problems emerging in this context is the use of information agents in a multi-agent environment, which cooperatively solve advanced information-retrieval problems. An intelligent information agent provides advanced capabilities resorting to some form of logical reasoning, based on ad-hoc-knowledge about the task in question and on background knowledge of the domain, suitably represented in a knowledge base.

In this thesis, our interest is in the role which some methods from the field of declarative logic programming can play in the realization of reasoning capabilities for intelligent information agents. We consider the task of updating extended logic programs (ELPs), since, in order to ensure adaptivity, an agent’s knowledge base is subject to change. To this end, we develop update agents, which follow a declarative update policy and a reimplemented in the IMPACT agent environment. The proposed update agents adhere to a clear semantics and are able to deal with incomplete or in consistent information in an appropriate way.

Furthermore, we introduce a framework for reasoning about evolving knowledgebases, which are represented as ELPs and maintained by an update policy. We describe a formal model which captures various update approaches, and define a logical language for expressing properties of evolving knowledge bases. We further investigate these mantical properties of knowledge states with respect to reasoning. In particular, we describe finitary characterizations of the knowledge evolution, and derive complexity results for our framework.

Finally, we consider aparticular problem of information agents, namely information source selection, and develop an intelligent site-selection agent. We use ELPs for representing relevant knowledge and for declarative query an alysis and query abstraction. We define syntax and semantics of declarative site-selection programs, making use of advanced methods from answer set programming for priority handling and quantitative reasoning. A site selection component is implemented on top of the DLVKR system and its plp front-end for prioritized ELPs. We report experimental results for this implementation, obtained using a representative example from a movie domain.

Zusammenfassung:

Die Suche nach spezifischer Information im Internet steht zur Zeit einer Reihe von Problemen gegenüber, die sich einerseits auf die große Anzahl verfügbarer Informationsquellen und andererseits auf deren immanente Heterogenität zurückführen lassen. Ein vielversprechender Ansatz zur Lösung der komplexen Probleme, die in diesem Zusammenhang auftreten, ist der Einsatz von Informationsagenten in Multi-Agenten Systemen, in denen mehrere Informationsagenten kooperieren, um gemeinsam schwierige Aufgaben der Informationsbeschaffung zu lösen. Ein intelligenter Informationsagent entwickelt dabei besondere Fähigkeiten, indem er logisches Schließen auf eine Wissensbasis anwendet, die auf formalem Wissen über die jeweilige Aufgabe und auf Hintergrundwissen über den Problembereich basiert. In dieser Dissertation wird untersucht, welche Rolle Methoden der deklarativen logischen Programmierung in der Entwicklung von Komponenten für intelligente Informationsagenten spielen können. Es wird zunächst das Problem betrachtet, eine Wissensbasis, die durch sogenannte Erweiterte Logische Programme (ELPs) repräsentiert ist, entsprechend zu aktualisieren. Dies ist deshalb von besonderer Bedeutung, da von einem intelligenten Informationsagenten erwartet wird, dass er sich an Änderungen seines Umfeldes entsprechend anpasst. Es werden sogenannte „Update Agents“ entwickelt und als IMPACT-Agenten implementiert, die diese Aufgabe lösen, indem sie einer deklarativen Strategie folgen. Die vorgeschlagenen Agenten zeichnen sich durch ihre klar definierte Semantik aus und sind darüberhinaus in der Lage, mit unvollständiger sowie inkonsistenter Information umzugehen.

Desweiteren wird ein theoretisches System eingeführt, welches das logische Schließen über dynamische Wissensbasen ermöglicht, welche als ELPs repräsentiert sind und anhand einer deklarativen Strategie aktualisiert werden. In diesem formalen Modell lassen sich verschiedenste Update-Ansätze und Methoden ausdrücken. Eine eigens definierte logische Sprache ermöglicht es, Eigenschaften derartiger Wissensbasen formal auszudrücken und durch formales Schließen zu verifizieren. Da letzteres aber rechnergestützt nur möglich ist, wenn die „Evolution“ der Wissensbasis durch eine endliche Anzahl verschiedener Zustände beschreibbar ist, werden endliche Charakterisierungen herausgearbeitet und zur Untersuchung der computationalen Komplexität des Systems herangezogen.

Zuletzt widmen wir uns einer konkreten Aufgabe von Informationsagenten, nämlich der Auswahl geeigneter Informationsquellen, und entwickeln dafür einen intelligenten „Site-Selection Agent“. Dabei werden ELPs nicht nur zur Repräsentation relevanten Wissens verwendet, sondern auch um Anfragen deklarativ zu analysieren und eine abstrakte Repräsentation einer Anfrage zu berechnen. Syntax und Semantik deklarativer „Site-Selection Programme“ werden definiert, indem auf fortgeschrittene Methoden der Answer-Set Programmierung zurückgegriffen wird, die der Behandlung von Prioritäten und dem quantitativen Schließen dienen. Unter Zuhilfenahme des Wissensverarbeitungs-Systems DLV und dessen Front-end PLP für ELPs mit Prioritäten wird eine „Site-Selection“ Komponente für intelligente Informationsagenten implementiert. Experimentelle Ergebnisse werden anhand einer repräsentativen Beispielanwendung aus dem Kinofilmbereich gewonnen und analysiert.

Table of Contents: