文档介绍：: .
明，智能规划再次成为人工智能研究领域的一个热点。
智能规划研究历史
人们对智能规划的研究已经有半个世纪了，最早可以追溯到 1956 年 Newell、Shaw 和
Simon 设计的逻辑理论家（Logic Theorist）程序，这个系统采用了启发式信息和反向搜索
技术；随后他们设计的 GPS 系统把领域知识与一般的搜索控制信息相分离。上述两个系统
特别是 GPS 在人工智能领域中具有非常重要的地位，但它们还不是真正面向规划问题研制
的智能规划系统。
1969 年，Green 通过归结定理证明的方法来进行规划求解，并且设计了 QA3 系统[8]，
这一系统被大多数的智能规划研究人员认为是第一个规划系统，原因就在于他是第一个面
向现实规划问题提出的规划系统；1971 年，Fikes 和 Nilsson 设计的 STRIPS 系统[9]在智能
规划的研究中具有重大的意义和价值，他的突出贡献是引入了 STRIPS 操作符的概念，使
得原来很神秘的规划问题求解变得明朗清晰起来；此后到 1977 年先后出现了 HACKER、
WARPLAN 、INTERPLAN、ABSTRIPS、NOAH、NONLIN 等规划系统。在这十年间人们
研究智能规划的兴致比较高，普遍认为规划问题必须用定理证明的理论来解决，直到
Chapman 设计的规划系统 TWEAK[10]出现。Chapman 详细全面地分析了利用定理证明理论
解决规划问题中的关键问题：模型与规划解的对应关系，提出了著名的模态真值标准
（Modal Truth Criterion）理论。Chapman 的分析使人们认识到简单地利用定理证明的方法
来解决规划问题是很难的，因此这以后到 1990 年间，在人们发现新的求解方法之前，对智
能规划的研究陷入了低谷，这期间仅有 SIPE、ABTweak 和 Prodigy[11]等较少的智能规划系
统出现。
1991 年,Soderland 和 Weld 等人设计了世界上第一个完备、完全、系统的非线性规划系
统 SNLP[12，13]，奠定了非线性规划系统的基础。1992 年，Kautz 等把规划问题求解转化为
可满足（SAT）问题[14，15，16]，一反定理证明式求解方法，利用在约束可满足问题算法上的
突破，有效地解决了部分规划问题。后来，基于此理论的 Blackbox 规划系统[17]在第一届智
能规划系统的比赛中表现了非凡的解决问题能力，一举夺魁，开辟了解决规划问题的又一
新途径。1995 年，Avrim Blum 等设计的图规划系统 Graphplan[18]第一次采用图的方式来解
决规划问题，并且提出了用于规划的规划图的概念。后来很多规划系统都借鉴了图规划系
统的方法，参加第一届智能规划比赛的规划系统除委内瑞拉的 HSP 外，其它四个规划系统
SGP、Blackbox、IPP 和 STAN 都或多或少地采用了图规划的某种（些）技巧，并且对图规
划做了相应的扩充：SGP 加入了用户互操作界面；Blackbox 则综合了基于规划图的快速规
划扩展和基于 SAT 的快速规划验证；IPP 扩充了图规划的问题描述语言，如支持 ADL 规划
描述语言，它能够处理条件效果等，这样它的表达能力比图规划系统要强大；STAN 在减
少搜索和构造规划图的费用上做了扩充。这些规划算法都是部分序或非线性的通用规划系
统，此次比赛表明部分序方法在规划求解中具有举足轻重的地位。两年