水下机器人任务流程建模与管理

张鸿皓，姜大鹏，庞永杰，李金龙

(哈尔滨工程大学智能水下机器人技术国防科技重点实验室，黑龙江哈尔滨150001)

自主机器人的作业流程总是可以在某一层次上划分成多个子过程.宏观的过程可以由子过程、子过程的发生次序以及决定这种次序的条件构成.人们创造了各式各样的规则，用来描述和管理自然发生或人为控制的过程.应用在机器人上的作业流程主要体现人的智能(操控者或机器本身的智能).在机器人相关领域内，对机器细微动作的精确控制早已实现，但针对体现高度智能的宏观任务流程的描述与自动管理，尚缺乏成熟的理论和实例.

自治式水下机器人由于工作环境与人隔绝，特别需要一套能完整表述任务规划者意愿，并能交由计算机自动执行管理的理论模型及实用化的方法.传统的Petri网和工作流模型虽能部分解决上述问题，但多少存在建模困难、编程实现复杂及描述能力受限等问题［1］，尚未出现一套成功而方便实用的解决方案.

任务工作流模型较大幅度地改进了传统的工作流理论，在增强了模型描述能力的同时，也大幅简化了模型的复杂度，能以图形化方式建模并方便地转换为计算机可以理解的文本描述方式，为理论模型的编程实现提供了良好的条件.在此理论基础上构建的水下机器人任务建模与管理系统已经过实践检验，能为复杂逻辑流程的快速建模与自动管理提供极大的便利.

1 Petri网

Petri网由表示状态的元素“库所”(place)和表示变化的元素“变迁”(transition)组成.联系S和T的是两者间的流关系，用F表示.库所可以容纳标记(token)，标记代表网路中流动的资源，资源的流动由流关系规定.Petri网结构是固定的，而库所中标记的分布是可变的，标记因变迁而形成的不同分布表征了Petri网的不同状态.

水下机器人的任务建模并不困难，只需用到Petri网的基本概念［2-3］，如图 1及表1中的例子所示.

图1 水下机器人任务示例(Petri网)Fig.1 An example of AUV task flow(Petri net)

表1 库所与变迁的含义Table 1 Meanings of places and transition

图1中的一些库所会产生冲突，例如当S2得到一个标记时，T2、T3不能同时发生.解决冲突的办法是由环境提供信息，决定由谁来占用资源.所以，决定了任务路由的一些重要条件实际是无法在Petri网中直接表示的，它需要对Petri网进行扩展，使标记和网路能够携带和处理更多的环境信息.环境信息的获取和处理往往相当抽象和复杂，通常只能由高级程序语言编程实现.如果要用Petri网来描述，由于Petri网过于严谨和形式化，将不得不增加一系列的扩展，增加了网系统的复杂程度，使得建模和理解都变得更加困难.

Petri网只描述事物间的依赖关系，没有更高层的控制流程和其他的人为因素影响，更适合用来描述符合自然规律的自然过程.然而水下机器人作为人类智能乃至机器智能的执行者，其作业过程无疑更接近人为过程.故虽然有人将Petri网引入水下机器人的任务管理，但描述和理解困难，不易编程实现，不适合作为抽象任务的建模工具.

2 工作流模型

工作流模型是对工作业务过程的抽象表示.工作流的应用通常需要完成业务过程的计算机化，其模型不仅要让人(不仅是专家，还包括普通用户)容易读懂，也必须让计算机能够理解.

在库所与变迁的基础上，为了定义出顺序、并行、选择、循环等常用的过程逻辑，工作流网构造了相应的结构化组件，为其规定了特殊的符号，供用户在建模时直接使用［4］.每一组件均可给出对应的Petri网建模方法:1)顺序;2)并行，它需要2个基本的工作流执行原语:“与分支”(AND_split)和“与连接”(AND_join)，也可将其当做特殊的任务.AND_split能同时发起多个任务，而AND_join能对多个并行的流程进行同步;3)选择，根据具体的执行情况进行“多选一”或“多选多”，构造选择路由需要“或分支”(OR_split)和“或连接”(OR_join);4)循环.

对于 AND_split、AND_join、OR_split、OR_join 这样经常使用的结构，采用图2中特定的符号来表示.

图2 工作流逻辑构件Fig.2 Logical components of workflow

