一種資源約束下的AUV編隊(duì)系統(tǒng)動(dòng)態(tài)任務(wù)規(guī)劃方法

郝莉莉, 顧 浩, 康鳳舉, 楊惠珍

?

一種資源約束下的AUV編隊(duì)系統(tǒng)動(dòng)態(tài)任務(wù)規(guī)劃方法

郝莉莉1,2, 顧 浩1, 康鳳舉1,2, 楊惠珍1,2

(1. 西北工業(yè)大學(xué) 航海學(xué)院, 陜西 西安, 710072; 2. 水下信息處理與控制國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室, 陜西 西安, 710072)

動(dòng)態(tài)任務(wù)規(guī)劃是協(xié)調(diào)復(fù)雜環(huán)境、自主水下航行器(AUV)有限資源以及動(dòng)態(tài)任務(wù)之間耦合, 提高編隊(duì)協(xié)同能力的關(guān)鍵技術(shù)。針對(duì)資源約束下的AUV編隊(duì)系統(tǒng)動(dòng)態(tài)任務(wù)規(guī)劃問(wèn)題, 提出了一種基于不公平度的資源均衡方法, 兼顧資源均衡和效能最大2個(gè)目標(biāo), 建立了基于合同網(wǎng)的多約束多目標(biāo)任務(wù)規(guī)劃數(shù)學(xué)模型, 基于著色Petri網(wǎng)實(shí)現(xiàn)了系統(tǒng)的形式化建模/仿真/驗(yàn)證一體化。仿真結(jié)果表明, 該方法能夠有效地解決以效能最大為目標(biāo)的資源選擇原則導(dǎo)致的優(yōu)者負(fù)載過(guò)重和以平均執(zhí)行任務(wù)數(shù)為核心的負(fù)載平衡算法帶來(lái)的任務(wù)等待時(shí)間延長(zhǎng)問(wèn)題, 提高了系統(tǒng)的效能。

AUV編隊(duì); 任務(wù)規(guī)劃; 著色Petri網(wǎng); 資源均衡

0 引言

動(dòng)態(tài)任務(wù)規(guī)劃作為自主水下航行器(autono- mous underwater vehicle, AUV)編隊(duì)系統(tǒng)的高層智能, 是指在AUV編隊(duì)任務(wù)執(zhí)行過(guò)程中根據(jù)環(huán)境信息和任務(wù)態(tài)勢(shì), 統(tǒng)籌評(píng)估任務(wù)需求、AUV的各項(xiàng)能力資源約束, 從而實(shí)現(xiàn)AUV能力的充分發(fā)揮, 資源有限時(shí)的動(dòng)態(tài)任務(wù)分配。與地面AUV和無(wú)人機(jī)相比, 復(fù)雜動(dòng)態(tài)的海洋環(huán)境使得AUV具有更多的約束, 主要表現(xiàn)在: 1) AUV采用水聲通信, 通信距離有限, 信息延遲時(shí)間長(zhǎng); 2) 水下環(huán)境中無(wú)法接收GPS等無(wú)線電信號(hào), 使得AUV導(dǎo)航定位能力弱; 3) 水溫、鹽度、深度及強(qiáng)噪聲等海洋自然環(huán)境也會(huì)影響AUV的信息測(cè)量精度。為此, 本文針對(duì)AUV資源約束、能力異構(gòu)、通信范圍有限及測(cè)量精度導(dǎo)致的任務(wù)動(dòng)態(tài)多樣等特點(diǎn), 研究資源有限時(shí)的AUV編隊(duì)系統(tǒng)動(dòng)態(tài)任務(wù)規(guī)劃方法。

