一种资源约束下的AUV编队系统动态任务规划方法

郝莉莉, 顾 浩, 康凤举, 杨惠珍



一种资源约束下的AUV编队系统动态任务规划方法

郝莉莉1,2, 顾 浩1, 康凤举1,2, 杨惠珍1,2

(1. 西北工业大学 航海学院, 陕西 西安, 710072; 2. 水下信息处理与控制国家级重点实验室, 陕西 西安, 710072)

动态任务规划是协调复杂环境、自主水下航行器(AUV)有限资源以及动态任务之间耦合, 提高编队协同能力的关键技术。针对资源约束下的AUV编队系统动态任务规划问题, 提出了一种基于不公平度的资源均衡方法, 兼顾资源均衡和效能最大2个目标, 建立了基于合同网的多约束多目标任务规划数学模型, 基于着色Petri网实现了系统的形式化建模/仿真/验证一体化。仿真结果表明, 该方法能够有效地解决以效能最大为目标的资源选择原则导致的优者负载过重和以平均执行任务数为核心的负载平衡算法带来的任务等待时间延长问题, 提高了系统的效能。

AUV编队; 任务规划; 着色Petri网; 资源均衡

0 引言

动态任务规划作为自主水下航行器(autono- mous underwater vehicle, AUV)编队系统的高层智能, 是指在AUV编队任务执行过程中根据环境信息和任务态势, 统筹评估任务需求、AUV的各项能力资源约束, 从而实现AUV能力的充分发挥, 资源有限时的动态任务分配。与地面AUV和无人机相比, 复杂动态的海洋环境使得AUV具有更多的约束, 主要表现在: 1) AUV采用水声通信, 通信距离有限, 信息延迟时间长; 2) 水下环境中无法接收GPS等无线电信号, 使得AUV导航定位能力弱; 3) 水温、盐度、深度及强噪声等海洋自然环境也会影响AUV的信息测量精度。为此, 本文针对AUV资源约束、能力异构、通信范围有限及测量精度导致的任务动态多样等特点, 研究资源有限时的AUV编队系统动态任务规划方法。

J. Lee提出了根据各Agent以往行为的信誉和风险动态绑定角色[1]。A. Singh引入信任度和惩罚机制[2], 来限制发放标书的范围和控制评价标书的数量来减少通信量。N. Liu引入各种心智参数来对招标范围进行限制, 并设置缓冲池来限制投标者接收标书的数目[3]。文献[1]~[3]有效地降低了时耗、满足AUV通信范围小等约束, 但易导致“能者多劳”, 甚至会因资源的匮乏引起“能者丢失”, 无法保证编队系统的完整性。为此, 文献[4]提出了带有资源缓存和优先附属的任务分配策略, 文献[5]提出了阈值限定下的负载均衡算法, 魏铁涛等基于能力裕度评价实现了多机协同目标分配的任务规划[6], 唐进岭等在任务选择的过程中设定了资源约束条件[7], 文献[8]设计了领航−跟随级资源最大化的联盟生成方法, 上述方法都以降低系统效能和增加时间为代价, 会导致许多任务处于等待状态。文献[9]基于社会福利的资源均衡算法生成联盟, 该方法仅从资源方面考虑任务分配, 并未考虑协作效能。

为此, 本文综合考虑资源和效能2个因素, 提出了一种涵盖了不公平程度和剩余资源均衡程度2个因子的资源均衡策略, 并结合效能最大这一目标, 建立合同网机制下的多约束多目标动态任务规划数学模型。为了对所研究的动态任务规划方法进行仿真和安全性分析, 本文基于着色Petri网完成了资源约束下的AUV编队系统动态任务规划系统的形式化建模、仿真与验证。

1 AUV编队系统任务规划问题的形式化描述

为了适应实际执行任务过程中区域广、时间长、动态变化等特点, AUV群体往往采取编队的形式, 以AUV性能、资源的多样性来弥补其AUV异构、导航和探测等精度不高, 能量、武器等资源不足的特点, 保证任务的高效执行。为了在保证效能最大的同时, 提高AUV生存能力和任务成功率, 本文从资源和效能2个方面研究AUV编队系统的任务规划问题。

1.1 基于效能的目标函数

任务规划的主要目的是为了提高AUV编队的协同作战效能, 为此, 本文采用下面的任务效能来综合反映AUV编队系统完成任务的质量、付出的代价和获得的收益。

1.2 基于不公平度的资源均衡算法