图3中的例子与图1中的流程大体相似［5-6］.尽管保留了库所、标记等元素，但它并不使用复杂的路径、资源的冲突等技巧来表达逻辑上的意义，而是用固有的逻辑组件来构造路由，将Petri网构造的逻辑结构隐藏在逻辑组件之下.

图3 任务示例(工作流模型)Fig.3 Example of AUV task flow(workflow)

虽然Petri网能够构造出一些精妙而准确的逻辑结构，但在多数时候，这种极其苛求洞察力和智力的建模方式并不适合面向普通人的、需要迅速作出灵活更改的任务建模.与经典的Petri网相比，工作流模型更灵活，更接近人类语言和人抽象的思维方式.但同时，由于缺乏标准、精确和成熟的理论基础，虽然市面上的工作流模型及基于工作流的应用软件种类繁多，但每种模型都或多或少存在明显的缺陷，例如OR_join任务同步时出现的逻辑问题［1］等，尚未见到理论上完美的解决方案［7］.然而总的说来，在适当的改进和处理之后，工作流模型能够更好地服务于机器人抽象任务建模.

3 任务工作流

任务工作流由工作流模型改进而来.定义任务工作流网为有向网N=(T，F)，其中T为任务，F为流关系，且需满足:

1)存在惟一的起始任务Tstart∈T作为网路的起始点，其前驱为空;

2)每个任务t∈T都位于连接到Tstart的一条通路上，不存在孤立的任务;

3)每一任务结束时必处于成功或失败2种状态之一，2种状态可分别指向不同的后继任务;

4)任务间的依赖关系F可分为2类:发起一个尚未执行的任务，或终止一个正在执行的任务.

模型中只存在任务极其依赖的关系，虽然没有库所和标记这样的元素，但类似的功能已被整合到任务中.默认情况下任何任务必须等到所有前驱任务全部结束才能执行，相当于AND_join型;任务结束后其对应的所有后继流程也都会被执行，相当于AND_split型.其他的逻辑关系，如OR_split和OR_join，将由特殊的任务来实现.不同之处在于区分出了“成功”和“失败”2种互斥的结束状态，且流关系也包括“发起”和“终止”2种.对任务首尾逻辑结构的处理不像Petri网那样显式地建模表示，而是用一个“工作流管理程序”来进行管理，这在编程实现时更加方便.

