ID 6252
Fink, Michael: Declarative Logic-Programming Components for Information Agents
Hamburg: Diplomica GmbH, 2002
Zugl.: Wien, Technische Universität, Dissertation / Doktorarbeit, 2002
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
Diplomica GmbH
http://www.diplom.de, Hamburg 2002
Printed in Germany
Abstract
At present, the World Wide Web faces several problems regarding the search for specific infor-
mation, 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 up-
date agents, which follow a declarative update policy and are implemented in the IMPACT agent
environment. The proposed update agents adhere to a clear semantics and are able to deal with
incomplete or inconsistent information in an appropriate way.
Furthermore, we introduce a framework for reasoning about evolving knowledge bases, 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 the semantical 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 a particular problem of information agents, namely information source se-
lection, and develop an intelligent site-selection agent. We use ELPs for representing relevant
knowledge and for declarative query analysis and query abstraction. We define syntax and se-
mantics 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
DLV
KR system and its
plp
front-end for prioritized ELPs. We re-
port experimental results for this implementation, obtained using a representative example from
a movie domain.
Kurzfassung
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 ande-
rerseits 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 koope-
rieren, um gemeinsam schwierige Aufgaben der Informationsbeschaffung zu lösen. Ein intelli-
genter 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 Pro-
grammierung in der Entwicklung von Komponenten für intelligente Informationsagenten spie-
len 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, daß er sich an Änderungen seines Umfeldes entsprechend anpaßt. 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 dy-
namische Wissensbasen ermöglicht, welche als ELPs repräsentiert sind und anhand einer de-
klarativen 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 Wis-
sensbasis 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 be-
rechnen. Syntax und Semantik deklarativer ,,Site-Selection Programme" werden definiert, indem
vi
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. Experi-
mentelle Ergebnisse werden anhand einer repräsentativen Beispielanwendung aus dem Kino-
filmbereich gewonnen und analysiert.
Acknowledgements
I am grateful to a number of people who contributed to this thesis in various ways. First of all,
I owe a great debt to my supervisors Thomas Eiter and Hans Tompits. Even from abroad they
always had an ear for (and, of course, answers to) my questions ranging from technical problems
to presentational matters. I am much obliged to Thomas Eiter for giving me the opportunity to
work within the Knowledge-based Systems Group at the Vienna University of Technology and a
special thanks to Hans Tompits for making me aware of this position.
I would also like to thank Piero Bonatti, Marco Cadoli, Jürgen Dix, Thomas Lukasiewicz, and
V.S. Subrahmanian (in alphabetical order) for deepening my interests in logic programming and
nonmonotonic reasoning in outstanding lectures and fruitful scientific discussions.
I want to acknowledge T.J. Rogers for disclosing the secrets of the IMPACT agent development
environment for me. I also benefitted a lot from work by Torsten Schaub and his student Sven
Thiele, who extended the
plp
front-end for our needs, and Wolfgang Faber was a great aid in all
questions concerning
DLV
. Many thanks at this point to Roman Schindlauer for his collaboration
regarding implementation tasks.
Giuliana Sabbatini completed our project team and I really enjoyed the time being room-fellows.
Special thanks to her and all members of our department for the warm and amicable working
atmosphere. Moreover, I want to express my gratitude to our secretary, Elfriede Nedoma, and
our technician, Matthias Schlögel, who have been a constant source of assistance.
Last, but never least, I want to thank my family, my close friends, and my beloved Bettina. They
encouraged me, tolerated my moods, and cared for distraction in bad times and during the "hot
stage" in the last weeks. With their love they make my life a pleasure.
This thesis was supported by the Austrian Science Fund (FWF) under grants P13871-INF and
P14781-INF.
Contents
Abstract
iii
Abstract in German
v
Acknowledgements
vii
Contents
ix
List of Figures
xiii
List of Tables
xv
1
Introduction
1
1.1
Intelligent Information Agents . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1.1
Problems and challenges . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.2
Systems and frameworks . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2
Declarative Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3
Outline
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2
Preliminaries
11
2.1
Declarative Logic Programming . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.1.1
Syntax
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.1.2
Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.1.3
First-order programs . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.1.4
Belief set and epistemic state . . . . . . . . . . . . . . . . . . . . . . . .
13
2.1.5
Computational complexity . . . . . . . . . . . . . . . . . . . . . . . . .
14
x
Contents
2.2
IMPACT
Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.2.1
Agent data structures . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.2.2
Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.2.3
Agent programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.2.4
Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3
Update Agents
19
3.1
Updating Logic Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.1.1
Update programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.1.2
Basic definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.1.3
Properties and characterizations . . . . . . . . . . . . . . . . . . . . . .
22
3.1.4
Minimal and strictly minimal answer sets . . . . . . . . . . . . . . . . .
23
3.2
Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.2.1
First-order programs . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.2.2
Minimal answer sets . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.2.3
Strictly minimal answer sets . . . . . . . . . . . . . . . . . . . . . . . .
30
3.2.4
Applying the system . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.3
Specifying Update Policies with EPI . . . . . . . . . . . . . . . . . . . . . . . .
33
3.3.1
The EPI framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
3.3.2
EPI syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3.3.3
EPI semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
3.3.4
EPI complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.4
Implementation of EPI: Update Agents . . . . . . . . . . . . . . . . . . . . . . .
41
3.4.1
Software package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
3.4.2
Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
3.4.3
Update policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
3.4.4
Beyond EPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
3.5
Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
Contents
xi
4
Reasoning about Evolution
49
4.1
Knowledge-Base Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.1.1
Evolution frame
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.1.2
Compilation and belief set . . . . . . . . . . . . . . . . . . . . . . . . .
52
4.1.3
Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
4.2
Capturing Frameworks for Knowledge Evolution . . . . . . . . . . . . . . . . .
56
4.2.1
Update Programs and EPI . . . . . . . . . . . . . . . . . . . . . . . . .
57
4.2.2
Dynamic Logic Programs, LUPS, and LUPS
. . . . . . . . . . . . . . .
58
4.2.3
Revision Programming . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
4.2.4
Abductive Theory Updates . . . . . . . . . . . . . . . . . . . . . . . . .
61
4.2.5
Program Updates by means of PLPs . . . . . . . . . . . . . . . . . . . .
62
4.2.6
Further approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
4.3
Reasoning About Knowledge-Base Evolution . . . . . . . . . . . . . . . . . . .
63
4.3.1
EKBL
syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
4.3.2
EKBL
semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
4.4
Knowledge-State Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
4.4.1
Local belief operators
. . . . . . . . . . . . . . . . . . . . . . . . . . .
68
4.4.2
Contracting belief operators . . . . . . . . . . . . . . . . . . . . . . . .
73
4.4.3
Canonical evolution frames
. . . . . . . . . . . . . . . . . . . . . . . .
74
4.5
Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
4.5.1
Complexity of state equivalence . . . . . . . . . . . . . . . . . . . . . .
86
4.6
Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
5
Site Selection Agents
93
5.1
System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
5.1.1
Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
5.1.2
Site selection capability
. . . . . . . . . . . . . . . . . . . . . . . . . .
95
5.2
Preferred Logic Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
5.3
Query Representation and Abstraction . . . . . . . . . . . . . . . . . . . . . . .
98
5.3.1
Low-level representation . . . . . . . . . . . . . . . . . . . . . . . . . .
98
5.3.2
High-level predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
xii
Contents
5.3.3
Query abstraction program . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.4
Site Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.5
Site Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.5.1
Syntax
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.5.2
Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.5.3
Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.6
Implementation and Application . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.6.1
Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.6.2
Application: Movie databases . . . . . . . . . . . . . . . . . . . . . . . 116
5.7
Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.7.1
Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.7.2
Results with modified selection bases . . . . . . . . . . . . . . . . . . . 124
5.8
Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
6
Conclusion
129
6.1
Outlook and Open Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
Bibliography
133
A Site Selection Resources
145
A.1 XML DTD for the Movie Databases . . . . . . . . . . . . . . . . . . . . . . . . 145
A.2 Low-level Query-Representation Examples . . . . . . . . . . . . . . . . . . . . 146
A.3 High-level Query-Description Examples . . . . . . . . . . . . . . . . . . . . . . 148
A.4 Experimental Site Description Program . . . . . . . . . . . . . . . . . . . . . . 149
A.5 Experimental Site-Selection Program . . . . . . . . . . . . . . . . . . . . . . . . 153
List of Figures
2.1
IMPACT
agent architecture. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.1
Algorithm to calculate minimal update answer sets. . . . . . . . . . . . . . . . .
29
3.2
From knowledge state to belief set at Step i. . . . . . . . . . . . . . . . . . . . .
35
5.1
Architecture of the site selection system. . . . . . . . . . . . . . . . . . . . . . .
95
5.2
Using a selection base
S =
qd
,
sd
,
dom
,
sel
, <
u
for site selection. . . . .
96
List of Tables
3.1
Syntax of an update statement in EPI. . . . . . . . . . . . . . . . . . . . . . . .
37
3.2
Complexity results for EPI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.1
Complexity results for regular and strongly regular evolution frames. . . . . . . .
87
5.1
Experimental results for original selection base. . . . . . . . . . . . . . . . . . . 123
5.2
Experimental results for "extended" selection base. . . . . . . . . . . . . . . . . 125
5.3
Experimental results for "reduced" selection base. . . . . . . . . . . . . . . . . . 126
1 Introduction
In the past decade, with the World Wide Web entering our daily life, a wealth of information has
become available to a large group of users. The Internet hype was carried by a wave of optimism
and expectations in the radically new forms of communication, information dissemination, and
information retrieval the new technology provided. To date, it seems that while the Web is still
highly appreciated for communicating and publishing, when searching the Web for information,
users are often dissatisfied with the means for searching and the results obtained.
A user faces several problems when looking for desired information on the Web, which arise from
the vast amount of available information sources and from their heterogeneity, since standards
are missing. First of all, the user has to identify the relevant sources which should be queried,
since bounds on resources, time, and/or cost of services usually do not permit to query all sources
which are available. The generation of a query plan is often quite expensive and cannot be optimal
when the user has no additional information about the knowledge contained in each source, but
merely a short description of it. Then, once the user has made up his or her plan, for each source
the query must be formulated in the appropriate way, depending on the interfaces available, as
well as on the data organization and presentation. Furthermore, the user must possibly adapt
the query more than once for each source in order to get the desired information, and must
learn several different query approaches. Furthermore, it may happen that some sources provide
as a result only partial or incomplete information to a query. The user has then to merge all
data retrieved, taking into account that the information provided by different sources may be
inconsistent. In such a situation, the user needs some notion of reliability for the sources in order
to choose the proper information.
There is need for a suitable information processing infrastructure relieving the user from these
tedious tasks. A promising approach for solving the complex problem is the use of a multi-agent
system for accessing several heterogeneous information sources. The user is presented a uniform
interface for accessing all available services and information sources, without having to bother
with the heterogeneity underneath. It is the system as a whole which takes care of searching the
appropriate sources, accessing them, and returning to the user the required information, and this
to an extent as complete and consistent as possible.
The realization of such systems requests for special functionalities and capabilities, which emerge
from specialized tasks like search and assessment of information sources, query planning, and
information merging and fusion, thereby dealing with incomplete information and inconsisten-
cies. Such capabilities are provided as services on request by various kinds of information agents,
2
1 Introduction
which usually form a society of agents for cooperatively solving complex information-retrieval
problems. It is not hard to imagine that an advanced approach to any of these problems must
involve, in some form, logical reasoning tasks, based on ad hoc knowledge about the task in
question and on background knowledge of the domain, suitably represented in a knowledge base.
It is the goal of this thesis to investigate how methods from declarative logic programming can
be employed to allow information agents to solve some of their tasks more "intelligently".
1.1
Intelligent Information Agents
In this thesis, we focus on information agents (sometimes also called middle agents [46]), a
special kind of so-called software agents (see [122], for an extensive overview of software agent
programming approaches). The term information agent is broadly used in the literature and
several types of information agents, as well as facilities for their cooperation, have been suggested
and implemented. Following [76], they can be classified as follows:
Facilitators: Agents which take control over a set of subordinated agents and coordinate the
services they offer and the use of the resources they require.
Brokers: Agents often used for matching between a set of different data sources and user re-
quests. Brokers receive requests, look for relevant sources matching them, and then per-
form actions using services from other agents (combining them with their own resources
or information).
Mediators: In the mediator approach [131], meta-knowledge about a number of other agents
(sometimes called provider agents) is available to the mediator, which exploits it to create
higher-level services (not provided by the underlying agents) for user applications. These
new services result by the combination and merging of low-level services on the basis of
the comprehensive meta-information which the mediator has. In a sense, mediators may
be seen as enhanced, high-level brokers.
Yellow Pages: A yellow pages dictionary helps users and other agents in finding the right pro-
viders (other agents or information sources) for the kind of service they need, possibly
performing a match between advertised services, ontology of the domain in question and
service requests.
Blackboards: A blackboard serves as a temporal repository for service requests which remain
to be processed. Agents offering some service can access the blackboard and look for (and
retrieve from it) service requests which they can satisfy.
We are particularly interested in information agents acting as mediators. Thus, we assume that
the agent has knowledge about the application domain of interest, and some meta-knowledge
about the contents and features of the distributed, heterogeneous information sources the system
has access to.
1.1 Intelligent Information Agents
3
In order to satisfy a user request, an information agent may have to solve various subgoals,
such as identifying and possibly ranking relevant information sources; retrieving the required
information (or ask some appropriate provider agent for it); processing the information returned
by the sources by combining, merging, and integrating them; optimizing the number of accessed
sources, or the total cost and time required for the search, or the precision and completeness of
the results.
For fulfilling these tasks, an agent has to make decisions about what to do or how to proceed at
certain points. An intelligent information agent takes its decisions by reasoning using the knowl-
edge that it possesses about the application and the particular request to be answered. Rather than
having decision mechanisms implicitly hard-coded into the agent's program, we assume that the
agent's decision making facilities are modularized and attached to it as reasoning components.
The latter can be realized in many ways, by using one of the numerous approaches that have been
developed in the agent and AI literature.
1.1.1
Problems and challenges
Intelligent information agents are supposed to provide advanced capabilities which help in im-
proving the quality of query results. It is these capabilites that might be realized as, or supported
by, reasoning components. We list some of these capabilities below, without claiming that the
list is exhaustive:
· Decompose a request in its "atomic" parts on the basis of available knowledge about
the information sources, and reformulate it according to the corresponding data structure.
The decomposition task can be of varying complexity and can generate a set of possible
decompositions, based on the information about the underlying sources and the domain of
interest [102, 103, 104, 37, 91, 23, 24, 26, 17, 18, 82, 83, 120, 6, 7, 8, 9].
· Integrate the query with additional user information, if available. This could require
asking first a profiling agent for the user profile, habits, rights and interests.
· Select the information sources to be queried, using the meta-knowledge about them and
about the application domain to determine which of the sources contain relevant data to
answer the query [102, 103, 104, 37, 91, 23, 24, 26, 8, 9, 17, 18, 82, 83, 120]. If possible,
determine further preferred information sources to be queried.
· Create a query plan. Determine in which order sub-queries are to be performed [102, 103,
104, 17, 18], on the basis of query decomposition, of the data available in every source,
and of preference over sources, in order to optimize the execution.
· Execute the plan, asking the corresponding provider agents for the required services and
waiting for their answers, possibly adapting the query plan dynamically to run-time infor-
mation and to the answers obtained so far [102, 103, 17, 18, 98].
· Compose and merge the answers. This task can have varying complexity, from simply
collecting all the answers and passing them to the interface agent without processing them,
4
1 Introduction
to organizing the retrieved data in some form (e.g., eliminating multiple instances of the
same information), to merging them in a single comprehensive answer, and so on [37, 91,
23, 24, 8, 9, 82, 83, 120].
· Detect and possibly remove inconsistencies among retrieved data [37, 91, 8, 9] on the
basis of an inconsistency removal strategy and of meta-knowledge about the sources, or
meta-knowledge contained in the answers themselves.
· Integrate incomplete information by means of internal reasoning capabilities [82, 83,
120].
· Start a learning procedure in order to improve or update internal models and reasoning
rules [17, 18], perhaps providing input to the profiling agent as well.
1.1.2
Systems and frameworks
Some of the tasks for intelligent information agents identified above have already been widely
addressed and some feasible solutions have been developed. Following the grouping suggested
in [105], existing intelligent Web systems have their main focus in some of the following fields:
User modeling and profiling: addressing the issue of deploying adaptive user interfaces and
recommendation systems, integrating user queries on the basis of the user profile or directly
suggesting the user items of interest.
Analysis and preprocessing of information sources: building up, on the basis of an applica-
tion domain description, the meta-knowledge on which reasoning and decision making is
based.
Information integration and information management: covering a wide area of applications
and different problems.
Especially in the field of information integration a large number of systems and frameworks
has been developed, e.g., the Information Manifold [102, 103, 104], Carnot [91, 37], InfoS-
leuth [23, 24, 26], HERMES [8, 9, 10, 127], IMPACT [128, 19, 69, 70], SIMS [17, 18], or
TSIMMIS
[82, 83, 120] (for an overview of these systems cf. [64]). They are highly relevant,
since the kind of problems tackled by them and suggestions for solutions are of interest in the
whole field of heterogeneous information integration. However, many of these systems use ad
hoc procedural techniques, rather than declarative methods especially declarative logic pro-
gramming methods in which we are interested in. For a comprehensive overview of existing
systems in the field of information integration and of the role of computational logic in some of
them, we refer to [52]; for hints and relevant literature on user modeling and preprocessing of
information sources, see [105].
1.2 Declarative Methods
5
1.2
Declarative Methods
By declarative methods, as opposed to procedural methods, we mean methods that allow us to
specify a problem in a formal language and to use an inference mechanism in order to solve
it, instead of operationally constructing, i.e., "programming", the solution of the problem. In
particular, by declarative logic programming we mean logic programming techniques, where the
ordering of rules, as well as the ordering of atoms or literals in their bodies, have no influence on
the inference procedure and thus on the models obtained (e.g., answer set programming [118] as
opposed to Prolog).
Our motivation to employ declarative methods and in particular answer set programming tech-
niques for developing reasoning components for information agents is driven by the following
advantages:
· They provide a clear formal semantics to the reasoning component.
· Changes in the specification are easily incorporated by modifying or adding suitable rules
or constraints, without the need for re-designing the entire component, as might be the
case, e.g., in procedural languages.
· Answer set programming is capable of handling incomplete information and performing
nonmonotonic inferences, which, arguably, is an inherent feature of the problem domain.
· Finally, the declarative nature of the answer set semantics formalism permits the coupling
with other logic-based components, e.g., sophisticated ontology tools and their reasoning
engines, which may be employed in order to providing advanced features.
In search for feasible or improved solutions to the challenges and problems of intelligent infor-
mation agents, given in Section 1.1.1, some central reasoning sub-tasks can be identified, which
the agent itself must have or be able to access in form of reasoning components. For some of
these reasoning tasks, listed below, declarative methods seem to be promising.
· Priority handling. Dealing with priority in the logic programming context has received
considerable attention, see, e.g., [86, 30, 93, 77, 47, 29, 32, 31, 14]. Priority information
needs to be encoded in the knowledge base of the agent, possibly explicitly in the object
language in which the knowledge itself is expressed. The preference relation may be static
or dynamic, in the latter case reasoning procedures have to account for possible changes.
· Revision and update. The knowledge base of the agent can be subject to change on the ba-
sis of information from the environment (the application domain itself, other agents inside
or outside the system, etc.), in order to incorporate changes in the outside world or changes
in the knowledge about it [29, 111, 101, 92, 123, 94, 78, 79, 11, 12, 13, 14, 15]. The epis-
temic state and the intended belief set of the agent have thus to be continuously revised,
depending on some specified update policy, which could be in turn explicitly described in
the knowledge base and maybe dynamically updated too.
6
1 Introduction
· Inconsistency removal. The agent should in the presence of conflicts in the knowledge
base be able to detect them and to find an acceptable fall-back knowledge configuration, in
order to ensure that the decision making process is not stopped or inconsistent as a whole.
The fall-back configuration is usually required to preserve "as much as possible" of the
available knowledge.
· Decision making with incomplete information. Under the manifestation of incomplete
information, some reasoning and deduction capabilities may provide candidate hypotheses
for the missing information pieces, in order to ensure that the process of decision making
can derive plausible results.
· Temporal reasoning. The evolution of a dynamic knowledge base could be subject to
specifications [15], and corresponding forms of reasoning about this evolution could be
provided for ensuring that the agent's behavior is appropriate, e.g., that some undesired
status cannot be reached [71, 43].
· Learning. Based on the history of the agent (sequence of changes in its knowledge base,
or sequence of observations), some form of inductive learning could be implemented [123,
94, 50].
A number of different models and methods for knowledge representation and reasoning have been
developed in the past, which may be used for this purpose, e.g., description logics, abduction,
induction, and argumentation (cf. [122] for a broad overview and references). However, the focus
of this thesis is on the role which some methods from the field of declarative logic programming
can play in the realization of reasoning components for information agents. In particular, we
are interested to see how they can be used, extended, and further developed for the needs of this
domain of application. For an overview of methods from declarative logic programming aimed
at the above reasoning tasks the reader is referred to [64]
1.3
Outline
The main problems addressed in this thesis are the following. First, we consider the task of
updating logic programs. Since an information agent is situated in an environment which is
subject to change, it is required to adapt over time, and to adjust its decision making. For agents
utilizing logic programming techniques for representing (parts of) their knowledge, this requires
the agent to be able to update logic programs accordingly, in order to ensure adaptivity. Several
approaches for updating nonmonotonic logic programs, have been proposed, cf. [11, 12, 55,
56, 121, 79, 94, 101]. Towards a reasoning component for updating the knowledge base of an
information agent using extended logic programs for knowledge representation, we choose one
of the approaches, viz. update answer set semantics [55, 56, 121], develop algorithms for its
implementation, and realize a tool for application.
Besides an underlying update semantics, which specifies how new, possibly inconsistent infor-
mation is to be incorporated into the knowledge base, an agent needs to have a certain update
1.3 Outline
7
policy, i.e., a specification of how to react upon the arrival of an update. The issue of how to
specify change requests for knowledge bases has received growing attention more recently and
suitable specification languages for nonmonotonic logic programs have been developed [15, 99,
100, 16, 57, 121, 62, 60]. We choose an approach, the language EPI [57, 121, 62, 60], which
is not only independent of the underlying update semantics, but can also be "agentized" in the
IMPACT
[128, 19, 69, 70] agent architecture in a straightforward way. By this means, we build
so-called update agents by "plugging-in" the implementation of update answer set semantics,
developed before.
Second, we address the task of temporal reasoning. Every intelligent agent is supposed to be able
to reason about future states, e.g., consequences of its behavior. While the update component
outlined above, enables an information agent, built on declarative logic programming techniques,
to query its knowledge state after a number of updates have occurred, it does not enable the agent
to answer queries such as whether a particular fact will be true in all possible future knowledge
states. Analogous issues, called maintenance and avoidance, have been recently studied in the
agent community [133]. However, reasoning about an evolving knowledge base, maintained
using an update policy, has not yet been formally addressed. Thus, we aim at a framework for
expressing reasoning problems over such evolving knowledge bases, where we generalize from
the update policy and of course of the update semantics used. Within the framework, it
shall be possible to capture different approaches of incorporating updates into logic programs,
still paying attention to the specific nature of the problem. Furthermore, it should be possible to
evaluate a formula, which specifies a desired evolution behavior, across different realizations of
update policies based on different grounds.
Third, we consider a particular problem of information agents, namely information source se-
lection, and develop an intelligent site selection agent building on declarative methods. Given a
query by the user and a collection of information sources, the agent's task is to select a source for
answering the query such that the utility of the answer, in terms of quality of the result and other
criteria, like, e.g., costs, is as large as possible for the user. An intelligent solution to this problem
needs to combine several aspects, such as basic properties of the information sources, knowledge
about their contents, and knowledge about the particular application domain. To this end, our site
selection component will incorporate advanced methods from declarative logic programming for
priority handling [30, 49, 95] and quantitative reasoning [34].
Main results. The main contributions of this thesis can be summarized as follows:
(1) We develop algorithms that allow for update answer set semantics to be implemented by
the use of existing logic programming systems as an underlying reasoning engine. Based on
these algorithms, we develop a tool, called
upd
, which is conceived as a front-end to the state-
of-the-art solver
DLV
[68, 54]. The implementation allows for different modes of reasoning and
handles also refinements of the semantics involving certain minimality-of-change criteria.
(2) We develop update agents, which deploy the update front-end as their basic reasoning
component and follow a declarative update policy. To this end, we implement the EPI framework
for update specification by developing appropriate software packages for the IMPACT agent
8
1 Introduction
platform. The implementation is generic in the sense that it allows for other implementations
of update semantics for logic programs to be plugged in. Furthermore, agents can make use of
additional features of IMPACT, e.g., enriching the policy language with deontic modalities.
(3) We introduce a generic formal model in which various approaches for updating extended
logic programs can be expressed. In particular, we introduce the concept of an evolution frame,
whose components serve to describe the evolution of knowledge states. Based on evolution
frames, we define the syntax and the semantics of a logical language for reasoning about evolving
knowledge bases, such that properties of an evolving knowledge base can be formally stated and
evaluated in a systematic fashion, rather than ad hoc.
(4) We investigate semantical properties of knowledge states for reasoning. In particular, since
in principle a knowledge base may evolve forever, we are concerned with finitary characteriza-
tions of evolution. To this end, we introduce various notions of equivalence between knowledge
states, and show several filtration results. As an application, we establish this for evolution frames
which model policies in the EPI framework for logic program updates using the answer set se-
mantics, as well as for LUPS and LUPS
policies [15, 16, 99] under the dynamic stable model
semantics [12].
(5) We derive complexity results for reasoning. Namely, we consider the problem of deciding
whether a given property, expressed by a formula in our logical language, holds for a given
knowledge state in a given evolution frame. While the problem is undecidable in general, we
single out several cases in which the problem is decidable, adopting some general assumptions
about the underlying evolution frame. In this way, we identify meaningful conditions under
which the problem ranges from PSPACE up to 2-EXPSPACE complexity. We again apply this to
the EPI framework, showing that its propositional fragment has PSPACE complexity.
(6) We develop a reasoning component for intelligent information source selection, using ex-
tended logic programs (ELPs) [85] to represent rich descriptions of the information sources, an
underlying domain theory, and queries in a formal language. We perform query analysis by ELPs
and compute query abstractions. At the heart, a declarative site selection program represents
both qualitative and quantitative criteria (e.g., site preference and costs).
(7) We consider the interesting and, to our knowledge, novel issue of contexts in logic pro-
grams. Structured data items require a careful definition of the selection semantics whilst in-
heritance-based approaches, such as [33], do not apply here. Furthermore, implicit priorities,
derived from context information, must be combined with explicit user preferences from the
selection policy, and arising conflicts must be resolved.
(8) We have implemented a site selection agent and performed experiments in an example
application from the movie domain. Our example application comprises several XML databases,
wrapped from movie databases available on the Web, and handles queries in XML-QL. Experi-
ments that we have conducted show that the system behaved intuitively on a number of natural
queries, some of which require reasoning from the background knowledge to identify the proper
selection.
1.3 Outline
9
The remainder of this thesis is organized as follows. In the next chapter we briefly introduce
extended logic programs, the basic formalism used for knowledge representation throughout this
thesis, and the IMPACT agent architecture, which represents the platform underlying our agent
implementations. Chapter 3 is devoted to update agents. There, we first introduce update answer
set semantics for updating extended logic programs, and then we address its implementation. In
the second part of the chapter, the EPI framework for update specifications is outlined leading
to the realization of update agents. In Chapter 4, we deal with reasoning about the evolution
of nonmonotonic knowledge bases. The formal definitions of an evolution frame and a formal
language for expressing properties of an evolving knowledge base serve as a starting point for
investigations on equivalence relations over knowledge states, which are useful in order to obtain
finite characterizations of the transition graph, and on the computational complexity of reasoning.
Site selection agents are the topic of Chapter 5. After giving an overview of the site selection
process and architecture, we formally define our approach to knowledge-based site selection,
before we turn to its implementation and application serving as a basis for the experimental results
reported. Finally, Chapter 6 concludes the thesis with a summary and some general remarks.
All original results contained in this thesis have been published as refereed papers in journals
and proceedings of international conferences. The update semantics and its implementation are
reported in Theory and Practice of Logic Programming [63] and appeared in preliminary form
in the proceedings of JELIA 2000 [55]. The
EPI
language and its agentization in IMPACT have
been presented at IJCAI 2001 [57] as well as at the AISB 2001 Symposium on Adaptive Agents
and Multi-Agent Systems [58]. Most results of Chapter 4 are contained, in preliminary form,
in the proceedings of LPAR 2001 [59], and the site-selection approach of Chapter 5 has been
presented at KR 2002 [61].
2 Preliminaries
2.1
Declarative Logic Programming
The key method for knowledge representation used throughout this thesis is declarative logic
programming. In particular, we deal with extended logic programs [85], i.e., sets of rules, built
over a set
A of (first-order) atoms where both default negation not (often also referred to as
weak negation and also called negation as failure) and strong negation
¬ (sometimes also called
classical negation) is available. Facts are represented by literals. A literal, L, is either an atom
A (a positive literal) or a strongly negated atom
¬A (a negative literal). For a literal L, the
complementary literal,
¬L, is ¬A if L = A, and A if L = ¬A, for some atom A. For a set
S of literals, we define
¬S = {¬L | L S}. We also denote by Lit
A
the set
A ¬A of all
literals over
A. A literal preceded by the default negation sign not is said to be a weakly negated
literal. In contrast to strong negation
¬L, expressing the fact that L is false, the intuition of weak
negation is, that not L is true if we cannot assert that L is true, i.e., if either L is false or we do
not know whether L is true or false. We first consider the propositional case, i.e.,
A is a set of
propositional atoms, while first-order programs will be introduced in Section 2.1.3.
2.1.1
Syntax
A rule, r, has the form
L
0
L
1
, . . . , L
m
, not L
m+1
, . . . , not L
n
,
where L
i
, 0
i n, are literals. We call L
0
the head of r and B(r) =
{L
1
, . . . , L
m
, not L
m+1
,
. . . , not L
n
} the body of r. Furthermore, we will often use H(r) to denote the head of rule r. If
B(r) =
, we also allow the case where L
0
may be absent. We define B
+
(r) =
{L
1
, . . . , L
m
}
and B
-
(r) =
{L
m+1
, . . . , L
n
}. The elements of B
+
(r) are referred to as the prerequisites
of r. Intuitively, rule r means that we can conclude L
0
if (i) L
1
, . . . , L
m
are known and (ii)
L
m+1
, . . . , L
n
are not known. We employ the usual conventions for writing rules like L
0
B
1
B
2
or L
0
B
1
{L} as L
0
B
1
, B
2
and L
0
B
1
, L, respectively.
If r has an empty head, then r is a constraint; if H(r) =
{L
0
} and the body of r is empty, then
r is a fact. In the latter case, slightly abusing notation, r is often simply represented by its head
literal L
0
. If n = m (i.e., if r contains no default negation), then r is a basic rule.
12
2 Preliminaries
An extended logic program (ELP), P , is a (possibly infinite) set of rules. If all rules in P are
basic, then P is a basic program. We say that P is an extended logic program over
A if all
atoms occurring in the rules of P are in a certain specified set
A of atoms. Usually, A will
simply be understood as the set of all atoms occurring in P . We denote by
L
A
the set of all rules
constructible using the literals in Lit
A
.
Example 1 Consider a knowledge base KB represented as an ELP consisting of the following
rules:
KB
=
{r
1
: night ,
,
r
2
: tv _on
,
r
3
: watch_tv
tv_on,
r
4
: sleep
night, not tv_on }.
KB consists of two facts, r
1
and r
2
, capturing a situation where it is night and my TV is on. The
basic rule r
3
states that whenever my TV is on, then I am watching TV. Finally, rule r
4
specifies
to infer, by default, that I am asleep, whenever it is night and it cannot be concluded that my TV
is on.
P
A set of literals is consistent iff it does not contain a complementary pair A,
¬A of literals.
Consistent sets of literals are also referred to as interpretations.
A literal L is true in an interpretation I (symbolically I
|= L) iff L I, and false otherwise.
Given a rule r, the body B(r) of r is true in I iff (i) each L
B
+
(r) is true in I and (ii) each
L
B
-
(p) is false in I. In other words, B(r) is true in I iff B
+
(r)
I and B
-
(r)
I = . We
write I
|= B(r) to express that B(r) is true in I. Rule r is true in I iff H(r) is true in I whenever
B(r) is true in I. In particular, if r is a constraint, then r is true in I if B(r) is not true in I. The
fact that r is true in I will be denoted by I
|= r. Likewise, for a program P , I |= P means that
I
|= r for all r P . In this case, I is said to be a model of P .
2.1.2
Semantics
Since rules may include weak negation, they are more expressive than ordinary Horn clauses.
This is the intuitive reason why we cannot always assign a unique set of consequences to an ELP.
Another effect is that there exist several semantics of ELPs [53]. One of the most important is the
concept of an answer set [85], introduced below, which generalizes the concept of a stable model
for general logic programs [84] (i.e., programs not containing classical negation,
¬).
Let r be a rule. Then r
+
denotes the basic rule obtained from r by deleting all weakly negated
literals in the body of r, i.e., r
+
= H(r)
B
+
(r). Furthermore, we say that rule r is defeated
by a set of literals S if some literal in B
-
(r) is true in S, i.e., if B
-
(r)
S = . As well, each
literal in B
-
(r)
S is said to defeat r.
The reduct, P
S
, of a program P relative to a set S of literals is defined by
P
S
=
{r
+
| r and r is not defeated by S}.
2.1 Declarative Logic Programming
13
In other words, P
S
is obtained from P by (i) deleting any r
P which is defeated by S and
(ii) deleting each weakly negated literal occurring in the bodies of the remaining rules. An
interpretation I is an answer set of a program P iff it is a minimal model of P
I
, i.e., I
|= P
I
and
no model I of P
I
exists, such that I is a proper subset of I . Observe that any answer set of P
is a fortiori a model of P . The set of all generating rules of an answer set S from P is given by
GR(P, S) =
{r P | S |= B(r)}.
By
AS(P ) we denote the collection of all answer sets of P . If AS(P ) = , then P is said
to be satisfiable, otherwise P is inconsistent. The answer set semantics is due to Gelfond and
Lifschitz [85] and, thus, the reduct P
I
is often called the Gelfond-Lifschitz reduct.
Example 2 Reconsider the knowledge base KB of Example 1. Given the interpretation S =
{night, tv_on, watch_tv}, the reduct KB
S
consists of the rules r
1
, r
2
, and r
3
. It is easily verified
that S is a minimal model of KB
S
. Hence, S is an answer set of KB .
P
2.1.3
First-order programs
It is quite straightforward to extend the notion of answer sets to the case where variables may
occur in rules. This is done in the usual way by defining the semantics of programs with variables
in terms of the semantics of ground programs.
Let
A be some countable first-order alphabet without equality and let P be a set of predicate
symbols from
A. By a first-order program, P , over P we understand a set of rules with P being
the totality of predicate symbols occurring in the rules of P .
For a list X = X
1
, . . . , X
n
of variables, we write r(X) to indicate that rule r may contain
the variables X
1
, . . . , X
n
. Accordingly, instances of r(X) will be denoted by r(t), where t =
t
1
, . . . , t
n
is a list of terms and r(t) results from r(X) by uniformly replacing occurrences of X
i
by t
i
(1
i n). We retain our convention of denoting the head of rule r by H(r) and the body
of r by B(r).
The Herbrand universe of a program P consists of all terms constructible from the constants and
function symbols occurring in P . An instance r(t) of a rule r(X)
P is ground iff t is a list of
terms from the Herbrand universe of P . The ground instantiation, P
, of P consists of all ground
instances of the rules from P . As already mentioned above, the ground instantiation P
of the
first-order program P determines the answer sets of P . More specifically, the set
AS(P ) of all
answer sets of P is identified with the set
AS(P
), where the answer sets of ground programs
are defined as for the propositional case.
2.1.4
Belief set and epistemic state
If a logic program P is regarded as the epistemic state of an agent, then the given semantics can
be used for assigning a belief state to any epistemic state P in the following way.
Let I
Lit
A
be an interpretation. Define
Bel
A
(I) =
{r L
A
| I |= r}.
14
2 Preliminaries
Furthermore, for a set
I of interpretations, let Bel
A
(
I) =
i
I
Bel
A
(I).
Definition 1 For a logic program P , the belief state, Bel
A
(P ), of P is given by Bel
A
(P ) =
Bel
A
(
AS(P )), where AS(P ) is the collection of all answer sets of P .
We write P
|=
A
r if r
Bel
A
(P ). As well, for any program Q, we write P
|=
A
Q if P
|=
A
q
for all q
Q. Two programs, P
1
and P
2
, are equivalent (modulo the set
A), symbolically
P
1
A
P
2
, iff Bel
A
(P
1
) = Bel
A
(P
2
). Usually we will drop the subscript "
A " in Bel
A
(
·), |=
A
,
and
A
if no ambiguity can arise.
2.1.5
Computational complexity
We appeal to the basic concepts of complexity theory as they can be found in [115] ([97] is
also a good source for basic complexity classes; for a background on complexity results in logic
programming, cf. [124, 66, 45]; for complexity results of nonmonotonic logics in general see [89,
36]). Let us briefly recall the definitions of relevant complexity classes.
We consider complexity classes of the form TIME(f ) (deterministic time), NTIME(f ) (nonde-
terministic time), SPACE(f ) (deterministic space), and NSPACE(f ) (nondeterministic space),
where f : N
N, is a nondecreasing, polynomial-time computable function. The class
TIME(f (n)) contains all decision problems which are solvable by a deterministic Turing ma-
chine in at most f (n) steps, while NTIME(f (n)) contains all decision problems which are solv-
able by a nondeterministic Turing machine in time bounded by f (n). Similarly, SPACE(f (n))
contains all decision problems solvable by a deterministic Turing machine requiring at most space
f (n) and NSPACE(f (n)) contains all decision problems solvable by a nondeterministic Turing
machine using space bounded by f (n).
We define the class P, consisting of all decision problems which are solvable in polynomial
time using a deterministic Turing machine, as P =
k>0
TIME(n
k
). Correspondingly, the class
NP =
k>0
NTIME(n
k
) consists of all decision problems which are solvable in polynomial time
using a nondeterministic Turing machine. Moreover,
P
2
is the class of all decision problems
solvable by a nondeterministic Turing machine in polynomial time with access to an oracle for
problems in NP (
P
2
is also written as NP
NP
). Furthermore, coNP refers to the class of problems
whose complementary problems are in NP, and
P
2
contains the complements of the problems in
P
2
.
1
All the mentioned classes belong to the polynomial hierarchy: NP and coNP are at the first
level of the polynomial hierarchy, and
P
2
and
P
2
are the second level. As well, NP
P
2
and
coNP
P
2
. It is widely held that these inclusions are proper.
Moreover, PSPACE is the class of all decision problems which are solvable in polynomial space
using a deterministic Turing machine (i.e., PSPACE =
k>0
SPACE(n
k
)). Similarly, NPSPACE
is the class of all decision problems which are solvable in polynomial space using a nondetermin-
istic Turing machine (i.e., NPSPACE =
k>0
NSPACE(n
k
)). It is well known that NPSPACE =
1
Two decision problems, D
1
and D
2
, are complementary (or, D
1
and D
2
are complements of each other) if it
holds that I is a yes-instance of D
1
exactly if I is a no-instance of D
2
.
2.2 IMPACT Agents
15
PSPACE, as well as it holds that every decision problem in the polynomial hierarchy is solvable
in PSPACE. Furthermore,
EXPSPACE =
k>0
SPACE(2
n
k
) and 2-EXPSPACE =
k>0
SPACE(2
2
nk
),
are the classes of decision problems solvable in (single) exponential space, respectively double
exponential space, using a deterministic Turing machine. Similarly,
EXPTIME =
k>0
TIME(2
n
k
) and 2-EXPTIME =
k>0
TIME(2
2
nk
),
are the exponential time, respectively double exponential time, classes.
Finite, propositional extended logic programming resides at the first level of the polynomial
hierarchy [110, 45], i.e., determining whether an extended logic program P has an answer set is
NP-complete, and determining whether L
Bel(P ) for some literal L is coNP-complete.
2.2
IMPACT Agents
As an agent framework for implementations, the Interactive Maryland Platform for Agents Col-
laborating Together (IMPACT ) ([128, 19, 69, 70]) agent system has been chosen for the follow-
ing reasons: IMPACT is an agent framework which allows for existing legacy code and data
sources to be "agentized". Moreover, the behavior of an IMPACT agent, i.e., which actions it
takes upon a state change, is specified declaratively by a set of rules. The possibility to employ
existing implementations, together with the possibility of declarative agent specifications, makes
the utilization of the declarative logic-programming components developed in this thesis within
IMPACT
agents straightforward.
Figure 2.1 shows the overall architecture of an IMPACT agent. All IMPACT agents have the
same architecture, and hence the same components, but the contents of these components can be
different, leading to different behaviors and capabilities offered by different agents.
Basically, the behavior of the agent is driven by an action policy. Each agent possesses a message
box, which contains incoming and outgoing messages. On the basis of the content of the message
box and of queries to legacy data (performed by means of function calls which abstract both from
the structure of the underlying data and of the information sources), the actions to be performed
are selected under a declarative semantics. Constraints ensure security and integrity of data and
behavior. Actions may themselves be changes to available data, postings of messages to other
agents, and so on.
2.2.1
Agent data structures
Agents are built "on top" of some existing body of code. Thus, to every agent, a set of types
can be assigned, which contains all data types or data structures that the agent manipulates. As
16
2 Preliminaries
Legacy Data
Function Calls
Meta-Kn
Action Policy
Security
Action
Base
Constr.
Integrity
Action
Constr.
Messages
In
Messages
Out
AGENT
W
N
E
T
O
R
K
Figure 2.1: IMPACT agent architecture.
usual, each data type has an associated domain which is the space of objects of that type. The set
of data structures is manipulated by a set of functions that are callable by external programs via
code calls. Such functions constitute the application programmer interface (API) of the package
on top of which the agent is built. An agent includes a specification of all signatures of these
API function calls (i.e., types of the inputs to such function calls and types of the output of such
function calls).
Every code call
S : f(t
1
, . . . , t
n
), where t
1
, . . . , t
n
are terms, i.e., either values or variables, is
based on a body of software code,
S (a so-called software package). Such a code call says "exe-
cute function f as defined in package
S on the list of arguments". A code call can be evaluated
providing it is ground, i.e., all arguments t
i
must be values. Its output is a set of objects.
Code call atoms are expressions of the form in(t, cc) or notin(t, cc), where t is a term and cc
is a code call. A ground term t succeeds (i.e., has answer true) if t is in the set of values returned
by cc, otherwise it fails (i.e., has answer false). If t is a variable, then a code call atom returns
each value from the result of cc, i.e., its answer is the set of ground substitutions for t such that
the code call atom succeeds.
A code call condition is a conjunction of code call atoms and constraint atoms, which may
involve deconstruction operations. An example of a constraint atom is X > 25, where X is a
variable. A code call condition checks whether the stated condition is true. In general, constraint
atoms are of the form t
1
t
2
where
{=, =, <, , >, } and t
1
, t
2
are terms.
Each agent has access to a message box data structure, together with some API function calls to
access it.
At any given point in time, the actual set of objects in the data structures (and the message box)
managed by the agent constitutes the state of the agent. The set of ground code calls which are
true in it are identified as the state,
O, of the agent.
2.2 IMPACT Agents
17
2.2.2
Actions
The agent has a set of actions. For example, reading a message from the message box, executing a
request, updating the agent data structures, or even doing nothing is an action. Expressions (t),
where is an action and t is a list of terms, are action atoms. They represent the sets of (ground)
actions which result if all variables in t are instantiated by values. Only such actions may be
executed by an agent. Every action has a precondition, P re(), a set of effects that describe how
the agent state changes when the action is executed, and an execution script or method consisting
of a body of physical code that implements the action.
2.2.3
Agent programs
Each agent has a set of rules (action rules) called the agent program specifying the principles
under which the agent is operating. These rules specify, using deontic modalities, what the agent
may do, must do, may not do, etc. Expressions O(t), P(t), F(t), Do (t), and W(t),
where (t) is an action atom, are called action status atoms. These action status atoms are
respectively read as (t) is obligatory, (t) is permitted, (t) is forbidden, do (t), and the
obligation to do (t) is waived.
If A is an action status atom, then A and
¬A are called action status literals. An agent program
P is a finite set of rules of the form
A
& L
1
&
· · · & L
n
,
where A is an action status atom, is a code call condition, and L
1
, . . . , L
n
are action status
literals.
2.2.4
Semantics
Each agent program has a formal semantics which is defined in terms of semantical structures
called status sets, i.e., sets of ground action status atoms. More specifically, the semantics of
an agent is defined with respect to feasible status sets, which satisfy various conditions. First, a
feasible status set S is required to be closed under the rules of the agent program and comply to
the deontic and action axioms listed below. Second, concurrently executing all actions such
that Do ()
S should take the agent from its current state O to another state O which satisfies
the integrity constraints,
IC, associated with the agent. Third, concurrent execution of the set
of all actions such that Do ()
S should not violate any of the action constraints, AC,
associated with the agent.
The deontic and action axioms a feasible status set S has to obey for any ground action , consist
of deontic and action consistency axioms:
· If O S, then W /
S,
· If P S, then F /
S,
18
2 Preliminaries
· If P S, then O
S
|= P re() (i.e., is executable in the state O
S
),
and of deontic and action closure rules:
· O S P S,
· O S Do S, and
· Do S P S.
Additionally, stronger semantical notions than feasible status sets have been introduced for IM-
PACT
agents, namely rational status sets and reasonable status sets. Informally, rational status
sets are minimal feasible status sets, i.e., no subset of the action status set can be removed while
the program rules and deontic axioms are still satisfied. Reasonable status sets further restrict
rational status sets by the treatment of negation in the spirit of the treatment of default negation
for logic programs as introduced in the previous section. Thus, reasonable status sets extend the
stable model semantics of logic programs as shown in [128]. Moreover, reasonable status sets
have elegant important properties and are computationally not as hard as the other semantics,
cf. [128].
There are also further components of IMPACT agents which are not relevant for our purposes
here. A more detailed description of the IMPACT system and the semantics of IMPACT agents
can be found in [128, 69].
3 Update Agents
"A wise man changes his mind, a fool never will." (Spanish Proverb)
Logic programming has not only been conceived as a computational logic paradigm for problem
solving offering a number of advantages over conventional programming languages and as
a well-suited tool for declarative knowledge representation and common-sense reasoning [21]
possessing a high potential as a key technology to equip software agents with advanced reasoning
capabilities in order to make those agents behave intelligently (e.g., [122]) but it has also been
realized that further work is needed on extending the current methods and techniques to fully
support the needs of agents.
An important aspect is that an agent is situated in an environment which is subject to change.
This requests the agent to adapt over time, and to adjust its decision making. For agents utilizing
logic programming techniques for representing knowledge, this requires the agent to be capable
of updating logic programs accordingly, in order to ensure adaptivity.
In a simple (but, as for currently deployed agent systems, realistic) setting, an agent's knowledge
base, KB , may be modeled as a logic program, which the agent may evaluate to answer queries
that arise. Given various approaches to semantics, the problem of evaluating a logic program is
quite well-understood. However, an agent might be prompted to adjust its knowledge base KB
after receiving new information in terms of an update U , given by a clause or a set of clauses that
need to be incorporated into KB . Simply adding the rules of U to KB does not give a satisfactory
solution in practice, and will result in inconsistency even in simple cases. For example, if KB
contains the rules a
b and b , and U consists of the rule ¬a stating that a is false,
then the union KB
U is not consistent under predominant semantics such as the answer set
semantics [85] or the (extended) well-founded semantics [129].
Besides an underlying update semantics, which specifies how new, possibly inconsistent infor-
mation is to be incorporated into the knowledge base, an agent needs to have a certain update
policy, i.e., a specification of how to react upon the arrival of an update. For instance, the policy
may specify the change or retraction of certain rules from the knowledge base, given some par-
ticular information. More precisely, given a new piece of information, the update mechanism has
to address the following questions:
1. Which facts and rules should be incorporated?
2. How should facts and rules be incorporated?
20
3 Update Agents
In this chapter, we deal with these important aspects of updating, which every intelligent agent
building on declarative logic-programming techniques has to face and we give answers to the
above questions. The next section introduces update programs and update answer set semantics,
and Section 3.2 is devoted to its implementation. In Section 3.3, we introduce the language EPI
for specifying update policies, which we implement in form of update agents in Section 3.4.
Section 3.5 then discusses related work.
3.1
Updating Logic Programs
Several update approaches have been proposed for updating knowledge bases represented as
logic programs, cf. [11, 12, 55, 63, 56, 121, 79, 94, 101, 100]. However, since the declarative
components developed in this thesis build on answer set semantics for knowledge represented by
extended logic programs, the natural choice for an update mechanism is one that is suitable for
ELPs and also based on answer set semantics. The method for updating logic programs due to
Eiter et al. [55, 63, 56, 121] best fits these requirements. Thus, it is chosen as a representative
for the semantics underlying update agents.
3.1.1
Update programs
Like related update formalisms, update answer set semantics due to Eiter et al. [55, 63, 56, 121]
incorporates new information into the current knowledge base according to a causal rejection
principle. This principle enforces that, in case of conflicts between rules, more recent rules have
precedence over older rules. The basic idea is the following. Given a sequence (P
1
, . . . , P
n
) of
extended logic programs, each P
i
is assumed to update the information expressed by the initial
section (P
1
, . . . , P
i
-1
). The sequence (P
1
, . . . , P
n
) is translated into a single logic program P ,
respecting the successive update information, such that the answer sets of P represent the answer
sets of (P
1
, . . . , P
n
). The translation is realized by introducing new atoms rej (
·) which control
the applicability of rules with respect to the update information. Informally, rej (r) states that
rule r is "rejected", in case a more recent rule r asserts a conflicting information. This conflict
is resolved by enabling rej (r) to block the applicability of r, and so rule r is given precedence
over r.
In some sense, the proposed update mechanism can be seen as some form of an inheritance
strategy, where more recent rules are viewed as "more specific" information, which have to be
given preference in case of a conflict. For a detailed comparison of update answer set semantics
with related approaches [32, 31, 11, 12], as well as for a detailed analysis of its properties we refer
to [55, 56, 121]. In the remainder of this section we summarize basic definitions and properties
taken taken from [63, 121, 56].
3.1 Updating Logic Programs
21
3.1.2
Basic definition
An update sequence, P, is a series (P
1
, . . . , P
n
) of propositional extended logic programs. (The
first-order case will be considered below.) P is an update sequence over
A iff A represents the
set of atoms occurring in the rules of the constituting elements P
i
of P (1
i n).
Given an update sequence P = (P
1
, . . . , P
n
) over a set of atoms
A, let A
be a set of atoms
extending
A by new, pairwise distinct atoms rej (r) and A
i
, for each r occurring in P and for
each atom A
A, 1 i n. Further assume an injective naming function N(·, ·), which
assigns to each rule r in a program P
i
a distinguished name, N (r, P
i
), obeying the condition
N (r, P
i
) = N (r , P
j
) whenever i = j. As usual, with a slight abuse of notation, r is identified
with N (r, P
i
). Finally, for a literal L, L
i
denotes the result of replacing the atomic formula A of
L by A
i
.
Definition 2 Given an update sequence P = (P
1
, . . . , P
n
) over a set of atoms
A, the update
program P
¡
= P
1
¡ . . . ¡ P
n
over
A
is defined as the extended logic program consisting of the
following items:
(i) all constraints in P
i
, 1
i n;
(ii) for each r
P
i
, 1
i n:
L
i
B(r), not rej (r)
if H(r) = L;
(iii) for each r
P
i
, 1
i n:
rej (r)
B(r), ¬L
i+1
if H(r) = L;
(iv) for each literal L occurring in P (1
i n):
L
i
L
i+1
;
L
L
1
.
Informally, this program expresses layered derivability of a literal L, beginning at the top layer
P
n
downwards to the bottom layer P
1
. The rule r at layer P
i
is only applicable if it is not refuted
by a literal derived at a higher level that is incompatible with H(r). Inertia rules propagate a
locally derived value for L downwards to the first level, where the local value is made global.
The transformation P
¡
is modular in the sense that for P = (P
1
, . . . , P
n
, P
n+1
) it augments
P
¡
= P
1
¡ . . . ¡ P
n
only with rules depending on n + 1.
The intended answer sets of an update sequence P = (P
1
, . . . , P
n
) are defined in terms of the
answer sets of P
¡
.
Definition 3 Let P = (P
1
, . . . , P
n
) be an update sequence over a set of atoms
A. Then, S
Lit
A
is an (update) answer set of P iff S = S
A for some answer set S of P
¡
. The collection
of all update answer sets of P is denoted by
U(P).
22
3 Update Agents
Following the case of single programs, an update sequence P = (P
1
, . . . , P
n
) can be regarded as
the epistemic state of an agent, and the belief state Bel
E
(P) is given by Bel
E
(
U(P)). As well,
the update sequence P is said to be satisfiable iff
U(P) = , and P P iff Bel
E
(P) = Bel
E
(P )
(P some update sequence).
For illustration of Definition 3, consider the following example, adapted from [11].
Example 3 Consider the update of the knowledge base KB from Example 1 by an update pro-
gram U
1
, where
U
1
=
{ r
5
:
¬tv_on power_failure,
r
6
: power_failure
}.
The single answer set of P = (KB , U
1
) is, as desired,
S =
{power_failure, ¬tv_on, sleep, night},
since the only answer set of P
¡
is given by
S
=
{ power_failure
2
, power_failure
1
, power_failure,
¬tv_on
2
,
¬tv_on
1
,
¬tv_on, rej (r
2
), sleep
1
, sleep, night
1
, night
}.
If new information arrives in form of the program U
2
:
U
2
=
{ r
7
:
¬power_failure },
then the update sequence (KB , U
1
, U
2
) has the answer set
T =
{ ¬power_failure, tv_on, watch_tv, night },
generated by the following answer set T of KB ¡ U
1
¡ U
2
:
T
=
{ ¬power_failure
3
,
¬power_failure
2
,
¬power_failure
1
,
¬power_failure,
rej (r
6
), tv_on
1
, tv_on, watch_tv
1
, watch_tv, night
1
, night
}.
P
3.1.3
Properties and characterizations
Next, we summarize some useful properties and characterizations of the approach.
Let P be an update sequence over a set of atoms
A, and let S be an answer set of P. Then,
S denotes the (uniquely determined) answer set of P
¡
obeying S = S
Lit
A
. Note that S is
well-defined due to a result that guarantees that answer sets of P are uniquely determined by
the answer sets of P
¡
. In particular it holds, that if S, T
Lit
A
are answer sets of P
¡
, then
S
Lit
A
= T
Lit
A
iff S = T .
Furthermore, if an update sequence P consists of a single program P
1
, then the update answer
sets of P coincide with the regular answer sets of P
1
.
3.1 Updating Logic Programs
23
Answer sets of update sequences can also be characterized in a purely declarative way. To this
end, the concept of a rejection set is introduced:
Two rules r
1
and r
2
are called conflicting iff H(r
1
) =
¬H(r
2
). Furthermore, for an update
sequence P = (P
1
, . . . , P
n
) over a set of atoms
A and S Lit
A
, the rejection set of S, Rej (S, P)
is defined by Rej (S, P) =
n
i=1
Rej
i
(S, P), where Rej
n
(S, P) =
, and, for n i 1,
Rej
i
(S, P) =
{ r P
i
| r P
j
\ Rej
j
(S, P), for some j
{i + 1, . . . , n},
such that r, r are conflicting and S
|= B(r) B(r ) }.
That is, Rej (S, P) contains those rules from P which are rejected on the basis of rules which are
not rejected themselves. It is proven that the rejection set precisely matches the intended meaning
of the control atoms rej (
·).
By means of the rejection set, update answer sets can be characterized in terms of a modified
Gelfond-Lifschitz reduction. For a given update sequence P = (P
1
, . . . , P
n
), let
P denote the
set of all rules occurring in P, i.e.,
P =
n
i=1
P
i
.
Theorem 1 [56, Eiter et al., 2000] Let P = (P
1
, . . . , P
n
) be an update sequence over a set of
atoms
A and S Lit
A
a set of literals. Then, S is an answer set of P iff S is a minimal model
of (
P \ Rej (S, P))
S
.
For finite, propositional update sequences, the complexity does not increase w.r.t. ordinary ELPs,
i.e., it remains on the first level of the polynomial hierarchy: Given an update sequence P =
(P
1
, . . . , P
n
) over a set of atoms
A, then determining whether P has an answer set is NP-
complete, and determining whether L
Bel
E
(P) for some literal L is coNP-complete. Hardness
holds in both cases for n = 1, cf. [63, 121].
3.1.4
Minimal and strictly minimal answer sets
A property which update programs intuitively do not respect is minimality of change. In general,
it is desirable to incorporate a new set of rules P
2
into an existing program P
1
with as little change
as possible. This is realized by the notions of minimal and strictly minimal update answer sets.
Intuitively, an update answer set S is minimal iff there is no update answer set S of an update
sequence yielding a smaller rejection set.
Definition 4 Let P = (P
1
, . . . , P
n
) be an update sequence. An answer set S
U(P) is minimal
iff there is no S
U(P) such that Rej (S , P) Rej (S, P).
Example 4 Consider the sequence (KB , U
1
, U
2
) from Example 3. Assume that the following
additional update is received, describing that a TV can also be turned off:
U
3
=
{r
8
: switched_off
not tv_on, not power_failure;
r
9
: tv_on
not switched_off, not power_failure;
r
10
:
¬tv_on switched_off;
r
11
:
¬switched_off tv_on }.
24
3 Update Agents
While (KB , U
1
, U
2
) has the single answer set
S
1
=
{night, ¬power_failure, tv_on, watch_tv},
the new sequence P = (KB , U
1
, U
2
, U
3
) has two answer sets:
S
1
{¬switched_off}
and, additionally,
S
2
=
{night, ¬power_failure, switched_off, ¬tv_on, sleep}.
Both answer sets reject rule r
6
, but S
2
rejects r
2
, too. Thus, S
1
is minimal and, corresponding to
our intuition, should be preferred to S
2
.
P
Minimal answer sets put no further emphasis on the temporal order of updates. Rules in more
recent updates may be violated in order to satisfy rules from previous updates. Strict minimality
is a somewhat stronger notion taking also the rules rejected at specific levels into account:
Definition 5 Let S, S
U(P), for some update sequence P = (P
1
, . . . , P
n
). Then, S is
preferred over S iff some i
{1, . . . , n} exists such that (i) Rej
i
(S, P )
Rej
i
(S , P ), and
(ii) Rej
j
(S, P ) = Rej
j
(S , P ), for all j = i + 1, . . . , n. An answer set S of P is strictly minimal,
if no S
U(P) exists which is preferred over S.
Example 5 Suppose in the previous example we had observed that the TV was off when the
power returned, i.e., replace U
2
in (KB , U
1
, U
2
, U
3
) by:
U
2
=
{ r
7
:
¬power_failure ,
r
7
:
¬tv_on }.
The modified update sequence P = (KB , U
1
, U
2
, U
3
) yields the same answer sets as before:
S
1
=
{night, ¬power_failure, ¬switched_off, tv_on, watch_tv};
S
2
=
{night, ¬power_failure, switched_off, ¬tv_on, sleep}.
However, now both answer sets, S
1
and S
2
, are minimal: We have Rej (S
1
, P ) =
{r
7
, r
6
} and
Rej (S
2
, P ) =
{r
2
, r
6
}. Thus, Rej (S
1
, P ) and Rej (S
2
, P ) are incomparable, and hence both
S
1
and S
2
are minimal answer sets. Since in S
1
the more recent rule of U
2
is violated, S
2
is the
unique strictly minimal answer set.
P
We denote by Bel
min
(P) the set of all rules which are true in any minimal answer set of an
update sequence P. Likewise, Bel
str
(P) denotes the set of all rules which are true in all strictly
minimal answer sets of P.
Under minimal updates, the complexity of updates increases by one level in the polynomial
hierarchy. Given an update sequence P = (P
1
, . . . , P
n
) over a set of atoms
A and some rule r,
the following two problems are
P
2
-complete: (i) determining whether r
Bel
min
(P), and (ii)
determining whether r
Bel
str
(P). Hardness holds even if n = 2.
Let us consider some further example stressing the difference between regular update answer
sets, minimal answer sets, and strictly minimal answer sets.
3.2 Implementation
25
Example 6 An agent consulting different sources in search of a performance or a final rehearsal
of a concert on a given weekend may be faced with the following situation. First, the agent is
notified by one of the sources that there is no concert on Friday:
P
1
=
{ r
1
:
¬concert_friday }.
Later on, a second source reports that it is neither aware of a final rehearsal on Friday, nor of a
concert on Saturday:
P
2
=
{ r
2
:
¬final_rehearsal_friday ,
r
3
:
¬concert_saturday }.
Finally, the agent is assured that there is a final rehearsal or a concert on Friday and that whenever
there is a final rehearsal on Friday, a concert on Saturday or Sunday follows:
P
3
=
{r
4
: concert_friday
not final_rehearsal_friday;
r
5
: final_rehearsal_friday
not concert_friday;
r
6
: concert_saturday
final_rehearsal_friday, not concert_sunday;
r
7
: concert_sunday
final_rehearsal_friday, not concert_saturday }.
The update sequence P = (P
1
, P
2
, P
3
) yields three answer sets:
S
1
=
{final_rehearsal_friday, ¬concert_friday, concert_saturday};
S
2
=
{final_rehearsal_friday, ¬concert_friday, ¬concert_saturday, concert_sunday};
S
3
=
{¬final_rehearsal_friday, concert_friday, ¬concert_saturday},
The corresponding rejection sets are:
Rej (S
1
, P)
=
{r
2
, r
3
};
Rej (S
2
, P)
=
{r
2
};
Rej (S
3
, P)
=
{r
1
}.
Thus, S
2
and S
3
are minimal answer sets, with S
3
being the single strictly minimal answer set of
P.
P
Clearly, every strictly minimal answer set is minimal, but not vice versa. It is also easily seen that
for the case of update sequences involving only two update programs, i.e., for update sequences
of the form P = (P
1
, P
2
), the notions of strictly minimal answer sets and minimal answer sets
coincide.
3.2
Implementation
Since answer sets of update sequences are defined in terms of answer sets of extended logic
programs, it is relatively straightforward to implement the update approach presented in the pre-
vious section. In fact, such an implementation can be built on top of existing solvers for the
26
3 Update Agents
answer set semantics. In the present case, we implemented the update formalism as a front-end,
called
upd
, for the logic programming tool
DLV
[68, 54]. The latter system is a state-of-the-
art solver for disjunctive logic programs (DLPs) under the answer set semantics. It allows for
non-ground function-free rules and calculates answer sets by performing a reduction to the stable
model semantics. Formally, disjunctive logic programs are characterized as extended logic pro-
grams where disjunctions may appear in the head of rules; the answer set semantics for DLPs is
also due to Gelfond and Lifschitz [85], and is a straightforward generalization of the answer set
semantics for disjunction-free ELPs. Of course,
smodels
[114], a state-of-the-art system for
normal logic programs, could also be employed as underlying reasoning engine.
3.2.1
First-order programs
Since
DLV
allows for non-ground rules for function-free (datalog) programs, in particular and
since it is equipped with an advanced grounding mechanism, one goal for the implementation is
to make use of these capabilities, i.e., to feature (function-free) first-order update sequences.
A first-order update sequence, P, over
P is a series (P
1
, . . . , P
n
) of function-free first-order
programs P
i
over
P
i
(1
i n) such that P =
n
i=1
P
i
.
The Herbrand universe of P is identified with the Herbrand universe of
n
i=1
P
i
, and the ground
instantiation, P
, of P is the sequence (P
1
, . . . , P
n
), where each P
i
(1
i n) is the ground
instantiation of P
i
over the Herbrand universe of P. Analogous to the case of single first-order
programs, answer sets of P are induced by the answer sets of P
, i.e.,
U(P) is defined as the set
U(P
).
As it stands, the answer sets of some given first-order update sequence P depend on the construc-
tion of the update program P
¡
resulting from the ground instantiation P
of P. In other words,
first one has to construct the ground instantiation P
of P, and afterwards Definition 2 is applied,
in the form of building the update program P
¡
. Actually, it is also possible to circumvent the
use of P
¡
by defining a non-ground generalization, P
¡
, of the notion of an update sequence, and
then to describe answer sets of P in terms of the answer sets of P
¡
. We describe this somewhat
more direct approach in the following.
Let P = (P
1
, . . . , P
n
) be a first-order update sequence over a set of predicate symbols
P. We
assume a set
P
extending
P by new, pairwise distinct predicate symbols rej
r
and p
i
, for each
r in P, each p
P, and each i {1, . . . , n}. It is furthermore assumed that rej
r
possesses the
same arity as r; and the same holds for p
i
and p. Moreover, following the propositional case,
for a literal L(X) having predicate symbol p, the expression L
i
(X) means the result of replacing
p in L(X) by p
i
. As well, we tacitly presume a suitable naming device for rules, analogously
defined as in the propositional case.
Definition 6 Given a first-order update sequence P = (P
1
, . . . , P
n
) over a set of predicate sym-
bols
P, we define the update program P
¡
= P
1
¡ . . . ¡ P
n
over
P
consisting of the following
items:
3.2 Implementation
27
(i) all constraints in P
i
, 1
i n;
(ii) for each r = r(X)
P
i
, 1
i n:
L
i
(Y)
B(r), not rej
r
(X)
if H(r) = L(Y);
(iii) for each r = r(X)
P
i
, 1
i n:
rej
r
(X)
B(r), ¬L
i+1
(Y)
if H(r) = L(Y);
(iv) for each literal L occurring in P (1
i n):
L
i
(X)
L
i+1
(X);
L(X)
L
1
(X).
Observe that for a propositional ELP, the programs in Definitions 2 and 6 coincide, thus the
present definition properly generalizes the one for the propositional case.
The following result states that P
¡
faithfully represents P
¡
.
Theorem 2 For any first-order update sequence P = (P
1
, . . . , P
n
) over
P, it holds that the
answer sets of P
¡
coincide with the answer sets of P
¡
.
Proof. Let r
t
be the name of a ground rule r
= r(t)
P
i
and let L
t
i
be the new literals used in
P
¡
for a literal of a ground atom A = p(t)
A. By replacing in P
¡
every occurrence of rej (r
t
)
with rej
r
(t), and L
t
i
with L
i
(t) respectively, it is easily seen that the grounding of P
¡
coincides
with P
¡
, which immediately proves the result.
P
We remark that P
¡
can obviously be slightly simplified, which is relevant for implementing the
approach. All weakly negated literals not rej
r
(X) in rules with heads L
n
(Y) can be removed:
Indeed, since rej
r
(t) cannot be derived for any grounding t of variables X, each such atom
evaluates to false in any answer set of P
¡
. Thus, no rule from P
n
is rejected in an answer set of
P
¡
, i.e., all most recent rules are obeyed.
Given a sequence of update programs as input,
upd
first translates this sequence into the single
extended logic program, P
¡
, and then invokes
DLV
to calculate the answer sets of P
¡
. In order
to obtain update answer sets of the given input sequence, the special-purpose atoms introduced
by the translation are filtered from the answer sets of P
¡
.
Concerning the implementation of minimal and strictly minimal answer sets, we will first show
how such answer sets can be characterized in terms of extended logic programs. Although in
principle it is possible to express the corresponding reasoning tasks in terms of disjunctive logic
programs (which is a consequence of the complexity results for calculating minimal and strictly
minimal answer sets and well-known expressibility results for the disjunctive answer set seman-
tics [66]), we chose instead to pursue a two-step evaluation approach for our purposes, remaining
within the present non-disjunctive framework, and, at the same time, adhering more closer to the
underlying intuitions.
28
3 Update Agents
Roughly speaking, this two-step approach can be described as follows (cf. Figure 3.1): First,
the answer sets of the update program P
¡
are calculated. As soon as an answer set S is pro-
duced (denoted by Next _Answer _Set (P
¡
) in Figure 3.1), it is tested for being minimal (strictly
minimal).
Testing a candidate, S, for minimality (strict minimality) is performed by evaluating a test pro-
gram, P
min
S
(P
strict
S
), consisting of the rules of P
¡
and a set of additional rules. Intuitively, the
additional rules constrain the answer sets of P
min
S
(P
strict
S
) to those answer sets of P
¡
having
a smaller set of rejected rules compared to the rules rejected by S (or to those answer sets of
P
¡
preferred over S, respectively). Hence, the candidate S is minimal (strictly minimal) if the
corresponding test program P
min
S
(P
strict
S
) has no answer set. In the following subsections, the
implementation approach is described more formally.
3.2.2
Minimal answer sets
Definition 7 Let P
¡
= P
1
¡ . . . ¡ P
n
be a (first-order) update program and S an answer set
of P
¡
. Let ok be a new nullary predicate symbol (i.e., a new propositional atom) and, for each
predicate symbol rej
r
occurring in P
¡
, let s
r
be a new predicate symbol having the same arity as
rej
r
. Then, the (first-order) minimality-test program with respect to S, denoted by P
min
S
, consists
of all rules and constraints of P
¡
, together with the following items:
(i) for each predicate symbol rej
r
occurring in P
¡
:
rej
r
(X), not s
r
(X);
(ii) for each ground formula rej
r
(t)
S:
ok
not rej
r
(t);
s
r
(t)
;
(iii) the constraint
not ok.
Note that in the above definition, only the rules and facts of (ii) manifest the dependence of P
min
S
from S. Informally, the constraints (i) eliminate all answer sets with rejection sets which cannot
be subsets of Rej (S, P), i.e., which reject at least one rule not rejected in S. In the remaining
answer sets, if any, either ok is true, i.e., at least one rule which is rejected in S is not rejected in
such a set, or ok is false, in which case their rejection sets equal Rej (S, P), and thus these sets
are eliminated by Constraint (iii). Actually, the following proposition holds:
Theorem 3 Let S be an answer set of P
¡
. Then, S is a minimal answer set of P
¡
iff P
min
S
has
no answer set.
3.2 Implementation
29
Algorithm Compute_Minimal_Models(P)
Input: A sequence of ELPs P = (P
1
,. . . ,P
n
).
Output: All minimal answer sets of P.
var S : AnswerSet ;
var MinModels : Set _Of _AnswerSets;
S := Next _Answer _Set (P
¡
);
while S = nil do
var Counter : Set _Of _AnswerSets;
Counter := Compute_Answer _Sets(P
min
S
);
if (Counter =
) then
MinModels := MinModels
{S };
fi
S := Next _Answer _Set (P
¡
);
od
return MinModels;
Figure 3.1: Algorithm to calculate minimal update answer sets.
Proof.
Only-if part. Suppose P
min
S
has an answer set S . Then ok must be true in S due to the constraint
(iii) of Definition 7. Since rules (ii) of Definition 7 are the only ones in P
min
S
with head ok,
there exists a ground term rej
r
(t)
S such that rej
r
(t) /
S . Moreover, no ground term
rej
r
(t)
S \ S can exist due to the constraints (i) of Definition 7. (Observe that rej
r
(t) /
S
implies s
r
(t) /
S ; hence, if rej
r
(t)
S , then the body of one of the constraints is true in S .)
This proves Rej (S , P
min
S
) = Rej (S , P)
Rej (S, P).
Since the predicate symbols ok and s
r
do not occur in P
¡
, and P
min
S
contains all rules and
constraints of P
¡
, results on the splitting of logic programs [106] imply that ~
S = S
\ ({ok}
{s
r
(t)
| s
r
(t)
S }) is an answer set of P
¡
. Given that Rej ( ~
S, P) = Rej (S , P)
Rej (S, P),
we obtain that S is not minimal.
If part. Suppose S is not minimal. Then there exists an answer set ~
S of P
¡
with Rej ( ~
S, P)
Rej (S, P). Consider S = ~
S
{ok} {s
r
(t)
| rej
r
(t)
S}. It is easily verified that ~
S is an
answer set of P
min
S
.
P
This result allows us to calculate all minimal answer sets of P
¡
using the straightforward algo-
rithm depicted in Figure 3.1, which proceeds as follows: compute all answer sets of P
¡
and, as
soon as an answer set S is produced, check if the corresponding minimality-test program P
min
S
has at least one answer set. If not, then add S to the set of minimal answer sets of P
¡
.
30
3 Update Agents
3.2.3
Strictly minimal answer sets
Definition 8 Let P
¡
= P
1
¡ . . . ¡ P
n
be a (first-order) update program and S an answer set of
P
¡
. Let ok, ok
i
(1
i n), and eq
i
(1
i n + 1) be new nullary predicate symbols, and, for
each predicate symbol rej
r
occurring in P
¡
, let s
r
be a new predicate symbol having the same
arity as rej
r
. Then, the program P
strict
S
consists of all rules and constraints of P
¡
, together with
the following items:
(i) for each predicate rej
r
occurring in P
¡
, corresponding to r
P
i
:
rej
r
(X), not s
r
(X), eq
i+1
;
(ii) for each ground term rej
r
(t)
S, corresponding to r P
i
:
ok
i
not rej
r
(t), eq
i+1
;
s
r
(t)
;
(iii) for 1
i n:
eq
i
eq
i+1
, not ok
i
;
ok
ok
i
;
(iv) the constraint
not ok
and the fact
eq
n+1
.
Again, program P
strict
S
depends on S only in virtue of Item (ii). The constraints of Item (i)
eliminate all answer sets S which cannot be preferred over S because at some level i they reject
a rule not rejected in S, and Rej
j
(S, P) = Rej
j
(S , P) holds for j = i + 1, . . . , n (expressed by
eq
i+1
). In the remaining answer sets, if there is any, ok is either true, or false. If ok is true in
S , then ok
i
is true in S for some level i, i.e., S does not reject a rule of P
i
which is rejected in
S, and Rej
j
(S, P) = Rej
j
(S , P) for j = i + 1, . . . , n. In this case, S is preferred over S. If,
however, ok is false in S , then Rej
i
(S, P) = Rej
i
(S , P), for i = 1, . . . , n, and S is killed by
the constraint of Item (iv).
An equivalent result as for minimality-test programs holds for the above test programs as well.
Hence, the same algorithm using P
strict
S
instead of P
min
S
can be used to compute all strictly
minimal answer sets of P
¡
.
Theorem 4 Let S be an answer set of P
¡
. Then, S is a strictly minimal answer set of P
¡
iff
P
strict
S
has no answer set.
3.2 Implementation
31
Proof.
Only-if part. Suppose P
strict
S
has an answer set S . Then ok must be true in S , due to Constraint
(iv) of Definition 8. Since the rules of Item (iii) of Definition 8 are the only ones in P
strict
S
with
head ok, there exists some i, 1
i n, such that ok
i
S . This implies that the body of the
corresponding rule of (ii) must be true in S . Hence, there exists a ground term rej
r
(t)
S \ S ,
where r
P
i
and such that eq
i+1
S . Moreover, except for the fact eq
n+1
, the rules of
(iii) are the only ones in P
strict
S
with eq predicate symbols in their heads, so that eq
i+1
implies
eq
j
S and ok
j
/
S for j = i + 1, . . . , n if i n. From this, and the constraints of (i),
it follows that no ground term rej
r
(t)S
\ S, r P
j
, j = i, . . . , n, can exist (rej
r
(t) /
S
implies s
r
(t) /
S ; hence, having rej
r
(t)
S and eq
j+1
S , the body of one of the
constraints is true in S ). It also follows that for every r
P
j
, j = i + 1, . . . , n, if rej
r
(t)
S,
then rej
r
(t)
S (otherwise the body of one of the rules of (ii) would be true in S , implying
ok
j
S , a contradiction).
Summarizing, we have shown the equivalences Rej
i
(S , P
strict
S
) = Rej
i
(S , P
¡
)
Rej
i
(S, P
¡
)
and Rej
j
(S , P
strict
S
) = Rej
j
(S , P
¡
) = Rej
j
(S, P
¡
), for j = i + 1, . . . , n. So, S is preferred
over S.
Since none of the predicate symbols ok, eq, and s
r
occurs in P
¡
, and P
strict
S
contains all rules
and constraints of P
¡
, by a similar argument as in the proof of Theorem 3 (i.e., invoking splitting
results from [106]) it follows that
~
S = S
\ ({ok, ok
i
} {eq
j
| j = i + 1, . . . , n + 1} {s
r
(t)
| s
r
(t)
S })
is an answer set of P
¡
. Given that Rej ( ~
S, P
¡
) = Rej (S , P
¡
), we obtain that ~
S is preferred over
S. Consequently, S is not a strictly minimal answer set.
If part. Suppose S is not a strictly minimal answer set. Then there exists an answer set ~
S
of P
¡
which is preferred over S. In particular, there exists some i, 1
i n, such that
Rej
j
( ~
S, P
¡
) = Rej
j
(S, P
¡
) for j = i + 1, . . . , n and Rej
i
( ~
S, P
¡
)
Rej
i
(S, P
¡
). Consider
S = ~
S
{ok, ok
i
} {eq
j
| j = i + 1, . . . , n + 1} {s
r
(t)
| rej
r
(t)
S}.
It is easily verified that ~
S is an answer set of P
strict
S
.
P
Based on these characterizations, the implementation
upd
handles the following reasoning tasks:
(i) checking the existence of an update answer set for a given update sequence, (ii) brave rea-
soning, and (iii) skeptical reasoning. Each of these tasks is realized for function-free (datalog)
programs under the basic update semantics, as well as for minimal and strictly minimal update
answer sets.
3.2.4
Applying the system
The general syntax of
upd
coincides with the syntax of
DLV
. Update sequences are represented
by grouping rules using the braces "
{
" and "
}
", as illustrated by the following example.
Ende der Leseprobe aus 331 Seiten
- nach oben
Details
- Arbeit zitieren
- , 2002, Declarative Logic-Programming Components for Information Agents, Hamburg, Bedey Media GmbH, https://www.diplom.de/document/221472
Ähnliche Arbeiten
Deutschlands größter Sharing Community
Jetzt Zusammenfassungen, Skripte und Klausuren kostenlos downloaden!
Uniturm.de
Ihre Vorteile als Autor
Geld verdienen Für jedes verkaufte Exemplar erhalten Sie Autorenhonorar - bis zu 40%.Kostenlose Buchveröffentlichung
Als eBook-Studie im Original und / oder auf Wunsch zusätzlich als hochwertiges Fachbuch in unserem renommierten Buchverlag.
Renommee als Fachbuchautor
Präsentieren Sie sich als Fachfrau oder Fachmann in Ihrem Fachgebiet und machen Sie sich bekannt.
Persönliche Betreuung
Unser Lektorat wird Sie persönlich betreuen und ist auch telefonisch unter 040-655992-14 erreichbar.
Weltweit im Buchhandel
Ihr Buch ist weltweit im Buchhandel und Online-Buchhandel wie z.B. amazon erhältlich.
Jetzt Autor werden!
Kommentare