在满足任务效能最大的同时, 为了保证编队内各AUV的武器、设备及能源等资源得到公平分配, 维护编队系统完整性, 提高系统生存能力, 提出了基于不公平度的资源均衡算法。

其中,表示满足资源约束的AUV数量。

1.3 资源约束下AUV编队系统任务规划数学模型

AUV编队执行过程中, 当发现1个新的任务, 仅从效能最大的角度考虑任务的分配会导致能者资源的过度匮乏, 长期作业任务的成功率降低, 以往仅是作为1个约束条件或者是只根据资源需求选择任务的方式又会带来效能不高, 为此, 综合效能最大和资源平衡2个目标函数, 则资源约束下的AUV编队系统任务规划目标函数为

2 基于合同网的分布式动态协商机制

在AUV编队系统中, 由于任务的类型不同和各AUV执行能力不同, 造成了不同AUV执行任务的效能不同, 整体的效能也随之改变。为此, 采用基于合同网的分布式的自适应动态协商机制, 通过AUV之间的互相协商和任务竞争, 以招标—投标—中标这种形式来获得整体的最优解, 从而以最优的系统配置和代价完成任务[10]。

图1 合同网协商机制

3 基于着色Petri网的形式化建模、仿真与验证

由3个AUV编队协同执行任务1~5, 预先分配AUV1执行1, AUV2执行2, AUV3执行3。当任务执行过程中AUV1相继发现type2类型的目标4,5, 通过协商和竞争来实现任务的有效分配。

AUV编队系统模型包括子模型, 即3个AUV子模型(AUV1, AUV2, AUV3), 及其顶层模型——AUV之间的合同网交互(contract net, CN)。设定建模所需的主要的颜色集, 其声明如表1所示。建立系统的顶层模型如图2所示。

表1 主要的颜色集声明

当AUV1发现新任务时, 设置招标变迁invite biding的警卫函数profit<200 orelse f_ret=0, 用于判断总目标函数是否小于阈值或者任务资源约束是否满足, 否则分别向AUV2和AUV3发送标书biding和biding11。AUV2和AUV3分别根据自身的情况来评价标书。以AUV2为例, AUV2根据当前正在执行的任务预测任务完成时的位置send2, 并结合标书根据式(6)设计函数genprofit评价总效益(receive biding2), 并投标。AUV1对AUV2和AUV3评价标书的效益profit2和profit3进行比较, 哪个AUV获得的效益大, 则变迁flag对其发送中标信息, 即标识1, 落标的发送标识0, 与此同时, 中标者的任务通过变迁zhong_bid而得到更新。

图2 AUV编队系统的顶层模型

4 仿真与验证

4.1 仿真结果与分析

分别针对本文提出资源约束下的AUV编队动态任务规划策略和不考虑资源均衡的效能最大任务规划策略进行仿真, 仿真结果如表2所示。

由仿真结果可知, 在AUV执行任务4和5时, 本文提出的综合资源均衡和效能的动态任务规划方法, 为了满足资源均衡这一要素, 由AUV1和AUV2协同执行任务4, 3个AUV协同执行任务5, 虽然在效能方面有所下降, 但是在剩余资源的完整性却很高, 任务数量较多时, 能够为后续多样任务的执行提供更大的可能性。

表2 仿真结果对比表

4.2 动态性能验证

利用辅助工具CPN Tools[11]进一步对资源限定下的AUV编队动态任务规划系统模型进行验证, 限于篇幅, 这里给出了部分状态空间报告, 如图3所示。

图3 部分状态空间分析报告

通过分析状态空间分析报告, 可以得到以下结论: 1) 所建的系统模型强联通结构图(Scc Graph)和状态空间图(State Space)所含的节点(131个)和弧(351条)一样多, 表明运行过程中没有无穷并发序列。公平性报告(Fireness Properties)再次证明了该点; 2) 由家态报告(Home Properties)可知, 初始标识不是家态标识, 即初始标识不能重新初始化其自身; 3) 由活性报告(Liveness Properties)可知, 仅模型终止节点第131个节点是死标识, 表明所建的系统模型具有活性。

5 结论

针对资源约束下的AUV编队系统动态任务规划技术, 提出了一种基于不公平度的资源均衡方法, 建立了含资源均衡和效能最大2个目标的任务规划数学模型, 并采用着色Petri网, 在CPN Tools平台上形式化地建立了基于合同网的AUV编队任务规划概念模型, 通过仿真验证了该算法的正确性和有效性, 以及模型的活性、公平性和家态等动态性能。AUV所面临的复杂环境, 使得AUV的通信延迟、信息不一致等, 深入研究复杂环境下的AUV编队任务规划方法是作者进一步的研究方向。