任务工作流有自己的图形语言，如图4所示，所有任务采用相同的图形样式.任务图形的头部可接纳多个前驱任务;图形的尾部分成2个区域，空白的一半表示执行成功，带叉的一半表示执行失败，从2个区域流出的箭头分别代表了2种状态下任务工作流网不同的路径.水下机器人任务流程中最为常见的成功或失败的分支流程在这里成为任务的内置属性.实箭头表示发起一个尚未运行的任务，虚箭头表示终止一个正在运行的任务.网络中的每个任务都有惟一的名称(称之为标号，以“#”开头)，同类型的不同任务的名称也必须不重复.每个任务都有内置的超时值，默认情况下其值为无穷大，超时后任务会被判定为失败，网路流程转向其失败后的路由.

图4 任务工作流图形描述方式Fig.4 Graphic description of task workflow

每个任务都是不可分割的原子任务，要扩展某一任务，只能在相应的流程处插入子网.任务的具体内容由高级编程语言编写，任务获取环境信息、判断任务成功执行或失败的代码都在其实现代码中.任务工作流模型只关注任务网络及流关系，并不规定任务的细节及具体实现方式.

OR_split结构的实现有2种方式［8］.其一如图5所示，在T4、T5前添加T2、T32个起着开关作用的判断任务，如果T4执行的条件满足而T5的条件不满足，则T2任务成功而T3任务失败，于是T4执行而T5不执行.另一种方式与具体的编程实现有关.在任务内部，可以访问并更改指向后继任务的流程.在上例中，T1内部本来保留有 T2、T3的名称作为后继，如果在某种条件下删除其中T3的名称，那么T1完成后就只能执行T2.这2种方式皆可在后继中任选数个任务来执行.

图5 任务工作流中OR_split结构Fig.5 OR_split structure in task workflow

图6中T1是一个OR_join任务，这是任务工作流模型中惟一特殊的任务，注意OR_join后面的参数，第1个参数2表示T1的前驱任务中任有2个结束后，T1就能以成功的状态执行完毕.为了避免无止境的等待，OR_join任务也有超时值.当第1个前驱任务结束时，OR_join任务就被激活，处于等待状态.如果超过时限后，前驱条件仍未完全达成，此OR_join会被当作失败.

图6 任务工作流中OR_join结构Fig.6 OR_join structure in task workflow

为避免OR_join结构可能产生的逻辑错误，OR_join任务在执行结束后会将其所有可能导致重复执行的前驱任务全部删除，以达到同步的效果.图6中，若T3、T4结束，T1成功，工作流管理程序应将其直接的前驱T2、T3、T4一并删除(删除即令运行中的任务停止，不考虑这些任务的任何后续影响).

然而OR_join运行时的前驱条件并不总是如此简单，上例中，OR_join任务的标记中还有另一串参数，显式指定给工作流管理程序并将其删除.于是T1结束后会将图6中所有6个前驱任务全部删除(默认删除 T2、T3、T4，显式删除 T5、T6、T7).这种方式强调对建模者意图的直接表述和利用，就模型本身而言并不严谨.然而在相关理论尚不完善之时，不失为一种简便有效的方案，相比更改或限制模型，以及用复杂的算法计算路径可达性的方法［9-10］，往往有着更好的实现效果.

循环结构的建模方式如图7所示，只需在其前方加入一个OR_join任务.

图7 任务工作流循环结构Fig.7 Circulation structure in task workflow

在精简了逻辑元素，整合了冗余的逻辑结构后，任务工作流能以更简洁的方式实现与其他任务模型相似的功能;而一些新特性的增加，如内置的成功或失败2种完成状态和超时值的应用，以及对OR_join结构逻辑问题的解决方案，不仅增加了模型的功能，也使得模型更加完善，更适合于水下机器人任务的建模.

4 任务工作流的建模流程

首先以图形化的方式对任务进行描述，如图8所示.对照图8可直接写出任务模型的文字描述:

#START{StartMission();;#ToTarget;;NULL;NULL;NEVER}

#ToTarget{ToTarget();#START;#Join1，#Record;;#Join2;;}

#Join1{OrJoin(1);#ToTarget，#Rearrange;#Work;;;;}

#Rearrange{Rearrange();#Work;#Join1;;;;}

#Record{Record();#ToTarget;;;;;}

#Work{Work();#Join1;#Join2;#Record;#Rearrange;;}

#Join2{OrJoin(1);#Work，#ToTarget;#Return;;;;}

#Return{Return();#Join2;#TakeBack;;#Move-Up;;3 600}

#TakeBack{TakeBack();#Return;#Join3;;;;}

#MoveUp{MoveUp();#Return;#Join3;;;;}

#Join3{OrJoin(1);#MoveUp，#TakeBack;#END;;;;}

#END{EndMission();#Join3;;;;;}

每一条描述语句的格式是相同的:

任务标号{任务类型及参数;前驱任务标号;成功执行后发起的任务标号;成功后终止的任务标号;失败后发起的任务标号;失败后终止的任务标号;超时值}.

描述语句中各项用分号隔开，若某一项任务标号为空，可以不写或写上“NULL”;若在超时值处为空或写上“NEVER”，则超时值为无穷.

图8 任务示例(任务工作流)Fig.8 An example of AUV task flow(task workflow)

网路中任一表示流程的箭头，将既被发起它的前驱任务描述，又被接纳它的后继任务描述，任务间的依赖关系便由此衔接起来.对单个任务的简单叠加就得到了整个任务网.每一条语句就是对模型中一个任务及其外延的流关系的直接描述，故图中任务方框的个数与描述语句数相同.描述语句没有先后顺序可言，任务流程描述文件的格式是相当灵活的.规定这样的描述语言，是为了计算机能直接读取任务文本，自动按流程发起任务并对任务进行操作和管理.由于此描述语言格式规范，因此完全可以开发相应的应用软件，让建模者直接以图形方式建模，而由程序自动生成模型的文本描述.

在程序实现中，每个任务类对应一个C++类，且每个任务类都继承统一的基类，在其中定义通用的数据类型和方法，包括对结束状态的判断，以及与外界通信的手段.如上例中，#Join1、#Join2、#Join3都属于OrJoin类型，它们都会采用一份相同的代码来实现.

5 任务管理程序的实现

作为实验室水下机器人模块化软件系统的一部分，基于上述原理与实现方式的水下机器人任务建模与管理系统已经成功开发，并在仿真平台和陆地机器人实验中得到了验证.这里仅简述此系统的几个特点:

1)所有的任务类型需提前编写(用C++语言)并编译完成.任务流程的描述由文本化的任务描述文件提供，系统读取文本中的任务类型名，自动生成对应的C++类的实例并执行此任务.任务只有在需要时才动态生成，执行完成后销毁，以节约内存空间.这涉及到C++中用字符串动态生成对象的技巧.

