基于因果图启发式的并行概率规划求解

并行概率规划(PPP)是近年来智能规划领域中的研究热点。在该类问题中,动作具有并发性和不确定性,非常贴近现实问题。然而,现有的两种针对PPP的主要求解方法都有明显的缺点。一种基于模拟抽样,以规划器PROST为代表,但求解速度慢；另一种基于迭代深化,以规划器Glutton为代表,但求解质量差。因此,我们尝试使用高效的启发式搜索方法来求解这类问题。目前,因果图启发式(CGH)是启发式规划方法中的佼佼者。考虑到PPP问题采用RDDL语言来描述,其中的条件概率函数(CPF)非常适合用于构建因果图(CG),所以我们引入因果图来对基于RDDL描述的PPP问题进行启发式求解。本文的主要启发式算法称为CGH_RDDL,整体求解方法是使用rddlsim模拟状态演化以及用CGH_RDDL引导搜索。具体做法是：先从领域描述构建出因果图及领域转换图(DTG)；然后根据CG和DTG,计算单个状态变量任意一对取值间的转换代价；接着在rddlsim的模拟演化过程中,由CGH_RDDL推送具有最佳估值的后继状态,其中状态的启发值定义为状态轨迹的转换代价和立即回报值的总和；最后累加在限定轮数内rddlsim状态演化的回报值,即为最终的求解质量。在PPP基准领域上的实验结果表明,在不允许手工干预和参数调整的前提下,本文方法的求解效果要好于PROST和Glutton。更进一步地,与其它的基本启发式相比,CGH_RDDL的求解质量高于随机搜索,求解速度快于爬山法。这表明在经典规划领域中高效的启发式搜索策略可扩展去求解这一类非经典规划问题。而非经典规划问题更具有现实意义和应用前景,更值得探讨先进的规划方法去求解它们。

Solving the Parallel and Probabilistic Planning problems based on Causal Graph Heuristic