[1] Lee J, Lee S J, Chen H M. Dynamic Role Binding with Agent-centric Contract Net Protocol in Agent Organiza- tions[C]//2008 IEEE International Conference on Systems, Man and Cybernetics. Manchester, United Kingdom: 636- 643.

[2] Singh A, Juneja D, Sharma A K. Introducing Trust Establishment Protocol in Contract Net Protocol[C]//2010 International Conference on Advances in Computer Engin- eering. Bangalore, India, 2010: 59-63.

[3] Liu N, Gao F Y. Research on the Negotiation Strategy of Multi-agent Based on Extended Contract Net[C]//Inter- national Conference on Future Computer and Communi- cation. Wuhan, China, 2009: 105-109.

[4] Jiang Y C, Huang Z C. The Rich Get Richer: Preferential Attachment in the Task Allocation of Cooperative Networked Multi-agent Systems with Resource Caching[J]. IEEE Transactions on Systems, Man, and Cybernetics —Part A: Systems and Humans, 2012, 42(5): 1040-1052.

[5] Hao L L, Yang H Z. Improvement and Simulation of Contract-Net-Based Task Allocation for Multi-Robot System[C]//Proceeding of 2011 2nd International Congress on Computer Applications and Computational Science. Bali, Indonesia(15-17), 2011: 61-67.

[6] 魏铁涛, 屈香菊. 多机协同与目标分配任务规划方法[J]. 北京航空航天大学学报, 2009, 35(8): 917-920, 924. Wei Tie-tao, Qu Xiang-ju. Route Planning Method for Multiple Vehicles Coordinated Target Assignment[J]. Jo- urnal of Beijing University of Aeronautics and Astronautics, 2009, 35(8): 917-920, 924.

[7] 唐进岭, 张著洪. 多项目多任务选择动态规划及其智能决策[J]. 计算机技术与发展, 2012, 22(9): 75-80.Tang Jin-ling, Zhang Zhu-hong. Dynamic Programming on Multiproject Multitask Selection and Its Intelligent Decision[J]. Computer Technology and Development, 2012, 22(9): 75-80.

[8] Chen J, Sun D. Resource Constrained Multi-robot Task Allocation Based on Leader-follower Coalition Methodology[J]. The International Journal of Robotics Research, 2011, 30(12):1423-1434.

[9] Kim M H, Kim S P, Lee S. Social-welfare Based Task Allocation for Multi-robot Systems with Resource Constraints[J]. Computers & Industrial Engineering, 2012, 63 (4): 994-1002.

[10] Smith R G.. The Contract Net Protocol: High Level Communication and Control in a Distributed Problem Solver[J]. IEEE Transactions on Computers, 1980, C29 (12): 1104-111.

[11] Jensen K. An Introduction to the Theoretical Aspects of Colored Petri Nets[D]. Aarhus :Aarhus University, 1994.

(责任编辑: 杨力军)

A Dynamic Mission Planning Method for AUV Formation with Resource Constraint

HAO Li-li, GU Hao, KANG Feng-ju, YANG Hui-zhen

(1. School of Marine Science and Technology, Northwestern Polytechnical University, Xi′an 710072, China; 2. National Key Laboratory of Underwater Information Process and Control, Xi′an 710072, China)

Dynamic mission planning is a key technology for coordinating the coupling among complex environment, autonomous underwater vehicle(AUV) with limited resources, and dynamic tasks to maximize the synergism of the members in AUV formation. This paper aims to propose a distributed mission planning algorithm for the AUV formation that undergoes resource constraint and operates in an unknown dynamic environment. The resource inequality function is employed, and a novel resource balance-based allocation algorithm is proposed. In combination with the objective function of efficiency maximum, a contract net-based mathematical model of multi-objective optimization with multiple constraints is established. Then, the integration of formal modeling, simulation and validation is presented based on Colored Petri Nets to analyze the logic, grammar, structure and properties of a mission planning system. Simulation results show that this method can avoid the overload on the winner caused by the rule of seeking efficiency maximum, and the longer waiting time caused by load balancing strategies, thus better performance is achieved.

autonomous underwater vehicle formation; mission planning; colored Petri nets; resource balance

2014-03-18;

2014-04-01.

船舶预研支撑技术基金(11J4.1.1).

郝莉莉(1985-), 女, 在读博士, 研究方向为任务规划与系统仿真.

TJ630.33; TP391.9

A

1673-1948(2014)04-0277-05