Preferences in answer set programming [Elektronische Ressource] / von Kathrin Konczak

Konczak

Sujets

• Informatik

Informations

• Publié par: universitat_potsdam
• Publié le: 01 janvier 2007
• Nombre de lectures: 7
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

WissensverarbeitungundInformationssysteme
Institutfur¨ Informatik
Universitat¨ Potsdam
PreferencesinAnswerSetProgramming
DISSERTATION
zurErlangungdesakademischenGrades
“Doctorrerumnaturalium”
(Dr. rer. nat.)
inderWissenschaftsdisziplinInformatik
unterderLeitungvon
Prof. Dr. TorstenSchaub
WissensverarbeitungundInformationssysteme
Institutfur¨ Informatik
eingereichtander
Mathematisch NaturwissenschaftlichenFakult at¨
der
Universitat¨ Potsdam
von
KathrinKonczakFur¨ PapaAcknowledgments
First of all, I would like to thank my supervisor Prof. Dr. Torsten Schaub for his invaluable support. I
would also like to thank my co authors Wolfgang Faber, Jerome Lang, Thomas Linke, and Ralf Vogel for
the successful collaboration, and my colleagues at the University of Potsdam, especially Christian Anger
and Martin Gebser for their helpful comments on my papers, as well as Jur¨ gen Brandt Mihram for the
technical support. Furthermore, I would like to thank Philippe Besnard and Kewen Wang for their helpful
assistance, as well as Andre´ Neumann and Susanne Grell for their assistance with the implementation of
oursoftwareandforprovidingexperimentalresults.
My work has been supported by the German Science Foundation (Deutsche Forschungsgemeinschaft)
under grant SCHA 550/6 4, TP C, and by the European Commission, FET (”Future Emerging Technolo
gies”)initiative,underprojectIST 2001 37004WASP.
Lastbutnotleast,Ithankmyfamilyandfriendsfortheirencouragementandconsiderateness.Kurzfassung
Die Antwortmengenprogrammierung entwickelte sich in den spaten¨ 90er Jahren als neues Paradigma
der logischen Programmierung und ist in den Gebieten des nicht monotonen Schließens und der deduk
tiven Datenbanken verwurzelt. Dabei wird eine Problemstellung als logisches Programm reprasentiert,¨
dessen Losungen,¨ die so genannten Antwortmengen, genau den Losungen¨ des ursprunglichen¨ Problems
entsprechen. DieAntwortmengenprogrammierungbildeteingeeignetesFundamentzurReprasentation¨ und
zum Losen¨ von Entscheidungs und Suchproblemen in der Komplexit atsklasse¨ NP. Anwendungen finden
wir unter anderem in der Produktkonfiguration, Diagnose und bei graphen theoretischen Problemen, z.B.
derSuchenachHamiltonschenKreisen.
In den letzten Jahren wurden viele Erweiterungen der Antwortmengenprogrammierung betrachtet. Die
am meisten untersuchte Erweiterung ist die Modellierung von Praferenzen.¨ Diese bilden eine naturliche¨
und effektive Moglichk¨ eit, unter einer Vielzahl von Losungen¨ eines Problems bevorzugte Losungen¨ zu
selektieren. Praferenzen¨ finden beispielsweise in der Stundenplanung, bei Auktionen und bei Produkt
konfigurationenihreAnwendung.
DerSchwerpunktdieserArbeitliegtinderModellierung,ImplementierungundAnwendungvonPrafe ¨
renzen in der Antwortmengenprogrammierung. Da es verschiedene Ansatze¨ gibt, um Praferenzen¨ darzu
¨stellen,konzentrierenwirunsaufgeordnetelogischeProgramme,wobeiPraferenzenalspartielleOrdnung
der Regeln eines logischen Programms ausgedruckt¨ werden. Dabei betrachten wir drei verschiedene Se
mantiken zur Interpretation dieser Praferenzen.¨ Im Vorfeld wurden fur¨ diese Semantiken die bevorzugten
AntwortmengendurcheinenCompileroderdurchMeta Interpretationberechnet. DaPr aferenzen¨ Losungen¨
selektieren,stelltsichdieFrage,obesmoglich¨ ist,diesedirektindenBerechnungsprozeßvonpraferenziert ¨
enAntwortmengenzuintegrieren,sodassdiebevorzugtenAntwortmengenohneZwischenschritteberech
net werden konnen.¨ Dazu entwickeln wir zuerst ein auf Graphen basierendes Gerust¨ zur Berechnung von
Antwortmengen. AnschließendwerdenwirdarinPraferenzen¨ integrieren,sodassbevorzugteAntwortmen
gen ohne Compiler oder Meta Interpretation berechnet werden. Es stellt sich heraus, dass die integrative
MethodeaufdenmeistenbetrachtetenProblemklassenwesentlichleistungsfahiger¨ istalsderCompileroder
Meta Interpretation.
Ein weiterer Schwerpunkt dieser Arbeit liegt in der Frage, inwieweit sich geordnete logische Pro
¨grammevereinfachenlassen. DazustehtdieMethodikderstrengenAquivalenzvonlogischenProgrammen
zur Verfugung.¨ Wenn ein logisches Programm streng aqui¨ valent zu einem seiner Teilprogramme ist, so
kann man dieses durch das entsprechende Teilprogramm ersetzen, ohne dass sich die zugrunde liegende
¨Semantik andert.¨ Bisher wurden strenge Aquivalenzen nicht fur¨ logische Programme mit Praferenzen¨ un
¨tersucht. IndieserArbeitdefinierenwirerstmaligstrengeAquivalenzenfur¨ geordnetelogischeProgramme.
¨WirgebennotwendigeundhinreichendeBedingungenfur¨ diestrengeAquivalenzzweiergeordneterlogis
cher Programme an. Des Weiteren werden wir auch die Frage beantworten, inwieweit geordnete logische
ProgrammeundderenPraferenzstrukturen¨ vereinfachtwerdenkonnen.¨
Abschließend prasentieren¨ wir zwei neue Anwendungsbereiche von Praferenzen¨ in der Antwortmen
genprogrammierung. ZuerstdefinierenwirneueProzedurenzurEntscheidungsfindunginnerhalbvonGrup
¨penprozessen. Diese integrieren wir anschließend in das Problem der Planung eines Treffens fur eine
Gruppe. Als zweite neue Anwendung rekonstruieren wir mit Hilfe der Antwortmengenprogrammierung
einelinguistischeProblemstellung,dieindeutschenDialektenauftritt. MomentanwirdimBereichderLin
guistik daruber¨ diskutiert, ob Regelsysteme von (menschlichen) Sprachen einzigartig sind oder nicht. Die
Rekonstruktion von grammatikalischen Regularitaten¨ mit Werkzeugen aus der Informatik erlaubt die Un
terstutzung¨ der These, dass linguistische Regelsysteme Gemeinsamkeiten zu anderen nicht linguistischen
Regelsystemenbesitzen.Abstract
Answer Set Programming (ASP) emerged in the late 1990s as a new logic programming paradigm,
having its roots in nonmonotonic reasoning, deductive databases, and logic programming with negation as
failure. The basic idea of ASP is to represent a computational problem as a logic program whose answer
sets correspond to solutions, and then to use an answer set solver for finding answer sets of the program.
ASPisparticularlysuitedforsolvingNP completesearchproblems. Amongthese,wefindapplicationsto
productconfiguration,diagnosis,andgraph theoreticalproblems,e.g.findingHamiltoniancycles.
On different lines of ASP research, many extensions of the basic formalism have been proposed. The
mostintensivelystudiedoneisthemodellingofpreferencesinASP.Theyconstituteanaturalandeffective
wayofselectingpreferredsolutionsamongaplethoraofsolutionsforaproblem. Forexample,preferences
havebeensuccessfullyusedfortimetabling,auctioning,andproductconfiguration.
In this thesis, we concentrate on preferences within answer set programming. Among several for-
malisms and semantics for preference handling in ASP, we concentrate on ordered logic programs with
the underlying D , W , and B semantics. In this setting, preferences are defined among rules of a logic
program. They select preferred answer sets among (standard) answer sets of the underlying logic pro
gram. Up to now, those sets have been computed either via a compilation method or by
meta interpretation. Hence, the question comes up, whether and how preferences can be integrated into an
existingASPsolver. Tosolvethisquestion,wedevelopanoperationalgraph basedframeworkforthecom
putation of answer sets of logic programs. Then, we integrate preferences into this operational approach.
We empirically observe that our integrative approach performs in most cases better than the compilation
methodormeta interpretation.
Another research issue in ASP are optimization methods that remove redundancies, as also found in
database query optimizers. For these purposes, the rather recently suggested notion of strong equivalence
for ASP can be used. If a program is strongly equivalent to a subprogram of itself, then one can always
use the subprogram instead of the original program, a technique which serves as an effective optimization
method. Up to now, strong equivalence has not been considered for logic programs with preferences. In
this thesis, we tackle this issue and generalize the notion of strong equivalence to ordered logic programs.
Wegivenecessaryandsufficientconditionsforthestrongequivalenceoftwoorderedlogicprograms. Fur-
thermore,weprovideprogramtransformationsfororderedlogicprogramsandshowinhowfarpreferences
canbesimplified.
Finally, we present two new applications for preferences within answer set programming. First, we
define new procedures for group decision making, which we apply to the problem of scheduling a group
meeting. As a second new application, we reconstruct a linguistic problem appearing in German dialects
within ASP. Regarding linguistic studies, there is an ongoing debate about how unique the rule systems of
languageareinhumancognition. Thereconstructionofgrammaticalregularitieswithtoolsfromcomputer
science has consequences for this debate: if grammars can be modelled this way, then they share core
propertieswithothernon linguisticrulesystems.