Título: An optimal method for reasoning about actions
Palestrante:  Andreas Herzig (prof. Visitante IME-USP), IRIT-CNRS (Toulouse,
France) 

Data:   13/10/2008, 14h30
Local:  Sala 03B, IME-USP

Resumo:
(paper with Hans van Ditmarsch and Tiago de Lima "Optimal regression for
reasoning about knowledge and actions" at AAAI'07; later version available
at http://drops.dagstuhl.de/portals/index.php?semnr=07351)

The frame problem is one of the major obstacles on the road towards
logical reasoning about actions in AI. Two versions can be distinguished.
The representational version is the problem of designing a logical
language and a semantics such that domains can be described without
stating all the non-effects of each action. The inferential version is to
design an efficient reasoning method for a given solution to the
representational problem. Several solutions to the representational
problem where proposed in the past. The solution of Reiter (1991), further
extended by Scherl and Levesque (1993), relies on the hypothesis of
inertia: each action only changes the truth value of a small number of
facts, leaving all the others unchanged. Reiter's associated regression
inference method eliminates action symbols from formulas by rewriting them
to formulas of propositional logic (or formulas of epistemic logic in
Scherl and Levesque's case). In the general case, however, the regressed
formula may be exponentially larger than the original formula, and hence
non-optimal. We here present the first optimal reasoning method for
Reiter's and Scherl and Levesque's solution. We first show that their
solution to the representational frame problem can be encoded into dynamic
epistemic logic of van Ditmarsch, van der Hoek and Kooi (2005). We then
give a polynomial reduction to epistemic logic. We also establish some
complexity results for our reasoning method: NP-completeness for a single
agent, PSPACE-completeness for multiple agents, and EXPTIME-completeness
when common knowledge is involved.