智能规划是人工智能研究领域近年来发展起来的一个热门分支,由于其广泛的实用性,受到研究者的高度重视。尤其是具有不完全信息和不确定信息的规划问题已经成为智能规划研究中的重点。在各种研究方法中,由于概率方法能较准确地对不确定信息进行定量描述,因此研究动作具有概率输出的概率规划方法体现了较强的优越性,这个方法得到了研究者的肯定,并在此基础上产生了大量的算法。基于Graphplan算法的PGraphplan是概率规划中较优秀的一款规划器。PGraphplan在图规划框架下利用动态规划算法找到随机规划解。但规划解是在“每个时间步只允许执行一个非空动作”的假设下求得的,这个假设的存在使得在规划图中无法使用互斥信息,找到的规划解相对冗长,浪费求解时间。并且算法只考虑概率信息,没有涉及状态的效用值信息,不便于处理现实世界的问题。本文针对概率规划中存在的这两点不足之处,提出了新的概率规划算法UC-PGraphplan。首先,我们通过添加结果结点,对经典规划图进行了扩展,并定义了并行有效轨迹及各种结点的互斥关系,尽可能多的包含所有的有效轨迹,使其在同一时间步实现了并行,打破了原有概率规划算法中“每个时间步只允许执行一个非空动作”的限制,弥补了原有算法的不足,提高了规划器的运行速度和性能。其次,在并行概率规划中运用了效用理论,使所有目标都能以最大的期望效用值去实现,从而提高了规划器的求解质量。该算法更适合于求解现实世界中的概率规划问题。本文在给出算法的基础上,利用C语言对该算法进行了实现,设计了可以处理带有最大期望效用值的并行概率规划系统UC-PGraphplan。实验证明该系统可以达到理论预期的效果,实现了概率规划算法中动作的并行执行,可以找到成功概率较大且具有最大期望效用值的规划解。提高了概率规划器的求解质量,使得概率规划器更适合于处理现实世界问题。