论文部分内容阅读
并行概率规划(PPP)是近年来智能规划领域中的研究热点。在并行概率规划问题中,放松了经典规划对所描述问题的严格约束,使得动作具有并发性和不确定性,从而能够更好的描述现实问题。然而,现有的两种针对PPP的主要求解方法都具有明显的缺点。一种是基于模拟抽样的方法,以规划器PROST为代表,求解质量相对较好,但求解速度慢;另一种是基于迭代深化的方法,以规划器Glutton为代表,求解速度相对较快,但求解质量差。因此,我们尝试使用新的方法来求解这类问题,并行概率规划问题不强求最优解,解题空间规模巨大,这些特点正是启发式搜索所擅长的应用领域,从而高效的启发式搜索方法成为我们的选择。目前,因果图启发式(CGH)是启发式规划方法中的佼佼者,并且该方法已经在经典规划领域中有不错的表现。而且考虑到PPP问题采用RDDL语言来描述,在RDDL语言中使用条件概率函数(CPF)来描述动作效果及状态转移,而CPF的结构形式则恰好可以较为直观的用于构建因果图(CG),所以我们引入因果图来对基于RDDL描述的PPP问题进行启发式求解。本文的主要启发式算法称为CGHRDDL,整体求解方法是使用rddlsim来模拟状态演化以及使用CGHRDDL引导搜索。具体的求解方法分为以下四步:首先从领域描述构建出因果图及领域转换图(DTG);然后根据CG和DTG,计算单个状态变量任意一对取值之间的转换代价;接着在rddlsim的模拟演化过程中,由CGHRDDL推送具有最佳估值的后继状态,其中状态的启发值定义为状态轨迹的转换代价和立即回报值的加权总和;最后累加在限定轮数内rddlsim状态演化的回报值,即为最终的求解质量。在PPP基准领域上的实验结果表明,在不允许手工干预和参数调整的前提下,本文设计方法的求解效果要好于PROST和Glutton。更进一步地,与其它的基本启发式相比,CGHRDDL的求解质量高于随机搜索,求解速度快于爬山法。这些都表明在经典规划领域中高效的启发式搜索策略可以扩展用来求解这一类非经典规划问题。而非经典规划问题由其特征可知更加具有现实意义和应用前景,更值得探讨先进的规划方法来求解它们。