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 123401
Funding scheme SNSF Professorships
Research institution Institut für Informatik Universität Bern
Institution of higher education University of Berne - BE
Main discipline Information Technology
Start/End 01.01.2009 - 31.12.2009
Approved amount 108'970.00
Show all

Keywords (9)

Reasoning; Artificial Intelligence; Probabilistic Inference; Logic; Bayesian Networks; Valuation Algebras; Knowledge Compilation; Anytime Algorithms; Approximation Algorithms

Lay Summary (English)

Lead
Lay summary
One of the major challenges in modern computer science is to solve problems for which it is computationally difficult or infeasible to find an exact or optimal solution. Such difficult problems are very common in intelligent knowledge-based systems. What makes such systems problematical is the unpredictability of the necessary computational resources consisting of time and memory. In real-world environments, in which the available computational resources are restricted, this is an unacceptable property. Examples of such intelligent systems are mobile robots acting in unknown real-time territories, intelligent agents making decisions in unpredictable multi-agent environments, or automated knowledge-based systems providing services to customers whose goals or expectations are only partially known. What characterizes these domains is that the computational resources required to reach the perfect or optimal solution reduce the overall utility of the results. It is thus (computationally) not feasible and (economically) not necessary to find the perfect or optimal solution. The problem is thus to construct systems that react to a situation after the "right amount of thinking". For this, it is necessary for a successful system to have the flexibility to trade off the quality of the results against the computational requirements of the underlying problem.The goal of this project is to analyze the foundations and properties of a particular class of so-called "anytime algorithms". Anytime algorithms are computational procedures for which the quality of the result improves gradually as computation time increases. They provide thus a flexible solution to the widespread problem of limited computational resources and are nowadays an emerging research topic in various areas. Of particular importance for this project is the area of reasoning under uncertainty in intelligent knowledge-based systems. Special attention is given to the analysis and further development of anytime algorithms for probabilistic networks. The main utility of this research project is a direct consequence of the numerous benefits of anytime algorithms compared to conventional approximation techniques. By studying approximation and anytime algorithms from a more general point of view, the results of the project will contribute to a better understanding of the nature of these types of algorithms and provide general solutions for resource-bounded reasoning. This will help to solve various difficult problems in real-time applications of intelligent knowledge-based systems.
Direct link to Lay Summary Last update: 21.02.2013

Responsible applicant and co-applicants

Employees

Associated projects

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

Abstract

Anytime algorithms are computational procedures for which the quality of the result improves gradually as computation time increases. They give the user the possibility to trade off computational resources against accuracy of the results. Anytime algorithms provide thus a flexible solution to the widespread problem of limited computational resources and are nowadays an emerging research topic in various areas. Of particular importance for this project is the field of real-time reasoning under uncertainty in intelligent knowledge-based systems. The goal of the project is to analyze the foundations and properties of resource-bounded reasoning and anytime algorithms in intelligent systems in further details. Special attention will be drawn to the analysis and further development of anytime algorithms in the area of probabilistic networks, particularly for Bayesian and credal networks. Some of the expected results will then be applied to generic local computation techniques, which are applicable to all sorts of inference problems in many different areas. For this, we will apply knowledge compilation techniques to the theory of semiring valuation algebras.The expected algorithms will be implemented and empirically evaluated in comparison to existing techniques. The relevance to specific application domains will be further explored.
-