Forward Search Planning Based on Implicit Decomposition with Landmarks
WEI Wei,OUYANG Dan Tong
College of Computer Science and Technology,Jilin University,Changchun 130012
Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education,Jilin University,Changchun 130012
A planning algorithm that implicitly decomposes the forward search procedure with landmark information is proposed. The original planning task is decomposed into several smaller sub tasks according to the estimation of the landmark counting heuristic. Whenever the search visits a state with lower heuristic value,a sub task is completed.The procedure is iterated until the estimation of the landmark counting heuristic reduces to zero. The plan fragments of all the sub tasks are connected into the final solution. The experimental results show the superiority of the proposed algorithm. The implicit task decomposition is introduced by the landmark counting heuristic. Therefore,compared with the existing decomposition methods that treat landmarks as mandatory subgoals,the proposed algorithm guides the forward search procedure faster,cuts down the search space dramatically and makes considerable improvement in both planning efficiency and planning quality.
［1］Gerevini A E,Haslum P,Long D,et al.Deterministic Planning in the Fifth International Planning Competition: PDDL3 and Experimental Evaluation of the Planners. Artificial Intelligence,2009,173(5/6): 619-668
［2］Bryce D,Cushing W,Kambhampati S. State Agnostic Planning Graphs: Deterministic,Non Deterministic,and Probabilistic Planning. Artificial Intelligence,2011,175(3/4): 848-889
［3］Wu Xiangjun,Jiang Yunfei,Ling Yingbiao. Research and Development of StepByStep AI Planner. Journal of Software,2008,19(9): 2243-2264(in Chinese)
(吴向军,姜云飞,凌应标.智能规划器StepByStep的研究与开发.软件学报,2008,19(9): 2243-2264)
［4］Cai Dunbo,Yin Minghao,Gu Wenxiang,et al. Fast Forward Planning System Based on Delayed Partly Reasoning. Chinese Journal of Computers,2008,31(5): 793-802(in Chinese)
(蔡敦波,殷明浩,谷文祥,等.基于延迟部分推理的快速前向规划系统.计算机学报,2008,31(5): 793-802)
［5］Helmert M,Geffner H. Unifying the Causal Graph and Additive Heuristics // Proc of the 18th International Conference on Automated Planning and Scheduling. Sydney,Australia,2008: 140-147
［6］Porteous J,Sebastia L,Hoffmann J. On the Extraction,Ordering,and Usage of Landmarks in Planning // Proc of the 6th European Conference on Planning. Toledo,Spain,2001: 37-48
［7］Sebastia L,Onaindia E,Marzal E. Decomposition of Planning Problems. AI Communications,2006,19(1): 49-81
［8］Hoffmann J,Porteous J,Sebastia L. Ordered Landmarks in Planning. Journal of Artificial Intelligence Research,2004,22: 215-278
［9］Richter S,Helmert M,Westphal M. Landmarks Revisited // Proc of the 23rd AAAI Conference on Artificial Intelligence. Chicago,USA,2008: 975-982
［10］Karpas E,Domshlak C. Cost Optimal Planning with Landmarks // Proc of the 21st International Joint Conference on Artificial Intelligence. Pasadena,USA,2009: 1728-1733
［11］Bonet B,Helmert M. Strengthening Landmark Heuristics via Hitting Sets // Proc of the 19th European Conference on Artificial Intelligence. Lisbon,Portugal,2010: 329-334
［12］Richter S,Westphal M. The LAMA Planner: Guiding Cost Based Anytime Planning with Landmarks. Journal of Artificial Intelligence Research,2010,39: 127-177
2013, Vol. 26 
