Dafna Shahaf – Publications

  • 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


  • 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.