HTN规划方法的性能研究

HTN规划方法的性能研究摘要人工智能作为一门对从环境接收感知信息并执行行动的智能体的研究的学科，近年来越来越受到各个领域研究人员的关注与重视，而自动规划是人工智能中一个十分重要的研究子领域，专门从计算上研究规划这种抽象的、清晰的深思熟虑过程，这个过程通过预期动作的期望效果，选择和组织一组动作，其目的是尽可能地实现一些预先给定的目标。自动规划的方法众多，但近年来HTN（分层任务网络）规划则是学界最热门的研究方向之一，同时在对HTN规划的研究中也产生了许多新的规划方法，例如规划空间规划的搜索空间节点部分规划的结构是从对HTN做出贡献的规划器NONLIN中逐步发展来的。本课题将选取HTN规划中由UniversityofMaryland的DanaNau等人开发的具有良好性能的开源规划器SHOP为例，通过编写领域知识对一个电梯载人问题进行求解并引入启发式的方法，同时用简单调度规则对此问题求解，在不同的问题规模下对求解的结果进行比较。最后，本课题对此标杆问题引入时态约束，在SHOP2规划器中用MTP（多时间轴预处理）技术对问题进行求解。关键词：人工智能；自动规划；HTN规划；时态约束

ResearchonPerformanceofHTNPlanningMethodsAbstractArtificialintelligence,adisciplinestudyingonreceptionofsensoryinformationfromenvironmentandaction,hasbeenpaidincreasinglyattentioninrecentyears.Asanimportantsubfieldofartificialintelligence,automaticplanningmainlyfocusesontheprocessofabstract,clearthoughtbycomputing.Byexpectingeffectofexpectedoperation,theprocessselectsandorganizesasetofactionstoachievegivengoals.Althoughmanymethodsinautomaticplanninghavebeenwellestablished,HierarchicalTaskNetwork(HTN)isbecomingpopularinthoseyearsandnovelplanningmethodshavebeendevelopedfromthestudyonHTNplanning.Forexample,thestructureofspatialplanning,thatisthenodeinthesearchspaceofplanningspaceplanning,hasbeendevelopedgraduallyfromtheNONLINplanner,whichhascontributedalottotheHTNplanning.ThispaperwillselecttheHTNopensourceplannerSHOP2withgoodperformancewhichisdevelopedbyDanaNauwhoisfromUniversityofMaryland,andsolveanelevatormannedproblembywritingthedomaindescriptionintheSHOP2plannerwithintroducingaheuristicapproach.Meanwhile,wewillusethesimpleschedulingrulestosolvetheproblem,andcomparetheresultsofthesimpleschedulingrulesandSHOP2plannerindifferentproblemscale.Finally,weintroducetemporalconstraintsintothisbenchmarkproblem,whilesolvethisproblembyusingtheMTP(multi-timelinepreprocessing)technologyinSHOP2planner.Keywords：ArtificialIntelligence;automaticplanning;HTNplanning;temporalconstraints

目录摘要 1Abstract 21. 选题背景 51.1. 课题来源及背景 51.2. 课题目的及意义 61.3. 课题内容及研究方法 61.4. 国内外基本研究概况 71.5. 指导思想与文章结构说明 102. 关键理论与技术 122.1. 规划问题的经典表示方法 122.2. HTN规划 142.3. MTP技术 163. 电梯载人问题HTN建模及求解 183.1. 电梯载人问题 183.2. 利用JSHOP2进行建模求解 194. HTN规划与简单调度规则的比较 304.1. 几种常用的简单调度规则 304.2. 调度规则求解及与规划器比较 304.3. 扩大问题规模并求解比较 325. 时态约束下的HTN规划 375.1. 引入时态约束后的问题 375.2. 对领域及问题描述所做的修改 375.3. 时态规划求解过程与结果 425.4. MTP处理时态约束的小结与存在问题 436. 总结与今后研究方向 456.1. 总结 456.2. 今后研究方向 46致谢 47参考文献 48附录代码清单 51附录一电梯载人问题代码 51附录二扩大规模后的电梯载人问题代码 55附录三引入时态约束后的电梯载人问题代码 58

