Proceedings

Logical Circuit Filtering

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2611-2617.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

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. Our tractability result is interesting because it contrasts sharply with intractability results for structured stochastic domains. The key to this advance lies in using logical circuits to represent belief states. We prove that both filtering time and representation size are linear in the sequence length and the input size. They are independent of the domain size if the actions have compact representations. The number of variables in the resulting formula is at most the number of state features. We also report on a reasoning algorithm (answering propositional questions) for our circuits, which can handle questions about past time steps (smoothing). We evaluate our algorithms extensively on AI-planning domains. Our method outperforms competing methods, sometimes by orders of magnitude.

  1. [Amir and Russell, 2003] E. Amir and S. Russell. Logical filtering. In IJCAI '03. MK, 2003.
  2. [Bertoli et al., 2001] P. Bertoli, A. Cimatti, and M. Roveri. Heuris- tic search + symbolic model checking = efficient conformant planning. In IJCAI '01. MK, 2001. IJCAI
  3. [Biere et al., 1999] A. Biere, A. Cimatti, E.M. Clarke, M. Fujita, and Y. Zhu. Symbolic model checking using SAT procedures instead of BDDs. In DAC'99, 1999.
  4. [Bryant, 1992] R. E. Bryant. Symbolic Boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys, 1992.
  5. [Cimatti and Roveri, 2000] A. Cimatti and M. Roveri. Conformant planning via symbolic model checking. JAIR, 2000.
  6. [Clarke et al., 2001] E.M. Clarke, A. Biere, R. Raimi, and Y. Zhu. Bounded model checking using satisfiability solving. Formal Methods in System Design, 2001.
  7. [Ganai et al., 2002] M. K. Ganai, P. Ashar, A. Gupta, L. Zhang, and S. Malik. Combining strengths of circuit-based and cnf-based algorithms for a high-performance sat solver. In DAC, 2002.
  8. [Liberatore, 1997] P. Liberatore. The complexity of the language A. ETAI, 1997.
  9. [Lin and Reiter, 1997] F. Lin and R. Reiter. How to progress a database. AIJ, 1997.
  10. [Lind-Nielsen, 1999] J. Lind-Nielsen. Buddy -a binary decision di- agram package. Technical report, Institute of Information Tech- nology, Technical University of Denmark, 1999.
  11. [Petrick and Bacchus, 2004] R.P.A. Petrick and F. Bacchus. Ex- tending the knowledge-based approach to planning with incom- plete information and sensing. In ICAPS-04. AAAI Press, 2004.
  12. [Reiter, 1991] R. Reiter. The frame problem in the situation cal- culus: A simple solution (sometimes) and a completeness result for goal regression. In Artificial Intelligence and Mathematical Theory of Computation. Academic Press, 1991.
  13. [Thiffault et al., 2004] C. Thiffault, F. Bacchus, and T. Walsh. Solv- ing non-clausal formulas with dpll search. In Principles and Practice of Constraint Programming, 2004.
  14. [Winslett, 1990] M.A. Winslett. Updating Logical Databases. Cambridge U. Press, 1990.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards