{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T18:01:32Z","timestamp":1793124092044,"version":"4.5.0"},"reference-count":74,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2003,7,1]],"date-time":"2003-07-01T00:00:00Z","timestamp":1057017600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T00:00:00Z","timestamp":1374710400000},"content-version":"vor","delay-in-days":3677,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[2003,7]]},"DOI":"10.1016\/s0004-3702(02)00379-x","type":"journal-article","created":{"date-parts":[[2003,2,28]],"date-time":"2003-02-28T14:00:13Z","timestamp":1046440813000},"page":"119-162","source":"Crossref","is-referenced-by-count":31,"title":["Contingent planning under uncertainty via stochastic satisfiability"],"prefix":"10.1016","volume":"147","author":[{"given":"Stephen M.","family":"Majercik","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael L.","family":"Littman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"issue":"3","key":"10.1016\/S0004-3702(02)00379-X_BIB001","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0004-3702(83)80015-0","article-title":"The \u2217-minimax search procedure for trees containing chance nodes","volume":"21","author":"Ballard","year":"1983","journal-title":"Artificial Intelligence"},{"issue":"1","key":"10.1016\/S0004-3702(02)00379-X_BIB002","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0004-3702(94)00011-O","article-title":"Learning to act using real-time dynamic programming","volume":"72","author":"Barto","year":"1995","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB003","series-title":"Proceedings of the Fourteenth National Conference on Artificial Intelligence","first-page":"203","article-title":"Using CSP look-back techniques to solve real-world SAT instances","author":"Bayardo","year":"1997"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB004","series-title":"Dynamic Programming","author":"Bellman","year":"1957"},{"issue":"1\u20132","key":"10.1016\/S0004-3702(02)00379-X_BIB005","first-page":"279","article-title":"Fast planning through planning graph analysis","volume":"90","author":"Blum","year":"1997","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB006","series-title":"Working Notes of the Workshop on Planning as Combinatorial Search, held in conjunction with the Fourth International Conference on Artificial Intelligence Planning","article-title":"Probabilistic planning in the Graphplan framework","author":"Blum","year":"1998"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB007","series-title":"Proceedings of the Fifth European Conference on Planning","first-page":"320","article-title":"Probabilistic planning in the Graphplan framework","author":"Blum","year":"1999"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB008","series-title":"Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence Workshop on Planning under Uncertainty and Incomplete Information","article-title":"GPT: A tool for planning with uncertainty and partial information","author":"Bonet","year":"2001"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB009","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.575","article-title":"Decision-theoretic planning: Structural assumptions and computational leverage","volume":"11","author":"Boutilier","year":"1999","journal-title":"J. Artificial Intelligence Res."},{"key":"10.1016\/S0004-3702(02)00379-X_BIB010","series-title":"Proceedings of the Thirteenth International Conference on Machine Learning","first-page":"54","article-title":"Approximating value trees in structured dynamic programming","author":"Boutilier","year":"1996"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB011","series-title":"Proc. IJCAI-95, Montreal, Quebec","first-page":"1104","article-title":"Exploiting structure in policy construction","author":"Boutilier","year":"1995"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB012","series-title":"Proceedings of The Thirteenth National Conference on Artificial Intelligence","first-page":"1168","article-title":"Computing optimal policies for partially observable decision processes using compact representations","author":"Boutilier","year":"1996"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB013","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0004-3702(94)90081-7","article-title":"The computational complexity of propositional STRIPS planning","volume":"69","author":"Bylander","year":"1994","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB014","series-title":"Proceedings of the Thirteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-97)","first-page":"54","article-title":"Incremental pruning: A simple, fast, exact method for partially observable Markov decision processes","author":"Cassandra","year":"1997"},{"issue":"2","key":"10.1016\/S0004-3702(02)00379-X_BIB015","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","article-title":"The complexity of stochastic games","volume":"96","author":"Condon","year":"1992","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0004-3702(02)00379-X_BIB016","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","article-title":"A machine program for theorem proving","volume":"5","author":"Davis","year":"1962","journal-title":"Comm. ACM"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB017","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","article-title":"A computing procedure for quantification theory","volume":"7","author":"Davis","year":"1960","journal-title":"J. ACM"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB018","series-title":"Dynamic Programming: Models and Applications","author":"Denardo","year":"1982"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB019","series-title":"Proceedings of the AAAI Spring Symposium on Decision Theoretic Planning","first-page":"76","article-title":"Probabilistic planning with information gathering and contingent execution","author":"Draper","year":"1994"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB020","series-title":"Proc. IJCAI-97, Nagoya, Japan","first-page":"1169","article-title":"Automatic SAT-compilation of planning problems","author":"Ernst","year":"1997"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB021","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0004-3702(71)90010-5","article-title":"STRIPS: A new approach to the application of theorem proving to problem solving","volume":"2","author":"Fikes","year":"1971","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB022","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"issue":"2","key":"10.1016\/S0004-3702(02)00379-X_BIB023","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/S0004-3702(97)00037-4","article-title":"Representing action: Indeterminacy and ramifications","volume":"95","author":"Giunchiglia","year":"1997","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB024","series-title":"The Second International Conference on Artificial Intelligence Planning Systems","first-page":"80","article-title":"Conditional linear planning","author":"Goldman","year":"1994"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB025","series-title":"Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning (KR-94)","first-page":"238","article-title":"Representing uncertainty in simple planners","author":"Goldman","year":"1994"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB026","unstructured":"S. Hanks, D. McDermott. Modeling, a dynamic and uncertain world I: Symbolic and probabilistic reasoning about change, Technical Report, Department of Computer Science and Engineering, University of Washington, Seattle, WA, 1993"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB027","series-title":"Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS)","first-page":"130","article-title":"Dynamic programming for POMDPs using a factored state representation","author":"Hansen","year":"2000"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB028","series-title":"Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence","first-page":"279","article-title":"SPUDD: Stochastic planning using decision diagrams","author":"Hoey","year":"1999"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB029","series-title":"Dynamic Programming and Markov Processes","author":"Howard","year":"1960"},{"issue":"1\u20132","key":"10.1016\/S0004-3702(02)00379-X_BIB030","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0004-3702(98)00023-X","article-title":"Planning and acting in partially observable stochastic domains","volume":"101","author":"Kaelbling","year":"1998","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB031","series-title":"Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning (KR-96)","first-page":"374","article-title":"Encoding plans in propositional logic","author":"Kautz","year":"1996"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB032","series-title":"Abstracts of the Poster Sessions of IJCAI-97","article-title":"Exploiting variable dependency in local search","author":"Kautz","year":"1997"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB033","series-title":"Proceedings of Tenth European Conference on Artificial Inttelligence (ECAI-92)","first-page":"359","article-title":"Planning as satisfiability","author":"Kautz","year":"1992"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB034","series-title":"Proceedings of the Thirteenth National Conference on Artificial Intelligence","first-page":"1194","article-title":"Pushing the envelope: Planning, propositional logic, and stochastic search","author":"Kautz","year":"1996"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB035","series-title":"Working Notes of the Workshop on Planning as Combinatorial Search","first-page":"58","article-title":"BLACKBOX: A new approach to the application of theorem proving to problem solving","author":"Kautz","year":"1998"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB036","series-title":"Proceedings of the Fourth International Conference on Artificial Intelligence Planning","first-page":"181","article-title":"The role of domain-specific knowledge in the planning as satisfiability framework","author":"Kautz","year":"1998"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB037","series-title":"Proc. IJCAI-99, Stockholm, Sweden","first-page":"318","article-title":"Unifying SAT-based and graph-based planning","author":"Kautz","year":"1999"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB038","series-title":"Proc. IJCAI-99, Stockholm, Sweden","first-page":"1324","article-title":"A sparse sampling algorithm for near-optimal planning in large Markov decision processes","author":"Kearns","year":"1999"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB039","series-title":"Proc. IJCAI-99, Stockholm, Sweden","first-page":"1332","article-title":"Computing factored value functions for policies in structured MDPs","author":"Koller","year":"1999"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB040","series-title":"Proceedings of the Sixteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI 2000)","article-title":"Policy iteration for factored MDPs","author":"Koller","year":"2000"},{"issue":"1\u20132","key":"10.1016\/S0004-3702(02)00379-X_BIB041","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0004-3702(94)00087-H","article-title":"An algorithm for probabilistic planning","volume":"76","author":"Kushmerick","year":"1995","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB042","series-title":"Proc. IJCAI-97, Nagoya, Japan","first-page":"366","article-title":"Heuristics based on unit propagation for satisfiability problems","author":"Li","year":"1997"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB043","series-title":"Proceedings of the Fourteenth National Conference on Artificial Intelligence","first-page":"748","article-title":"Probabilistic propositional planning: Representations and complexity","author":"Littman","year":"1997"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB044","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.505","article-title":"The computational complexity of probabilistic plan existence and evaluation","volume":"9","author":"Littman","year":"1998","journal-title":"J. Artificial Intelligence Res."},{"issue":"3","key":"10.1016\/S0004-3702(02)00379-X_BIB045","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1023\/A:1017584715408","article-title":"Stochastic Boolean satisfiability","volume":"27","author":"Littman","year":"2001","journal-title":"J. Automat. Reason."},{"key":"10.1016\/S0004-3702(02)00379-X_BIB046","series-title":"Proceedings of the Sixteenth National Conference on Artificial Intelligence","first-page":"541","article-title":"On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems","author":"Madani","year":"1999"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB047","series-title":"Proceedings of the AAAI Spring Symposium on Search Techniques for Problem Solving Under Uncertainty and Incomplete Information, Stanford, CA","article-title":"C-MAXPLAN: Contingent planning in the MAXPLAN framework","author":"Majercik","year":"1999"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB048","series-title":"Proceedings of the Eighteenth National Conference on Artificial Intelligence Workshop on Probabilistic Approaches in Search","article-title":"APROPOS2: Approximate probabilistic planning out of stochastic satisfiability","author":"Majercik","year":"2002"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB049","series-title":"Proceedings of the Fourth International Conference on Artificial Intelligence Planning Systems","first-page":"86","article-title":"MAXPLAN: A new approach to probabilistic planning","author":"Majercik","year":"1998"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB050","series-title":"Proceedings of the Fifteenth National Conference on Artificial Intelligence","first-page":"954","article-title":"Using caching to solve larger probabilistic planning problems","author":"Majercik","year":"1998"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB051","series-title":"Proceedings of the Sixth International Conference on Artificial Intelligence Planning Systems","article-title":"Faster probabilistic planning through more efficient stochastic satisfiability problem encodings","author":"Majercik","year":"2002"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB052","unstructured":"S.M. Majercik, Planning under uncertainty via stochastic satisfiability, PhD Thesis, Department of Computer Science, Duke University, September 2000"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB053","series-title":"Proceedings of the Sixteenth National Conference on Artificial Intelligence","first-page":"557","article-title":"On the utility of plan-space (causal) encodings","author":"Mali","year":"1999"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB054","series-title":"Proceedings of the Fourteenth National Conference on Artificial Intelligence","first-page":"321","article-title":"Evidence for invariants in local search","author":"McAllester","year":"1997"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB055","series-title":"Principles of Artificial Intelligence","author":"Nilsson","year":"1980"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB056","unstructured":"N. Onder, Personal communication, 1998"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB057","unstructured":"N. Onder, Personal communication, 2000"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB058","series-title":"Proceedings of the Fourth European Conference on Planning: Recent Advances in AI Planning","first-page":"364","article-title":"Contingency selection in plan generation","author":"Onder","year":"1997"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB059","series-title":"Proceedings of the Sixteenth National Conference on Artificial Intelligence","first-page":"577","article-title":"Conditional, probabilistic planning: A unifying algorithm and effective search control mechanisms","author":"Onder","year":"1999"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB060","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1016\/0022-0000(85)90045-5","article-title":"Games against nature","volume":"31","author":"Papadimitriou","year":"1985","journal-title":"J. Computer Systems Sci."},{"key":"10.1016\/S0004-3702(02)00379-X_BIB061","series-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB062","series-title":"Proceedings of the First International Conference on Artificial Intelligence Planning Systems","first-page":"189","article-title":"Conditional nonlinear planning","author":"Peot","year":"1992"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB063","unstructured":"M.A. Peot, Decision-theoretic planning, PhD Thesis, Department of Engineering-Economic Systems and Operations Research, Stanford University, May 1998"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB064","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1613\/jair.277","article-title":"Planning for contingencies: A decision-based approach","volume":"4","author":"Pryor","year":"1996","journal-title":"J. Artificial Intelligence Res."},{"key":"10.1016\/S0004-3702(02)00379-X_BIB065","doi-asserted-by":"crossref","first-page":"1127","DOI":"10.1287\/mnsc.24.11.1127","article-title":"Modified policy iteration algorithms for discounted Markov decision processes","volume":"24","author":"Puterman","year":"1978","journal-title":"Management Sci."},{"key":"10.1016\/S0004-3702(02)00379-X_BIB066","series-title":"Proceedings of the Fortieth Annual IEEE Symposium on Foundations of Computer Science","first-page":"410","article-title":"A probabilistic algorithm for k-SAT and constraint satisfaction problems","author":"Sch\u00f6ning","year":"1999"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB067","series-title":"Knowledge Representation and Defeasible Reasoning","first-page":"23","article-title":"Monotonic solution of the frame problem in the situation calculus; An efficient method for worlds with fully specified actions","author":"Schubert","year":"1990"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB068","series-title":"Cliques, Coloring, and Satisfiability","article-title":"Local search strategies for satisfiability testing","volume":"26","author":"Selman","year":"1996"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB069","series-title":"Proceedings of the Fifteenth National Conference on Artificial Intelligence","first-page":"889","article-title":"Conformant Graphplan","author":"Smith","year":"1998"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB070","series-title":"Proceedings of Fifteenth European Conference on Artificial Intelligence (ECAI-2002)","article-title":"Stochastic constraint programming","author":"Walsh","year":"2002"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB071","series-title":"Proceedings of the Summer Conference on AI and Simulation of Behavior","first-page":"344","article-title":"Generating conditional plans and programs","author":"Warren","year":"1976"},{"key":"10.1016\/S0004-3702(02)00379-X_BIB072","series-title":"Proceedings of the Fifteenth National Conference on Artificial Intelligence","first-page":"897","article-title":"Extending Graphplan to handle uncertainty and sensing actions","author":"Weld","year":"1998"},{"issue":"1\u20133","key":"10.1016\/S0004-3702(02)00379-X_BIB073","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1023\/A:1006351428454","article-title":"Implementing the Davis\u2013Putnam method","volume":"24","author":"Zhang","year":"2000","journal-title":"J. Automat. Reason."},{"issue":"1\u20132","key":"10.1016\/S0004-3702(02)00379-X_BIB074","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","article-title":"The complexity of mean payoff games on graphs","volume":"158","author":"Zwick","year":"1996","journal-title":"Theoret. Comput. Sci."}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S000437020200379X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S000437020200379X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,27]],"date-time":"2019-03-27T08:57:05Z","timestamp":1553677025000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S000437020200379X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,7]]},"references-count":74,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2003,7]]}},"alternative-id":["S000437020200379X"],"URL":"https:\/\/doi.org\/10.1016\/s0004-3702(02)00379-x","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[2003,7]]}}}