The Logical Filtering Project

Investigators

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

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

    Software and Projects

    E. Amir, STRIPS Filter Version 0.5 (also packaged), now available for CMUCL (CMU Common Lisp). Logical Filter for STRIPS domains, where an assumption is made that the actions succeeded, and the effect is (nondeterministically) changing the same set of propositional state features (fluents). 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. (January 2003) [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]

    Relevant Resources and Groups

       
    Eyal Amir Stuart Russell Last updated on April 5, 2004.