规划问题语言

前面的讨论建议了规划问题的表示——状态、行动和目标——应该使规划算法利用问题的逻辑结构成为可能。关键是找到一种有足够表达能力能够描述范围很宽的各种问题的语言，但又是充分限定的以使高效算法能够执行。在本节中，我们首先概括了经典规划器的基本表示语言，即STRIP语言[2]。稍后，我们指出类STRIPS语言的许多变种中的一些。

状态表示。规划器将世界分解成逻辑条件，并且把一个状态表示为正文字的合取。我们将考虑命题文字；例如，Poor∧Unknown 可能表示了一个不幸智能体的状态。我们也使用一阶文字；例如， At(Plane1, Melbourne)∧At(Plane2, Sydney)可能表示包裹递送问题中的一个状态。一阶状态描述中的文字必须是基项（ground，即无变量的项——译者注）并且是无函数（function-free）的。而形如At(x, y)或At(Father(Fred), Sydney)的文字是不允许的。采用了封闭世界假设，含义是在一个状态中未提及的条件被假定为假。

目标表示。目标是用正的基文字的合取式表示的不完全指定状态，例如Rich∧Famous或At(P2, Tahiti)。假如一个命题状态s包含目标g的所有原子（可能还有有其它原子），那么s满足g。例如，状态Rich∧Famous∧Miserable满足目标Rich∧Famous。

行动表示。一个行动是根据前提和效果来指定的，前提在该行动执行前必须成立，效果则是在其执行后发生。例如，一个表示飞机从一个地方飞到另一个地方的行动：（其中PRECOND表示前提，EFFECT表示效果——译者注）

Action(Fly(p, from, to),

PRECOND:At(p,from)∧Plane(p)∧Airport(from)∧Airport(to),

EFFECT:¬ At(p,from)∧At(p,to))

更确切的是称之为行动模式，意思是它表示了许多不同行动，这些行动能够通过把变量p，from和to初始化为不同常量得到。通常，一个行动模式由3部分组成：

• 行动名和参数表——例如，Fly(p, from, to) ——用来标识行动。

• 前提是无函数正文字的合取式，规定在行动能够被执行前，一个状态中哪些文字必须为真。前提中的任何变量也必须出现在行动参数表中。

• 效果是无函数文字的合取式，描述了当行动执行时状态是如何变化的。效果中的正文字P在由行动产生的状态中被断言为真，而否定文字（负文字）¬P 则被断言为假。效果中的变量也必须出现在行动参数表中。

为了提高易读性，一些规划系统将效果划分为正文字的增加表和负文字的删除表。

在定义了规划问题的表示语法之后，我们现在可以定义语义了。最直接的方法是描述行动是如何影响状态的。（一个可供选择的方法是指定到后继状态公理的直接转换，它的语义来自一阶逻辑；参见习题11.3。）首先，我们称一个行动在任何满足前提的状态中都是可用的；否则，行动没有效果。对于一阶的行动模式，建立可用性将包括一个对前提中变量的置换θ。例如，假设当前状态描述为

At(P1, JFK)∧At(P2, SFO)∧Plane(P1)∧Plane(P2)∧Airport(JFK)∧Airport(SFO)

这个状态满足前提

At(p, from)∧Plane(p)∧Airport(from)∧Airport(to)

用{p/P1,from/JFK,to/SFO}进行置换（除了其它以外——参见习题11.2）。这样，具体行动Fly(P1,JFK, SFO)是可用的。

从状态s出发，执行一个可用行动a的结果是状态s'，除了把a的效果中任何正文字P添加到s'中，把任何负文字¬P从s'中去除以外，s'与s是一样的。这样，在Fly(P1, JFK, SFO)之后，当前状态变为

At(P1, SFO)∧At(P2, SFO)∧Plane(P1)∧Plane(P2)∧Airport(JFK)∧Airport(SFO)

注意如果一个正效果已经在s中，它不会被再次添加，如果一个负效果不在s中，这部分效果将被忽略。这个定义体现了所谓的STRIPS假设：在效果中没提及的每个文字保持不变。以这种方式，STRIPS避免了第十章中描述的表示框架问题。

最后，我们可以定义规划问题的解。在它的最简单形式中，这就是一个行动序列，当在初始状态中执行时，导致满足目标的状态。本章的后面部分，我们将允许解为行动的偏序集，倘若每个符合偏序的行动序列都是一个解。