Research on state reachability in planning based on model checking

被引：0
作者：
Wen, Zhong-Hua [1 ]
Huang, Wei [2 ]
Liu, Ren-Ren [1 ]
Jiang, Yun-Fei [3 ]
机构：
[1] College of Information Engineering, Xiangtan University, Xiangtan
[2] School of Computer Science and Technology, University of Science and Technology of China
[3] Institute of Software, Sun Yat-Sen University
来源：
Jisuanji Xuebao/Chinese Journal of Computers | 2012年 / 35卷 / 08期
关键词：
Adjacency matrix; Hypergraph; Model checking; Planning under uncertainty; Reachability relations;
D O I：
10.3724/SP.J.1016.2012.01634
中图分类号：
学科分类号：
摘要：
This paper studies how to obtain state reachability in a directed graph. Hypergraph is defined in a nondeterministic state-transition system. The adjacency matrix of the hypergraph and the reachability matrix of the hypergraph are defined. According to the relationship between the reachability matrix and the adjacency matrix of the hypergraph, a method about how to use the adjacency matrix to count the reachability matrix is presented, and a method about how to use the reachability matrix to count the state reachability is presented also. Some important conclusions about weak solution, strong solution, and strong cyclic solution are obtained by using the state reachability. These conclusions tell us what are useless when we search weak planning, strong planning, and strong cyclic planning. So a great deal of state-action pairs can be eliminated directly from the universal policy. The work is significant to improve the efficiency for solving planning.
引用
收藏
页码：1634 / 1643
页数：9
相关论文
共 25 条
  • [1] Jameson A., Numerical uncertainty management in user and student modeling: An overview of systems and issues, User Modeling and User-Adapted Interaction, 5, 3, pp. 193-251, (1995)
  • [2] Vinnicombe G., Frequency domain uncertainty and the graph topology, IEEE Transactions on Automatic Control, AC-38, 9, pp. 1371-1382, (1993)
  • [3] Cimatti A., Pistore M., Et al., Weak, strong, and strong cyclic planning via symbolic model checking, Artificial Intelligence, 147, 1, pp. 35-84, (2003)
  • [4] Bertoli P., Cimatti A., Et al., Strong planning under partial observability, Artificial Intelligence, 170, 4, pp. 337-384, (2006)
  • [5] Jensen R., Veloso M., OBDD-based universal planning for synchronized agents in non-deterministic domains, Journal of Artificial Intelligence Research, 13, pp. 189-226, (2000)
  • [6] Cimatti A., Roveri M., Conformant planning via symbolic model checking, Journal of Artificial Intelligence Research, 13, pp. 305-338, (2000)
  • [7] Huang W., Wen Z.H., Et al., Observation reduction for strong plans, Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'2007), pp. 1930-1935, (2007)
  • [8] Bertoli P., Pistore M., Planning with extended goals and partial observability, Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS'2004), pp. 270-278, (2004)
  • [9] Bertoli P., Cimatti A., Et al., Planning in nondeterministic domains under partial observability via symbolic model checking, Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI'2001), pp. 473-478, (2001)
  • [10] Bertoli P., Cimatti A., Et al., A framework for planning with extended goals under partial observability, Proceedings of the 13th International Conference on Automated Planning and Scheduling (ICAPS'2003), pp. 215-225, (2003)
123