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

Solving parallel and probabilistic planning problems based on causal graph heuristic

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

Parallel and probabilistic planning(PPP)is a hot spot in AI planning in recent years.In the PPP,actions could be concurrent and non-deterministic.These properties were very close to those of practical problems in the real world.Howe-ver,both of the two primary methods of solving the PPP had obvious shortcomings,respectively.Therefore,this paper tried to apply some efficient heuristic searching methods into solving the PPP.The newest planning description language for the PPP was the RDDL where the conditional probabilistic functions(CPF)were very helpful to construct causal graphs(CG).Therefore,it introduced causal graph heuristic(CGH)into solving the PPP.Its core heuristic algorithm was called CGH RDDL.In the solving process,it used the simulator,rddlsim,to simulate the state evolution and used the CGH RDDL to guide the searching.Experiment results in some PPP benchmark domains show that the proposed method performs better than the two representative planners,PROST and Glutton,without allowing any manual intervention or parameter resetting.Furthermore,when compared with other heuristic methods,the CGH RDDL is better than the random searching method and faster than the pure hill-climbing method.This shows that it can extend some efficient heuristic searching methods in the classical planning to solve this kind of non-classical planning problems.