nips nips2013 nips2013-323 nips2013-323-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Tuan A. Nguyen, Subbarao Kambhampati, Minh Do
Abstract: Most current planners assume complete domain models and focus on generating correct plans. Unfortunately, domain modeling is a laborious and error-prone task, thus real world agents have to plan with incomplete domain models. While domain experts cannot guarantee completeness, often they are able to circumscribe the incompleteness of the model by providing annotations as to which parts of the domain model may be incomplete. In such cases, the goal should be to synthesize plans that are robust with respect to any known incompleteness of the domain. In this paper, we first introduce annotations expressing the knowledge of the domain incompleteness and formalize the notion of plan robustness with respect to an incomplete domain model. We then show an approach to compiling the problem of finding robust plans to the conformant probabilistic planning problem, and present experimental results with Probabilistic-FF planner. 1
[1] E. Amir and A. Chang. Learning partially observable deterministic action models. Journal of Artificial Intelligence Research, 33(1):349–402, 2008.
[2] D. Bryce, S. Kambhampati, and D. Smith. Sequential monte carlo in probabilistic planning reachability heuristics. Proceedings of ICAPS06, 2006.
[3] K. Delgado, S. Sanner, and L. De Barros. Efficient solutions to factored mdps with imprecise transition probabilities. Artificial Intelligence, 2011.
[4] C. Domshlak and J. Hoffmann. Probabilistic planning via heuristic forward search and weighted model counting. Journal of Artificial Intelligence Research, 30(1):565–620, 2007.
[5] T. Eiter, W. Faber, N. Leone, G. Pfeifer, and A. Polleres. Planning under incomplete knowledge. Computational LogicCL 2000, pages 807–821, 2000.
[6] M. Fox, R. Howey, and D. Long. Exploration of the robustness of plans. In Proceedings of the National Conference on Artificial Intelligence, volume 21, page 834, 2006.
[7] A. Garland and N. Lesh. Plan evaluation with incomplete action descriptions. In Proceedings of the National Conference on Artificial Intelligence, pages 461–467, 2002.
[8] R. Givan, S. Leach, and T. Dean. Bounded-parameter markov decision processes. Artificial Intelligence, 122(1-2):71–109, 2000.
[9] P. Gmytrasiewicz and P. Doshi. A framework for sequential planning in multiagent settings. Journal of Artificial Intelligence Research, 24(1):49–79, 2005.
[10] P. Gmytrasiewicz and E. Durfee. Rational coordination in multi-agent environments. Autonomous Agents and Multi-Agent Systems, 3(4):319–350, 2000.
[11] N. Hyafil and F. Bacchus. Conformant probabilistic planning via csps. In Proceedings of the Thirteenth International Conference on Automated Planning and Scheduling, pages 205–214, 2003.
[12] R. Jensen, M. Veloso, and R. Bryant. Fault tolerant planning: Toward probabilistic uncertainty models in symbolic non-deterministic planning. In Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS), volume 4, pages 235–344, 2004.
[13] S. Kambhampati. Model-lite planning for the web age masses: The challenges of planning with incomplete and evolving domain models. In Proceedings of the National Conference on Artificial Intelligence, volume 22, page 1601, 2007.
[14] D. Koller and N. Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[15] N. Kushmerick, S. Hanks, and D. Weld. An algorithm for probabilistic planning. Artificial Intelligence, 76(1-2):239–286, 1995.
[16] D. Morwood and D. Bryce. Evaluating temporal plans in incomplete domains. In Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012.
[17] A. Nilim and L. Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780–798, 2005.
[18] F. A. Oliehoek. Value-Based Planning for Teams of Agents in Stochastic Partially Observable Environments. PhD thesis, Informatics Institute, University of Amsterdam, Feb. 2010.
[19] J. Satia and R. Lave Jr. Markovian decision processes with uncertain transition probabilities. Operations Research, pages 728–740, 1973.
[20] S. Seuken and S. Zilberstein. Formal models and algorithms for decentralized decision making under uncertainty. Autonomous Agents and Multi-Agent Systems, 17(2):190–250, 2008.
[21] A. Shapiro and A. Kleywegt. Minimax analysis of stochastic problems. Optimization Methods and Software, 17(3):523–542, 2002.
[22] L. Valiant. The complexity of computing the permanent. Theoretical computer science, 8(2):189–201, 1979.
[23] L. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410–421, 1979.
[24] C. Weber and D. Bryce. Planning and acting in incomplete domains. Proceedings of ICAPS11, 2011.
[25] C. White III and H. Eldeib. Markov decision processes with imprecise transition probabilities. Operations Research, pages 739–749, 1994.
[26] Q. Yang, K. Wu, and Y. Jiang. Learning action models from plan examples using weighted max-sat. Artificial Intelligence, 171(2):107–143, 2007. 9