计算机科学 ›› 2015, Vol. 42 ›› Issue (2): 228-232.doi: 10.11896/j.issn.1002-137X.2015.02.047
伍小辉,文中华,李洋,劳佳琪
WU Xiao-hui, WEN Zhong-hua, LI Yang and LAO Jia-qi
摘要: 在不确定规划领域中,以往对强规划解的研究侧重于解本身,很少考虑不确定转移系统执行动作所需的代价;而已有的研究最小权值强规划解的算法效率不高。针对这一问题,引入模型检测的强规划分层方法,设计了一种快速求解最小权值强规划解的算法。该算法首先将不确定规划问题中的状态进行强规划分层,然后利用分层信息反向搜索最小权值强规划解;且在搜索的过程中,根据算法策略,实时更新所需搜索层数的上界和下界,从而避免了大量的无用搜索,提高了搜索效率。实验表明:所设计的算法能快速求解出最小权值强规划解,求解效率比已有的直接求解最小权值强规划解的算法高;且分层数和动作数越大,优势越明显。
[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! |
|