人工智能基础：一种利用工作流模型的分层任务网络规划领域建模方法

第6卷第3期 智能系统学报 Vol.6 No.3 2011年6月 CAAI Transactions on Intelligent Systems Jun.2011 doi:10.3969/i.issn.1673-4785.2011.03.008 一种利用工作流模型的 分层任务网络规划领域建模方法 张万鹏，王楠，陈璟 (国防科学技术大学机电工程与自动化学院，湖南长沙410073) 摘要：为了有效地获取和利用领域知识，提高规划效率，分析了工作流模型和分层任务网络(HTN)规划领域模型 的相似性，提出了一种采用工作流模型进行规划领域建模，对领域知识进行获取和表达的方法.工作流模型中的行 动和工作流模式，转换为HTN规划中的行动和任务分解；另外，引入了循环(Lop)工作流模式，转换为HTN规划中 的递归调用，扩展了工作流模式对规划领域知识的表达能力.在典型的几个规划领域中，引入领域知识后大大提高 了规划器的求解效率，从而验证了应用工作流模型进行规划领域建模的有效性， 关键词：工作流；分层任务网络；规划领域建模 中图分类号：TP391文献标识码：A文章编号：16734785(2011)03023909 An HTN planning domain modeling method using a workflow model ZHANG Wanpeng,WANG Nan,CHEN Jing (College of Mechatronic Engineering and Automation,National University of Defense Technology,Changsha 410073,China) Abstract:In order to improve planning efficiency by acquiring and utilizing domain knowledge,workflow process models were compared along with hierarchical task network (HTN)planning domain models,and a new method was presented based on the workflow to model planning domain.Activities and workflow patterns were respectively translated into actions and composed tasks in the HTN domain.Loop pattern was introduced to represent recursion in the HTN domain in order to extend the knowledge acquisition and representation abilities of workflow patterns.In experiments on several classical planning domains,such knowledge acquired in workflow models was shown to speed up the classical planner by several orders of magnitude.The experiments validate the HTN planning domain modeling method using a workflow model. Keywords:workflow;hierarchical task network;planning domain modeling 领域知识的表达与应用，一直是规划技术应用定义的语言输入领域知识的能力，并且提供了图形 于实际的一个主要难题山，因为很多规划问题的描 化的界面使用户能够方便地输入领域知识.过去几 述往往依赖于规划系统内部运行的相关知识，还需 年中的研究表明，智能规划(AI planning）)与工作流 要专业人员（往往是规划系统的开发人员）进行领 管理的结合是一个值得研究的方向.一方面，研究人 域建模，而一般的用户要将实际的规划问题描述为 员在利用规划技术进行流程自动生成方面取得了较 规划系统能够识别的领域模型和问题模型还是一个 大的进展，欧洲规划调度研究网络(European net- 相当繁琐且复杂的过程. work of excellence in AI planning,PLANET)2003 在工作流管理系统(workflow management sys- 年的研究计划21对此有详细的描述.另一方面，一 tem,WFMS)中，已经具备了允许非专业人员按照预 些研究人员也对利用工作流进行规划的领域建模进 行了探索34).文献[3]对工作流管理系统和AI规 收稿日期：2010-11-17 划系统的相似性进行分析，首次提出了使用业务流 基金项目：国家自然科学基金资助项目(61005077). 程管理工具对规划领域进行建模，并转换为规划领 通信作者：张万鹏.E-mail:wpzhang@nudt.ed血.cm