J. Lee提出了根據(jù)各Agent以往行為的信譽(yù)和風(fēng)險(xiǎn)動(dòng)態(tài)綁定角色[1]。A. Singh引入信任度和懲罰機(jī)制[2], 來(lái)限制發(fā)放標(biāo)書(shū)的范圍和控制評(píng)價(jià)標(biāo)書(shū)的數(shù)量來(lái)減少通信量。N. Liu引入各種心智參數(shù)來(lái)對(duì)招標(biāo)范圍進(jìn)行限制, 并設(shè)置緩沖池來(lái)限制投標(biāo)者接收標(biāo)書(shū)的數(shù)目[3]。文獻(xiàn)[1]~[3]有效地降低了時(shí)耗、滿足AUV通信范圍小等約束, 但易導(dǎo)致“能者多勞”, 甚至?xí)蛸Y源的匱乏引起“能者丟失”, 無(wú)法保證編隊(duì)系統(tǒng)的完整性。為此, 文獻(xiàn)[4]提出了帶有資源緩存和優(yōu)先附屬的任務(wù)分配策略, 文獻(xiàn)[5]提出了閾值限定下的負(fù)載均衡算法, 魏鐵濤等基于能力裕度評(píng)價(jià)實(shí)現(xiàn)了多機(jī)協(xié)同目標(biāo)分配的任務(wù)規(guī)劃[6], 唐進(jìn)嶺等在任務(wù)選擇的過(guò)程中設(shè)定了資源約束條件[7], 文獻(xiàn)[8]設(shè)計(jì)了領(lǐng)航?跟隨級(jí)資源最大化的聯(lián)盟生成方法, 上述方法都以降低系統(tǒng)效能和增加時(shí)間為代價(jià), 會(huì)導(dǎo)致許多任務(wù)處于等待狀態(tài)。文獻(xiàn)[9]基于社會(huì)福利的資源均衡算法生成聯(lián)盟, 該方法僅從資源方面考慮任務(wù)分配, 并未考慮協(xié)作效能。

為此, 本文綜合考慮資源和效能2個(gè)因素, 提出了一種涵蓋了不公平程度和剩余資源均衡程度2個(gè)因子的資源均衡策略, 并結(jié)合效能最大這一目標(biāo), 建立合同網(wǎng)機(jī)制下的多約束多目標(biāo)動(dòng)態(tài)任務(wù)規(guī)劃數(shù)學(xué)模型。為了對(duì)所研究的動(dòng)態(tài)任務(wù)規(guī)劃方法進(jìn)行仿真和安全性分析, 本文基于著色Petri網(wǎng)完成了資源約束下的AUV編隊(duì)系統(tǒng)動(dòng)態(tài)任務(wù)規(guī)劃系統(tǒng)的形式化建模、仿真與驗(yàn)證。

1 AUV編隊(duì)系統(tǒng)任務(wù)規(guī)劃問(wèn)題的形式化描述

為了適應(yīng)實(shí)際執(zhí)行任務(wù)過(guò)程中區(qū)域廣、時(shí)間長(zhǎng)、動(dòng)態(tài)變化等特點(diǎn), AUV群體往往采取編隊(duì)的形式, 以AUV性能、資源的多樣性來(lái)彌補(bǔ)其AUV異構(gòu)、導(dǎo)航和探測(cè)等精度不高, 能量、武器等資源不足的特點(diǎn), 保證任務(wù)的高效執(zhí)行。為了在保證效能最大的同時(shí), 提高AUV生存能力和任務(wù)成功率, 本文從資源和效能2個(gè)方面研究AUV編隊(duì)系統(tǒng)的任務(wù)規(guī)劃問(wèn)題。

1.1 基于效能的目標(biāo)函數(shù)

任務(wù)規(guī)劃的主要目的是為了提高AUV編隊(duì)的協(xié)同作戰(zhàn)效能, 為此, 本文采用下面的任務(wù)效能來(lái)綜合反映AUV編隊(duì)系統(tǒng)完成任務(wù)的質(zhì)量、付出的代價(jià)和獲得的收益。

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

在滿足任務(wù)效能最大的同時(shí), 為了保證編隊(duì)內(nèi)各AUV的武器、設(shè)備及能源等資源得到公平分配, 維護(hù)編隊(duì)系統(tǒng)完整性, 提高系統(tǒng)生存能力, 提出了基于不公平度的資源均衡算法。

其中,表示滿足資源約束的AUV數(shù)量。

1.3 資源約束下AUV編隊(duì)系統(tǒng)任務(wù)規(guī)劃數(shù)學(xué)模型