2)此系统提供任务流程更改的全套接口.无论任务位于文本描述文件中，还是正在内存中执行，都有标准的接口用于更改任务的流关系及类型，以便在不更换描述文件的情况下更改任务流程.

3)除起始任务、OR_join任务等少数内置任务外，所有任务类型都由用户定义并编写，任务管理系统只是按照前文所述的方式自动读取并管理任务的执行流程.同一任务类型可以被多次使用，也可以给任务传递参数，使同一份任务代码完成不同的工作.由于任务可重用，故已经存在的任务越完善，建模的过程就越方便快捷.

4)基于任务工作流的系统只关注任务间的流程关系，对系统的应用范围并不做规定.但相对而言，此模型更适合宏观抽象的任务流程建模，在机器人的自主智能尚不完善之时，将人类设计的抽象任务转换为机器可以理解的方式.

6 结束语

通过引入并改进工作流的相关理论，基于任务工作流的模型不仅建模简单(可完全依赖图形描述)、容易理解，更重要的是模型能直接转化为规范的文本描述供计算机读取，利于计算机编程实现.任务工作流对传统的工作流模型做了较多改进，在减少了模型组成元素的同时增强了模型的表述能力，并以合理的方式弥补了理论上的不足.在此基础上开发的水下机器人任务建模与管理系统已有实际使用的实例，其性能稳定可靠.随着机器人任务流程进一步复杂化，专用的任务建模及管理系统必将发挥愈发重要的作用.

［1］袁崇义.Petri网原理与应用［M］.北京:电子工业出版社，2005.

［2］邹海，边信黔，熊华胜.AUV控制系统规划层使命与任务协调方法研究［J］.机器人，2006，28(6):651-655.ZOU Hai，BIAN Xinqian，XIONG Huasheng.Research on the mission and task coordination method of AUV control system at planning layer［J］.Robot，2006，28(6):651-655.

［3］韩丽洁.水下机器人任务规划技术研究［D］.哈尔滨:哈尔滨工程大学，2010:36-56.

［4］VAN DER AALST W，VAN HEE K M.Workflow management:models，methods，and systems［M］.Cambridge，USA:The MIT Press，2002.

［5］张亮，姚淑珍.基于Petri网的工作流模式研究［J］.计算机集成制造系统，2006，12(1):54-58.ZHANG Liang，YAO Shuzhen.Research on workflow patterns based on Petri nets［J］.Computer Integrated Manufacturing Systems，2006，12(1):54-58.

［6］王斌，章云，王晓红.基于Petri网的工作流模式建模及应用［J］.计算机工程与应用，2008，44(13):238-241.WANG Bin，ZHANG Yun，WANG Xiaohong.Modeling research and application of workflow patterns based on Petri nets［J］.Computer Engineering and Application，2008，44(13):238-241.

［7］VAN DER AALST W M P，TER HOFSTEDE A H M.YAWL:yet another workflow language［R］.Brisbane，Australia:Queensland University of Technology，2003.

［8］陈荣辉，陈新度，陈新.基AND_OR图深度优先搜索的工作流模型验证［J］.机电工程技术，2008，37(6):56-71.CHEN Ronghui，CHEN Xindu，CHEN Xin.Workflow model verification based on AND_OR graph depth-first searching［J］.Mechanical ＆ Electrical Engineering Technology，2008，37(6):56-71.

［9］孙玲芳，方锦烽，汲铮，等.YAWL中OR_join任务使能判断的改进及形式化说明［J］.江苏科技大学学报:自然科学版，2007，21(5):64-68.SUN Lingfang，FANG Jinfeng，JI Zheng，et al.Improvement in enabling of OR-join in yet another workflow language［J］.Journal of Jiangsu University of Science and Technology:Natural Science Edition，2007，21(5):64-68.

［10］曹国荣，谭庆平，吴浩，等.规范流网中OR-join任务的语义及使能判定算法［J］.计算机科学与探索，2010，4(6):542-551.CAO Guorong，TAN Qingping，WU Hao，et al.Semantics and implementation of the OR-join in regular flow nets［J］.Journal of Frontiers of Computer Science and Technology，2010，4(6):542-551.