240 智能系统学报 第6卷 域描述语言PDDL进行求解的方法.在对于层次化 更细的任务或操作的组合 领域知识(hierarchical task netowrk knowledge)的获 本文在分析工作流模型和HTN规划领域模型 取方面，G-Ferrer等在文献[4]中，利用工作流模式 的基础上，给出利用工作模型进行HTN规划领域建 (workflow pattern)对HTN知识进行表达，并转换为 模的方法，并利用经典规划器在引入和未引入领域 HTN-PDDL描述语言，利用HTN规划器进行求解. 知识时的求解效率的实验对比，验证所给出的建模 在2009年第3届国际规划调度知识工程大赛(ICK 方法的有效性。 EPS)中，G-Ferrer等开发的JABBH系统5]，将用于 表达HTN知识的工作流模式进一步精炼为3种：顺 1工作流与HTN规划 序(serial)、并行(parallel)和选择(exclusive-OR). 工作流是针对工作中具有固定程序的常规活动 工作流过程(process)可以定义为一组偏序的 而提出的一个概念，最初源于文件的处理，主要管理 步骤，它可以由更低级的过程或行动组成，按照顺 文件在各个部门之间的传递和审阅.通过将工作活 序、并行、分支、选择、合并、循环等关系进行组织，以 动分解成定义良好的任务、角色、规则和过程来进行 达成某个既定的目标.这与分层任务网络(hierarchi- 执行和监控，达到提高生产组织水平和工作效率的 cal task network,HTN)规划中任务的表达非常类 目的.工作流管理联盟(workflow management coali- 似，在HTN规划中，规划的目标不是达成某个目标 tion,WFMC)提供了一种工作流的过程元模型6]， (集)而是完成一组任务，高层的任务可以被分解为 如图1. Process (W.Process) Type declaration Data field Activity set (Property) (Embedded sub-process) Application uses performer reference i-uses Participant Transition performer Activity -0 -from- (Sequence flow) --------------ses- -uses- Pool Lane Task/Tool Block activity W.Relevant data Route Sub flow 小… System and Resource repository or environmental data organizational model Gateway Event 图1WFMC给出的工作流流程元模型 Fig.1 Workflow meta-model presented by WFMC 在该元模型描述中，一个工作流过程(workflow 者(participant)和（或）应用程序(application)所执 process)由一个或多个行动(activities),也称为执行 行.行动与行动之间通过“转移”(transitions)相关 行动(implementation activities)组成，每个行动包含 联，“转移”可以是有条件的（包含了允许或禁止执 了一个合乎逻辑的、独立的工作单元，该行动由参与 行该转移的评估表达式)，也可以是无条件的，在流

第3期 张万鹏，等：一种利用工作流模型的分层任务网络规划领域建模方法 ·241· 程内部形成串联或并联的行动序列.在图形化的表 号；task(m)为非原子任务；文字集合precond(m)为 达中，“转移”即是2个表达行动的节点之间的连 方法m的前提条件；network(m)为一任务网络，该 接.此外，在过程元模型中，还有一种称为路由行动 任务网络中的任务是方法m的子任务 (route activities)的特殊行动，这类行动被用于确定 4)STN规划领域：STN的规划领域是一序对： 过程中行动流程的路径.一个行动也可以是一个子 D=(O,M),其中O为动作集合，M为方法集合. 流程(subflow),也称为行动集(activityset),它可以 5)STN规划问题：STN的规划问题是一个4元 作为一个子过程（单独定义的）执行的容器.通道 组：P=(s,ω，0，M),其中：s为初始状态，0是任 (lanes)在过程元模型中对行动进行组织和分类，常 务网络，通常称为初始任务网络，D=(O,M)为STN 常被用于指定执行行动的角色、部门等.过程元模型 规划领域 采取了标准的数据类型（字符、整型、实型、日期型 此外，在HTN规划领域建模中，类型(tyes)、常 等)，并允许用户自定义数据字段(data field)和扩展 量(constants)、谓词(predicates)、函数(functions)、行 属性(extended attributes). 动(actions)的定义与经典规划相同.同时在描述规划 工作流模式作为一种通用的结构，用于表达流 问题时，还需要定义规划问题所涉及的对象(b 程中常用的任务/行动间的关系，它们常常被嵌套于 jects). 流程中以形成完整的流程模型].文献[7]中共给 通过上述对工作流过程元模型和HTN规划领域 出了15类工作流模式，对规划的领域建模而言，并 模型的分析，可以看出二者具有很强的相似性（表 不需要所有的工作流模式.G-Ferrer等人I4的研究 1).其中，HTN规划领域模型中的任务对应于工作流 中给出了顺序(sequence)、并行(parallel split)、选择 模型中的过程，用于表征规划的任务列表；二者的行 (exclusive choice)和合并(simple merge)4种用于规 动模型均可用于表征完成任务所需要的底层行动： 划领域建模的工作流模式， TN规划中的对象对应于工作流模型中的参与者/ 在众多AI规划技术的分支中，分层任务网络 通道，用于对行动的执行者进行组织；子任务和子流 规划由于其推理能力和对经验知识的有效表达，在 程相对应，用于表征组成上层任务/流程的任务/流 实际中得到了广泛的应用.HTN规划的领域建模本 程；方法和工作流模式对应，用于表征流程和任务的 质上是对过程的建模，可以指定参数化的过程描述， 分解方式。 这些过程通过规划器的作用组合并实例化，以生成 表1工作流模型与TN规划领域模型比较 Table 1 Workflow model and HIN domain model 满足给定目标的计划. 为了描述的方便和不失一般性，采用Ghallab 工作流模型 HTN规划领域模型 等人给出的一种简化版本的HTN规划，即简单任务 工作流过程(process) 任务(task) 网络(simple task network,STN)规划I说明HTN规 行动(activity) 行动(action) 划领域建模所需的要素. 参与者/通道(participant/lane）) 对象(objects) 1)任务(task):一个任务是形如t(T1,2,…,) 子流程(subflow） 子任务(subtask) 工作流模式(workflow patterns) 方法(methods) 的表达式，其中t为一任务符号，1，「2，…，”k为项.如 果t是一操作符号，则任务t为原子任务；否则任务t 为非原子任务。 2 模型转换 2)任务网络(task network):一个简单任务网络 工作流模型向HTN规划领域模型的转换主要包 (或者简称任务网络)为一无环图ω=（U,E),其 括2个方面，一是将工作流行动转换为规划行动：二 中U为节点集合，E为边的集合.对每一节点u∈U, 是将工作流模式转换为组合任务(composed tasks)的 均包含一任务t.,图ω中的边定义了U中节点的部 分解方法 分序关系，即u<v当且仅当存在一条从节点u到节 2.1行动的转换 点v的路径， 规划领域的行动一般由3部分组成：行动名和参 3)方法(method):一个STN方法是一个4元组： 数表、行动的前提与行动的结果.在工作流模型中，行 m =(name(m ),task(m),precond(m ),network (m)). 动名和参数可以直接表达，而行动的前提和结果一般 式中：name(m)为方法的名字，是形如n(1,x2,…, 通过行动的规则来描述.规则由2部分组成：1)前提 x)的语法表达式，这里n为惟一的方法符号，x1,2, （if rules):行动执行的条件，也就是说行动在什么情 …,x。是所有能在方法m,中任意地方出现的变量符 况下能够执行；2)结果(then rules):行动执行后对状

