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

摘要

对一个不确定状态转移系统求多个规划问题,那么获得不确定状态转移系统的状态可达关系可以方便求解规划问题,减少冗余计算,建立系统的引导信息.提出一个关于矩阵求不确定领域的状态可达性关系的方法,主要思想是以矩阵乘法来模拟状态转移系统中状态转移,对不确定动作带来的扩散和确定关系带来的聚合进行了统计和处理,从而获得状态可达信息.证明了方法的正确性和有效性.在不确定规划中确定了状态之间的可达性关系,可以在求规划解时删除对规划没有用的状态节点和状态动作序偶;选择能到达目标节点的状态节点和状态动作序偶;进行启发式正向搜索;减少大量冗余计算;提高求解效率.%It is frequent to solve many planning problems over a nondeterminisiic slate-transition system in non-determinate plan. So getting state accessibility for the nondeterministic state-transition system can make solving plan-ning problems easier, reduce redundant calculations and create a guided information for the nondeterministic state-transition system. This paper presented a method base on matrix order to acquire state accessibility in the uncertain field. The main idea is using matrix multiplication to simulate transition of state in the nondeterministic state-transi-tion system, making statistics and processing for the spread brought by uncertain actions and the aggregation brought by the determine relationship between states, and then obtaining the information of state accessibility. The paper proved the correctness and validity of the method. If the non-determinate plan has the information of state accessibili-ty, we can delete useless states and actions and choose states and actions that can reach goal state to carry out the heuristic forward search, reduce the amount of redundant computation, and improve solution efficiency then solve planning problem.