选题背景课题来源及背景规划是关于动作的推理。它是一种抽象的、清晰的深思熟虑过程，这个过程通过预期动作的期望效果，选择和组织一组动作，其目的是尽可能好地实现一些预先给定的目标。而智能规划则是人工智能（AI）中专门从计算上研究这个深思熟虑过程的一个领域[1]。规划的形式由于动作的种类繁多而多种多样，例如运动规划是在移动系统所在的参数配置空间中寻找一条轨迹，感知规划是解决类似于需要何种信息及合适需要这些信息的问题，等等。由于对于自动规划的研究始于工程实践中对于快速经济且有效地解决规划问题的需求，早期的自动规划实践都集中在领域相关规划，即对每种问题都根据问题的特点使用专门的表示并设计开发与之相适应的技术，这种规划方法的好处在于能够很好的利用领域知识解决问题，但也存在着不可回避的缺陷，对于每种规划问题都需要分别进行处理而不是使用一般化的工具，其费用较高。基于此，自动规划研究的更主要是与领域无关的通用方法，这种规划是基于抽象的、通用的动作模型。这类模型主要有以下一些形式的模型与规划能力：项目规划，所用的模型动作已简化为时代和次序约束；调度与资源分配，所用动作模型包括项目规划中的约束，还增加了动作的资源约束；规划合成，所用模型的动作比前面两种模型更丰富，增加了动作运用的条件和动作对世界状态的效果。尽管自动规划在理论上的研究还处于早期阶段，但实际应用中已经发展到可以满足许多需求的程度了，而在这方面的成功例子非常多，例如在自动化立体仓库中AGV小车的路径与动作规划。通过自动规划技术，可以让智能体通过感知周边的环境为实现给定的目标自动的规划出一套行动方案。课题目的及意义到目前为止，国内外学者提出了各种各样思路完全不同的规划方法，不同的规划方法能够处理的问题的特征也不尽相同。在过去的15年内，大部分在人工智能规划系统上的实用工作都基于分层任务网络（HTN）规划[2]，这是继STRIPS规划后最为重要的规划方法。同时，针对于某一种具体的规划方法，也有许多有着差别的规划器被提出，例如HTN规划中比较有影响力的规划器有UMCP[3]、NONLIN[4]、SHOP2[5]、SIPE-2[6]、O-PLAN[7][8]等。本课题将选取HTN规划中由UniversityofMaryland的DanaNau等人开发的具有良好性能的开源规划器SHOP为例，通过编写领域知识对一个电梯载人问题进行求解并引入启发式的方法对其进行改进，同时用简单调度规则对此问题求解，在不同的问题规模下对求解的结果进行比较。最后，本课题对此标杆问题引入时态约束，在SHOP2规划器中用MTP（多时间轴预处理）技术对问题进行求解。通过对本课题的研究，能够使得自己对HTN规划有更为清晰与全面的了解，同时也对规划空间规划做一定的了解，通过与简单调度规则对问题求解的结果进行比较，对自动规划技术的优势产生一定的感性认识，并学习MTP技术为今后的研究奠定基础。此外，从学习规划器语法、编写领域知识、到求解等这一系列过程，通过自己的切实参与，会使自己基本了解研究问题、解决问题包括哪些基本步骤。对模型的求解过程会使自己在算法设计方面积累一定的经验。课题内容及研究方法本课题由一个电梯载人问题展开，在使用HTN方法解决此问题的过程中对HTN进行多方面的探究。课题首先使用在2002年国际规划大赛上获得了前四名的好成绩的高效规划系统——SHOP2规划器对此问题进行建模求解，在此过程中逐步加入启发式规则引导搜索，以期得到更高的规划解。并设计一个问题，对此领域进行测试，以确保领域的可靠性与完备性。之后课题提出几种常用在电梯调度领域的调度规则对问题进行手动求解，并对求解的结果进行比较。扩大问题规模后，再次用SHOP2规划器与调度规则求解比较。同时，鉴于规划空间规划的搜索空间节点部分规划的结构是从对HTN做出贡献的规划器NONLIN中逐步发展来的，课题也试图在规划空间规划中最具代表性的开放源代码的UCPOP的Lisp执行程序中对此问题的求解进行了一定的探索。最后，由于时态约束是最重要的一类约束，课题也对此做了一定的工作，课题为之前所提到的电梯问题增添时态约束，并使用MTP（多时间轴预处理）技术在SHOP2规划器中进行求解。国内外基本研究概况到目前为止，国内外学者提出了各种各样思路完全不同的规划方法，不同的规划方法能够处理的问题的特征也不尽相同。同时，针对于某一种具体的规划方法，也有许多有着差别的规划器被提出，例如HTN规划中比较有影响力的规划器有UMCP[3]、NONLIN[4]、SHOP2[5]、SIPE-2[6]、O-PLAN[7][8]等。本课题主要是对一个电梯载人问题进行研究，通过标准化的方法将规划问题进行表达，所涉及到的规划方法主要有HTN规划、规划空间规划，并在本文最后的部分对时态约束规划有一定的涉及。因此本章节将从四个方面进行综述：(1)智能规划的模型及规划问题的表示。(2)HTN规划。(3)时态规划。智能规划的模型及规划问题的表示自动规划的早期研究工作收到了自动推理证明的很大影响。首批自动规划阐述的一种形式[9]使用了对初始状态、目标状态和规划操作的公理化描述，使用归结定理证明产生对存在规划的构造性证明，然后使用答案抽出过程找出实际规划。然而，这种方法在处理众所周知的框架问题[10]时遇到了困难，建立经典规划描述的目的之一就是这种描述为框架问题提供了一个简单的解法：在经典规划中，在操作效果中没有提到的原子在动作过程中保持不变。经典规划与早期的规划系统STRIPS联系在一起，每个操作有前提条件、增加表、删除表，这些表允许包含任何的一阶逻辑合式公式。在后来的工作中，研究者对表示做了限制，使用前提条件、增加表、删除表只能包含原子。Nilssiom在他1980年的教科书中用这种方式阐述了STRIPS[11]。从此以后，操作和表示方法分别变成了众所周知的STRIPS型操作和STRIPS型规划。在UCPOP[12]规划器中，Penberthy和Weld对STRIPS型操作做了句法修改，操作不再具有增加表和删除表，而是写成正效果和负效果。这种表示是我们经典规划操作表示的基础。Pednault[13,14]引进了动作描述语言表示（ActionDescriptionLanguage，ADL），值金额中语言权衡了一般逻辑表示的表达能力和利用表示推理的复杂性。从UCPOP[9]开始，各种规划器对ADL或者是接近于ADL的表示做了推广，使之能处理经典规划中大多数的扩展。这些扩展都已经在PDDL规划语言中实现，PDDL语言用于国际人工智能规划和调度会议（InternationalConferenceonAIPlanningandScheduling，AIPS）的规划大赛中。HTN规划在过去的15年内，大部分在人工智能规划系统上的实用工作都基于分层任务网络（HTN）规划[2]，这是继STRIPS规划后最为重要的规划方法。HTN规划用状态原子集合来表达世界的状态，并在一定的前提下，动作将通过增加和/或删除状态原子改变世界。在这一点上，HTN与经典规划十分相似，但不同的是规划问题的类型及对问题进行规划的方法。HTN规划的基本思想最初是Sacerdoit[15]在25年前的研究中提出并发展而来的，Tate的Nonlin规划器[4]也是最早使用HTN规划基本思想的规划器。Yang[16]、Kambhampati和Hendler[17]等人首次对HTN规划的理论模型进行了研究。Erol[3]等人提出了一种完备的模型，该模型的提出为复杂性分析[18]奠定了基础，并且给出了第一个可被证明为正确的HTN规划程序，即UMCP[3]。下面列出了一些最为著名的领域无关的HTN规划系统：Nonlin[4]是最早的HTN规划系统之一。SIPE-2[6]已被应用于许多领域。O-plan[7][8]也在许多应用领域得到应用。UMCP[3]是第一个使用被证明是可靠且完备的规划算法的系统。SHOP2[3]是一个高效的规划系统，该系统在2002年国际规划大赛上获得了前四名的好成绩。需要说明的是，Lifted-PFD程序是简化版本的SHOP2，Lifted-TFD程序是SHOP2的前身SHOP的简化版本，而我们的Abstract-HTN程序是简化版本的UMCP。NONLIN和SIPE-2系统使用了外部前提条件，不过其外部前提条件实在领域描述中声明的。而UMCP系统则采用了能自动发现外部前提条件的算法。O-Plan、SIPE-2和SHOP2各自都能处理某类时态规划问题。综上所述，与经典规划相比，HTN规划器主要的有点在于其推理能力以及它们能对经验知识进行有效表示。HTN规划器能表示并求解多种非经典规划问题。如果有好的HTN方法集合引导搜索的话，HTN规划器求解经典规划问题的速度能比那些经典的或新经典规划器快好几个数量级。HTN规划器的主要缺点是不仅需要领域专家给出规划动作集合，还要给出方法集合。时态规划对于时态规划问题，既可以从面向状态的角度处理，也可以从面向时间的角度处理。正如大多数近期出现的规划器一样，早期的关于时态规划的工作采用的是面向状态的角度。这主要是由于这种面向状态的处理方法更接近于经典规划的处理方法，因此可以更容易地与经典规划技术相结合，也更容易地从这些经典规划技术的最新进展中获益。使用面向状态的处理技术的规划器有：在状态空间规划器中，根据Deviser[19]早期的工作，最近已经出现了几个能处理时间的采用启发式引导技术的规划器，例如TLplan及其后续规划器[20,21]、ALplanner[22,23,24]和HS[25]规划器。在规划空间规划中，ZENO[26]系统能表示可变的持续时间和线性约束。在规划图方法中个，TGP[27]、SAPA[28]和TPSYS[29]能处理持续时间和其他时态结构。在HTN规划中，几个规划器如O-plan[7][8]、SIPE[30]和SHOP2[2]在各自的表示和搜索过程中整合了时间窗口和约束的技术。在这些规划方法中，最近几个规划器显示了非常高的求解效率，并且允许进行合理的调节。然而，通常这些方法都会导致并发动作的受限模型。通常的假定是，动作带有一持续时间，但不考虑在该持续时间内的中间时间点的情况。动作的前提条件和效果均在持续时间区间的端点处被声明，并且这些前提条件和效果的取值情况将在持续时间区间内保持不变。面向时间角度的规划观点来自Allen[31]的开创性工作。该规划器正是采用Allen的区间代数处理动作的条件和效果命题间的定性时序约束，这些约束可以出现在动作持续时间内的任何位置。该规划器在规划空间中进行搜索，它是通过IA约束来处理因果链的。面向时间角度的规划方面，另外一个重要的成果是Dean和McDermott[32]的时间映射管理器以及基于它的几个规划器。这些规划期处理我们所表示的时态数据库。指导思想与文章结构说明本课题以小见大，通过对一个电梯载人问题进行研究，试图理清不同规划方法的异同，以及规划与调度之间的联系与区别，并在此过程中加深对于自动规划理解，为今后进一步的研究打下基础。同时，在此对后面的几个章节主要内容进行一个大致的说明。第二章是关键理论与技术。主要对规划问题的经典表示方法、HTN规划、规划空间规划及MTP等理论及技术进行阐释。第三章是电梯载人问题HTN建模及求解。主要对电梯载人问题用SHOP2进行建模，引入启发式规则引导搜索并求解，同时设计一个问题，对此领域进行测试，以确保领域的可靠性与完备性。第四章是HTN规划与简单调度规则的比较。主要使用几种常用在电梯调度领域的调度规则对问题进行手动求解，并对求解的结果进行比较。扩大问题规模后，再次用SHOP2规划器与调度规则求解比较。第五章是时态约束下的HTN规划。主要使用MTP技术对引入时态约束后的电梯载人问题进行规划求解。第六章是对总结与今后研究方向。分析课题研究中有待进一步完善的地方，并给出本课题之后研究方向。