.242. 智能系统学报 第6卷 态的影响。 Parameters() 下面给出的伪代码描述了一个办公室机器人移 (method msbl 动行动的规则 preconditon() <Rule name=“moveActivity”> :tasks((A1)(A2)))) <Rule.Condition 2)并行模式工作流表示及对应的HTN编码： moveActivity.locl.rloc <ParallelActivity x:Name=“PBl”> &moveActivity.d.closed <SequenceActivity &moveActivity.door.realvalue x:Name=“sequenceActivity1”> </Rule.Condition> <ns0:MoveActivity:Name=“A1”/> <Rule.ThenAction </SequenceActivity moveActivity.loc2.rloc =true <SequenceActivity &&moveActivity.loc1.rloc false x:Name=“sequenceActivity.2”> Rule.ThenAction <ns0:MoveActivity:Name=“A2”/> </Rule </SequenceActivity> 上述例子转换为HTN规划的行动表达如下 </ParallelActivity (action move 对应的HTN编码如下： parameters (?loc1-ROOM ?loc2-ROOM ?d- (task PB1 ROOMDOOR) Parameters() precondition (and (rloc ?loc1)(door ?loc1 (method mpbl loc2 ?d)(not (closed ?d))) preconditon() effect (and (rloc ?loc2)(not (rloc ?loc1))) :tasks([(A1)(A2)])）) 3)选择模式工作流表示及对应的HTN编码： 其中，二者对于状态的表达有所不同.在规划的 <IfElseActivity:Name=“XORB1”> 领域模型中，状态由一组基础谓词的合取来表达；而 <IfElseBranchActivity 在工作流模型中，状态一般由对象、对象实例(- x:Name=“ifBranch”> stances)、属性(attributes)以及属性的值(variable)来 <IfElseBranchActivity.Condition> 表达.在工作流模型中，用bool型变量来表达命题，如 RuleCondition Reference “bool armempty”表达机器手臂是否为空；用对象的 ConditionName=“ifConditon'”/> bool型属性来表达一元谓词，如“bool door.closed”表 </IfElseBranchActivity.Condition 达门是否关闭；用谓词对象来表达多元谓词，其中谓 <ns0:MoveActivityx:Name=“Al”/> 词的项由对象的属性来表达，而谓词的断言(asser- </IfElseBranchActivity tion)可以由对象中的一个bool型属性来表达， <IfElseBranchActivity 2.2工作流模式的转换 x:Name-“elseBranch”> G-Ferrer等人在其开发的JABBH系统（将业务 <ns0:MoveActivity:Name=“A2”/> 流程模型转换为HTN规划模型的一个JAVA应用 </IfElseBranchActivity 程序框架)51应用了3种典型的工作流模式来表达 </IfElseActivity HTN规划的任务分解方法.以下是这3种模式的工 ifConditon: 作流编码和转换为HTN方法后的HTN编码. this.x ==true 1)顺序模式工作流表示及对应的HTN编码： 对应的HTN编码如下： <SequenceActivity x:Name=“SBl”> (task XORB1 <ns0:MoveActivity:Name=“Al”/> Parameters(?x-parameter) <ns0:MoveActivityx:Name=“A2”/> （:method ifBranch </SequenceActivity> preconditon(value ?x true) 对应的HTN编码如下： tasks((A1))) （:task SB1 (method elseBranch

第3期 张万鹏，等：一种利用工作流模型的分层任务网络规划领域建模方法 ·243· preconditon(value ?x false) 有集装箱为止.以下是该方法循环模式的工作流表 :tasks(((A2)））) 示及对应的HTN编码， 图2所示为顺序、并行、选择的工作流模式 <WhileActivity x:Name=“move-stack”> <WhileActivity.Condition A <RuleConditionReference (a)顺序(serial)模式 ConditionName=“precond”/> </WhileActivity.Condition SequenceActivity x:Name ="sequenceAc- AND AND tivity1”> nsl:MoveActivity x:Name ="mov-top- most-container”/> ns1:CountActivity x Name ="count-re- (b)并彳(parallel split join)模式 cursive-times'”/> =true A </SequenceActivity </WhileActivity XOR XOR precond:this.p.empty =false &this.r times >0 A: =false 对应的HTN编码如下： (c)选择(parallel exclusive -OR)模式 (task move-stack 图23种典型的工作流模式 parameters(?p-place ?g-place ?r_times- Fig.2 Three classical workflow patterns times) 此外，在HfTN规划中，递归(recursive)调用是 (method recursive-move 一种重要的方法，它可以方便地描述需要重复执行 preconditon(and((not(empty ?p ) 的行动.不过，递归的引入给HTN规划带来了不可 (GreaterThan ?r_times 0))) 判定的问题，即使基础状态空间是有限的].此困 tasks((mov-topmost-container) 难的出现是因为如果分解是可以递归的，那么HTN count-recursive-times) 规划解可以是任意长的，不能在固定的时间内终止 (move-stack)）) 搜索.为了解决不可判定性的问题，一些HTN规划 本文在循环的条件中增加了对调用次数的限制， 器采取了限定规划解长度的方式，因为状态空间是 如果超过了最大调用次数则递归终止.一般情况下， 有限的，一个步骤比状态空间的状态还多的规划一 如果状态空间是有限的，任务的分解基本上都会在有 定包含了访问同一个状态2次或2次以上的回路。 限步骤内达到原子行动.如上例所描述的情况，如果 在工作流模型中，可以采用循环(loop)模式（图3） p上的集装箱个数是有限的（如有K个），则move 来表达方法的递归调用，为了解决不可判定的问题， stake行动将在被递归调用K次之后完成.当基础的 可以在循环的条件中增加调用次数的限制 状态的空间是有限的，而组合的状态空间可能是无限 =false 的，例如在上例中，如果将p上的集装箱移动到q后， XOR 还有另外的行动又将其移动到p上，这样对move- stack的调用将会无休止地进行下去.在这种情况下， =true 限定规划解的长度，即限定递归调用的次数是解决不 可判定性的一个有效方法，虽然可能会损失规划解的 完备性（可能会出现这样的情况，有的任务就是要求 图3工作流循环(loop)模式 将集装箱从p搬到q,然后再搬回来). Fig.3 Loop workflow pattern 例如，为了完成将一堆集装箱从位置p移动到 3实例分析 位置q的任务，可按照下列方式进行处理：重复移动 位置p最上面的集装箱到位置g,直到位置p上不再 为了验证工作流模型在规划领域建模中应用的 有效性，采用MSWF(Microsoft workflow founda-