AUV編隊(duì)執(zhí)行過(guò)程中, 當(dāng)發(fā)現(xiàn)1個(gè)新的任務(wù), 僅從效能最大的角度考慮任務(wù)的分配會(huì)導(dǎo)致能者資源的過(guò)度匱乏, 長(zhǎng)期作業(yè)任務(wù)的成功率降低, 以往僅是作為1個(gè)約束條件或者是只根據(jù)資源需求選擇任務(wù)的方式又會(huì)帶來(lái)效能不高, 為此, 綜合效能最大和資源平衡2個(gè)目標(biāo)函數(shù), 則資源約束下的AUV編隊(duì)系統(tǒng)任務(wù)規(guī)劃目標(biāo)函數(shù)為

2 基于合同網(wǎng)的分布式動(dòng)態(tài)協(xié)商機(jī)制

在AUV編隊(duì)系統(tǒng)中, 由于任務(wù)的類型不同和各AUV執(zhí)行能力不同, 造成了不同AUV執(zhí)行任務(wù)的效能不同, 整體的效能也隨之改變。為此, 采用基于合同網(wǎng)的分布式的自適應(yīng)動(dòng)態(tài)協(xié)商機(jī)制, 通過(guò)AUV之間的互相協(xié)商和任務(wù)競(jìng)爭(zhēng), 以招標(biāo)—投標(biāo)—中標(biāo)這種形式來(lái)獲得整體的最優(yōu)解, 從而以最優(yōu)的系統(tǒng)配置和代價(jià)完成任務(wù)[10]。

圖1 合同網(wǎng)協(xié)商機(jī)制

3 基于著色Petri網(wǎng)的形式化建模、仿真與驗(yàn)證

由3個(gè)AUV編隊(duì)協(xié)同執(zhí)行任務(wù)1~5, 預(yù)先分配AUV1執(zhí)行1, AUV2執(zhí)行2, AUV3執(zhí)行3。當(dāng)任務(wù)執(zhí)行過(guò)程中AUV1相繼發(fā)現(xiàn)type2類型的目標(biāo)4,5, 通過(guò)協(xié)商和競(jìng)爭(zhēng)來(lái)實(shí)現(xiàn)任務(wù)的有效分配。

AUV編隊(duì)系統(tǒng)模型包括子模型, 即3個(gè)AUV子模型(AUV1, AUV2, AUV3), 及其頂層模型——AUV之間的合同網(wǎng)交互(contract net, CN)。設(shè)定建模所需的主要的顏色集, 其聲明如表1所示。建立系統(tǒng)的頂層模型如圖2所示。

表1 主要的顏色集聲明

當(dāng)AUV1發(fā)現(xiàn)新任務(wù)時(shí), 設(shè)置招標(biāo)變遷invite biding的警衛(wèi)函數(shù)profit<200 orelse f_ret=0, 用于判斷總目標(biāo)函數(shù)是否小于閾值或者任務(wù)資源約束是否滿足, 否則分別向AUV2和AUV3發(fā)送標(biāo)書(shū)biding和biding11。AUV2和AUV3分別根據(jù)自身的情況來(lái)評(píng)價(jià)標(biāo)書(shū)。以AUV2為例, AUV2根據(jù)當(dāng)前正在執(zhí)行的任務(wù)預(yù)測(cè)任務(wù)完成時(shí)的位置send2, 并結(jié)合標(biāo)書(shū)根據(jù)式(6)設(shè)計(jì)函數(shù)genprofit評(píng)價(jià)總效益(receive biding2), 并投標(biāo)。AUV1對(duì)AUV2和AUV3評(píng)價(jià)標(biāo)書(shū)的效益profit2和profit3進(jìn)行比較, 哪個(gè)AUV獲得的效益大, 則變遷flag對(duì)其發(fā)送中標(biāo)信息, 即標(biāo)識(shí)1, 落標(biāo)的發(fā)送標(biāo)識(shí)0, 與此同時(shí), 中標(biāo)者的任務(wù)通過(guò)變遷zhong_bid而得到更新。

圖2 AUV編隊(duì)系統(tǒng)的頂層模型

4 仿真與驗(yàn)證

4.1 仿真結(jié)果與分析

