论文部分内容阅读
智能规划是人工智能研究领域近年来发展起来的一个热门分支,由于其广泛的实用性,受到研究者的高度重视。尤其是具有不完全信息和不确定信息的规划问题已经成为智能规划中的研究重点。在各种研究方法中,由于概率方法能较准确地对不确定信息进行定量描述,因此研究动作具有概率输出的概率规划方法体现了较强的优越性,这个方法得到了研究者的肯定,并在此基础上产生了大量的算法。在 2004 年举行的 IPC-4(2004 International Planning Competition),第一次把概率域列入了竞赛的项目,再一次表明了概率规划在智能规划研究领域中的重要地位。 智能规划领域的研究者针对规划问题中的不确定性(uncertainty)问题和不完全信息(incomplete)问题,开发了一些有效的规划器,其中 Blum 与 Langford 提出了专门针对动作结果不确定的规划问题的算法 Probabilistc GraphPlan(简称 PGP),相关的实验结果表明 PGP 优于解决同类问题的规划器 Buridan,SPI,BlackBox 等。但PGP 算法只局限于处理 STRIPS 动作的概率规划问题,对于动作带有条件效果的概率规划问题,PGP 算法就不适用了。为了扩大 PGP 规划器的处理范围,提出该研究课题。 本文首先从表示方法、规划类型、复杂度、规划语言等几方面分析了概率规划的研究现状,概括了研究概率规划的相关理论和相关技术,并分别介绍了经典规划器与概率规划器中对动作带有条件效果的规划问题的处理方法,其次介绍自己做的主要工作,包括两个部分:(一)研究与实现基于互斥约束的概率规划器,该规划器是对 PGP加以改进,改进后的算法相对于 PGP 规划器减少了规划图中的结点数目,节省了存储空间.(二)提出处理动作带有条件效果的概率规划器的算法。最后阐明了未来继续要做的工作,对第二部分提出算法进行程序实现。