求强规划解的快速状态分层算法

Fast Hierarchical States Algorithm for Solving Strong Planning

在求强规划解时,通过状态分层可以大幅减少问题规模,提高搜索效率,并能得到规划路径较短的强规划解。但现有分层算法本身有一定的复杂度,在状态较多时开销较大。为此,通过改进已有分层算法,设计一种适用于求强规划解的快速状态分层算法。采用链式双向图结构保存数据,在分层时修改已遍历的状态动作序偶,并根据修改结果直接进行分层判断,使得分层时只需要判断前一层状态而不是所有已分层状态,避免对非必要状态转移的搜索以及对必要状态转移的重复搜索。实验结果表明,该算法的分层速度优于已有的矩阵乘分层算法。

When solving strong plan, through using hierarchical states, it can sharply reduce the scale of the problem, boost search, and it can get the solution of shorter path. But existing hierarchy algorithms are still complex in some extent, and when the number of states is big, it costs large. Based on the ideal of hierarchy, it designs a fast hierarchy algorithm. It uses bidirectional chain graph to save data. In hierarchy, it directly modifies traversed state-action pair, and according to the modified results to make decision directly. With that, only one previous hierarchy is needed to judge rather than all hierarchical states. And it avoids searching the state transition of unnecessary and avoids repeat searching on necessary state transition. Experimental result shows that this algorithm runs more quickly than similar algorithms such as the matrix multiplication hierarchy algorithm.