On the projection problem in active knowledge bases with incomplete information

Belle, Vaishak; Lakemeyer, Gerhard

doi:999910269035

On the projection problem in active knowledge bases with incomplete information = Über das Projektionsproblem in dynamischen Wissensbasen mit unvollständigen Informationen

Belle, Vaishak (Author)

2012

Verantwortlichkeitsangabevorgelegt von Vaishak Belle

ImpressumAachen : Publikationsserver der RWTH Aachen University 2012

UmfangXIV, 200 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2012

Zsfassung in dt. und engl. Sprache

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Lakemeyer, Gerhard (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2012-06-08

Online
URN: urn:nbn:de:hbz:82-opus-41963
URL: https://publications.rwth-aachen.de/record/82797/files/4196.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Artificial Intelligence: AI (Genormte SW) ; Inferenz <Künstliche Intelligenz> (Genormte SW) ; Wissensrepräsentation (Genormte SW) ; Informatik (frei) ; knowledge representation (frei) ; artificial intelligence (frei) ; reasoning about action (frei) ; epistemic logic (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Das Problem der Projektion wurde als fundamentale Eigenschaft in dynamischen Domains erkannt, wobei die Aufgabe darin besteht, zu bestimmen, ob einige Bedingungen nach der Ausführung einer Aktionssequenz, ausgehend von einem initialen Zustand, anschließend weiterhin gelten oder nicht. Um das Problem zu lösen ist wenigstens effektives Folgern darüber nötig, wie Aktionen die Welt verändern, sowie das Ziehen von Rückschlüssen ausgehend von der initialen Wissensbasis. Aus verschiedenen Gründen, wie unter anderem der Berechenbarkeit, wird in Anwendungen oft die Closed-World Assumption angenommen, wodurch die Einsetzbarkeit dieser Systeme in der realen Welt eingeschränkt wird. In dieser Arbeit verwenden wir die Sprache des Situationskalküls um die rechenbetonten Eigenschaften einer Reihe von ungelösten Schlussfolgerungsaufgaben im Kontext der Projektion mit unvollständigen Wissensbasen zu untersuchen. Zuerst betrachten wir inhärent unvollständige Wissensbasen, wobei die dem Agenten zur Verfügung gestellten Informationen nicht jeden Fakt über die Welt abbilden können. Projektion kann dann beinhalten zu folgern, was und was nicht angenommen wird. Dann schauen wir auf physische Agenten mit unzuverlässiger Hardware, durch die Aktionen zu bestimmten Arten von unvollständigem Wissen führen können. Intuitiv sollten Annahmen periodisch synchronisiert sein mit diesem Rauschen. Schließlich betrachten wir die Anwesenheit anderer Agenten in der Umgebung, deren Annahmen sich willkürlich unterscheiden können. Der Formalismus sollte Sensorwahrnehmungen von anderen Agenten mit einbeziehen und von ihnen während der Aktionsausführung lernen. Um die exakte mathematische Behandlung von unvollständigen Wissensbasen zu ermöglichen knüpfen wir an die wegweisende Arbeit von Levesque an, welche bekannt ist als "Only Knowing". Aufbauend auf dieser bestehenden Arbeit untersuchen wir Projektion in Bezug auf Erweiterungen des Situationskalküls für Only Knowing, verrauschte Hardware und multiple Agenten. Unser zentraler Beitrag wird es sein zu zeigen, dass - ungeachtet der gesteigerten Ausdrucksstärke - das Schlussfolgern über Wissen und Aktionen sich auf nicht-epistemisches, nicht-dynamisches Folgern über die initiale Wissensbasis zurückführen lässt. Genauer gesagt zeigen wir, dass wir, wenn die Wissensbasis eine beliebige Logiktheorie erster Ordnung ist, Bedingungen bestimmen können unter denen Projektion durch Progression der Wissensbasis lösbar ist, welche die Änderungen durch bereits geschehene Aktionen darstellt. Ferner erlauben wir dem System wahrscheinlichkeitstheoretische Annahmen wenn Effektoren unzuverlässig sind und zeigen wie Projektion als Aktualisieren der Annahmen verstanden werden kann. Schließlich zeigen wir für den Fall mehrerer Agenten im Szenario, dass Anfragen über die Zukunft durch Regression der Anfrage zurück auf eine Formel über die initiale Wissensbasis beantwortet werden können. Only Knowing beinhaltet ein bedeutendes Resultat, dass es uns erlaubt, Anfragen über Wissen auf das Beweisen von Logiktheoremen erster Ordnung zurückzuführen, welche dann Projektion zur Lösung verwenden können.

The problem of projection has been identified as a fundamental reasoning concern in dynamical domains, where we are to determine whether or not some conditions will hold after a sequence of actions has been performed starting in some initial state. Solving the problem requires, at the very least, effectively reasoning about how actions transform the world, and inferring the logical consequences of the initial knowledge base (KB). For various reasons, tractability one of them, applications often make the closed-world assumption, thereby limiting the scope of these systems for the real world. In this thesis, using the language of the situation calculus, we investigate the computational properties of a number of unsolved reasoning tasks in the context of projection with incomplete information. We first look at inherently incomplete KBs, where the information provided to the agent may not determine every fact about the world. Projection, then, may involve reasoning about what is believed and also, about what is not believed. We then look at physical agents with unreliable hardware, as a result of which actions lead to certain kinds of incomplete knowledge. Intuitively, beliefs should be (periodically) synchronized with this noise. Finally, we consider the presence of other agents in the environment, whose beliefs may differ arbitrarily, and the formalism should incorporate what others sense and learn during actions. To enable a precise mathematical treatment of incomplete KBs, we appeal to a seminal proposal by Levesque, called only knowing. Building on existing work, we investigate projection wrt extensions to the situation calculus for only knowing, noisy hardware and multiple agents. Our central contribution will be to show that, in spite of the additional expressivity, reasoning about knowledge and action reduces to non- epistemic non-dynamic reasoning about the initial KB. More precisely, we show that when the initial KB is an arbitrary first-order theory, we are able to identify conditions under which projection can be solved by progressing the KB to a sentence reflecting the changes due to actions that have already occurred. Moreover, when effectors are unreliable, we allow the system to maintain probabilistic beliefs and then show how projection can be addressed by means of updating these beliefs. Finally, when there are many agents in the picture, we show that queries about the future can be resolved by regressing the query backwards to a formula about the initial KB. Only knowing comes with a significant result that allows us to reduce queries about knowledge to first-order theorem-proving tasks, which is then made use of when solving projection.

Fulltext:
PDF