汪 泉，文中华，伍 选

(湘潭大学信息工程学院，湖南 湘潭 411105)

1 概述

现实生活中存在很多规划问题[1]，规划的执行又常常存在着一些不确定性因素，使动作结果偏离预期目标[2-3]。这使得不确定规划在许多环境中更符合现实情况，对其做进一步研究具有很强的实际价值[4-5]。强规划解是一种重要的不确定规划解，能够在不确定的状态转移中得到确定的结果状态[6-7]。

由于动作的不确定性，求强规划解一般都是采用从目标状态开始的反向搜索算法[8-9]。这类算法随着问题规模的扩大，重复及无效搜索会越来越多[10]，因此只适用于规模较小的问题，且效率不高。文献[11]提出了状态分层的方法，在状态分层后，大量不必要的状态动作序偶被去掉，从而较大程度地减少了问题规模。而且分层后求规划解可以从上一层直接往下一层搜索，而不需要考虑同层之间的转移及往之前各层的转移，提高了求解效率[12]。

分层简化了求规划解，但现有状态分层算法仍然有较高的复杂度，具有很大的可优化空间。本文参考已有分层算法，设计一种新的分层算法，通过采用特殊双向链式结构保存规划领域的超图，以防止对一些无关状态的搜索以及对一些状态的重复搜索。并在分层中对已遍历的状态做相应修改，使得在分层的判断过程中，只需要考虑直接的下一层，而无需考虑其他各层。

2 相关定义

定义 1 一个规划领域是一个不确定的状态转移系统Σ=(S, A, γ)[1]，其中，S是有限状态集；……