关键理论与技术本章节将分为3个子章节分别对对规划问题的经典表示方法、HTN规划及MTP技术等理论及技术进行阐释。规划问题的经典表示方法概念模型是描述一个问题的主要因素的简单的理论方法。它的意义在于可以把描述同计算和算法分隔开来。多数的规划方法使用了状态转移系统的模型，又称为离散事件系统。一个状态转移系统是一个四元组Σ=S,A,E,γS=sA=aE=e1γ:S×A×E→2一个状态转移系统也可以用有向图表示，其中节点表示S中的状态。如果s'∈γs,u，其中u是一个偶对a,e，a∈A且e∈E，那么途中包含一条从s到s对概念模型施加以下各种限定假设，从而得到受限的概念模型。：假设A0（有限的Σ），假设A1（完全可观察的Σ），假设A2（确定的Σ），假设A3（静态的Σ），假设A4（受限的目标），假设A5（序列式计划），假设A6（隐去时间），假设A5（脱机规划）。经典规划一般是指对受限的状态转移系统进行规划[1]，常用的表示方法有三种，它们具有同等的表示能力：在规划的集合论表示中，世界的状态是一组命题集合，动作是一种句法构造表示，说明当状态具有哪些命题时才可以使用该动作，在应用了动作后所得到的新的状态里，哪些命题是动作加上去的，哪些命题是动作删去的。在经典表示中，状态和动作的描述类似于集合论表示，但是使用一阶文字和逻辑连接符，而不是使用命题。在状态变量的表示中，每一个状态都表示成状态变量的n元组，而每一个动作都用一个状态变量的n元组到另外一个n元组的部分映射函数表示。这种方法常用于表示特征集合在某一有限范围而特征的值随时间改变的领域。其中，经典表示是受限状态转移系统中最常用的。所以下面详细阐述经典表示[1]：经典规划表示中，一个状态是一阶逻辑语言L的一个基原子集。因为L中没有函数，可能状态集S必定是有限集。并规定，一个原子p在s中成立当且仅当p∈s。一个规划操作就是一个三元组o=(nameoname(o)，操作的名字，是形如n(x1,…,xk)的语法表示，其中precondo和effects(o)分别是o一个经典规划领域是一个受限的状态转移系统Σ=S,A,γS⊆2A={O中操作的所有基例}，其中γs,a=(s-effects-(a))∪effect+S对γ是封闭的，即，如果s∈S，则对每一个可应用于s的动作a，γs,a一个经典规划问题是一个三元组P=(Σ,初始状态s0是S目标g是任意一个基文字集；Sg一个规划问题P=(Σ,s0HTN规划如同其他经典的AI规划，HTN规划将现实世界的状态用一组原子表示，而每一个动作都意味着一个确定性的状态转换。但HTN规划与其他经典的AI规划区别在于它们规划什么与它们如何规划。HTN规划器的目标是产生一序列的动作以表示一些活动或工作。规划领域知识的表述包括和其他经典规划器一样的一组操作，以及表示如何将一个任务分解为子任务的方法。给定一个规划领域知识，规划问题的表述将同其他经典规划器一样包括一系列初始状态，但问题规范还包括一组部分有序的需要完成的任务。求解过程中，通过使用方法递归地将任务分解为越来越小的子任务，直到达到能够直接用规划操作来表达的原始任务。对于每个非原始任务，规划器选择一个可应用的方法，实例化并将其分解为子任务，然后选择并实例化方法进一步对子任务进行分解。如果规划随后被证明是不可行的，规划器会滚回并尝试其他方法。HTN方式通常描述了标准操作过程，这通常在一些领域中用来表达任务。HTN规划能够以较快的速度求解规划问题，且规划解的质量取决于领域知识的编写。大多数HTN的实践者认为这样的表达对于现实世界中的很多领域比经典的规划操作更加适合，因为他们更好地描绘了用户思考问题的方式。任务网络是形如w=(U,C)的序对，其中U为任务节点集合，C为约束集合。规划问题的所有解规划必须满足CHTN方法是一个4元组：m其中各成员的含义分别是：namem为方法的名称，是形如n(x1,…,xk)的表达式，这里n是唯一的方法符号（也就是说，规划领域中不存在两种具有相同名称的方法）taskm为(subtasksm,假定w=(U,C)为一任务网络，u∈U为一任务节点，u对应的任务为tu，m为方法M的一个实例，并且taskm=tuδ 其中，C’是对C做下列修改后得到的：对所有含u的先后约束，用含subtasks(m’)的节点的先后约束代替。对前置约束、效果约束或中间约束，如果这些约束中的任务节点集合U‘含有u，则以U-u∪subtasksm'HTN规划领域是一序对：D=(并且一个HTN规划问题是一4元组：P=其中，s0是初始状态，w是初始任务网络，O是动作集合，M为HTN如果w=U,C为原子任务网络，并且存在(U,C)的一个基例(U‘,C’)以及U‘节点集上规划π中的动作由节点u1,…,uk命名，也就是说对于i=1,…,k，规划π在状态s0下全序u1,…,uk满足C‘中的先后约束，也就是说，C’中不存在u对于C‘中的每一前提条件before(U’,l)，l在动作ai的直前驱状态si-1下成立，这里ai为对于C‘中的每一效果约束after(U’,l)，l在动作aj所产生的状态sj下成立，其中ai为U‘对于C‘中的每一中间约束between(U’,U'',l)，l在动作ai和aj的所有中间状态下保持成立，其中ai为U’中最后一个节点命名的动作，a如果w=U,C为非原子任务网络，若此时存在一个可以作用于w并将其分解成原子任务网络w’的任务分解序列，则π为w’的解，则π即为w的解。在此情况下，π的MTP技术SHOP2操作的表达力至少在PDDL第二层，但SHOP2不支持在PDDL第三层中的持续时间动作，SHOP2也没有明确的机制来对持续时间动作与并发动作进行推理。但SHOP2仍然有足够的表达力来表示持续时间动作与并发动作，因为规划过程每一步的当前状态是明确的，且它的操作可以给变量赋值同时进行数值计算。这使得我们可以开发一种叫MTP（Multi-TimelinePreprocessing，多时间轴预处理）的技术，将PDDL操作转化为SHOP2操作，同时保持现在状态中暂时信息的追踪。图2-1中的伪代码对MTP的机制做了一个算法上的描述。为了使MTP的表达简洁，假设在每个状态s，每个原子(pc1…cn)表达了单值属性。如果操作可以改变cn的值则为动态属性。对于每个随着时间改变的属性p，MTP修改操作以保持对现在状态下属性变化时的时间及取决于属性的各种前提条件的时间的追踪。对于每个动态属性p，当前状态将会包含两个时间标记：read-time(p)（最后一个读取p的值的时间）和write-time(p)（最后一个修改p的值的时间）。MTP修改操作在动作读取动态属性这种情况下，操作会更新属性的读时间，如果操作修改了动态属性则还会更新些时间。因此，不同于一个单独的全局时间，当前状态会包含很多局部时间，即每个动态属性的读时间和写时间。foreveryoperatorointheplanningdomainaddtwoparameters?startand?durationtooino’spreconditionaddanassignment?duration←dwheredisaformulaforcalculatingo’sdurationaddanassignment?start←swheresisaformulathattakesthemaximumofthewritetimesofalldynamicpropertiesino’spreconditionandthereadtimesofalldynamicpropertiesino’seffectsforeachdynamicpropertypino’seffectsaddeffectstochangethevalueofwrite-time(p)to?start+?durationforeachdynamicpropertythatappearsinoaddeffectstochangeread-time(p)tothemaximumofread-time(p)and?start+?duration图foreveryoperatorointheplanningdomainaddtwoparameters?startand?durationtooino’spreconditionaddanassignment?duration←dwheredisaformulaforcalculatingo’sdurationaddanassignment?start←swheresisaformulathattakesthemaximumofthewritetimesofalldynamicpropertiesino’spreconditionandthereadtimesofalldynamicpropertiesino’seffectsforeachdynamicpropertypino’seffectsaddeffectstochangethevalueofwrite-time(p)to?start+?durationforeachdynamicpropertythatappearsinoaddeffectstochangeread-time(p)tothemaximumofread-time(p)and?start+?duration图STYLEREF1\s2SEQ图\*ARABIC\s11MTP机制

电梯载人问题HTN建模及求解本章主要是对电梯载人问题用SHOP2进行建模并求解，同时介绍对使用UCPOP解决此问题所做的探究。电梯载人问题课题以电梯载人问题为例对HTN规划性能进行研究。电梯载人问题如下：一栋大楼从低到高有n0到n8共9层，该大楼有快速电梯一部(fast0)，慢速电梯两部(slow1和slow2)。快速电梯fast0最初停留在n0处，fast0可达到各个楼层，在n1、n2、n3层只允许乘客进入电梯，在n4、n6、n8层只允许乘客出电梯。慢速电梯slow1可到达的楼层为n0、n1、n2、n3、n4，最初停留在n4层，在n0和n4层只允许乘客进入电梯，在n2层只允许乘客出电梯；慢速电梯slow2可到达的楼层有n4、n5、n6、n7和n8，最初停留在n4层，在n4和n6层只允许乘客进入电梯，在n7层只允许乘客出电梯。现有乘客4人，分别记为p0、p1、p2、p3，其中p0在n5层，p1在n7层，p2在n1层，p3在n8层。这四个乘客要乘坐电梯各自达到自己希望的楼层，即：p0要去n4层，p1要去n3层，p2要去n2层，p3要去n6层。考虑每个电梯容量为一个人，设计相应的规划方案，以此解决电梯载人问题。利用JSHOP2进行建模求解JSHOP作为SHOP2规划器的JAVA版本可以在Eclipse-Java中运行，作为一种HTN规划器，对问题建模应分为两个部分：领域与问题。这两个部分又可以继续分解为几个子部分，其从属关系及所包含的内容如图3-1所示。 图STYLEREF1\s3SEQFigure\*ARABIC\s11HTN规划问题建模以下分操作、方法、初始状态、初始任务网络四个子章节详细阐述建模的过程。最后2个子章节，将分别介绍测试问题与规划求解的过程及结果。完整的代码参见附录。操作在电梯载人领域中，操作一共有3个，分别完成乘客搭乘电梯、乘客离开电梯、电梯移动三个动作。操作：乘客搭乘电梯。(:operator(!lift-in?p?n?lift) ( (or(in?lift?n)(both?lift?n)) (un-occupy?lift) (lift-at?lift?n) (at-floor?p?n) ) ( (:protection(lift-at?lift?n)) (un-occupy?lift) (at-floor?p?n) ) ( (occupy?lift) (at-lift?p?lift) ))代码如图3-2所示。操作名为!lift-in，前面添加!表明操作为实际操作。如果一个操作为虚拟操作则在名称前添加!!，则在最后的规划解的动作序列中将不出现此虚拟操作。操作的参数有乘客?p、电梯?lift、楼层?n。前提条件有四项，分别为楼层?n允许乘客搭乘电梯、电梯?lift未被占用，电梯?lift在楼层?n，乘客?p在楼层?n。操作删除的状态有保护状态（在后面的章节会对此进行解释）——电梯?lift在楼层?n(:operator(!lift-in?p?n?lift) ( (or(in?lift?n)(both?lift?n)) (un-occupy?lift) (lift-at?lift?n) (at-floor?p?n) ) ( (:protection(lift-at?lift?n)) (un-occupy?lift) (at-floor?p?n) ) ( (occupy?lift) (at-lift?p?lift) ))图STYLEREF1\s3SEQFigure\*ARABIC\s12乘客搭乘电梯操作操作：乘客离开电梯。代码如图3-3所示。操作名为!lift-out。操作的参数有乘客?p、电梯?lift、楼层?n。前提条件有四项，分别为楼层?n允许乘客离开电梯、电梯?lift被占用，电梯?lift在楼层?n，乘客?p在电梯?lift里。操作删除的状态有保护状态（在后面的章节会对此进行解释）——电梯?lift在楼层?n、电梯?lift被占用、乘客?p在电梯?lift里。同时操作增加的状态有电梯?lift未被占用、乘客?p在楼层?n。图STYLEREF1\s3图STYLEREF1\s3SEQFigure\*ARABIC\s13乘客离开电梯操作(:operator(!lift-out?p?n?lift) ( (or(out?lift?n)(both?lift?n)) (occupy?lift) (lift-at?lift?n) (at-lift?p?lift) ) ( (:protection(lift-at?lift?n)) (occupy?lift) (at-lift?p?lift) ) ( (un-occupy?lift) (at-floor?p?n) ))代码如图3-4所示。操作名为!lift-move。操作的参数有电梯?lift、所在楼层?n-from、目标楼层?n-to。前提条件有三项，分别为电梯?lift在楼层?n-from、?n-to允许乘客搭乘或离开，电梯?lift在楼层?n-from。操作删除的状态有电梯?lift在楼层?n-from。同时操作增加的状态有保护状态——电梯?lift在楼层?n-to、电梯?lift在楼层?n-to。图STYLEREF1\s3SEQFigure\*ARABIC\s14电梯移动操作(:operator(!lift-move?lift?n-from?n-to) ( (lift-at?lift?n-from) (or(in?lift?n-to)(both?lift?n-to)(out?lift?n-to)) (or(in?lift?n-from)(both?lift?n-from)(out?lift?n-from)) ) ( (lift-at?lift?n-from) ) ( (lift-at?lift?n-to) (:protection(lift-at?lift?n-to)) ))添加保护状态用于告诉规划系统不允许执行任何删除此被保护的状态的图STYLEREF1\s3SEQFigure\*ARABIC\s14电梯移动操作(:operator(!lift-move?lift?n-from?n-to) ( (lift-at?lift?n-from) (or(in?lift?n-to)(both?lift?n-to)(out?lift?n-to)) (or(in?lift?n-from)(both?lift?n-from)(out?lift?n-from)) ) ( (lift-at?lift?n-from) ) ( (lift-at?lift?n-to) (:protection(lift-at?lift?n-to)) ))方法在电梯载人领域中，方法一共有3个，分别为选择一个可用的电梯并确定移动的楼层、将电梯运送到乘客所在楼层、将乘客移动到要去的楼层。方法：选择一个可用的电梯并确定移动的楼层。(:method(move?p?n) ;branch0: ( (un-occupy?lift) (or(out?lift?n)(both?lift?n)) (at-floor?p?n-now) (or(in?lift?n-now)(both?lift?n-now)) ) ( (lift-move?p?n?lift) ) ;branch1: ( (at-floor?p?n-now)(:method(move?p?n) ;branch0: ( (un-occupy?lift) (or(out?lift?n)(both?lift?n)) (at-floor?p?n-now) (or(in?lift?n-now)(both?lift?n-now)) ) ( (lift-move?p?n?lift) ) ;branch1: ( (at-floor?p?n-now) (or(in?lift?n-now)(both?lift?n-now)) (or(out?lift?n-to)(both?lift?n-to)) (or(out?lift-other?n)(both?lift-other?n)) (or(in?lift-other?n-to)(both?lift-other?n-to)) (un-occupy?lift) ) ( (lift-move?p?n-to?lift) (move?p?n) ) ;branch2: ( (at-floor?p?n-now) (lift-at?lift?n-now) (un-occupy?lift) (or(in?lift?n-now)(both?lift?n-now)) (or(out?lift?n-to)(both?lift?n-to)) ) ( (lift-move?p?n-to?lift) (move?p?n) ) ;branch3: ( (at-floor?p?n-now) (or(in?lift?n-now)(both?lift?n-now)) (un-occupy?lift) (or(out?lift?n-to)(both?lift?n-to)) ) ( (lift-move?p?n-to?lift) (move?p?n) ) )图STYLEREF1\s3SEQFigure\*ARABIC\s15方法：选择一个可用的电梯并确定移动的楼层方法的名字和参数为(move?p?n)，为初始任务网络在规划搜索中最先进行分解的所用的方法，需要将任务（将乘客?p移动到楼层?n）分解为(lift-move?p?n-to?lift)（将乘客?p用电梯?lift移动到楼层?n-to）与(move?p?n)（如果有电梯可以直接将乘客移动到目标楼层?n，则此任务略去）。为此，为此方法设计了4个分支，对应于不同的情况设置了相应的启发式规则以引导搜索。以下分别具体解释4个分支：Branch0：在此分支里，首先检验是否有未被占用的电梯可以将乘客?p直接移动到目标楼层?n，并且乘客所在楼层搭乘电梯与目标楼层离开电梯都满足此电梯的约束，如果是则分解为(lift-move?p?n?lift)（将乘客?p用电梯?lift移动到楼层?n），目标任务完成。Branch1：如果不满足Branch0的前提条件，则需要将乘客移动至其他楼层以便换乘其他电梯。为了减少换乘次数，检验乘客能否通过换乘一次电梯到达目标楼层，如果存在这样的途径就优先选择这样这方式先移动到换乘楼层，分解为(lift-move?p?n-to?lift)与(move?p?n)。而在下一次对(move?p?n)分解时就会进入Branch0完成任务。如此，方法的前提条件会搜索是否有电梯?lift满足在乘客?p所在楼层?n-now允许乘客搭乘且在某一楼层?n-to允许乘客离开，同时另外有一部电梯?lift-other在楼层?n-to允许乘客搭乘且在目标楼层?n允许乘客离开，如果满足条件就说明存在这样的一次换乘途径可以到达目标楼层。Branch2：如果都不满足以上两个分支的前提条件，且有电梯停留在乘客所在的楼层，则乘客优先搭乘这部电梯随机的前往电梯停留规则允许的某楼层。同上一分支分解成(lift-move?p?n-to?lift)与(move?p?n)两个任务。Branch3：如果以上分支的前提条件都不满足，则随机选择一部电梯，并随机确认一个对应电梯停留规则允许的某楼层。同上一分支分解成(lift-move?p?n-to?lift)与(move?p?n)两个任务。将Branch1放在Branch2之前进行判断则是考虑应优先寻找可以通过一次换乘到达目标楼层的方案，而不是先考虑哪个电梯在本楼层，因为如果电梯不在本楼层也只需多执行一个将电梯移动至本楼层的动作，而如果舍弃了一次换乘就能到达目标楼层的方案可能需要通过3到4个动作在能够完成到达目标楼层的任务。方法：将电梯运送到乘客所在楼层。(:method(lift-move?p?n-to?lift) ;branch0: ( (at-floor?p?n-now) (lift-at?lift?n-now) ) ( (move-to-floor?p?n-to?lift) ) ;branch1: ( (at-floor?p?n-now) (lift-at?lift?n-other) ) ( (!lift-move?lift?n-other?n-now) (:method(lift-move?p?n-to?lift) ;branch0: ( (at-floor?p?n-now) (lift-at?lift?n-now) ) ( (move-to-floor?p?n-to?lift) ) ;branch1: ( (at-floor?p?n-now) (lift-at?lift?n-other) ) ( (!lift-move?lift?n-other?n-now) (move-to-floor?p?n-to?lift) ))图STYLEREF1\s3SEQFigure\*ARABIC\s16方法：将电梯运送到乘客所在楼层此方法处理方式较为简单，共有两个分支：Branch0：如果电梯在乘客所在的楼层，则此方法什么也不做。直接分解为(move-to-floor?p?n-to?lift)。Branch1：如果乘客搭乘的电梯不在乘客所在的楼层，此方法将电梯移动到乘客所在的楼层。分解为操作(!lift-move?lift?n-other?n-now)与(move-to-floor?p?n-to?lift)。方法：将乘客移动到要去的楼层。代码如图3-7所示。方法名称及参数为(move-to-floor?p?n-to?lift)。任务分解到此，需要做的只有将乘客移动到目标楼层，故此方法将任务分解为3个操作：(!lift-in?p?n-now?lift)、(!lift-(:method(move-to-floor?p?n-to?lift)( (lift-at?lift?n-now) )(:method(move-to-floor?p?n-to?lift)( (lift-at?lift?n-now) ) ( (!lift-in?p?n-now?lift) (!lift-move?lift?n-now?n-to) (!lift-out?p?n-to?lift) ))图STYLEREF1\s3SEQFigure\*ARABIC\s17方法：将乘客移动到要去的楼层初始状态;快速电梯停留楼层(bothfast0n0)(infast0n1)(infast0n2)(infast0n3)(outfast0n4)(bothfast0n5)(outfast0n6)(bothfast0n7)(outfast0n8);慢速电梯1停留楼层(inslow1n0)(bothslow1n1)(outslow1n2)(bothslow1n3)(inslow1n4);慢速电梯2停留楼层(inslow2n4)(bothslow2n5)(inslow2n6)(outslow2n7)(bothslow2n8);电梯初始位置(lift-atfast0n0)(lift-atslow1n4)(lift-atslow2n4);;快速电梯停留楼层(bothfast0n0)(infast0n1)(infast0n2)(infast0n3)(outfast0n4)(bothfast0n5)(outfast0n6)(bothfast0n7)(outfast0n8);慢速电梯1停留楼层(inslow1n0)(bothslow1n1)(outslow1n2)(bothslow1n3)(inslow1n4);慢速电梯2停留楼层(inslow2n4)(bothslow2n5)(inslow2n6)(outslow2n7)(bothslow2n8);电梯初始位置(lift-atfast0n0)(lift-atslow1n4)(lift-atslow2n4);人初始位置(at-floorp0n5)(at-floorp1n7)(at-floorp2n1)(at-floorp3n8);电梯是否占用(un-occupyfast0)(un-occupyslow1)(un-occupyslow2)图STYLEREF1\s3SEQFigure\*ARABIC\s18初始状态其中，(in?lift?n)表示电梯?lift允许乘客在楼层?n搭乘，(out?lift?n)表示电梯?lift允许乘客在楼层?n离开，(both?lift?n)表示电梯?lift允许乘客在楼层?n搭乘或离开。初始任务网络 (movep0n4) (movep1n3) (movep2n2) (movep0n4) (movep1n3) (movep2n2) (movep3n6)图STYLEREF1\s3SEQFigure\*ARABIC\s19初始任务网络测试问题(defproblemproblemelevator(;快速电梯停留楼层(infast0n2)(outfast0n6);慢速电梯1停留楼层(inslow1n0)(outslow1n2)(bothslow1n4);慢速电梯2停留楼层(inslow2n6)(outslow2n5)(defproblemproblemelevator(;快速电梯停留楼层(infast0n2)(outfast0n6);慢速电梯1停留楼层(inslow1n0)(outslow1n2)(bothslow1n4);慢速电梯2停留楼层(inslow2n6)(outslow2n5);慢速电梯3停留楼层(inslow3n5)(outslow3n8);电梯初始位置(lift-atfast0n2)(lift-atslow1n4)(lift-atslow2n5)(lift-atslow3n8);人初始位置(at-floorp0n0);电梯是否占用(un-occupyfast0)(un-occupyslow1)(un-occupyslow2)(un-occupyslow3) )( (movep0n8) ))图STYLEREF1\s3SEQFigure\*ARABIC\s110测试问题代码对此测试领域进行求解，得到任务分解过程如图3-11所示。其中第一次调用图STYLEREF1\s3SEQFigure\*ARABIC\s111测试问题任务分解过程方法(movep0n8)进入的是Branch3，第二次调用进入的是Branch2，第三次调用进入的是Branch1，第四次调用进入的是Branch0。方法(lift-move?p?n-to?lift)的4次调用中进入Branch1的次数为3次，进入Branch2的次数为图STYLEREF1\s3SEQFigure\*ARABIC\s111测试问题任务分解过程以此，可以认为，领域是可靠且完备的，可以用来求解类似的电梯载人问题。测试问题求解的结果如图3-12所示。图STYLEREF1\s3SEQFigure\*ARABIC\s112测试问题规划解规划求解的过程及结果图STYLEREF1\s3SEQFigure\*ARABIC\s113电梯载人问题任务分解过程将领域文件elevator与问题文件problem输入到JSHOP2中，编译后即可打开GUI图形规划界面进行规划求解，规划的过程如图3-13所示。由于篇幅所限，其中方法(move-to-floor?p?n-to?lift)分解结果的三个动作图STYLEREF1\s3SEQFigure\*ARABIC\s113电梯载人问题任务分解过程可以看到每个乘客都在一次以内的换乘到达目标楼层。规划解如图3-14所示。整个规划搜索过程共84步，得到的规划解长度为23。四个目标任务中，乘客p0通过4个动作，直接搭乘电梯fast0到达目标楼层n4；乘客p1通过7个动作，搭乘电梯fast0在楼层n4换乘电梯slow1到达目标楼层n3；乘客p2通过4个动作，直接搭乘电梯slow0到达目标楼层n2；乘客p3通过8个动作，搭乘电梯slow2在楼层n7换乘电梯fast0到达目标楼层n6。图图STYLEREF1\s3SEQFigure\*ARABIC\s114电梯载人问题规划解

HTN规划与简单调度规则的比较本章首先介绍几种在电梯中常用的简单调度规则，用其进行求解电梯载人问题，并与SHOP2规划器求解的结果进行比较，而后，扩大问题的规模再进行求解，比较结果。故本章分为以下3个小结进行阐述：几种常用的简单调度规则、依据调度规则求解并与规划器比较、扩大问题规模并求解比较。几种常用的简单调度规则电梯领域的调度规则有许多，这里仅提出2种适用于此电梯载人问题调度规则。规则1：优先选择离乘客最近且允许进入的电梯到达离目标楼层最近且允许离开的楼层，直到到达目标楼层为止。规则2：优先选择允许进入的快速电梯到达离目标楼层最近且允许离开的楼层，再换乘慢速电梯到达目标楼层。在下一章节中将分别利用这2条规则对电梯载人问题进行求解。调度规则求解及与规划器比较使用规则1对电梯载人问题进行求解，得到的结果如图4-1所示。所需进行的动作数为23个。使用规则2对电梯载人问题进行求解，得到的结果如图4-2所示。所需进行的动作数为27个。而根据上一节求解的结果，使用SHOP2规划器对电梯载人问题进行求解，得到的结果中，所需进行的动作数为23个。可以看到，在电梯载人问题上，SHOP2规划器求解的结果在解的质量上与规则1一样，比规则2要优，则可认为SHOP2规划器求解的结果在解的质量上至少不会劣于简单调度规则。而在求解的速度上，如果采用手动方式依据简单调度规则调度效率比较低下，而采用计算机程序依据简单调度规则进行调度效率与规划器效率相仿，但当对规划问题做适当修改后，SHOP规划领域知识通过少量的修改便可用于求解新的规划问题，而依靠简单调度规则的计算机程序则需做较为[1](!lift-movefast0n0n5) [2](!lift-inp0n5fast0)[3](!lift-movefast0n5n4) [4](!lift-outp0n4fast0)[1](!lift-movefast0n0n5) [2](!lift-inp0n5fast0)[3](!lift-movefast0n5n4) [4](!lift-outp0n4fast0)[5](!lift-movefast0n4n7) [6](!lift-inp1n7fast0)[7](!lift-movefast0n7n4) [8](!lift-outp1n4fast0)[9](!lift-inp1n4slow1) [10](!lift-moveslow1n4n3)[11](!lift-outp1n3slow1) [12](!lift-moveslow1n3n1)[13](!lift-inp2n1slow1) [14](!lift-moveslow1n1n2)[15](!lift-outp2n2slow1) [16](!lift-moveslow2n4n8)[17](!lift-inp3n8slow2) [18](!lift-moveslow2n8n7)[19](!lift-outp3n7slow2) [20](!lift-movefast0n4n7)[21](!lift-inp3n7fast0) [22](!lift-movefast0n7n6)[23](!lift-outp3n6fast0)图STYLEREF1\s4SEQFigure\*ARABIC\s11规则1对电梯规划问题求解结果[1](!lift-movefast0n0n5) [2](!lift-inp0n5fast0)[3](!lift-movefast0n5n4) [4](!lift-outp0n4fast0)[5](!lift-movefast0n4n7) [6](!lift-inp1n7fast0)[7](!lift-movefast0n7n4) [8](!lift-outp1n4fast0)[9](!lift-inp1n4slow1) [10](!lift-moveslow1n4n3)[11](!lift-outp1n3slow1) [12](!lift-movefast0n4n1)[13](!lift-inp2n1fast0) [14](!lift-movefast0n1n4)[15](!lift-outp2n4fast0) [16](!lift-moveslow1n3n4)[17](!lift-inp2n4slow1) [18](!lift-moveslow1n4n2)[19](!lift-outp2n2slow1) [20](!lift-moveslow2n4n8)[21](!lift-inp3n8slow2) [22](!lift-moveslow2n8n7)[23](!lift-outp3n7slow2)[24](!lift-movefast0n4n7)[25](!lift-inp3n7fast0) [26](!lift-movefast0n7n6)[27](!lift-outp3n6fast0)图STYLEREF1\s4SEQFigure\*ARABIC\s12规则2对电梯规划问题求解结果扩大问题规模并求解比较一般来说，当问题规模较小时，依据简单调度规则进行手动或计算机程序调度与自动规划器规划的性能差别不大，而当问题的规模扩大，其性能上的差异可能逐渐显现，故本节的目的在于验证此观点。扩大规模后的问题。对问题规模进行扩大，乘客数扩大到8人，楼层数扩大到15层，电梯数扩大到快速电梯1部、慢速电梯4部。原问题中，快速电梯可以停留所有楼层，而慢速电梯则停留大约一半的楼层，慢速电梯之间有一个楼层的都可停留，故扩大规模后的问题中，快速电梯依旧可以停留所有楼层，而慢速电梯则停留稍多于总楼层数四分之一的楼层，同时各相邻慢速电梯之间均有移到两个楼层都可停留，同时，为了保证所有的乘客都能通过此电梯系统从任意初始楼层移动到任意目标楼层，所有的楼层都至少存在电梯可以搭乘或到达。规模扩大后的问题如下：一栋大楼从低到高有n0到n14共15层，该大楼有快速电梯一部(fast0)，慢速电梯四部(slow1和slow2)。快速电梯fast0最初停留在n0，fast0可达到各个楼层，在n1、n2、n3、n10、n11层只允许乘客进入电梯，在n4、n6、n8、n12、n14层只允许乘客出电梯慢速电梯slow1可到达的楼层为n0、n1、n2、n3、n4，最初停留在n0层，在n0和n4层只允许乘客进入电梯，在n2层只允许乘客出电梯；慢速电梯slow2可到达的楼层有n3、n4、n5、n6和n7，最初停留在n3层，在n4、n6层只允许乘客进入电梯，在n3、n7层只允许乘客出电梯。慢速电梯slow3可到达的楼层有n7、n8、n9、n10和n11，最初停留在n7层，在n7、n9层只允许乘客进入电梯，在n11层只允许乘客出电梯。慢速电梯slow4可到达的楼层有n10、n11、n12、n13和n14，最初停留在n10层，在n12、n13、n14层只允许乘客进入电梯，在n10层只允许乘客出电梯。现有乘客8人，分别记为p0、p1、p2、p3、p4、p5、p6、p7，其中p0在n0层，p1在n2层，p2在n4层，p3在n5层，p4在n7层，p5在n8层，p6在n12层，p7在n13层。这八个乘客要乘坐电梯各自达到自己希望的楼层，即：p0要去n11层，p1要去n10层，p2要去n14层，p3要去n1层，p4要去n3层，p5要去n13层，p6要去n0层，p7要去n10层。考虑每个电梯容量为一个人，设计相应的规划方案，以此解决电梯载人问题。SHOP2规划器求解情况扩大后的电梯规则不影响领域文件elevator，无需做任何修改，而只需对问题文件problem进行修改，因篇幅限制，修改后的代码略去，详见附录的代码清单。求解的结果如图20所示。可以看到，规划解动作的个数为59个。整个规划搜索过程为210步。从结果中可以看到，乘客p0、p1、p3和p4通过乘坐快速电梯换乘慢速电梯到达目标楼层，乘客p7直接乘坐慢速电梯到达目标楼层，乘客p2、p5和p6通过搭乘慢速电梯换乘快速电梯到达目标楼层。[1](!lift-inp0n0fast0) [2](!lift-movefast0n0n8) [3](!lift-outp0n8fast0)[4](!lift-moveslow3n7n8)[1](!lift-inp0n0fast0) [2](!lift-movefast0n0n8) [3](!lift-outp0n8fast0)[4](!lift-moveslow3n7n8) [5](!lift-inp0n8slow3) [6](!lift-moveslow3n8n11)[7](!lift-outp0n11