计算机科学 ›› 2014, Vol. 41 ›› Issue (10): 266-269.doi: 10.11896/j.issn.1002-137X.2014.10.056

• 人工智能 • 上一篇    下一篇

信息传递法求不确定系统中的状态可达关系

劳佳琪,文中华,伍小辉,李洋   

  1. 湘潭大学信息工程学院 湘潭411105;湘潭大学信息工程学院 湘潭411105;湘潭大学信息工程学院 湘潭411105;湘潭大学信息工程学院 湘潭411105
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受国家自然科学基金资助

Method of Information Delivery for State Accessibility in Non-determinate System

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

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

摘要: 在不确定规划领域中,在求规划问题的解时,由于缺少引导信息,会导致许多无用状态和动作被搜索,造成冗余计算。所以在求规划解之前,找到不确定状态转移系统中状态之间的可达关系是很有意义的。以往的算法是通过矩阵相乘来模拟状态转移,但该类算法对于规模较大的系统开销较大。因此,提出了用信息传递法来求解可达关系,用矩阵来模拟不确定状态转移系统。其中每个状态记录了其他状态到达该状态的可达信息,通过状态之间的可达信息的传递,求得不确定系统的状态可达关系,以避免大量的矩阵运算。通过实验对比表明,当不确定系统规模较大时,所设计的算法优于矩阵相乘的算法。

关键词: 不确定规划,可达关系,信息传递

Abstract: In the field of non-determinate planning,when solving planning problems,due to lack of guidance information,the search will lead to many unwanted states and actions,resulting in the redundant calculations.So before seeking planning solution, it is significant to find up to the reachability relations between states in an indeterminate state transfer system.Previous algorithm is simulated by the state transition matrix multiplication,but such algorithm for large-scale system overhead is large.Therefore we proposed the method of information transmission to solve state accessibility with the matrix analog uncertain system.Each state records reachability information that the other states reach the state,and by passing reachability information between states,seek relationship between status in uncertain system to avoid a large number of matrix operations.Contrastive experiments show that the algorithm is superior to the design matrix multiplication algorithm.

Key words: Non-determinate planning,State accessibility,Information delivery

[1] Weld D S.Recent advances in AI planning[J].AI Magazine,1999,20(2):93-123
[2] Cimatti A,Roved M,Traverso P.Strong planning in nondeterministic domains via model checking[C]∥Proceedings of the 4th International Conference on AI Planning Systems.1998:36-43
[3] Cimatti A,Roveri M.Conformant planning via symbolic model checking[J].Journal of Artificial Intelligence Research,2000,3(3):305-338
[4] Wen Zhong-hua,Huang Wei,Liu Ren-ren.Method of hierarchical states in planning based on model checking[J].Journal of Software,2009,20(4):858-869
[5] Cimatti A,Pistore M,Roveri M,et al.Weak,strong,and strong cyclic planning via symbolic model checking[J].Artificial Intelligence,2003,47(1):35-84
[6] 黄丽芳,文中华,胡雨隆,等.不确定规划中状态循环可达关系的求解方法[J].计算机应用研究,2013,0(9):2689-2693
[7] 胡雨隆,文中华,常青,等.不确定规划中状态非循环可达关系的求解方法[J].计算机仿真,2012,9(5):114-117
[8] Huang Wei,Wen Zhong-hua,Jiang Yun-fei,et al.Observationreduction for strong plans[C]∥Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07).2007:1930-1935
[9] 文中华,黄巍,刘任任,等.模型检测规划中的状态之间的可达关系研究[J].计算机学报,2012,5(8):1634-1643
[10] 谢希仁.计算机网络(第五版)[M].北京.电子工业出版社,2007:147-152

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!