Dafna Shahaf, Logical
Filtering and Learning in Partially Observable Worlds.
Master's Thesis, University of
Illinois at Urbana-Champaign, Computer Science Department, 2007.
Under the supervision of Prof.
Eyal Amir.
Agents
often need to act intelligently under uncertainty. Two main sources
of
uncertainty
are partial observability and unknown world dynamics: in partially
observable
domains, agents do not know the complete state of the world (for
example,
they
can only observe their immediate surroundings). In partially known
worlds,
the
agents do not know how their actions affect the world.
Dafna Shahaf and Eyal Amir,
Towards a Theory of
AI-Completeness, CommonSense'07.
(read
with a whole saltshaker :-) )
In
this paper we present a novel classification of computational
problems.
Motivated by a theoretical investigation
of
Artificial Intelligence (AI), we present (1) a complexity
model
for computational problems that includes a human in
the
process, and (2) a classification of prototypical problems
treated
in the AI literature.
Dafna Shahaf and Eyal Amir,
Logical Circuit Filtering,
IJCAI'07.
Logical
Filtering is the problem of tracking the possible
states
of a world (belief state) after a sequence
of
actions and observations. It is fundamental to
applications
in partially observable dynamic domains.
This
paper presents the First exact logical
Filtering
algorithm that is tractable for all deterministic
domains.
Dafna Shahaf and Eyal Amir,
Learning Partially
Observable Action Schemas, AAAI'06.
We
present an algorithm that derives actions' effects and preconditions
in
partially observable, relational domains. Our
algorithm
has two unique features: an expressive relational
language,
and an exact tractable computation.
Dafna Shahaf, Allen Chang and Eyal
Amir, Learning Partially
Observable Action Models: Efficient Algorithms, AAAI'06
We
present tractable, exact algorithms for learning actions'
effects
and preconditions in partially observable domains.
Our
algorithms maintain a propositional logical representation
of
the set of possible action models after each observation
and
action execution.
