近年来,智能规划已经成为人工智能的研究热点,可能性规划作为不确定规划的一种,由于能够定性的刻画现实世界中的不确定性,更适合于求解现实世界中的规划问题,而逐渐得到人们的关注。而现有可能性图规划器Poss-Graphplan限定每个时间步只执行一个动作,且规划图中无法使用互斥信息,找到的规划解相对冗长,并且比较浪费求解时间。本文在深入研究可能性理论的基础上,针对这一问题,提出新的可能性规划算法PC-Graphplan。首先,在可能性图框架下重新定义了互斥关系和并行动作集的概念,使之能够符合可能性规划中动作的不确定性,PC-Graphplan算法在规划图扩展阶段标记节点间的互斥信息,有效利用规划图的特性,提高了规划器的求解质量;接着,在规划提取中给出了乐观和悲观两种情况下生成并行动作集的算法,实现了可能性图框架下动作的并行执行,弥补了Poss-Graphplan规划器中每个时间步只能执行一个动作的不足;然后,分乐观和悲观两种情况给出了带有并行动作的可能性规划的图规划算法PC-Graphplan;最后,用C语言在Windows系统下实现了基于可能性理论的可处理并行动作的PC-Graphplan图规划器,实验证明PC-Graphplan图规划器可以达到理论预期的效果,实现了可能性规划过程中动作的并行执行,与Poss-Graphplan相比提高了求解质量,使得可能性规划更适合于处理现实世界问题。