不确定规划中可达关系的快速求解算法

Fast Solving Algorithm of Reachability Relation in Uncertain Planning

在不确定规划领域中,通常需要在同一个不确定状态转移系统中解决多个规划问题,如果能得到不确定规划中状态之间的可达关系即可方便求解该规划问题,然而现有矩阵乘法求解可达关系时存在算法复杂度高的问题。为此,设计一种快速求解不确定规划中状态之间可达关系的算法,将确定动作和不确定动作区分处理,先求解所有确定动作的可达关系,再采用链表和队列求解不确定动作的可达关系。实验结果表明,与矩阵乘法相比,该算法能得到更全面的可达关系,且求解效率更高。

In uncertain planning field,it is frequent to solve many planning problems over a nondeterministic statetransition system in uncertain planning. So getting the state reachability for the nondeterministic state-transition system can make solving planning problems easier. However,the existing solution matrix multiplication of relations exist the problem of high algorithm complexity. Therefore,this paper presents a fast solving algorithm of reachability relation between the states in uncertain planning. The algorithm determines the certainly action and uncertainty actions separately. It determines the relationships between the certainty action,then solves relations between uncertain actions with lists and queues.Experimental result shows that the algorithm not only can get a more comprehensive relationship,but also has higher efficiency than the matrix multiplication algorithm.