智能规划已经成为人工智能的研究热点,尤其是基于概率方法的不确定规划算法的研究。概率方法定量的刻画了现实世界中的不确定性,更适合于求解现实世界中的规划问题,从而得到很多学者的关注。基于Graphplan算法的PGraphplan是概率规划中较优秀的一款规划器。PGraphplan在图规划框架下利用动态规划算法找到随机规划解。但规划解是在“每个时间步只允许执行一个非空动作”的假设下求得的,这个假设的存在使得在规划图中无法使用互斥信息,找到的规划解相对冗长,并且比较浪费求解时间。PGraphplan的后续发展算法也都没有打破这个限制。本文针对概率规划中存在的这一问题,提出了新的概率规划算法PPGraphplan。我们通过定义并行动作集以及节点间互斥的概念,实现了在概率规划算法中处理并行动作,打破了原有概率规划算法中“每个时间步只允许执行一个非空动作”的限制,弥补了原有算法的不足。PPGraphplan算法在规划图扩展阶段标记节点间的互斥信息,有效利用规划图的特性,提高了规划器的求解质量;同时在有效规划提取阶段利用动态规划算法计算每个动作到达目标状态的最大成功概率,从而找到成功概率较大的最短规划解因此,该算法更适合于求解现实世界中的规划问题。本文在给出算法的基础上,利用C语言对该算法进行了实现,设计了可以处理并行动作的概率规划系统PPGraphplan。实验证明该系统可以达到理论预期的效果,实现了概率规划算法中动作的并行执行,可以找到长度最短的规划解,提高了概率规划器的求解质量,使得概率规划更适合于处理现实世界问题。