规划图（Planning Graph）：
被认为是革命性的博士论文做着色图算法的Avrim L. Blum阿夫里姆·布鲁姆（参考这页海南琼州大学是世界上第一个发现不唯一着色图的领域）和Merrick L. Furst合作的“规划图”论文：Fast Planning Through Planning Graph Analysis. In Proceeding of the International Joint Conference on Artificial Intelligence, 1995, 1636-1642，被引已3千多次（https://dl.acm.org/action/ajaxShowCitedBy?doi=10.5555/1643031.1643111）；而Blum 和 Furst 的这论文“Fast Planning Through Planning Graph Analysis”仅经过几年已已被认为是具有重要意义的一篇文献。正是由于 Graphplan 的提出，使得规划领域不在仅仅着眼于单纯的偏序规划，因而被Daniel S. Weld 1999年在《人工智能杂志》发表的综述文章“人工智能规划领域的最新进展”中就已称作为革命性的算法。

第一 引言 规划问题是人工智能机器学习研究领域经典问题之一，通常意义上讲，规划（planning）是指在给定的初始条件下，求得一个动作序列（串行、并行或串并行混合）的过程，而依次执行此动作序列可以完成某一特定的具体任务，最终达到一个特定目标。事实上,即使在日常生活中,这种在行动之前就拟定出行动步骤的行为也是随处可见的: 即使简单如泡茶这样的工作, 我们也需要拟定好诸如放好茶杯,放茶叶,烧水这些动作的顺序,否则在茶杯没有放好之前就冒失的倒水,其结果可想而知。

而智能规划（intelligent planning）就是利用计算机模拟人脑进行规划的过程。是一个智能规划 agent 的抽象模型，在图中该 agent 希望通过对环境的操作以达到其目标。它能够感知当前的外部环境并能通过执行动作来改变外部环境，因此一个规划即是由一个能够改变环境以达到期望目标的动作序列构成。

由于在复杂环境下执行复杂任务的系统（智能体）往往需要海量（甚至无法计算）的存储，同时要求设计者需要有超人类的预见能力，需要为机器遇到的所有情况预期合适的反应。而与之相对的，利用智能规划技术和规划识别技术，采取以适应性代替显示设计的方法，通过对系统（智能体）所处环境和结果状态建构模型，使得预期计算的结果能够自动的学习和演化，因而即使在设计者本人也无法预见的情况下，系统（智能体）依然可以自主的选择合适的动作来执行，从而提高了系统的效率，减轻了设计者的负担。因此，智能规划被广泛运用于问题规模较大，复杂性较高这类问题上：如自动数据处理，电子游戏角色设计，大规模后勤调度等。

也正因为如此，智能规划越来多的受到各国的重视，各顶尖大学和研究机构均围绕智能规划，实施了多个项目，如美国 DAPRA和 Rome 实验室的 ARPI 计划英国的国家航空和宇宙航空局赞助的 EUMETSAT 项目,美国国家航空和宇宙宇航局也投入大量的人力、物力，开展关于规划理论的研究，运用在航空器上，这些项目有力的推动了规划理论的研究。而智能规划的相关文献也经常出现在人工智能领域的相关顶级期刊和顶级会议中，如AAAI-99 和 IJCAI-99 中就有约 20％的智能规划方面的文章。而Artificial Intelligent 杂志也分别于 1994 年和 2003 年分别对智能规划技术开了两期专刊。

其中Blum 和 Furst 的上面文献“Fast Planning Through Planning Graph Analysis”无疑是具有重要意义的一篇文献。正是由于 Graphplan 的提出，使得规划领域不在仅仅着眼于单纯的偏序规划，因而被Daniel S. Weld 1999年在《人工智能杂志》发表的综述文章“人工智能规划领域的最新进展”中就已称作为革命性的算法。而在Graph plan 的基础上，Hoffman 等人设计出了 Fast Forward，LPG等灵活快速的规划器，而这些规划器几乎包揽了近几届来的规划比赛的所有冠军（参见附录 A， B， C）。

