基于静态前提的谓词知识树分解策略

doi:10.11896/j.issn.1002-137X.2017.01.044

摘要/Abstract

摘要： 智能规划问题实质是一种搜索问题,通常需采用某种策略来缩小搜索空间,提高规划效率。在“以谓词为主体”的规划求解方法中,规划树的生成效率将直接影响规划求解效率。为此,提出了基于静态前提的谓词知识树分解策略,并给出了相应的分解算法。对任意一个规划领域,利用该分解算法可将知识树分解成若干个较小规模的知识子树。在规划求解的过程中,利用知识子树可有效地减少搜索空间,从而快速生成规划树,提高规划效率。同时,利用知识子树还可提取出隐含在动作描述中的领域知识。实验结果表明该分解算法是有效的。

关键词: 智能规划,知识树,静态前提,分解策略

Abstract: AI planning is essentially a search problem,usually using some strategies to reduce the search space,improving planning efficiency.In the planning method of taking the predicate as target,the efficiency of planning tree generation will affect planning efficiency directly.Therefore,this paper proposesd a decomposition strategy for knowledge tree of predicate based on the static preconditions,and gave the corresponding decomposition algorithm.For any domain,using the algorithm,knowledge tree of predicate can be decomposed into a number of smaller knowledge sub-trees.The use of knowledge sub-trees in planning process can reduce the search space effectively,thus generating plan tree quickly and improving the planning efficiency.At the same time,the domain knowledge is extracted from the domain with them.Finally,the experiment results show that decomposition algorithm is efficient.

Key words: AI planning,Knowledge tree,Static precondition,Decomposition strategy

边芮,吴向军,陈蔼祥. 基于静态前提的谓词知识树分解策略[J]. 计算机科学, 2017, 44(1): 235-242. https://doi.org/10.11896/j.issn.1002-137X.2017.01.044

BIAN Rui, WU Xiang-jun and CHEN Ai-xiang. Decomposition Strategy for Knowledge Tree of Predicate Based on Static Preconditions[J]. Computer Science, 2017, 44(1): 235-242. https://doi.org/10.11896/j.issn.1002-137X.2017.01.044

参考文献

