Computer Science ›› 2015, Vol. 42 ›› Issue (2): 228-232.doi: 10.11896/j.issn.1002-137X.2015.02.047

Previous Articles     Next Articles

Solving Minimal Cost Strong Planning Solution by Hierarchical Algorithm

WU Xiao-hui, WEN Zhong-hua, LI Yang and LAO Jia-qi   

  • Online:2018-11-14 Published:2018-11-14

Abstract: In nondeterministic planning areas,previous studies on the strong planning solution focused on the solution itself,with little regard for the required cost of nondeterministic transfer system performing an action,and the algorithms’ efficiency which exists is not high.Aiming at this problem,we introduced a strong planning hierarchical method in model-checking,designed an algorithm to solve the minimal cost strong planning solution quickly.Firstly,this algorithm uses strong planning hierarchical method to get hierarchical states of nondeterministic problem,and then it reversely searches the minimal cost strong planning solution by using the hierarchical information.In the search process,according to the algorithm strategy,the upper and lower bounds of required searching layer are real-time updated to avoid a lot of useless search,improving search efficiency.Experimental results show that this algorithm can not only solve the minimal cost strong planning solution quickly and precisely,but also run more efficient than existing algorithms.And the greater the number of layers and the number of actions,the more obvious the advantages.

Key words: Nondeterministic planning,Minimal cost strong planning solution,Model-checking,Strong planning hierarchical method

[1] Ghallab M,Nau D,Traverso P.Automated Planning Theory and Practice[M].Massachusetts:Morgan Kaufmann Publishers,2004:1101-1132
[2] 丁德路,姜云飞.智能规划及其应用的研究[J].计算机科学,2002,29(2):100-103
[3] Da Silva F A G,Ciarlini A E M,Siqueira S W M.Nondeterministic planning for generating interactive plots[M].Berlin:Springer Berlin Heidelberg,2010:133-143
[4] Patrizi F,Lipovetzky N,Geffner H.Fair LTL synthesis for non-deterministic systems using strong cyclic planners[C]∥Proceedings of the Twenty-Third international joint conference on Artificial Intelligence.USA:AAAI Press,2013:2343-2349
[5] Fu J,Bastani F B,et al.Simple and fast strong cyclic planning for fully-observable nondeterministic planning problems[C]∥IJCAI Proceedings-International Joint Conference on Artificial Intelligence.2011:1949-1954
[6] 薛晗.不确定规划的群体智能计算[D].长沙:国防科学技术大学,2009
[7] Cimatti A,Roveri M,Traverso P.Strong planning in nondeterministic domains via model checking[C]∥Proceedings of the 4th International Conference on Artificial Intelligence Planning Systems (AIPS’ 98).USA:Carnegie Mellon University,1998:36-43
[8] Cimatti A,Pistore M,Roveri M,et al.Weak,strong,and strong cyclic planning via symbolic model checking[J].Artificial Intelligence,2003,147(1/2):35-84
[9] Cimatti A,Roveri M.Conformant planning via model checking andheuristic search[J].Artificial Intelligence,2004,159(1/2):127-206
[10] 文中华,黄巍,刘任任,等.模型检测规划中的状态分层方法[J].软件学报,2009,20(4):858-869
[11] Bertoli P,Cimatti A,Roveri M,et al.Strong planning under partial observability[J].Artificial Intelligence,2006,170(4/5):337-384
[12] 唐杰,文中华,汪泉,等.不确定可逆规划的强循环规划解[J].计算机研究与发展,2013,50(9):1970-1980
[13] Huang Wei,Wen Zhong-hua,Jiang Yun-fei,et al.Observation reduction for strong plans[C]∥Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07).India:IJCAI,2007:1930-1935
[14] 陈建林,文中华,马丽丽,等.一种求解最小权值强规划的方法[J].计算机工程,2011,37(17):167-171

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 .