当前,对基于模型检测规划研究的算法中存在大量的冗余计算,一些不可能参与构成解的状态动作序偶被反复筛选.文中给出了一种在不确定规划领域求规划解的新思路:在求规划解之前,找到不确定状态转移系统的状态之间的可达关系,从而根据状态之间的可达关系进行约简.提出了不确定状态转移系统的超图、超图的邻接矩阵和可达矩阵等概念,设计了用超图的邻接矩阵求不确定状态转移系统中状态之间可达关系的方法.利用不确定状态转移系统的超图、超图的邻接矩阵和状态之间的可达关系获得了关于弱规划解、强规划解和强循环规划解的一些重要性质.这些性质是关于一些状态动作序偶是否不可能参与构成弱规划解、强规划解和强循环规划解的结论.通过这些性质可以将大量的状态动作序偶直接去掉,从而大幅度简化求规划解的过程,提高求规划解效率.%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.
展开▼
