Strong planning under partial observability

Albore, 2004, Generating safe assumption-based plans for partially observable, nondeterministic domains F. Bacchus, C. Boutilier, A.J. Grove, Rewarding behaviors, in: Proceedings of AAAI-96, Portland, OR, 1996 F. Bacchus, C. Boutilier, A.J. Grove, Structured solution methods for non-Markovian decision processes, in: Proceedings of AAAI-97, Providence, RI, 1997 Burch, 1992, Symbolic model checking: 1020 states and beyond, Inform. and Comput., 98, 142, 10.1016/0890-5401(92)90017-A P. Bertoli, A. Cimatti, M. Pistore, M. Roveri, P. Traverso, MBP: a model based planner, in: Proceeding of ICAI-2001 workshop on Planning under Uncertainty and Incomplete Information, Seattle, WA, 2001, pp. 93–97 P. Bertoli, A. Cimatti, M. Pistore, P. Traverso, A framework for planning with extended goals and partial observability, in: Proceedings of ICAPS-03, 2003 P. Bertoli, A. Cimatti, M. Roveri, Conditional planning under partial observability as heuristic-symbolic search in belief space, in: Proceedings of the European Conference on Planning (ECP), 2001 Bertoli, 2001, Heuristic search + symbolic model checking = efficient conformant planning, 467 Bertoli, 2001, Planning in nondeterministic domains under partial observability via symbolic model checking, 473 P. Bertoli, A. Cimatti, J. Slaney, S. Thiebaux, solving power supply restoration problems with planning via model checking, in: Proceedings of ECAI-02, 2002 P. Bertoli, A. Cimatti, P. Traverso, Interleaving execution and planning for nondeterministic, partially observable domains, in: Proceedings of ECAI-04, 2004 Boutilier, 1999, Decision-theoretic planning: structural assumptions and computational leverage, J. Artificial Intelligence Res. (JAIR), 11, 1 Blum, 1997, Fast planning through planning graph analysis, Artificial Intelligence 1–2, 90, 279 B. Bonet, H. Geffner, Learning sorting and decision trees with POMDPs, in: Proceedings of the International Conference on Machine Learning (ICML), 1998 Bonet, 2000, Planning with incomplete information as heuristic search in belief space, 52 Bonet, 2000, Planning with incomplete information as heuristic search in belief space, 52 Bonet, 2003, Labeled RTDP: improving the convergence of real-time dynamic programming, 12 B. Bonet, H. Geffner, An algorithm better than AO*, in: Proceedings of 20th National Conf. on Artificial Intelligence (AAAI-05), 2005, pp. 1343–1348 R. Brafman, J. Hoffmann, Conformant planning via heuristic forward search: a new approach, in: Proceedings of ICAPS-04, 2004 Bacchus, 2000, Using temporal logic to express search control knowledge for planning, Artificial Intelligence, 116, 123, 10.1016/S0004-3702(99)00071-5 D. Bryce, S. Kambhampati, Heuristic guidance measures for conformant planning, in: Proceedings of ICAPS'03 Workshop on Planning under Uncertainty and Incomplete Information, Trento, Italy, 2003 C. Boutilier, A POMDP formulation of preference elicitation problems, in: AAAI/IAAI Proceedings, 2002 P. Bertoli, M. Pistore, Planning with extended goals and partial observability, in: Proceedings of ICAPS-04, 2004 Brace, 1990, Efficient implementation of a BDD package, 40 Bryant, 1986, Graph-based algorithms for boolean function manipulation, IEEE Trans. Comput., C-35, 677, 10.1109/TC.1986.1676819 Bryant, 1991, On the complexity of VLSI implementations and graph representations of boolean functions with application to integer multiplication, IEEE Trans. Comput., 40, 205, 10.1109/12.73590 Bryant, 1992, Symbolic boolean manipulation with ordered binary-decision diagrams, ACM Comput. Surv., 24, 293, 10.1145/136035.136043 Bonet, 2003, GPT meets PSR, 102 Cimatti, 2000, NuSMV: a new symbolic model checker, Internat. J. Software Tools Technol. Transfer (STTT), 2 Clarke, 1986, Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Trans. Programming Languages Systems, 8, 244, 10.1145/5397.5399 Castellini, 2003, SAT-based planning in complex domains: concurrency, constraints and nondeterminism, Artificial Intelligence J., 147, 85, 10.1016/S0004-3702(02)00375-2 Cassandra, 1994, Acting optimally in partially observable stochastic domains O. Coudert, J.C. Madre, H. Touati, TiGeR version 1.0 user guide, Digital Paris Research Lab, December 1993 Cimatti, 2003, Weak, strong, and strong cyclic planning via symbolic model checking, Artificial Intelligence, 147, 35, 10.1016/S0004-3702(02)00374-0 Cimatti, 2000, Conformant planning via symbolic model checking, J. Artificial Intelligence Res. (JAIR), 13, 305, 10.1613/jair.774 Cimatti, 2004, Conformant planning via symbolic model checking and heuristic search, Artificial Intelligence, 159, 127, 10.1016/j.artint.2004.05.003 Cimatti, 1998, Strong planning in non-deterministic domains via model checking Clarke, 1996, Formal methods: state of the art and future directions, ACM Comput. Surv., 28, 626, 10.1145/242223.242257 Dal Lago, 2002, Planning with a language for extended goals, 447 De Giacomo, 1999, Automata-theoretic approach to planning for temporally extended goals Eiter, 2003, A logic programming approach to knowledge-state planning, Artificial Intelligence, 144, 157, 10.1016/S0004-3702(02)00367-3 S. Edelkamp, M. Helmert, On the implementation of MIPS, in: AIPS-Workshop on Model-Theoretic Approaches to Planning, 2000, pp. 18–25 Fagin, 1995 Goldsmith, M. Mundhenk, Complexity issues in Markov decision processes, in: Proceedings of 13th Conference on Computational Complexity, 1998 Goldman, 1997, Dynamic abstraction planning, 680 R.P. Goldman, D.J. Musliner, M.J. Pelican, Using model checking to plan hard real-time controllers, in: Proceeding of the AIPS2k Workshop on Model-Theoretic Approaches to Planning, Breckeridge, CO, 2000 M. Genesereth, I. Nourbakhsh, Time-saving tips for problem solving with incomplete information, in: Proceedings of the National Conference on Artificial Intelligence, 1993 R.P. Goldman, M. Pelican, D.J. Musliner, Hard real-time mode logic synthesis for hybrid control: a CIRCA-based approach, 1999. Working notes of the 1999 AAAI Spring Symposium on Hybrid Control N. Hyafil, F. Bacchus, Conformant probabilistic planning via CSPs, in: Proceedings of ICAPS-03, 2003 J. Hoffmann, R. Brafman, Contingent planning via heuristic forward search with implicit belief states, in: Proceedings of ICAPS-05, 2005 A. Herzig, J. Lang, P. Marquis, Action representation and partially observable planning using epistemic logic, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-03), Acapulco, Mexico, 2003 Hoey, 1999, SPUDD: Stochastic planning using decision diagrams, 279 Hansen, 2001, LAO*: a heuristic search algorithm that finds solutions with loops, Artificial Intelligence, 129, 35, 10.1016/S0004-3702(01)00106-0 Jimenez, 2000, An efficient algorithm for searching implicit AND/OR graphs with cycles, Artificial Intelligence, 124, 1, 10.1016/S0004-3702(00)00063-1 Jensen, 2000, OBDD-based universal planning for synchronized agents in non-deterministic domains, J. Artificial Intelligence Res. (JAIR), 13, 189, 10.1613/jair.649 R.M. Jensen, M.M. Veloso, M.H. Bowling, OBDD-based optimistic and strong cyclic adversarial planning, in: Proceedings of ECP-01, 2001 Karlson, 2001, Conditional progressive planning under uncertainty Kabanza, 1997, Planning control rules for reactive agents, Artificial Intelligence, 95, 67, 10.1016/S0004-3702(97)00031-3 Kushmerick, 1995, An algorithm for probabilistic planning, Artificial Intelligence, 76, 239, 10.1016/0004-3702(94)00087-H Kaelbling, 1998, Planning and acting in partially observable stochastic domains, Artificial Intelligence, 101, 99, 10.1016/S0004-3702(98)00023-X H.A. Kautz, B. Selman, Pushing the envelope: planning, propositional logic, and stochastic search, in: Proceedings of AAAI-96, Portland, OR, 1996 Koenig, 1998, Solving robot navigation problems with initial pose uncertainty using real-time heuristic search, 145 Mahanti, 1985, AND/OR graph heuristics search methods, J. ACM, 32, 28, 10.1145/2455.2459 McMillan, 1993 S. Majercik, M. Littman, MAXPLAN: a new approach to probabilistic planning, in: Proceedings of AIPS-1998, 1998 A. Martelli, U. Montanari, Additive AND/OR graphs, in: Proceedings of IJCAI-73, Stanford, CA, 1973, pp. 1–11 Martelli, 1978, Optimising decision trees through heuristically guided search, Comm. ACM, 21, 1025, 10.1145/359657.359664 Nillson, 1980 P. Poupart, C. Boutilier, Value-directed belief state approximation for POMDPs, in: Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), 2000 P. Poupart, C. Boutilier, Vector-space analysis of belief-state approximation for POMDPs, in: Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), 2001 R. Petrick, F. Bacchus, A knowledge-based approach to planning with incomplete information and sensing, in: Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS-02), 2002 R. Petrick, F. Bacchus, Extending the knowledge-based approach to planning with incomplete information and sensing, in: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS-04), 2004, pp. 2–11 Pryor, 1996, Planning for contingency: a decision based approach, J. Artificial Intelligence Res., 4, 81, 10.1613/jair.277 Peot, 1992, Conditional nonlinear planning, 189 Papadimitriou, 1987, The complexity of Markov decision processes, Math. Oper. Res., 12, 441, 10.1287/moor.12.3.441 M. Pistore, P. Traverso, Planning as model checking for extended goals in non-deterministic domains, in: Proceedings of IJCAI-01, Seattle, WA, 2001 Rintanen, 1999, Constructing conditional plans by a theorem-prover, J. Artificial Intellegence Res., 10, 323, 10.1613/jair.591 Rintanen, 1999, Improvements to the evaluation of quantified boolean formulae, 1192 J. Rintanen, Backward plan construction for planning as search in belief space, in: Proceedings of the International Conference on AI Planning and Scheduling (AIPS), 2002 Rintanen, 2004, Complexity of planning with partial observability, 345 Rintanen F. Somenzi, CUDD: CU decision diagram package—release 2.1.2. Department of Electrical and Computer Engineering—University of Colorado at Boulder, April 1997 Sondik, 1978, The optimal control of partially observable Markov decision processes over the infinite horizon: discounted costs, Oper. Res., 26, 282, 10.1287/opre.26.2.282 S. Thiebaux, M.O. Cordier, Supply restoration in power distribution systems: a benchmark for planning under uncertainty, in: Proceedings of ECP-01, 2001 Thiebaux, 2003, In defense of PDDL axioms Tovey, 2000, Gridworlds as testbeds for planning with incomplete information, 819 S. Thiebaux, F. Kabanza, J. Slaney, Anytime state-based solution methods for decision processes with non-Markovian rewards, in: Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), 2002 Weld, 1998, Extending graphplan to handle uncertainty and sensing actions and sensing actions, 897 B. Yang, R.E. Bryant, D.R. O'Hallaron, A. Biere, O. Coudert, G. Janssen, R.K. Ranjan, F. Somenzi, A performance study of BDD-Based model checking, in: Proceedings of the Formal Methods on Computer-Aided Design, 1998, pp. 255–289