Qualitative constraint-based reasoning: methods and applications

Hochschulschrift

Zusammenfassung: Die vorliegende Arbeit behandelt das sogenannte qualitative Schließen mittels Constraint-basierten Methoden. Dabei werden qualitative Informationen in Form von Einschränkungen (Constraints) an Objekte formuliert und durch Algorithmen untereinander in Bezug gesetzt um Aussagen über die Realisierbarkeit der Beschreibung zu erhalten. Klassischerweise wurden solche Ansätze oft auf der Basis von Relationenalgebren formalisiert. Diese Problemauffassung bildet insbesondere die Grundlage für die oft zitiert und verwendete Definition von qualitativen Constraint-Kalkülen.Diese Dissertation stützt sich größtenteils auf den Ansatz der Constraintprogrammierung, in der verschiedene Arten von Constraints miteinander verbunden und durch spezifische oder generische Algorithmen verarbeitetet werden. Dabei tritt inbesondere der eigentliche relationenalgebraische Ansatz in den Hintergrund, da die Art der Constraints und deren Verarbeitung deutlich freier gewählt werden kann. Zu diesem Zweck wird hier ein Vergleich des relationenalgebraischen Ansatzes zu den alternativen Formalismen, Constraint-Sprachen und Prädikatenlogik erster Stufe, gezogen. Dieser Vergleich liefert auch direkt die Erkenntnisse, dass ein sehr ähnlicher, aber deutlich generellerer, Ansatz auch mittels Constraint-Sprachen möglich ist und eine frühere Aussage über Eigenschaften qualitativer Constraint-Kalküle fehlerhaft ist. Nachfolgend werden dann die Algorithmen aus der Literatur über solche Kalküle den generischen Algorithmen der Constraintprogrammierung gegenübergestellt. Auch dieser Vergleich führt zu dem Schluss, dass die Constraintprogrammierung sehr geeignet ist um diese Art des qualitativen Schließens darzustellen und zu verarbeiten, wenngleich vereinzelte "qualitative Techniken" nicht unmittelbar als generische Algorithmen in der Constraintprogrammierung zu finden sind. Eine Implementation, die Techniken beider Seiten vereint, stellt das von mir mitentwickelte Programm GQR da, welches Probleminstanzen der qualitativen Constraint-Kalküle effizient löst.Um weiter den Unterschied zwischen dem Ansatz mittels Relationenalgebren und Constraintprogrammierung zu verdeutlichen, werden hier bekannte Beispiele qualitativer Constraint Kalküle - die Punkt- und Intervall-Algebra, sowie RCC8 - verbessert modelliert und für diese effiziente Schlussregeln entwickelt. Der urprüngliche Ansatz mittels Relationenalgebren lässt sich ebenfalls als eine Menge von Schlussregeln auffassen, so dass sich auch hier wieder ein Vergleich anbietet. Dieser wird sowohl theoretisch als auch empirisch durchgeführt. Es zeigt sich, dass insbesondere solche Regelmengen Grundlage für effiziente Lösungsansätze sind, die Sprachfragmente abdecken, die in polynomieller Zeit lösbar sind. Diese Untersuchung zeigt insbesondere Eigenschaften früherer Lösungsansätze mittels Programmen zur Lösung des propositionalen Erfüllbarkeitsproblems.Danach werden raumzeitliche Probleme mittels qualitativen Constraints im Rahmen der Constraintprogrammierung formuliert. Hier wird der Ansatz theoretisch abgebildet und gezeigt, dass nahezu alle solche Probleme NP-vollständig sind, selbst wenn nur die sehr simple Punkt-Algebra zugrunde gelegt wird. Desweiteren wird kurz eine Anwendung dieses raumzeitlichen Formalismus auf die Planung von Roboterarmbewegungen präsentiert.Zuletzt wird auf Berechnungsprobleme im Rahmen von qualitativen Routenbeschreibungen eingegangen. Hier ist die Grundidee, die Komplexität der Generierung und Evaluierung einer Routenbeschreibung zu bestimmen. Dabei wird Bezug auf zugrundeliegende Agentenmodele genommen. Diese formalisieren Annahmen über Agenten, die einer Beschreibung folgen oder für die eine Beschreibung generiert werden soll. Zum Schluss wird dieser Ansatz probabilistisch erweitert, mit früheren Arbeiten verglichen und empirisch evaluiert.In dieser Dissertation wird also der ältere Ansatz qualitativer Constraint-Kalküle über Relationenalgebren mit alternativen, neueren Ansätzen kontrastiert. Insbesondere ist dies der erste solche Vergleich in der Literatur. Die alternativen Ansätze sind Constraint-Sprachen und die Prädikatenlogik erster Stufe, womit diese Arbeit eine gebietsübergreifende Brücke von qualitativen Constraint-Kalkülen zu flexibleren und ausdrucksstärkeren Formalismen schlägt. Nebenbei werden Fehler in früheren Arbeiten aufgezeigt, bestehende Algorithmen deutlich verbessert, und die neugewonnen Flexibilität ausgenutzt um effizientes logisches Schließen in einer Vielzahl von Anwendungen zu ermöglichen. Am Ende wird als Erweiterung von Constraint-Problemen, die Berechnungskomplexität im Kontext von qualitativen Routenbeschreibungen analysiert. Dies führt insbesondere zu einer einfachen probabilistischen Erweiterung früherer Ansätze
Zusammenfassung: This thesis considers so-called qualitative constraint-based reasoning: qualitative information is formalized and posed as constraints to entities. Algorithms process these constraints to decide the satisfiability of the description. This approach has often been formalized by means of relation algebras, which has led to the definition of qualitative constraint calculi. In contrast, I consider the reasoning problem in the context of constraint programming. To this end, I compare the relation-algebraic approach to established alternative formalisms, such as constraint languages and first-order logic. The results illustrate shortcomings in previous work and show that a more flexible approach by means of constraint languages can be used to substitute the relation-algebraic view. Further, previously used "qualitative techniques" are compared with established generic algorithms from constraint programming. This results in an implementation of a solver, called GQR, which combines techniques from both sides to provide improved qualitative constraint-based reasoning.To further illustrate the difference between qualitative constraint calculi and constraint programming, I formulate several popular examples of such calculi - the Point and Interval Algebra, as well as RCC8 - in the form of improved representations with dedicated sets of logic rules. The relation-algebraic approach can also be understood in this way, such that a comparison is possible. Both theoretical study and empirical evaluation show that efficient approaches are in particular those representations with sets of rule that are capable of solving large fragments of the language in polynomial time. Moreover, this research shows properties of previous approaches by means of propositional satisfiability.Next, qualitative spatio-temporal constraint problems are studied. As these have been solved with constraint programming before, I theoretically formulate the problem for the Point Algebra. An analysis shows that most fragments of the spatio-temporal language have an associated NP-complete satisfiability problem - despite the fact that constraint problems of the simple Point Algebra are polynomial time. I also briefly present an application of this formalism to robot motion planning.Finally, I consider reasoning problems in the context of qualitative route descriptions. The main focus here is to derive computational complexity results for generating and evaluating such descriptions on a given map. These results are obtained in dependency of underlying agent models, which formalize several aspects of understanding route descriptions. A probabilistic extension of this framework is presented and compared with previous work.In summary, in this thesis I compare the approach to qualitative constraint-based reasoning by means of qualitative constraint calculi defined on the basis of relation algebras, to alternative, newer approaches, such as constraint languages and first-order logic. The obtained results pave the way to improve qualitative reasoning and ease its application by adopting a less restrictive, more flexible view. In the process, flaws in earlier work are discussed and algorithms significantly improved. At the end, I consider extended decision problems in the context of qualitative route descriptions. Here, features of agents are discussed that influence the computational complexity of the tasks

Angaben zum Objekt

• Standort: Deutsche Nationalbibliothek Frankfurt am Main
• Umfang: Online-Ressource
• Sprache: Englisch
• Anmerkungen: Albert-Ludwigs-Universität Freiburg, Dissertation, 2015

Klassifikation und Themen

• Klassifikation: Informatik
• Schlagwort: Künstliche Intelligenz ; Wissensrepräsentation ; Qualitatives Schließen

Beteiligte, Orts- und Zeitangaben

• Ereignis: Veröffentlichung
• (wo): Freiburg
• (wer): Universität
• (wann): 2015
• Urheber: Westphal, Matthias
• Beteiligte Personen und Organisationen: Nebel, Bernhard

Weitere Informationen

• DOI: 10.6094/UNIFR/10148
• URN: urn:nbn:de:bsz:25-freidok-101488
• Rechteinformation: Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Letzte Aktualisierung: 25.03.2025, 13:42 MEZ