[1]YAN Shu-ya,YIN Ming-hao,GU Wen-xiang,et al.Research and advances in probabilistic planning[J].CAAI Transactions on Intelligent Systems,2008,3(1):9-22.
Copy

Research and advances in probabilistic planning

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 3 Number of periods: 2008 1 Page number: 9-22 Column: 综述 Public date: 2008-02-25
Title:
Research and advances in probabilistic planning
Author(s):
YAN Shu-ya1;  YIN Ming-hao1; 2;  GU Wen-xiang1;  LIU X iao-fei1
1. School of Computer, Northeast Normal University, Changchun 130117, China;
?2. Colleg e of Computer Science and Technology, Jilin University, Changchun 130012, China
Keywords:
intelligent planning;  probabilistic planning;  dynami c programming;  PPDDL
CLC:
TP18
DOI:
-
Abstract:
Probabilistic planning has an important role in allowing intelligent planning to adapt to uncertainty. This paper introduces a new probabilistic plan domain def inition language (PPDDL), followed by its syntax and semantics. Various methods of probabilistic planning are described, such as dynamic programming a lgorithms, heuristic dynamic programming algorithms and algorithms based on plan ning graph. The features of each algorithm are then analyzed. Finally, we give a brief introduction to the international probabilistic planning competition. The conclusions in this paper should be helpful to researchers interested in this f ield.
References:
［1］ WELD D. Recent advances in AI planning［R］. UWCSE9810 01, 1999.
［2］ CIMATTI A, ROVERI M. Conformant planning via symbolic model checking［J］ . Journal of Artificial Intelligence Research, 2000, 13: 305338.
［3］ CIMATTI A, ROVERI M, BERTOLI P. Conformant planning via symbolic model ch e c king and heuristic search［J］. Artificial Intelligence, 2004, 159 (12):1272 0 6.
［4］ HOFFMAN J, BRAFTMAN R. Conformant planning via heuristic forward search: a new approach［J］. Artificial Intelligence, 2006, 170(67): 507541.
［5］ SMITH D, WELD D. Conformant graphplan［C］// Proceedings of 15th National C onference on Artificial Intelligence. Madison, Wisconsin, 1998.
［6］ WELD D, ANDERSON C, SMITH D. Extending graphplan to handle uncertainty & s en sing actions［C］// Proceedings of 15th National Conference on Artificial Intel li gence. Madison, Wisconsin, 1998. 
［7］ HOFFMANN J, BRAFMAN R I. Contingent planning via heuristic forward search wi th implicit belief states［C］// Proceedings of Fifteenth International Confere nc e on Automated Planning & Scheduling.［S.l.］：AAAI Press, 2005.
［8］ WAH B W, CHEN Y. Constrained partitioning in penalty formulations for sol v in g temporal planning problems［J］. Artificial Intelligence, 2006, 170(3): 1872 3 1.
［9］ CHEN Y, HSU C, WAH B. Temporal planning using subgoal partitioning and re s ol ution in SGplan［J］. Journal of Artificial Intelligence Research, 2006, 26: 323 369.
［10］FOX M, LONG D. PDDL2.1: an extension to PDDL for expressing temporal plan ni ng domains［J］. Journal of Artificial Intelligence Research, 2003, 20: 61124. 
［11］PHILIPPE L. Algorithms for propagating resource constraints in AI plannin g and scheduling: existing approaches and new results［J］. Artificial Intelligenc e, 2003, 143(2):151188.
［12］HANSEN E, ZILBERSTEIN S. LAO*: a heuristic search algorithm that finds so lutions with loops［J］. Artificial Intelligence, 2001, 129(12): 3562.
［13］BONET B, GEFFNER H. Improving the convergence of realtime dynamic program mi ng［C］// Proceedings of 13th International Conference on Automated Planning an d Scheduling(ICAPS). Trento, Italy, 2003.
［14］BONET B, GEFFNER H. An algorithm better than AO*?［C］// Proceedings of A A AI05. Pittsburgh, Pennsylvania： AAAI Press，2005.
［15］MCDERMOTT D. The 1998 AI planning systems competition［J］. AI Magazine, 2000, 21(2): 3555.
［16］GHALLAB M, HOWE A E, KNOBLOCK C A, et al. PDDLthe planning domain defini tion language［R］. CVC TR98003/DCS TR1165, 1998.
［17］YOUNES H, LITTMAN M L, WEISSMAN D, et al. The first probabilistic track o f the international planning competition［J］. Journal of Artificial Intelligence Research, 2005, 24: 851887.
［18］YOUNES H, LITTMAN M. The language for the probabilistic part of IPC4［C ］// Proceedings of International Planning Competition. Whistler, Canada, 2004 .
［19］DEARDEN R, BOUTILIER C. Abstraction and approximate decisiontheoretic pl anning［J］. Artificial Intelligence, 1997, 89(12):219283.
［20］BERTSEKAS D P. Dynamic programming and optimal control［M］. Belmont: Ath ena Scientific, 1995.
［21］BELLMAN R E. Dynamic programming［M］. Princeton: Princeton University Pr ess, 1957.
［22］RUSSELL S, NORVIG P.人工智能——一种现代方法［M］.2版.姜 哲, 金奕江, 译. 北京: 人民邮电出版社, 2004.
［23］BERTSEKAS D P. Dynamic programming: deterministic and stochastic models［ M］. New Jersey: PrenticeHall, 1987.
［24］BARTO A, BRADTKE S, SINGH S. Learning to act using realtime dynamic prog ramming［J］. Artificial Intelligence， 1995, 72(12): 81138.
［25］KORF R. Realtime heuristic search［J］. Artificial Intelligence, 1990, 4 2(23): 189211.
［26］GARDNER M. Mathematical games［J］. Sci Amer, 1973, 228(1): 108.
［27］WATKINS C J. Learning from delaye d rewards［ D］. Cambridge: Cambridge University, 1989.
［28］BONET B, GEFFER H. mGPT: a probabilistic planner based on heuristic searc h［J］. Journal of Artificial Intelligence Research, 2005, 24: 933944.
［29］BONET B，GEFFNER H. Faster heuristic search algorithms for planning with un certainty and full feedback［C］// Proceedings of the 18th International Joint Co nference on Artificial Intelligence. Acapulco, Mexico，2003.
［30］TARJAN R E. Depth first search and linear graph algorithms［J］. SIAM Jou rnal on Computing, 1972, 1(2): 146160.
［31］BONET B, GEFFNER H. Learning in depthfirst search: a unified approach to h euristic search in deterministic, nondeterministic, probabilistic, and game tr e e settings［R］. Caracas:Universidad Simon Bolivar, 2005.
［32］BONET B, GEFFNER H. Learning depthfirst search: a unified approach to he ur istic search in deterministic and nondeterministic settings, and its applicati o n to MDPs［C］// Proceedings of 16th International Conference on Automated Plan ni ng and Scheduling. Cumbria, UK, 2006.
［33］BUFFET O, ABERDEEN D. The factored policy gradient planner［C］// Proceed i ngs of the Fifth International Planning Competition. Cumbria, UK , 2006.
［34］MAUSAM, WELD D. Concurrent probabilistic temporal planning［C］// Interna t iona l Conference on Automated Planning and Scheduling (ICAPS). Monterey, CA, US A, 2005.
［35］BAXTER J, BARTLETT P, WEAVER L. Experiments with infinitehorizon［J］. J ournal of Artificial Intelligence Research, 2001, 15: 351381.
［36］YOUNES H L S, LITTMAN M L. An extension to PDDL for expressing planning d om ains with probabilistic effects［R］. CMUCS04167, Carnegi e M ellon University, 2004.
［37］FENG Z, HANSEN E. Symbolic heuristic search for factored Markov decis ion pr ocesses［C］// Proceedings of the 18th National Conference on Artificial Intell ig ence (AAAI02). Edmonton, Alberta, Canada, 2002.
［38］BLUM A, FURST M. Fast planning through planning graph analysis［J］. Arti ficial Intelligence, 1997, 90(1): 281300.
［39］YANG Q, WU K H, JIANG Y F. Learning action models from plan examples usin g weighted MAXSAT［J］. Artificial Intelligence, 2007, 171(23):107143.
［40］HUANG W, WEN Z H, JIANG Y F, et al. Observation reduction for strong pla ns ［C］// Proceedings of the 20th International Joint Conference on Artificial In te lligence. Hyderabad, India, 2007.
［41］陈蔼祥, 姜云飞, 张学农,等. GP基于规划图的遗传规划算法［J］. 计算机学报, 2007, 30 (1): 153160.
?CHEN Aixiang JIANG Yunfei, ZHANG Xuenong, et al. GP: genetic planning algori thm based on planning graph［J］.Chinese Journal of Computers, 2007, 30(1):153 1 60.
［42］SMITH D E, WELD D. Conformant graphplan［C］// Proceedings of 15t h National Co nference on Artificial Intelligence. Madison, Wisconsin, USA, 199 8.
［43］BLUM A, LANGFORD J. Probabilistic planning in the graphplan framework［C ］// P roceedings of the Fifth European Conference on Planning. Durham, UK, 19 99.
［44］GU W X, OU H J, LIU R X, et al. An improved probabilistic planning algori th m based on pgraphplan［C］// Proceedings of the Third International Conference on Machine Learning and Cybernetics. Shanghai, 2004.
［45］LITTLE I, BAUX S. Concurrent probabilistic planning in the graphplan fr amework［C］// The 16th International Conference on Automated Planning and Sche du ling(ICAPS). Cumbria, UK, 2006.
［46］SANNER S, BOUTILIER C. Probabilistic planning via linear valueapproximat io n of firstorder MDPs［C］// The 16th International Conference on Automated Pl an n ing and Scheduling(ICAPS). Cumbria,U K, 2006.
［47］REITER R. Knowledge in action: logical foundations for specifying and imp lementing dynamical systems［M］. Cambridge： MIT Press, 2001.
［48］BOUTILIER C, REITER R, PRICE B. Symbolic dynamic programming for firstor de r MDPs［C］// Proceedings of the 17th International Joint Conference on Artific ia l Intelligence. Seattle, WA, 2001.
［49］SANNER S, BOUTILIER C. Approximate linear programming for firstorder MDP s［M］. Arlington, Virginia： AUAI Press, 2005.
［50］GUESTRIN C, KOLLER D, PARR R, et al. Efficient solution methods for facto red MDPs［J］. Journal of Artificial Intelligence Research, 2002, 19: 399468. 
［51］KOENIGSBUCH F T, FABIANI P. Symbolic stochastic focused dynamic programmin g with decision diagrams［C］// Proceedings of International P lanning Competition. Cumbria, UK, 2006.
［52］BAHAR R I，FROHM E A, GAONA C M,et al. Algebraic decision diagrams and th ei r applications［C］// IEEE /ACM International Conference on CAD. Santa Cl ara, USA, 1993.
［53］HOEY J, STAUBIN R, HU A, et al. Optimal and approximate stochastic plann in g using decision diagrams［R］. TR200005, University of Bri ti sh Columbia, 2000.
［54］SOMENZI F. Cudd: cu decision diagram package release［Z］. University of Colorado at Boulder, 1998.
［55］DEAN T, KANAZAWA K. A model for reasoning about persistence and causation ［J］. Computational Intelligence, 1989, 5(3): 142150.
［56］YOON S W, FERN A, GIVAN R. Learning reactive policies for probabilistic p l anning domains［C］// Proceedings of International Planning Competition. W hi stler, CA, 200 4.
［57］BERTSEKAS D P, TSITSIKLIS J N. Neurodynamic programming［M］. Belmont: A thena Scientific, 1996.
［58］FERN A, YOON S, GIVAN R. Approximate policy iteration with a policy langu ag e bias［C］// Proceedings of the Neural Information Processing Conference. Ista nbulm, Turkey, 2003
［59］FERN A, YOON S, GIVAN R. Learning domainspecific control knowledge from ra ndom walks［C］// Proceedings of 14th International Conference on Automated Plan ning a nd Scheduling. Whistler, British Columbia, Canada, 2004.
［60］MAJERCIK S M, LITTMAN M L. Contingent planning under uncertainty via stoc hastic satisfiability［J］. Artificial Intelligence, 2003, 147(1): 119162.
［61］DAVIS M, LOGEMANN G, LOVELAND D. A machine program for theorem proving［J ］. Comm ACM 5, 1962，5(7)：394397.
［62］GIUNCHIGLIA E, KARTHA G N, LIFSCHITZ V. Representing action: indeterminac y and ramifications［J］. Artificial Intelligence, 1997, 95(2): 409438.
［63］YOUNES H S, LITTMAN M L, WEISSMAN D, et al. The first probabilistic track of the international planning competition［J］. Journal of Artificial Intelligen ce Research, 2005,24:851887.
［64］BONET B, GIVAN B. Results of probabilistic track in the 5 th international planning competition［C］// Proceedings of International Planing Competition. Cumbria, UK, 2006.
Similar References:

Memo

-

Last Update: 2009-05-09

Copyright © CAAI Transactions on Intelligent Systems