🚀 go-pugleaf

THE PRELIMINARY ORAL EXAMINATION FOR THE DEGREE OF PH.D IN COMPUTER SCIENCE
FOR 

Gerardo Ignacio Simari

DATE: Thursday November 6, 2008 at 12:30 p.m.

LOCATION: Room 3450 Williams Building

TITLE: Stochastic Reasoning with Action Probabilistic Logic Programs

ABSTRACT: Probabilistic logic programming is a well known formalism for
reasoning in the presence of uncertainty. It has been shown to be highly
flexible, since it allows imprecise probabilities to be specified in the
form of intervals that convey the uncertainty inherent in the knowledge.
Furthermore, no independence assumptions are made, in contrast to many of
the probabilistic reasoning formalisms that have been proposed (e.g.,
Bayes's Nets). Up to now, all work in probabilistic logic and probabilistic
logic programming has focused on the problem of entailment, i.e., given a
set of formulas, deciding whether or not a certain 
logical formula (not in the original set) can be entailed from the
established knowledge base with given probability bounds. The naive approach
to solving this problem can be shown to be exponential in the number of
ground atoms in the domain, and much work has been focused on making these
inferences tractable. Even though entailment plays a very important role in
reasoning under uncertainty, we argue that the problem of finding the most
probable world (or model) is also a major part of this process, and provide
a discussion of several real-world scenarios in which this problem has been
shown to be of interest. 

In this work, we define what we mean by most probable worlds in different
settings, including 
single-agent and multi-agent environments under varying assumptions, as well
as in the presence 
of temporal information. We show that the computational cost of solving
these problems is much 
higher than that of entailment, since we must perform computations very
similar to those required 
by entailment many times. Given this result, we focus on finding both exact
and approximate 
algorithms to compute the most probable worlds efficiently, as well as
building prototype 
implementations in order to evaluate their performance. Finally, we also
investigate a problem 
that is in some sense the dual of the most probable world problem, i.e.,
that of effecting changes
in the environment in order to evoke certain desired actions. We study
several variations of this 
problem, including finding state change attempts with minimal cost and/or
maximum probability 
of success.


Examining Committee:

Dr. V S. Subrahmanian - Chair
Dr. Samir Khuller - Dept. Representative
Dr. Dana Nau - Committee Member
                                               

EVERYONE IS INVITED TO ATTEND THE PRESENTATION