Talk by Eyal Amir:
Logical Filtering
Date: Friday, May 18th
Time: 3-4pm
Room: PT266
Abstract
Logical Filtering is the combination of two tasks: (a) Filter: Determine (represent in some way) the set of possible states (belief state) of a dynamic system at some time t, given previous observations and a belief state at time 0; and (b) Inquire: Answer queries about this belief state. We are particularly interested in dynamic systems and observations that permit tractable filtering and inquiry indefinitely.
In this talk I will present our current results about efficient logical filtering algorithms and complexity bounds. Logical filtering is hard in general, so I will focus on three types of propositional systems for which polynomial time filtering is possible (the first two also enable polynomial time inquiry):
(1) Systems in which actions are variants of STRIPS, i.e., non-deterministic systems with no conditional effects.
(2) Systems in which actions can be characterized with non-singular Boolean matrices, and
(3) Deterministic actions of few effects and preconditions.
I will give the main ideas behind tractability of these systems and also behind intractability of the general case.
Our results affect future investigations into monitoring, planning, diagnosis, real-time control, and reinforcement learning in partially observable domains. They have already been applied to learning and planning in partially observable domains. They also lead to more efficient stochastic filtering.
This talk includes materials from [Amir & Russell; IJCAI ‘03], [Shahaf & Amir; IJCAI ‘07], [Amir & Russell; J. manuscript in preparation]
Applications mentioned in this talk appear in [Amir; IJCAI ‘05], [Shahaf & Amir; AAAI ‘06], [Shahaf etal.; AAAI ‘06], [Chang & Amir; ICAPS’06]
URL: http://reason.cs.uiuc.edu/eyal
