Symbolic Model Checking Without Bdds Bibtex Bibliography

Title: Conformant Planning via Symbolic Model Checking

Authors:A. Cimatti, M. Roveri

(Submitted on 1 Jun 2011)

Abstract: We tackle the problem of planning in nondeterministic domains, by presenting a new approach to conformant planning. Conformant planning is the problem of finding a sequence of actions that is guaranteed to achieve the goal despite the nondeterminism of the domain. Our approach is based on the representation of the planning domain as a finite state automaton. We use Symbolic Model Checking techniques, in particular Binary Decision Diagrams, to compactly represent and efficiently search the automaton. In this paper we make the following contributions. First, we present a general planning algorithm for conformant planning, which applies to fully nondeterministic domains, with uncertainty in the initial condition and in action effects. The algorithm is based on a breadth-first, backward search, and returns conformant plans of minimal length, if a solution to the planning problem exists, otherwise it terminates concluding that the problem admits no conformant solution. Second, we provide a symbolic representation of the search space based on Binary Decision Diagrams (BDDs), which is the basis for search techniques derived from symbolic model checking. The symbolic representation makes it possible to analyze potentially large sets of states and transitions in a single computation step, thus providing for an efficient implementation. Third, we present CMBP (Conformant Model Based Planner), an efficient implementation of the data structures and algorithm described above, directly based on BDD manipulations, which allows for a compact representation of the search layers and an efficient implementation of the search steps. Finally, we present an experimental comparison of our approach with the state-of-the-art conformant planners CGP, QBFPLAN and GPT. Our analysis includes all the planning problems from the distribution packages of these systems, plus other problems defined to stress a number of specific factors. Our approach appears to be the most effective: CMBP is strictly more expressive than QBFPLAN and CGP and, in all the problems where a comparison is possible, CMBP outperforms its competitors, sometimes by orders of magnitude.

Submission history

From: A. Cimatti [view email]
[v1] Wed, 1 Jun 2011 16:40:44 GMT (187kb)

Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)

  • [1]

    Arne Borälv. The industrial success of verification tools based on Stålmarck’s Method. In Orna Grumberg, editor, International Conference on Computer-Aided Verification (CAV’97), number 1254 in LNCS. Springer-Verlag, 1997.Google Scholar

  • [2]

    R. E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, 35(8):677–691, 1986.MATHCrossRefGoogle Scholar

  • [3]

    J. R. Burch, E. M. Clarke, and K. L. McMillan. Symbolic model checking: 1020 states and beyond. Information and Computation, 98:142–170, 1992.MATHCrossRefMathSciNetGoogle Scholar

  • [4]

    E. Clarke and E. A. Emerson. Design and synthesis of synchronization skeletons using branching time temporal logic. In Proceedings of the IBM Workshop on Logics of Programs, volume 131 of LNCS, pages 52–71. Springer-Verlag, 1981.Google Scholar

  • [5]

    E. Clarke, O. Grumberg, and K. Hamaguchi. Another look at LTL model checking. In David L. Dill, editor, Computer Aided Verification, 6th International Conference (CAV’94), volume 818 of LNCS, pages 415–427. Springer-Verlag, June 1994.Google Scholar

  • [6]

    Edmund M. Clarke, Orna Grumberg, and David E. Long. Model checking and abstraction. ACM Transactions on Programming Languages and Systems, 16(5):1512–1542, 1994.CrossRefGoogle Scholar

  • [7]

    M. Davis and H. Putnam. A computing procedure for quantification theory. Journal of the Association for Computing Machinery, 7:201–215, 1960.MATHMathSciNetGoogle Scholar

  • [8]

    E. A. Emerson and C.-L. Lei. Modalities for model checking: Branching time strikes back. Science of Computer Programming, 8:275–306, 1986.CrossRefMathSciNetGoogle Scholar

  • [9]

    F. Giunchiglia and R. Sebastiani. Building decision procedures for modal logics from propositional decision procedures-the case study of modal K. In Proc. of the 13th Conference on Automated Deduction, Lecture Notes in Artificial Intelligence. Springer-Verlag, 1996.Google Scholar

  • [10]

    D. S. Johnson and M. A. Trick, editors. The second DIMACS implementation challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1993. (see http://dimacs.rutgers.edu/Challenges/).

  • [11]

    H. Kautz and B. Selman. Pushing the envelope: planning, propositional logic, and stochastic search. In Proc. AAAI’96, Portland, OR, 1996.Google Scholar

  • [12]

    O. Lichtenstein and A. Pnueli. Checking that finite state concurrent programs satisfy their linear specification. In Poceedings of the Twelfth Annual ACM Symposium on Principles of Programming Languages, pages 97–107, 1985.Google Scholar

  • [13]

    A. J. Martin. The design of a self-timed circuit for distributed mutual exclusion. In H. Fuchs, editor, Proceedings of the 1985 Chapel Hill Conference on Very Large Scale Integration, 1985.Google Scholar

  • [14]

    K. L. McMillan. Symbolic Model Checking: An Approach to the State Explosion Problem. Kluwer Academic Publishers, 1993.Google Scholar

  • [15]

    A. P. Sistla and E. M. Clarke. The complexity of propositional linear temporal logics. Journal of Assoc. Comput. Mach., 32(3):733–749, 1985.MATHMathSciNetGoogle Scholar

  • [16]

    G. Stålmarck and M. Säflund. Modeling and verifying systems and software in propositional logic. In B. K. Daniels, editor, Safety of Computer Control Systems (SAFECOMP’ 90), pages 31–36. Pergamon Press, 1990.Google Scholar

  • [17]

    P. R. Stephan, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. Combinational test generation using satisfiability. Technical Report M92/112, Departement of Electrical Engineering and Computer Science, University of California at Berkley, October 1992.Google Scholar

  • [18]

    H. Zhang. SATO: An efficient propositional prover. In International Conference on Automated Deduction (CADE’97), number 1249 in LNAI, pages 272–275. Springer-Verlag, 1997.Google Scholar

  • 0 thoughts on “Symbolic Model Checking Without Bdds Bibtex Bibliography

    Leave a Reply

    Your email address will not be published. Required fields are marked *