智能规划的研究与发展
2021-12-14李东兵谷文祥
刘 莹，李东兵，谷文祥
(1.长春人文学院公共计算机教研部，长春 130117; 2.长春汽车工业高等专科学校信息技术学院，长春 136000; 3.东北师范大学信息科学与技术学院，长春 130117)
智能规划自诞生之日起就一直倍受瞩目，大到航空航天、智能工厂、智能交通，小到机器人控制、作业调度、桥牌游戏，无不是智能规划在现实世界中的价值体现。由于其重要的应用价值，近年来已经成为人工智能领域极为活跃的研究热点。
通俗地说，规划就是为了实现某项任务而进行了一系列活动。由于在任务执行过程中还会有这样或那样的约束，所以只有规划得当，才能更快更好地完成各种任务。具体地说，智能规划是有组织有目的地选择一系列动作去尽可能好地实现的目标。由于现实世界的复杂性和应用领域的不同，也衍生出许多种规划方法，如图规划、概率规划、时序规划、启发式规划、感知规划等。
1969年，由Newell和Simon设计的通用问题求解器(GPS)[1]是一款在人工智能领域中非常重要的求解器，它标志着智能规划研究的起点。同年，QA3系统[2]问世，它使用定理证明的方法来构造规划。1971年，Fikes 和Nilsson 共同设计了STRIPS规划系统[3]，它在智能规划领域中具有划时代的意义，许多规划方法都是在STRIPS规划系统的基础上进行了扩展。在20世纪80年代对于智能规划的研究一度低迷，直到90年代才出现了三种新的规划方法，对智能规划的研究又一次获得全世界的关注。这三种新方法是将规划问题求解转化为可满足(SAT)问题[4-5]、图规划[6-7]和启发式规划方法[8]。近年来，在这三种方法的基础上，又演变出更多更好的规划系统，成功地解决了许多实际问题[9-10]。此外，自1998年开始，每两年举办一次的国际规划竞赛也为世界各国的规划系统提供了一个全新的舞台[11]。
智能规划发展至今共有三种表示方式：STRIPS[12]、ADL[13]、PDDL[14]。STRIPS操作符可以对规划进行清晰地描述和操作。动作描述语言(ADL)，除了具备STRIPS的表达能力外，还能表达条件效果、量化效果等。规划领域定义语言(PDDL)具有超强的表达能力，能够刻画时间和数值方面的属性，目前它已经成为国际智能规划竞赛的公认标准。
1 智能规划的分类
智能规划自诞生之日起已经繁衍出许多种类型，经过归纳总结，大致可分为四种，如表1所示。
1.1 经典规划
在经典规划中，一个问题被定义成一个四元组
经典规划的求解方法，主要可以归为两大类：状态空间规划和规划空间规划。状态空间规划主要是将状态空间搜索技术应用于规划，其中的操作符同时显式地指明了前提和效果，可以前向或后向构建搜索。而在规划空间规划中，规划器搜索的是规划空间，规划定义成具有一定顺序并被变量绑定的规划操作集合，它不一定对应一个动作序列[9]。
1.2 现代经典规划
与经典规划一样，现代经典规划也是受限的状态转换系统，它将搜索空间的每个结点看作成几个部分规划的集合。把这个集合当成一个搜索结点时，该集合在数据结构上或者是显式的，或者是隐含的，但有一点事实是显然的：在现代经典规划方法中，不是每一个结点的动作都出现在从该结点开始的可达解规划中。现代经典规划技术的发展，给规划带来了新的搜索空间和搜索算法，扩大了可解的经典规划问题的规模。在现代经典规划技术中，主要有图规划技术、命题可满足技术和约束可满足技术[19]。本文着重介绍图规划及其扩展技术。
1.2.1 图规划 图规划系统(Graphplan)是世界上第一个采用图来解决规划问题的方法。图规划求解方法主要有：扩展规划图和搜索规划图两个步骤。图的扩展和搜索迭代循环进行，直到找到一个有效规划，或满足终止条件为止。图规划从初始状态构成的命题层出发，在动作集合找到每个命题需要的支撑动作，构成动作层，通过添加每个动作执行的效果再次构成命题层，就这样向后扩张规划图，当所有目标都出现在命题列时，立即从后往前搜索有效规划。由于引入了命题结点和动作结点互斥的概念，有效地缩小了规划图的搜索空间，求解能力也得到了很大的提升。
图规划是公认的经典而优雅的算法，自其问世以来，吸引了越来越多的目光，研究者们也对其展开了相当多的研究，做了不少的改进与扩展，形成了一个庞大的图规划家族。
1.2.2 图规划的扩展 最小承诺的图规划[20]是在图规划的基础进行了扩展，其算法也包括图扩张和解搜索两个阶段。采用该方法在搜索空间上比较紧凑，目标出现早，提高了求解的效率。试验表明，在经典规划域中，最小承诺的图规划算法能够比图规划以及图规划家族的其它规划器解决更多的问题。
为了使图规划可以处理更具表达力的语言和更复杂的规划问题，在规划中加入条件效果。带有条件效果的图规划方法主要有全扩展法[21]、要素扩展法[22]和IPP扩展法等。2003年，刘日仙等人在此基础上提出了利用兄弟元件改进的要素扩展法[23]，该方法将带有条件效果的动作分解成元件，还利用了独立集选择的启发式提高了搜索的效率。
灵活图规划方法(FGP)[24-25]弥补了图规划对获取现实世界中的某些细节不充分的缺陷，对原有的规划定义进行了扩展，并且提升了规划问题求解综合效率。它可以处理更为复杂的现实问题，更加贴近人们的生活。灵活图规划中增加了满意度和主观真值度的定义，显示出在求解过程中更加重视规划的质量，在某种程度上不惜以规划长度来换取规划质量。2005年，徐丽提出了以目标为导向的灵活图规划算法(GDFGP)[26]，从目标开始逆向扩张规划图，并且避免了满意度传播这一复杂过程。对灵活图规划的研究还有很多，如基于启发式搜索的灵活规划算法[27]、基于软约束的多Agent灵活规划[28-29]等。
数值图规划可以解决带有资源约束的规划问题。Koehler提出的规划系统Resource-IPP[30]就可以有效地解决这类问题，它也是数值图规划的代表。任斐在数值图规划的基础上，提出了嵌入模糊部件的数值图规划生成算法[31]，通过引入模糊部件，重新定义互斥关系及满意度在规划图中的传播方法来提高规划系统的工作效率。
时序图规划就在图规划的基础上增加了时序的要求，TGP和TPSYS[32-33]就是性能比较优秀的两款时序图规划器。在现实世界中，动作的完成时间可能是并行的，也可能是重叠的，并具有不同的持续时间，而经典STRIPS域规划模型的表达是完全不够的，而时序图规划恰好可以解决这类问题。
1.3 不确定规划
在纷杂的现实世界中，总会存在这样或那样的不确定性，想要得到所有确定的信息几乎是不可能的，这就需要不确定规划来实现。
马尔可夫决策过程(MDP)是将规划看成一个最优化问题，可以比较高效地处理多种不确定规划问题。利用MDP求解智能规划问题时，每个动作都会有多种可能的输出，通过输出的概率值、目标和效用值进行计算，最后规划算法搜索出效能函数值最大的规划方案。
基于符号模型检测[34]的规划方法可以处理涉及概率分布的和部分可观察的规划问题，它将规划领域看成是一个不确定的状态转换系统，动作的多个效果被表示为多个不同的状态，其规划目标也按照不同的强度来表示，并使用有序二元决策图(OBDD)[35]的符号处理技术来实现算法。
概率规划、一致图规划和感知图规划都是基于图规划的不确定规划。概率规划PGP[36]算法采用概率分布的方式来描述动作结果的不确定性，可以在给定的最大时间步T内找到成功概率最大的最优规划。一致图规划CGP[37]可以感知动作的效果，可以在初始条件及动作效果不确定的情况下，可以找到规划解。感知图规划SGP[38]可以处理初始状态不确定，动作带有条件效果且具有感知动作的规划问题。
1.4 启发式规划
启发式规划将规划问题看作是一个搜索问题，运用启发式搜索技术朝着可能的目标结点方向进行搜索找到目标结点。启发式的设计原则就是放松，即对原来的问题做一些简化假设和放松某些约束而得到一个更简单的问题。在求解方法中，启发式搜索可以和其它的方法结合使用，大大地提高了规划系统的效率。文献[39]将图规划下的启发式搜索方法进行了综述，比较分析了多种启发式方法。
HSP[40]是一款基于启发式搜索思想的域独立规划器，通过累加启发值(hadd)计算目标实现的代价。1998年，HSP在世界规划大赛中超越了GraphPlan和SatPlan，赢得了冠军。就解决问题的数量而言，HSP无疑是最优秀的规划器，但速度较慢、规划的长度较长，且不能保证规划解的质量是它的不足之处。
HSP-r[41]利用启发值指导进行后向搜索，可以访问到更多的状态，能够在较短的时间内产生更优的规划解。HSP-r采用了同Graphplan相同互斥思想来进行剪枝，但是与同域指定的搜索算法相比，速度还是比较慢。
FF(Fast-Forward)[42-43]是最成功的启发函数设计方法之一。它采用加强爬山算法，在每个搜索状态中都会调用放松图规划，从而获得一个关于估计的目标距离的信息以及一个当前状态的最有希望的后继状态。FF还采用目标删除和目标日程两种技术成功地避免了找不到解和浪费很多时间去找排在后面的目标的情况，大大地提升了求解的质量和速度。
LPG[44]是一款采用局部搜索来解决规划图问题的快速规划器。它能够使用各种基于参数化的目标函数的启发式。LPG充分运用了规划图结构，搜索空间由规划图的特殊子图——动作图构成，能够处理考虑到动作执行代价的规划问题，得到优质解。实验表明，LPG非常高效，在很多著名问题的解决上优于规划图类算法。
2 智能规划与规划识别的联系
规划识别是将行动者执行的一个动作序列作为输入，观察者将根据观察到的动作进行推理，最后推测出执行者的最终目标，而智能规划是寻找能够实现给定目标的动作序列，由此可见，智能规划是规划识别的反向推导过程，二者联系极其密切。若将智能规划与规划识别统一起来，就可以解决更多更复杂的问题，这也是未来一个重要而热门的研究难点。
2.1 规划识别即是智能规划
规划识别是逆向规划，在规划中，寻求实现目标的动作序列，而在规划识别中，寻求解释所观察到动作的目标。这两种任务都具有诱导性，需要采用一些假设来解释给定的信息：规划解释目标，目标解释部分观察到的规划。
实际上，规划识别的工作是独立于规划进行的，主要使用与规划无关的手工库或算法。因此，Miquel Ramírez等[45-46]通过利用近代经典规划算法的功能和通用性来消除规划识别和规划之间的隔阂，从而实现对给定域理论的一系列观察结果的识别。该模型比基于库的方法更加灵活，并允许一些简单的扩展，如处理通量的观察、处理执行时必须观察的操作以及对观察的部分排序。然而，该模型的一个重要方面是，它并不对可能的假设(目标)进行加权，而只是对它们进行过滤。
2.2 基于智能规划、规划识别与解析的启发式方法
2016年Miquel Ramírez 等又提出了基于智能规划、规划识别与解析的启发式方法[45]。该方法通过将规划库编译为STRIPS理论，证明了该公式包含了库规划识别的标准公式。这些库对应于可能是循环的与或图，其中与节点的子节点可能是部分有序的。这些库将上下文无关语法作为一种特殊情况，在这种情况下，规划识别问题变成了带有丢失标记的解析问题。对于标准库的规划识别可以成为任何现代规划器都能轻松解决的规划问题。而对于更为复杂的规划库的识别，即包括上下文无关语法，则说明了当前规划启发式的局限性，并提出了可能提高其他规划问题的建议。
2.3 基于规划识别与智能规划构建有帮助的虚拟智能体
2016年，Geib等[47]提出了一种基于规划识别和智能规划交互的协同行为模型。基于对“发起者”Agent的行为的观察，“支持者”Agent使用规划识别来假设发起者的规划和目标。然后“支持者”Agent提出并规划一组它将实现的子目标来帮助发起者。该方法假设“发起者”Agent和“支持者”Agent在谈判中使用的术语之间有密切的对应关系。因为Agent之间的知识重叠程度越高，用于识别领域概念的名称之间的对应越紧密，就会出现合作更容易协商的情况。
主要思想是规划识别和规划组件的成功集成以规划识别器进行适当的子目标识别为中心，并结合轻量级的协商过程，生成目标供规划器用于构建适当的动作序列。该方法在一个开放源代码的虚拟机器人平台上进行了演示，并获得了成功，充分展示了这种方法的潜力，未来这些技术将被扩展到更为复杂的现实情况。
3 结语和展望
智能规划一直以来都是人工智能的一个重要研究方向。随着科技的不断创新与发展，它已经逐渐地深入到我们的生活与生产当中。大到航空航天、生产调度，小到网络游戏、电子导航，其应用不胜枚举[48-49]。本文从智能规划的起源讲到分类，并详细地对各种目前比较成功的规划进行了对比与说明。最后对智能规划与规划识别的关系进行了阐述，并列举分析了几种先进的研究方法。“路漫漫其修远兮，吾将上下而求索”，相信在智能规划的研究路途中，会涌现出更多更好的规划方法，为人们的生活带来更多的便利和乐趣。