但是上述的规划器大多是被运用于经典规划领域中，而经典规划通常是建立在如下的假设的基础上的：

1. 原子时间(atomic time)：规划的执行被认为是从一个世界状态到另一个时间状态的原子转移（ atomic transformation）。因此，规划器在动作执行时不需要考虑环境的变化。

2. 确定性效果(Deterministic effects)：任何动作的执行都被看作从动作到动作结果的一个确定性函数，换言之，给定世界状态和相关动作，动作的执行结果总是相同的。

3. 万能、全知(Omniscience): agent 对所处环境的初始状态有完全知识，并且对动作的本质的认识是已知的。

4. 变化的单调性(Sole cause of change)：环境是静态的，引起环境的变化的原因只是由 agent 的动作造成的。

正因为如此，虽然这些规划器在规划速度和规划规模上取得了巨大的成就，但是实际上依然只是局限在例如积木问题等小的抽象世界中，大而且复杂的规划问题仍然没有得到很好的解决。为了解决实际问题，必须寻求规划表达能力更强的知识表达方式以及更有效的挖掘蕴涵知识。为此，国内外学者对此作出了相当多的尝试和努力，Graphplan 的设计者之一 Blum 就考虑到扩展图规划的知识表示到 Probabilistic Planning 中[9]，Weld 等也认为经典规划主观上臆断初始世界状态是完全已知的根本就是不现实的推测，并因此将规划图算法扩展以处理非确定性动作。

事实上，自从非经典规划提出以来，概率规划模型作为不确定规划的一种，其发展尤为迅速。而令人惊奇和不解的是，同为解决不确定性的重要方法之一，模糊性或者可能性在规划建模中一直得到没有相应的利用。而智能规划系统其本质是适用于复杂系统的，这种复杂性的产生也并非偶然，这是由规划系统设计的目的即完成所需要完成的任务的复杂性决定的。这种复杂性导致了规划的客体的模糊性或者可能性的必然所在。虽然历史上已经有了对将模糊理论运用到规划问题中的尝试，但是这些问题多集中在数学规划理论和模糊优化上，在问题求解方面依然停留于 1991 年前的定理证明方法，也很少运用非线性规划手段采用目标导向方法求取规划解。

为此本文的目的就在于将基于模糊集合表示的可能性理论构造可能性规划模型，设计出基于可能性理论的规划图算法。本文的组织如下，在第一章中我们主要介绍可能性理论相关知识以及可能性理论和概率理论的比较；第二章中，我们回顾规划图模型；在第三章中我们探讨可能性规划以及其基本表示方式，提出POPDDL（可能性规划定义语言）；在第四章中我们讨论基于规划图框架的可能性规划算法；在第五章我们给出总结并探讨将来的相关工作。

第二 规划图算法

在规划图算法提出以前，人工智能规划研究主要集中于所谓的非线性规划或者偏序规划上. 规划图算法至少从两个方面扩展了规划研究方向：

（1） 搜索一条有固定长度的规划（根据规划图扩张的过程可以看出）

（2） 使用互斥信息用于搜索树的剪枝。

正是这些不同点使得规划图算法的性能远远超越了早期的规划算法。而规划图的成功反过来又使得整个规划研究领域寻找传统规划方法以外的策略。在规划图算法之后 Kautz 等又进一步使用一种通用的 SAT 算法并将之与规划图相结合，这就是第一届规划器比赛冠军 Blackbox 的理论原型。而 Kautz 的方法又激励了研究者们寻找将规划算法翻译为其他可计算问题。另一方面，Bonet 等将规划转换为状态空间中启发式搜索的方法，而 Hoffman等又将此方法和规划图方法相结合，并构造出 FF 系统，该系统

在第二届和第三届规划比赛中也取得了不俗的成绩。事实上当前效率较高，求解能力较强的规划器大部分是建立在规划图算法的基础上或者和规划图算法有着密不可分的联系。

