人工智能9.3偏序规划9.3.1偏序规划的描述这样一种方法在构建规划的次序上也具有灵活性的优点，也就是说，规划系统能够先进行“显然的”和“重要的”决策，而不是被迫按历时顺序的步骤进行决策。如，一个在伯克利的人想去蒙特卡洛，他可能先试图寻找从旧金山到巴黎的航班；得知了关于出发和到达时间，然后它就可以继续想办法如何往返机场。在搜索期间延迟某个选择的通用策略称为最少承诺策略。最少承诺没有形式化定义，显然某种程度的承诺是必要的，以免搜索没有任何进展。尽管无形式化定义，对于分析搜索问题何时应该做出决策，最少承诺是十分有用的概念。我们的第一个具体例子比规划一个假期要简单得多，考虑穿一双鞋的简单问题，我们可以把它描述为如下一个形式化规划问题：Goal(RightShoeOn∧LeftShoeOn)Init()Action(RightShoe,PRECOND:RightSockOn,EFFECT:RightShoeOn)Action(RightSock,EFFECT:RightSockOn)Action(LeftShoe,PRECOND:RightSockOn,EFFECT:LeftShoeOn)Action(LeftSock,,EFFECT:LeftSockOn)一个规划系统应该能够找到RightSock后紧跟着RightShoe的双行动序列来获得目标的第一个合取子句，找到LeftSock后紧跟着LeftShoe的双行动序列来获得目标的第二个合取子句，然后这两个序列可以被合并而产生最后的规划。为了做到这些，规划系统会独立处理这两个子序列，而不承诺一个序列中的一个行动是另一个序列的行动之前还是之后。从一个空规划开始。然后我们考虑改进规划的途径，直到我们找到一个能够解决问题的完整规划。这个搜索中的行动并不是现实世界中的行动，而是规划上的行动：给规划增加一步，通过将一个行动放到另一个的前面而强加顺序，等等。下面，定义偏序规划的POP算法，将POP算法写成一个独立程序是一种惯例，但是把偏序规划形式化表示为搜索问题的一个实例。这使我们集中于可用的规划改进步骤，而不用担心算法是如何探索空间的。事实上，一旦搜索问题被形式化表示后，范围广泛的各种无信息搜索和启发式搜索都可以被运用。10注意，我们搜索问题的状态是（大多数是未完成的）规划。为了避免同现实世界中的状态相混淆，我们将讨论规划而不是状态。每个规划都有下列4个部分，其中前两个定义了规划的步骤，后两个提供决定如何扩展规划的记录功能：（1）一组行动组成规划的步骤：这是从规划问题的行动集中选取的。“空”规划只包含Start和Finish行动，Start行动没有前提且将规划问题初始状态中的所有文字作为其效果，Finish行动没有效果且将规划问题的目标文字作为其前提。（2）一组定序约束：每个定序约束的形式是A﹤B，读作“A在B之前”，它的意思是行动A必须在行动B之前某时刻执行，但是并不必要在紧邻的“之前”。定序约束必须描述一个合适的偏序，任何循环（例如A﹤B和B﹤A）表示矛盾。所以如果会造成循环，该定序约束不能添加到规划中。（3）一组因果连接。规划中行动A和B之间的因果连接写为，读作“A为B获得P”。例如，因果连接断言RightSockOn是行动RightSock的效果，同时是RightShoe的一个前提。它还断言在从执行行动RightSock的时刻到执行行动RightShoe的时刻的这段时期内，RightSockOn必须保持为真。（4）一组开放前提。当一个前提不能从规划的一些行动中得到时，它是开放的。在不引入矛盾的情况下，规划系统会致力于缩少开放前提集合直到它成为空集。例如，图9-1中的最终规划有下面这些组成部分（没有显示将任何其他行动放在Start之后及Finish之前的定序约束）。行动：{RightSock,RightShoe,LeftSock,LeftShoe,Start,Finish}定序：{RightSock﹤RightShoe,LeftSock﹤LeftShoe}连接：{,,}开放前提：{}。这意味着我们可以把“执行规划”的概念从全序扩展到偏序。一个偏序替代一个偏序规划是通过反复选用任何可能的下一个行动来执行的。后面会讨论到，Agent在执行规划时可得到的灵活性在现实世界不与它协作时可能非常有用。灵活的定序也使得将小规划合并到大的规划中变得更容易，因为每个小规划能够重新对它的行动排序以避免与其他规划冲突。现在我们已经准备好形式化表示POP求解的搜索问题，我们将从适合命题规划问题的形式化方法出发，而把一阶的复杂情况留给以后讨论，通常定义包括初状态、行动和目标测试。（1）初始规划包括Start和Finish，定序约束Start﹤Finis