分別針對(duì)本文提出資源約束下的AUV編隊(duì)動(dòng)態(tài)任務(wù)規(guī)劃策略和不考慮資源均衡的效能最大任務(wù)規(guī)劃策略進(jìn)行仿真, 仿真結(jié)果如表2所示。

由仿真結(jié)果可知, 在AUV執(zhí)行任務(wù)4和5時(shí), 本文提出的綜合資源均衡和效能的動(dòng)態(tài)任務(wù)規(guī)劃方法, 為了滿足資源均衡這一要素, 由AUV1和AUV2協(xié)同執(zhí)行任務(wù)4, 3個(gè)AUV協(xié)同執(zhí)行任務(wù)5, 雖然在效能方面有所下降, 但是在剩余資源的完整性卻很高, 任務(wù)數(shù)量較多時(shí), 能夠?yàn)楹罄m(xù)多樣任務(wù)的執(zhí)行提供更大的可能性。

表2 仿真結(jié)果對(duì)比表

4.2 動(dòng)態(tài)性能驗(yàn)證

利用輔助工具CPN Tools[11]進(jìn)一步對(duì)資源限定下的AUV編隊(duì)動(dòng)態(tài)任務(wù)規(guī)劃系統(tǒng)模型進(jìn)行驗(yàn)證, 限于篇幅, 這里給出了部分狀態(tài)空間報(bào)告, 如圖3所示。

圖3 部分狀態(tài)空間分析報(bào)告

通過(guò)分析狀態(tài)空間分析報(bào)告, 可以得到以下結(jié)論: 1) 所建的系統(tǒng)模型強(qiáng)聯(lián)通結(jié)構(gòu)圖(Scc Graph)和狀態(tài)空間圖(State Space)所含的節(jié)點(diǎn)(131個(gè))和弧(351條)一樣多, 表明運(yùn)行過(guò)程中沒(méi)有無(wú)窮并發(fā)序列。公平性報(bào)告(Fireness Properties)再次證明了該點(diǎn); 2) 由家態(tài)報(bào)告(Home Properties)可知, 初始標(biāo)識(shí)不是家態(tài)標(biāo)識(shí), 即初始標(biāo)識(shí)不能重新初始化其自身; 3) 由活性報(bào)告(Liveness Properties)可知, 僅模型終止節(jié)點(diǎn)第131個(gè)節(jié)點(diǎn)是死標(biāo)識(shí), 表明所建的系統(tǒng)模型具有活性。

5 結(jié)論

針對(duì)資源約束下的AUV編隊(duì)系統(tǒng)動(dòng)態(tài)任務(wù)規(guī)劃技術(shù), 提出了一種基于不公平度的資源均衡方法, 建立了含資源均衡和效能最大2個(gè)目標(biāo)的任務(wù)規(guī)劃數(shù)學(xué)模型, 并采用著色Petri網(wǎng), 在CPN Tools平臺(tái)上形式化地建立了基于合同網(wǎng)的AUV編隊(duì)任務(wù)規(guī)劃概念模型, 通過(guò)仿真驗(yàn)證了該算法的正確性和有效性, 以及模型的活性、公平性和家態(tài)等動(dòng)態(tài)性能。AUV所面臨的復(fù)雜環(huán)境, 使得AUV的通信延遲、信息不一致等, 深入研究復(fù)雜環(huán)境下的AUV編隊(duì)任務(wù)規(guī)劃方法是作者進(jìn)一步的研究方向。

[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ī)協(xié)同與目標(biāo)分配任務(wù)規(guī)劃方法[J]. 北京航空航天大學(xué)學(xué)報(bào), 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ìn)嶺, 張著洪. 多項(xiàng)目多任務(wù)選擇動(dòng)態(tài)規(guī)劃及其智能決策[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 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.

(責(zé)任編輯: 楊力軍)

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.

船舶預(yù)研支撐技術(shù)基金(11J4.1.1).

郝莉莉(1985-), 女, 在讀博士, 研究方向?yàn)槿蝿?wù)規(guī)劃與系統(tǒng)仿真.

TJ630.33; TP391.9

A

1673-1948(2014)04-0277-05