规划图算法延续了早期规划研究领域的传统，即采用STRIPS 域来作为规划描述语言。一个 STRIPS 域包括:规划目标集合（由命题的与构成）和 动作集合，每个动作由“与”前提，“与”效果构成，并且定义了一个从一个状态到另一个状态的转移函数。动作只有在前提条件满足的情况下可以执行。

规划图通过构造和分析一个紧凑的结构（即 planning graph）来获得规划解。它包括两个步骤：一个向前的阶段，在此阶段中，规划图不断扩张知道目标出现；一个向后的阶段，在此过程中，规划解通过分析规划图来获得。图 3 给出了一个规划图的模型。我们可以看出规划图实际是一个有向的分层的图结构，它包含两种节点：命题节点和动作节点，并由此分成动作层（由动作节点构成）和命题层（由命题节点构成）。初始层是一个特殊的层次，因为它是由初始命题构成，描述了初始的世界状态。

2.1 规划图扩张过程

在规划图的扩张中，动作层的扩张是指扩张那些所有的前提条件存在于前一命题层且前提条件不互斥的动作，而命题层的扩张是将前一动作层的动作效果添加到该层中，值得一提的是，在规划图中还采用了一种伪动作－noop，用以保证命题的延续。

规划图的另一个特性在于它在扩张过程中利用了节点间的互斥关系，下面是有关互斥的相关定义。

对于两个不同的动作节点，若它们不一致，则存在下述情况： 不一致效果（Inconsistent Effects）：一动作的结果之一是另一个动作结果之一的反，例如：开车从城市 c1 到城市 c2 使得“卡车在 c2”命题为真，而开车从 c2 到 c3 使得“卡车在 c2”为假，因而这两个动作互斥。

推理困难（Interference difficulty）：动作 1 的效果之一是另一个动作发生的必要条件之一的反。例如：开车从 c2 到 c1 使得“卡车在 c2”命题为假，而开车从 c2 到 c3 的一个必要前提就是“卡车在 c2”。

竞争需要（Competing Needs）：两个动作的前提示相互排斥的。比如：开车从 c1 到 c2 需要卡车在 c1，而士兵在 c2 上车要求卡车在 c2。

由动作间互斥关系可以推导出命题的互斥，即：

互反（Negation）：两个命题之间是互反的。

非一致支持（Inconsistent Support）:所有可以产生此命题 1的动作和所有可以产生命题 2 的动作都互斥。比如，所有使得卡车在 c1 的动作都和所有使得卡车在 c2 的动作互斥。

2.2 规划图求解过程

规划图的扩张过程持续到所有目标都出现在图中，且目标命题之间不互斥。在此之后，规划图求解过程被调用。求解过程是一个递归调用的过程，给定目标，求解过程不断寻找连接该目标的不互斥的子图，一直回溯到初始状态。求解的基本过程如下： （1） 扩张规划图知道所有目标均出现在当前层，且目标之间不互斥。

（2） 对于每个支持目标（即结果含有目标）的一致的动作集合，将这一动作集合的前提构成的命题集合看成是子目标。

（3） 对于每个子目标集合：

若没有一致的动作集合支持此目标在回溯到上一层寻找另一个动作集合。

…

Merrick L Furst还和Jonathan L Gross,Richard Statman合写Genus distributions for two classes of graphs一类项链图在Klein瓶上的嵌入.Journal of Combinatorial Theory, Series B.1989,46(1).22-36；

也应参考最近Malik Ghallab马利克•加拉卜、Dana S. Nau达纳•诺、Paolo Traverso保罗•特拉韦尔索合著《自动规划：理论和实践》，姜云飞、杨强、凌应标等翻译，清华大学出版社2008年；姜云飞等的“规划图”论文，。以及北京大学计算机叶志远教授等的“基于动态贝耶斯规划图的状态安全报警关联”-参考上文等等。