智能规划是人工智能领域的一个重要的研究内容。经典的规划问题假设世界的信息是完全可知的,并且动作的执行效果是确定的,这使得经典的规划问题只能求解规模较小的模型规划问题。为了求解现实问题,近年来,对不完全信息和不确定效果的规划问题的研究已经逐渐深入。 概率规划器由于能够较准确地对不确定信息进行定量描述,已经得到人们的高度重视。其中 Blum & Furst 提出了专门针对动作效果不确定的规划算法TGP(Trajectory GraphPlan),TGP 算法就是将求解经典规划问题的 GraphPlan 算法从STRIPS 域扩展到动作效果具有概率输出的概率规划域。相关的实验效果表明 TGP的速度比解决同类问题的规划器都快。 动作的条件效果也是处理动作效果不确定的一种方法。但是条件效果与具有概率输出的动作效果是两种性质不同的不确定性。动作的概率输出效果是根据经验事先给出的,一旦动作被执行,就会产生一个具有给定概率值的效果输出列表,不同概率值的输出不可能同时发生,因此同一个动作的概率输出是互斥的;而条件效果是由动作执行时所处状态动态确定的,同一个动作不同的条件效果只要不互斥,效果条件在当前状态得到满足,就可以同时发生。将两种表达不同性质的不确定性的方法有机融合在一起,有着重要的研究价值,因此提出本课题。 本文首先回顾了智能规划技术以及规划语言的发展,其次介绍了经典规划算法GraphPlan,再次阐述了现有条件效果的处理方法,然后分析了概率规划的研究现状,最后本文阐述了将概率规划器 TGP 扩展到 PPDDL(Probabilistic Planning DomainDefinition Language)的部分域的规划算法,使其能够求解具有不同确定性动作的规划问题。