[1] KUTLUHAN E,DANA S N,SUBRAHMANIAN V S.Com-plexity,Decidability and Undecidability Results for Domain-Independent Planning[J].Artificial Intelligence,1995,76(1/2):75-88.
[2] ROBERTS M,HOWE A.Learning from planner performance[J].Artificial Intelligence,2009,173(5/6):536-561.
[3] HELMERT M,RGER G.How good is almost perfect[C]∥Proceedings of the 23rd National Conference on Artificial Intelligence,2008.Menlo Park:AAAI Press,2008:944-949.
[4] HOFFMANN J,NEBEL B.The FF planning system:Fast plan generation through heuristic search[J].Journal of Artificial Intelligence Research,2001,4:253-302.
[5] CAI Dun-bo,YIN Ming-hao,GU Wen-xiang,et al.Fast forward planning system based on delayed partly reasoning[J].Chinese Journal of Computers,2008,1(5):793-802.(in Chinese) 蔡敦波,殷明浩,谷文祥,等.基于延迟部分推理的快速前向规划系统[J].计算机学报,2008,1(5):793-802.
[6] LIANG Rui-shi,JIANG Yun-fei,BIAN Rui,et al.A High-Qua-lity Domain- Independent Pruning Strategy for Forward-Chaining Planning [J].Chinese Journal of Computers,2012,5(8):1620-1633.(in Chinese) 梁瑞仕,姜云飞,边芮,等.一种高质量的领域无关前向规划剪枝策略[J].计算机学报,2012,5(8):1620-1633.
[7] WEI Wei,OUYANG Dan-tong,LV Shuai.Conformant planning based on reducing belief states[J].Journal of Software,2013,4(7):1557-1570.(in Chinese) 魏唯,欧阳丹彤,吕帅.基于缩减信念状态的Conformant规划方法[J].软件学报,2013,4(7):1557-1570.
[8] KOEHLER J,HOFFMANN J.On reasonable and forced goal orderings and their use in an agenda-driven planning algorithm[J].Journal of Artificial Intelligence Research,2000,12:338-386.
[9] RICHTER S,WESTPHAL M.The LAMA planner:Guidingcost-based anytime planning with landmarks[J].Journal of Artificial Intelligence Research,2010,9:127-177.
[10] LIANG Rui-shi,JIANG Yun-fei,BIAN Rui,et al.Admissiblesubgoal ordering for automated planning[J].Journal of Software,2011,22(5):914-928.(in Chinese) 梁瑞仕,姜云飞,边芮,等.智能规划中的可纳子目标排序[J].软件学报,2011,2(5):914-928.
[11] KNOBLOCK C.Automatically generating abstractions for planning[J].Artificial Intelligence,1994,68(2):243-302.
[12] LANSKY A,GETOOR L.Scope and abstraction:two criteriafor localized planning[C]∥Proceedings of the 14th International Joint Conference on Artificial Intelligence,1995.San Francisco:Morgan Kaufmann,1995:1612-1619.
[13] AMIR E,ENGELHARDT B.Factored planning[C]∥Procee-dings of the 18th International Joint Conference on Artificial Intelligence,2003.San Francisco:Morgan Kaufmann,2003:929-935.
[14] KELAREVA E,BUFFET O,HUANG J B,et al.Factored planning using decomposition trees[C]∥Proceedings of the 20th International Joint Conference on Artificial Intelligence,2007.Amsterdam:Elsevier Science,2007:1942-1947.
[15] CHEN Yi-xin,YAO Guo-hui.Completeness and Optimality Preserving Reduction for Planning[C]∥Proceedings of the 21st International Joint Conference on Artificial Intelligence,2009.Amsterdam:Elsevier Science,2009:1659-1664.
[16] CHEN Yi-xin,XU You,YAO Guo-hui.Stratified Planning[C]∥Proceedings of the 21st International Joint Conference on Artificial Intelligence,2009.Amsterdam:Elsevier Science,2009:1665-1670.
[17] CHEN Y X,WAH B W,HSU C W.Temporal planning using subgoal partitioning and resolution in SGPlan[J].Journal of Artificial Intelligence Research,2006,26:323-369.
[18] WAH B W,CHEN Y X.Constraint Partitioning in Penalty Formulations for Solving Temporal Planning Problems[J].Artificial Intelligence,2006,170(3):187-231.
[19] CROSBY M,ROVATSOS M,PETRICK R P A.Automated Agent Decomposition for Classical Planning[C]∥The Procee-dings of the 23rd International Conference on Autonomous Planning and Scheduling,2013.Menlo Park,Calif.AAAI Press 2013:46-54.
[20] ASAI M,FUKUNAGA A.Solving Large-Scale Planning Problems by Decomposition and Macro Generation[C]∥The proceedings of the 25th International Conference on Autonomous Planning and Scheduling,2015.Menlo Park,Calif.AAAI Press 2015:16-24.
[21] WU Xiang-jun,JIANG Yun-fei,LING Ying-biao.Research and development of StepByStep planner[J].Journal of Software,2008,19(9):2243-2264.(in Chinese) 吴向军,姜云飞,凌应标.智能规划器StepByStep的研究和开发[J].软件学报,2008,9(9):2243-2264.
[22] WU Xiang-jun,BIAN Rui,LING Ying-biao,et al.Research onDecomposition Strategy for Knowledge Tree of Characteristic Predicate[J].Journal of Computer Research and Development,2011,48(2):186-194.(in Chinese) 吴向军,边芮,凌应标,等.特征谓词知识树分解策略的研究[J].计算机研究与发展,2011,48(2):186-194.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed