Project

Back to overview

Foundations of Resource-Bounded Reasoning and Anytime Algorithms

English title Foundations of Resource-Bounded Reasoning and Anytime Algorithms
Applicant Haenni Rolf
Number 102652
Funding scheme SNSF Professorships
Research institution Institut für Informatik Universität Bern
Institution of higher education University of Berne - BE
Main discipline Mathematics
Start/End 01.01.2005 - 31.12.2008
Approved amount 810'889.00
Show all

All Disciplines (2)

Discipline
Mathematics
Information Technology

Keywords (10)

Logic; Artificial Intelligence; Uncertain Reasoning; Probability Theory; Argumentation; Real-Time Systems; Intelligent Agents; Dempster-Shafer; Theorie; Information Algebras

Lay Summary (German)

Lead
Lay summary
I. KONTEXT UND WISSENSCHAFTLICHER RAHMENDieses Forschungsprojekt ist im Spannungsfeld zwischen zwei bedeutendenund aktuellen Fragestellungen eingebettet. Diese werden im folgenden kurzvorgestellt."Logisches und probabilistisches Schliessen": Wenn es darum geht,automatische Systeme zu bauen, die sich gemäss menschlichem Vorbildintelligent verhalten, dann ist das sognannte "Schliessen" eine wichtigeKomponente, die es zu realisieren gilt. Schliessen heisstSchlussfolgerungen aus vorhandenem Wissen ziehen. Um dies zuautomatisieren bedarf es einer formalen Theorie, die möglichst vieleAspekte des Schliessens miteinbezieht. Von besonderer Bedeutung ist dabeidie Tatsache, dass vorhandenes Wissen oft unvollständig, unsicher, oderwidersprüchlich ist. Man spricht deshalb auch vom "Schliessen unterUnsicherheit". In der Literatur, die über die künstliche Intelligenzhinausgeht, gibt es zwei klassische Ansätze, nämlich das "logische" unddas "probabilistische" Schliessen. Logisches Schliessen basiert auf derTheorie der formalen Logik, die sich im einfachsten Fall auf Aussagenlogikreduziert, in interessanteren Fällen aber allgemeine Constraints, lineareoder nicht-lineare Gleichungen und Ungleichungen, oder aber dievollständige Prädikatenlogik miteinbezieht. Das probabilistischeSchliessen basiert auf der Wahrscheinlichkeitstheorie und ist heute in derPraxis meist mit Bayesianischen Netzwerken verwirklicht. Beide Arten desSchliessens haben eine Geschichte, die mehrere hundert Jahre alt ist, undsind bei Mathematikern und Philosophen ebenso wichtig wie in derInformatik.Was bis heute relativ unklar geblieben ist, ist die Frage, wie sichlogisches und probabilistisches Schliessen unter einen Hut bringen lässt.Ein Ansatz, der eine befriedigende Lösung vorschlägt, ist die Theorie des"argumentativen Schliessens", welche im Umfeld des Projektleitersentwickelt wurde. Was für den Erfolg dieser Theorie entscheidend ist, sindentsprechende Rechenverfahren, mit deren Hilfe konkrete Probleme effizientbehandelt werden können."Anytime-Algorithmen": Ein Algorithmus im klassischen Sinn ist einRechenverfahren, dass für gegebene Eingangswerte (Input) bestimmteAusgangswerte (Output) berechnet. In der Regel sind Algorithmendeterministisch, d.h. ein bestimmer Input erzeugt immer derselbe Output.Bei schwierigen Problemen kann es vorkommen, dass das Berechnen desOutputs sehr aufwendig oder im Extremfall sogar praktisch nichtdurchführbar ist. Solche schwierigen Probleme sind im Bereich des formalenSchliessens besonders typisch. Was man dann tun kann, ist auf das genaueResultat zu verzichten, und sich mit einer approximierten Lösung zufriedenzu geben. Ein "Anytime-Algorithmus" ist ein Rechenverfahren, dass für einebestimte vorgegebene Rechenzeit ein solches approximiertes Resultatberechnet. Besonderns beim Bau von intelligenten Systemen, die innerhalbeiner nützlichen Zeit intelligente Entscheidungen treffen sollen, sindAnytime-Algorithmen besonders wünschenswert. In der Literatur wurdenAnytime-Algorithmen vor ungefähr 10 Jahren eingeführt, sind aber nochrelativ unerforscht.II. PROJEKTZIELE UND BEDEUTUNGDas Projekt zielt darauf hinaus, Anytime-Algorithen als solches und imspeziellen Bereich des formalen Schliessens genauer zu untersuchen. Esgeht also darum, diesen besonderen Rechenverfahren ein theoretischesFundament zu geben, und deren Anwendbarkeit in verschiedensten Bereichenzu überprüfen. Der verfolgte Ansatz basiert auf der Theorie der"Informationsalgebren", die ein allgemeines Rechenverfahren für dasformale Schliessen vorgeben. Dieses allgemeine Vefahren gilt es inentsprechende Anytime-Algorithmen umzuformen. Dabei sind verschiedenetheoretische und praktische Fragen zu beantworten.Im Lichte dieses allgemeinen Ansatzes werden dann verschiedene konkreteMethoden des formalen Schliessens in Hinblick auf entsprechendeAnytime-Algorithmen untersucht. Unter anderem geht es dabei um Ansätze deslogischen Schliessens, des probabilistischen Schliessens, oder umkombinierte Ansätze wie das probabilistische Argumentieren. Die dabei zuerwartenden Resultate müssen mit den in der Literatur bekannten Verfahrenverglichen werden, was auf experimentelle Evaluationen hinauslaufen wird.Voraussetzung dazu sind entsprechende Implementationen. In erfolgreichenFällen gilt es diese Verfahren dann in konkreten Anwendungen einzusetzen.Ein Beispiel einer vielversprechenden Anwendung ist desVertrauensmanagment in verteilten Netzwerken.Die Bedeutung des Projektes ist durch die Wichtigkeit des Schliessens, imspeziellen des logischen und probabilistischen Schliessens, mit denzahlreichen Anwendungen innerhalb und ausserhalb der Informatik gegeben.Hinzu kommt, dass Anytime-Algorithmen der Komplexität der Probleme indiesem Bereich in idealer Art und Weise entgegenwirken. Für den Bau vonintelligenten Systems ist dies eine grundlegende Voraussetzung.
Direct link to Lay Summary Last update: 21.02.2013

Responsible applicant and co-applicants

Employees

Associated projects

Number Title Start Funding scheme
123401 Foundations of Resource-Bounded Reasoning and Anytime Algorithms 01.01.2009 SNSF Professorships

-