命题编码的复杂度

命题方法的主要缺陷是从原始规划问题产生的命题知识库的绝对规模。例如，行动模式Fly(p, a1, a2)变成T ×|Planes|×|Airports|2个不同的命题符号。通常，行动符号总数限制在T ×|Act|×|O|P内，其中|Act|是行动模式数，|O|是域内对象数，P是任何行动模式的最大数量（参数的个数）。子句数还要更多。例如，10个时间步，12架飞机，及30个机场，完全的行动排斥公理拥有5.83亿条子句。

因为行动符号的个数是行动模式参数个数的指数级，一种答案可能是试着减少参数个数。我们可以借用语义网络（第十章）的思想来实现。语义网络只使用二元谓词；具有多个参数的谓词可以被简化为一组独立描述每个参数的二元谓词。将这个思想用于诸如Fly(P1, SFO, JFK)0的行动符号，我们得到3个新的符号：

Fly1(P1)0：飞机P1在时刻0起飞

Fly2(SFO)0：飞行起点是SFO

Fly3(JFK)0：飞行目的地是JFK

这个过程称为符号分割，消除了对指数级符号个数的需要。我们只需要T ×|Act|× P ×|O|。

符号分割自身能够减少符号数，但是不能自动减少 KB（知识库）中的公理数。也就是，如果每个子句中的每个行动符号只是简单的被一个三个符号的合取式代替，那么知识库总规模将大致保持不变。符号分割事实上的确降低了KB的规模，因为某些分割符号对特定公理是不相关的，可以被忽略。例如，考虑公式（11.1）中的后继状态公理，修改它，以包含LAX和忽略所有行动前提（这会被分离的前提公理涵盖）：

At (P1, JFK)1⇔ (At (P1, JFK)0∧ ¬Fly(P1, JFK, SFO)0∧ ¬Fly(P1, JFK, LAX)0)

∨ Fly(P1, SFO, JFK)0∨Fly(P1, LAX, JFK)0

第一个条件说明P1会位于JFK，如果时刻0它在那里而且没有从JFK飞往任何其它城市，无论哪一个；第二个说明它将在那里，如果它从任何另一个城市飞往JFK，无论哪个城市。使用分割符号，我们可以简单地忽略那些值不要紧的参数：

At (P1, JFK)1⇔ (At (P1, JFK)0∧ ¬(Fly1(P1)0∧ Fly2(JFK)0))

∨ (Fly1(P1)0∧ Fly3(JFK)0)

注意在这条公理中没有再提到SFO和LAX。更一般地，分割行动符号现在允许每个后继状态公理的规模独立于机场数目。同样的缩减发生在前提公理和行动排斥公理上（参见习题11.16）。对于早先描述的10个时间步，12架飞机及30个机场的情况，完全的行动排斥公理从5.83亿条子句减少到9360条子句。

有一个缺陷：分割符号表示不允许并行行动。考虑两个并行行动Fly(P1, SFO, JFK)0和Fly(P2, JFK, SFO)0。转变成分割表示，我们有

Fly1(P1)0∧ Fly2(SFO)0∧ Fly3(JFK)0∧

Fly1(P2)0∧ Fly2(JFK)0∧ Fly3(SFO)0

不可能再判断发生了什么！我们知道 P1和 P2飞行，但是我们无法确定每个飞行的起点和目的地。这意味着必须使用一个有前面提到的明显缺点的完全行动排斥公理。

基于可满足性的规划器能够处理大规模规划问题——例如，找到拥有许多块积木的积木世界规划问题的最优30步解。命题编码的规模和解的耗散是高度依赖于问题的，但是在大部分情况下，存储命题公理所需要的内存是瓶颈。从这个工作中的一个有趣发现是在求解规划问题上，诸如DPLL这样的回溯算法往往比诸如 WALKSAT 这样的局部搜索算法更好。这是因为命题公理的大部分是霍恩子句，用单元传播技术来处理是十分有效的。这个观察结果导致把某些随机搜索与回溯以及单元传播结合起来的混和算法的发展。