计算机科学 ›› 2016, Vol. 43 ›› Issue (4): 202-205.doi: 10.11896/j.issn.1002-137X.2016.04.041
陈秋茹,文中华,袁润,戴良伟
CHEN Qiu-ru, WEN Zhong-hua, YUAN Run and DAI Liang-wei
摘要： 不确定规划研究的最终目标是求出规划解,但是由于缺少引导信息,直接求规划解会导致大量的无用状态和动作被搜索。获得状态间的可达关系可以避免冗余计算。目前求可达关系的方法效率较低,因此设计了一种求可达关系的新方法。将不确定状态转移系统抽象成一个图,在这个图中,查找状态之间的可达信息是否形成一个有向环。若存在一个有向环,说明环内每两个状态之间都有可达关系。将其中一个状态作为父节点,并且将这个环内所有状态的可达关系记录在父节点中,通过访问父节点的可达信息更新环内状态的可达信息,减少了许多无用的状态和动作被搜索。实验结果表明,所设计的算法不仅能得到更全面的可达关系,而且效率也高于已有的算法。
| [1] Jameson A.Numerical uncertainty management in user andstudent modeling:An overview of systems and issues[J].User Modeling and User-Adapted Interaction,1995,5(3):193-251 [2] Vinnicombe G.Frequency domain uncertainty and the graph topology[J].IEEE Transactions on Automatic Control,1993,8(9):1371-1382 [3] Peng Jin,Liu Bao-ding.Uncertain Programming:Current Status and Future Prospects[J].Operations Research and Manage-ment Science,2002,11(2):1-10(in Chinese) 彭锦,刘宝碇.不确定规划的研究现状及其发展前景[J].运筹与管理,2002,11(2):1-10 [4] Liu Bao-ding,Zhao Rui-qing.Uncertain Programming and Further Research Problems[J].Journal of Institute of Command and Technology,1999,10(6):102-105(in Chinese) 刘宝碇,赵瑞清.不确定规划及进一步的研究问题[J].指挥技术学院学报,1999,10(6):102-105 [5] Mattmüller R,Nebel B.Informed Progression Search for Fully Observable Nondeterministic Planning[D].University at sbibliothek Freiburg,2013 [6] Bertoli P,Cimatti A,Roveri M,et al.Planning in nondeterministic domains under partial observability via symbolic model checking[C]∥IJCAI,2001.2001:473-478 [7] Da Silva F A G,Ciarlini A E M,Siqueira S W M.Nondeterministic planning for generating interactive plots[M].Springer Berlin:Heidelberg,2010:133-143 [8] Fu J,Ng V,Bastani F B,et al.Simple and fast strong cyclic planning for fully-observable nondeterministic planning problems[J].IJCAI Proceedings-International Joint Conference on Artificial Intelligence,2011,22(3):1949 [9] Wen Zhong-hua,Huang Wei,Liu Ren-ren,et al.Research onState Reachability in Planning Based on Model Checking[J].Chinese Journal of Computers,2012,35(8):1634-1643(in Chinese) 文中华,黄巍,刘任任,等.模型检测规划中的状态之间的可达关系研究[J].计算机学报,2012,35(8):1634-1643 [10] Lao Jia-qi,Wen Zhong-hua,Wu Xiao-hui,et al.Method of Information Delivery for State Accessibility in Non-Determinate System[J].Computer Science,2014,1(10):266-269(in Chinese) 劳佳琪,文中华,伍小辉,等.信息传递法求不确定系统中的状态可达关系[J].计算机科学,2014,1(10):266-269 [11] Yuan Ye,Wang Guo-ren.Answering threshold-based reachability queries over probabilistic graphs[J].Chinese Journal of Computers,2010,3(12):2219-2228 [12] Huang Li-fang,Wen Zhong-hua,Hu Yu-long,et al.Method of getting circular reachability relation in non-determinate panning[J].Application Research of Computers,2013,0(9):2689-2693(in Chinese) 黄丽芳,文中华,胡雨隆,等.不确定规划中状态循环可达关系的求解方法[J].计算机应用研究,2013,0(9):2689-2693 [13] Yuan Ye,Wang Guo-ren.Answering probabilistic reachabilityqueries over uncertain graphs[J].Chinese Journal of Compu-ters,2010,3(8):1378-1386 [14] Hu Yu-long,Wen Zhong-hua,Chang Qing,et al.Method of Get State Accessibility of Non-Cyclic in Non-Determinate Plan[J].Computer Simulation,2012,9(5):114-117(in Chinese) 胡雨隆,文中华,常青,等.不确定规划中状态非循环可达关系的求解方法[J].计算机仿真,2012,9(5):114-117 [15] Zhang Shuo,Gao Hong,Li Jian-zhong,et al.Efficient QueryProcessing on Uncertain Graph Databases[J].Chinese Journal of Computers,2009,32(10):2066-2079(in Chinese) 张硕,高宏,李建中,等.不确定图数据库中高效查询处理[J].计算机学报,2009,32(10):2066-2079 |
| No related articles found! |
|
||
首页