Resource-Bounded Reasoning about Knowledge

Authors: 
Ho, Ngoc Duc
Year: 
2001
Language: 
English
Abstract in English: 
One of the principal goals of agent theories is to describe realistic, implementable agents, that is, those which have actually been constructed or are at least in principle implementable. That goal cannot be reached if the inherent resource-boundedness of agents is not treated correctly. Since the modal approach to epistemic logic is not suited to formalize resource-bounded reasoning, the issue of resource-boundedness remains one of the main foundational problems of any agent theory that is developed on the basis of modal epistemic logic. My work is an attempt to provide theories of agency with a more adequate epistemic foundation. It aims at developing theories of mental concepts that make much more realistic assumptions about agents than other theories. The guiding principle of my theory is that the capacities attributed to agents must be empirically verifiable, that is, it must be possible to construct artificial agents which satisfy the specifications determined by the theory. As a consequence, the unrealistic assumption that agents have unlimited reasoning capacities must be rejected. To achieve the goal of describing resource-bounded agents accurately, the cost of reasoning must be taken seriously. In the thesis I have developed a framework for modeling the relationship between knowledge, reasoning, and the availability of resources. I have argued that the correct form of an axiom for epistemic logic should be: if an agent knows all premises of a valid inference rule and if he performs the right reasoning, then he will know the conclusion as well. Because reasoning requires resources, it cannot be safely assumed that the agent can compute his knowledge if he does not have enough resources to perform the required reasoning. I have demonstrated that on the basis of that idea, the problems of traditional approaches can be avoided and rich epistemic logics can be developed which can account adequately for our intuitions about knowledge.
Abstract: 
Der Begriff ``Agent'' hat sich als eine sehr nützliche Abstraktion erwiesen, um verschiedene Problembereiche auf eine intuitive und natürliche Art und Weise zu konzeptualisieren. Intelligente Agenten haben daher Anwendung gefunden in verschiedenen Teilbereichen der Informatik. Zur Modellierung werden intelligente Agenten meist als intentionale Systeme aufgefaßt und mit Hilfe von mentalistischen Begriffen wie Wissen, Glauben (oder Überzeugung), Wunsch, Pflicht, Intention usw. beschrieben. Unter diesen mentalen Begriffen gehören die epistemischen Begriffe (d.h., Wissen und Glauben) zu den wichtigsten und wurden auch am intensivsten untersucht. Zur Modellierung von Wissen und Glauben werden in der Regel modale epistemische Logiken verwendet. Solche Systeme sind aber nicht geeignet, um ressourcenbeschränkte Agenten zu beschreiben, weil sie zu starke Annahmen bezüglich der Rationalität von Agenten machen. Zum Beispiel wird angenommen, daß Agenten alle logischen Wahrheiten sowie alle Konsequenzen seines Wissens kennen. Dieses Problem ist bekannt als das Problem der logischen Allwissenheit (``logical omniscience problem''). Da alle Agenten grundsätzlich nur über begrenzte Ressourcen (wie z.B. Zeit, Information, Speicherplatz) verfügen, können sie nur eine begrenzte Menge von Informationen verarbeiten. Daher müssen alternative Modelle entwickelt werden, um Agenten realistisch modellieren zu können (siehe Kapitel 2). Daß modale epistemische Logik für die Formalisierung des ressourcenbeschränkten Schließens (``resource-bounded reasoning'') nicht geeignet ist, wird als ein offenes Problem der Agententheorien anerkannt. Es gibt bisher aber keine brauchbaren Alternativen zur Modallogik. Die meisten Ansätze zur Lösung des logischen Allwissenheitsproblems versuchen, Wissen und Glauben mit Hilfe schwacher Modallogiken zu beschreiben. Solche Versuche sind nicht befriedigend, da sie eine willkürliche Einschränkung der Rationalität der Agenten zur Folge haben (siehe Kapitel 3). Mein Ziel ist es, einen Rahmen für das ressourcenbeschränktes Schließen über Wissen und Glauben zu entwickeln. Damit soll eine solide Grundlage für Theorien intelligenter Agenten geschaffen werden. Als Nebenergebnis wird das logische Allwissenheitsproblem auf eine sehr intuitive Art und Weise gelöst: obwohl Agenten rational sind und alle logischen Schlußregeln anwenden können, sind sie nicht logisch allwissend, weil ihnen nicht genügend Ressourcen zu Verfügung stehen, um alle logischen Konsequenzen ihres Wissens zu ziehen. Im Kapitel 4 wird eine Reihe von Logiken vorgestellt, die den Begriff des expliziten Wissens formalisieren. Es wird eine Lösung des Problems der logischen Allwissenheit der epistemischen Logik vorgeschlagen, die die Rationalität der Agenten nicht willkürlich einschränkt. Der Grundgedanke dabei ist der folgende. Ein Agent kennt die logischen Konsequenzen seines Wissens nur dann, wenn er sie tatsächlich hergeleitet hat. Wenn ein Agent alle Prämissen einer gültigen Schlußregel kennt, kennt er nicht notwendigerweise die Konklusion: er kennt sie nur nach der Anwendung der Regel. Wenn er den Schluß nicht ziehen kann, z.B. weil er nicht die notwendigen Ressourcen dazu hat, wird sein Wissen nicht um diese herleitbare Information erweitert. Die Herleitung neuer Informationen wird als die Ausführung mentaler Handlungen aufgefaßt. Mit Hilfe einer Variante der dynamischen Logik können diese Handlungen beschrieben werden. Im Kapitel 5 werden Systeme für das ressourcenbeschränkte Schließen über Wissen und Glauben entwickelt, die auch quantitative Bedingungen über die Verfügbarkeit von Ressourcen modellieren können. Mit Hilfe dieser Logiken können Situationen beschrieben werden, wo Agenten innerhalb einer bestimmten Zeitspanne entscheiden müssen, welche Handlungen sie ausführen sollen. Der Ansatz besteht darin, epistemische Logik mit Komplexitätstheorie zu verbinden. Mit Hilfe einer Komplexitätsanalyse kann ein Agent feststellen, ob ein bestimmtes Problem innerhalb vorgegebener Zeit lösbar ist. Auf der Grundlage dieses Wissens kann er dann die für die Situation geeignete Entscheidung treffen. Damit ist es gelungen, eine direkte Verbindung zwischen dem Wissen eines Agenten und der Verfügbarkeit seiner Ressourcen herzustellen.
Pubdate / Erscheinungsdatum: 
2001-04-23
Promoter / Gefördert durch: 
ein Promotionsstipendium des Freistaates Sachsen, ein Forschungsstipendium der Australischen Regierung
Pages / Seitenanzahl: 
76
AttachmentSize
2001-19.pdf480.4 KB