不确定规划中状态循环可达关系的求解方法

在不确定规划领域中, 不确定状态转移系统求规划解常常会搜索大量无用的状态和动作, 造成冗余计算。获得不确定状态转移系统的状态可达关系可以避免无用搜索、减少冗余计算, 为系统提供引导信息。以非循环可达关系为基础, 定义矩阵的计算规则, 使用系统的邻接矩阵来计算可达矩阵。同时首次提出了循环可达关系的分类、二可达关系等, 并设计了求循环可达关系的算法, 且以实例证明了算法的有效性和正确性。在不确定规划中获得状态之间的可达性关系, 在求规划解的过程中可以删除大量无用的状态动作序偶, 降低问题规模, 提高求解规划问题的效率。

Method of getting circular reachability relation innon-determinate planning

It is frequent to search a lot of useless states and actions which can result in redundant calculations in solving planning problems over a non-deterministic state-transition system in non-determinate plan field. Getting state accessibility relation for the nondeterministic state-transition system can avoid useless searching, reduce redundant calculations and create a guided information for the nondeterministic state-transition system. Based on acyclic reachability relation , this paper defined the calculation rules of matrix multiplication, classification of circular reachability relation and two-reachability relation. It aslo presented the method to get circular reachability relation and designed an algorithm for this. The example proves the validity and correctness of the algorithm. If the non-determinate plan has the information of state accessibility, it can delete useless states and actions to reduce the size of the problem and improve solution efficiency of solving planning problem.