Computer Science ›› 2017, Vol. 44 ›› Issue (1): 235-242, 270.doi: 10.11896/j.issn.1002-137X.2017.01.044

Previous Articles     Next Articles

Decomposition Strategy for Knowledge Tree of Predicate Based on Static Preconditions

BIAN Rui, WU Xiang-jun and CHEN Ai-xiang   

  • Online:2018-11-13 Published:2018-11-13

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

[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.

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .