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

并行概率规划(PPP)是近年来智能规划领域中的研究热点。在该类问题中,动作具有并发性和不确定性,非常贴近现实问题。然而现有的两种针对PPP的主要求解方法都有明显的缺点。因此,尝试使用高效的启发式搜索方法来求解这类问题。考虑到PPP问题采用RDDL语言来描述,其中的条件概率函数(CPF)非常适合用于构建因果图(CG),所以引入因果图启发(CGH)来进行求解。提出的启发式算法称为CGH_(RDDL),整体求解方法是使用rddlsim模拟状态演化以及用CGH_(RDDL)引导搜索。实验结果表明,在不允许手工干预和参数调整的前提下,该方法的求解效果要好于代表性规划器PROST和Glutton;并且与其他启发式相比,CGH_(RDDL)的求解质量高于随机搜索,求解速度快于爬山法,这表明在经典规划领域中高效的启发式搜索策略可扩展去求解这一类非经典规划问题。

基于多值表示的并行规划方法

Fast Downward规划系统是第四届国际规划竞赛的冠军。以高效的串行规划系统Fast Downward为基础,设计并实现了并行规划系统Parallel Downward。首先提出4个并行规划的相关定义;之后提出多值规划任务下动作互斥的定义、充要条件,并实现了动作互斥判断算法;在此基础上设计了候选并行动作集的生成算法;然后为提高系统求解质量重新设计了新的搜索控制策略;最后,给出剪枝策略来抑制并行规划状态空间的指数级膨胀。通过对国际规划竞赛测试问题的实验,Parallel Downward表现出良好的规划效率和规划质量,相比Sapa规划系统Parallel Down-ward具有较好的可扩展性。