Computer Science ›› 2016, Vol. 43 ›› Issue (4): 202-205.doi: 10.11896/j.issn.1002-137X.2016.04.041

Previous Articles     Next Articles

Solving Reachability Relationship by Property of Directed Cycle

CHEN Qiu-ru, WEN Zhong-hua, YUAN Run and DAI Liang-wei   

  • Online:2018-12-01 Published:2018-12-01

Abstract: The goal of non-deterministic planning is getting the planning solution.Due to the lack of the helpful information,searching the problem space directly leads to a large number of useless work,which can be reduced dramatically by capturing the reachability relationship between states.But current methods perform poorly with respect to efficiency,thus we designed a new algorithm.We built a graph from the non-deterministic system,and checked whether there are some paths between states leading to some cycles.We concluded that every two states in the cycle are mutually reachable,if such a cycle does exist.We could treat vertex as the parent,and tagged it with the reachability relationships.By using this relationships and updating the reachability information of the states in the cycle,we could prevent many useless states to be searched.The experimental results show that the designed algorithm not only gains more complete reachability relationships,but also outperforms the current algorithms in efficiency.

Key words: Non-deterministic planning,Reachability relationship,Directed graph

[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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!