基于路标隐式分解的前向搜索规划方法

Abstract
Figure/Table
References (0)
Related Citation (15)

Download: PDF (416 KB) HTML (1 KB)
Export: BibTeX | EndNote (RIS)

Abstract

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.

Key words： Landmark Counting Heuristic Implicit Decomposition Forward Search Plan Fragment

Received: 14 August 2012

ZTFLH:

TP181

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	WEI Wei
	OUYANG Dan Tong

Cite this article:

WEI Wei,OUYANG Dan Tong. Forward Search Planning Based on Implicit Decomposition with Landmarks[J]. , 2013, 26(6): 513-520.

URL:

http://manu46.magtech.com.cn/Jweb_prai/EN/ OR http://manu46.magtech.com.cn/Jweb_prai/EN/Y2013/V26/I6/513

［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