The Logic Filtering Project


Investigators

  • Eyal Amir, University of Illinois at Urbana-Champaign
  • Stuart Russell, University of California at Berkeley

  • Students

  • Afsaneh Hajiamin
  • Hannaneh Hajishirzi
  • Brian Hlubocky
  • Megan Nance


  • This project is funded by DAF Air Force Research Laboratory Award FA8750-04-2- 0222 (DARPA REAL program).

    General information

    Filtering denotes any method whereby an agent updates its belief state --- its knowledge of the state of the world --- from a sequence of actions and observations. In logical filtering, the belief state is a logical formula describing possible world states and the agent has a (possibly nondeterministic) logical model of its environment and sensors. This project aims at efficient logical filtering algorithms that maintain a compact belief state representation indefinitely, for a broad range of environment classes including nondeterministic, partially observable STRIPS environments and environments in which actions permute the state space. Efficient filtering is also possible when the belief state is represented using prime implicates, or when it is approximated by a logically weaker formula.

    Papers and Publications

    E. Amir and S. Russell, Logical Filtering, in 18th Intl' Joint Conference on Artificial Intelligence (IJCAI'03), 2003.
    E. Amir and S. Russell, Logical Filtering, Sixth Symposium on the logical formalization of commonsense reasoning, part of the AAAI Spring Symposium, 2003.
    E. Amir, Learning partially observable action models, 4th international workshop on cognitive robotics (CogRob'04), part of ECAI'04, 2004.
    B. Hlubocky and E. Amir, Knowledge-gathering agents in adventure games, AAAI-04 workshop on Challenges in Game AI, 2004.

    Software and Projects

    E. Amir, STRIPS Filter Version 0.5 with README, now available for CMUCL (CMU Common Lisp). Logical Filter for STRIPS domains, which assumes that the actions succeeded, and the effect is (nondeterministically) changing the same set of propositional state features (fluents). The implementation receives as input a domain description in PDDL, a sequence of actions and observations, and an initial belief state formula, and outputs a belief state formula. Version 0.5 was tested on the Blocks-World domain (January 2003).  [new]
    E. Amir and Megan Nance, STRIPS Filter Version 0.6 with README, now available for CMUCL (CMU Common Lisp). Logical Filter for STRIPS domains, which assumes that the actions succeeded, and the effect is (nondeterministically) changing the same set of propositional state features (fluents). The implementation receives as input a domain description in PDDL, a sequence of actions and observations, and an initial belief state formula, and outputs a belief state formula. Unlike version 0.5, version 0.6 does not assume that the belief state is already in PI-CNF, so it employs ZRES, (compiled for Linux x86), a prime implicates finder created by Laurent Simon and Alvaro del Val. Version 0.6 was tested on a Chess Domain (September 2004).  [new]
    Alex Jaffe (re-using STRIPS-filter code by Eyal Amir), NNF Filter Version 0.5 (also packaged and with README), now available for CMUCL (CMU Common Lisp). Logical Filter for domains where filtering distributes over conjunction (giving a logically weaker belief-state formula (i.e., more states) when this assumption does not hold). This implementation receives as input a domain description in PDDL, a sequence of actions and observations, and an initial belief state formula, and it outputs a belief state formula. It was tested on the Blocks-World domain. (May 2003)  [new]
    Megan Nance, Brian Hlubocky, and Afsaneh Hajiamin (re-using STRIPS-filter code by Eyal Amir), Random Action Generator 0.5, now available for CMUCL (CMU Common Lisp). Generates a list of random actions/observations. Inputs to the generator include a domain description of STRIPS actions (no conditional effects) in PDDL (which lists all the possible action schemas), and an initial world state. The generator assumes anything not listed in the initial world state to be false. It finds actions whose preconditions are satisfied by the world state, and updates the world state accordingly, outputting a sequence of actions and observations. It was tested on the Blocks-World domain. (January 2005)  [new]

    Relevant Resources and Groups


     
    Eyal Amir Stuart Russell Last updated on January 19, 2005.