不确定规划中循环可达状态信息的维护

Maintenance of Cyclic State Reachability in Nondeterministic Planning

动态环境下,动作执行的不确定性会因外部因素存在变动,因此将导致不确定系统中的状态可达关系可能发生改变。为解答这一问题,论文对信息传递法中状态之间可达关系的更新方式进行改进,提出一种新的状态可达关系的维护算法。该算法将变更的状态之间可达关系与原可达矩阵对比,利用邻接矩阵中对应可达信息对变更后状态的可达信息进行修改,然后通过状态之间信息传递,求解不确定系统中局部状态可达关系,从而避免了更新过程中的重复计算。实验结果表明,该方法在运算时间上要优于重新利用信息传递法来维护系统的状态可达关系。

In a dynamic environment,the uncertainty of action exection may change due to external factors,which may change the state reachablility relationship in uncertain system. The update method of the reachability relationship between states in the information transfer method is improved,and a new maintenance algorithm of state reachability relationship is proposed to solve this problem. This algorithm compares the reachability relation between the changed states with the original reachability matrix,and modifies the reachability information of the changed state with the corresponding reachability information in the adjacency matrix,and then solves the reachability relation of the local state in the uncertain system through the information transfer between the states,thus the repeated calculation is avoided in the update process. The experimental results show that this method is better than reusing the information transfer method to maintain the state reachability relationship.