群機(jī)器人任務(wù)分工與協(xié)同搜索方法

劉 倩，陳嶷瑛，馮艷紅

(河北地質(zhì)大學(xué) 信息工程學(xué)院，河北 石家莊 050031)

0 引 言

就目前的機(jī)器人發(fā)展水平而言，單個(gè)機(jī)器人的探測(cè)能力和運(yùn)動(dòng)能力非常有限，在復(fù)雜環(huán)境下執(zhí)行搜索等復(fù)雜任務(wù)存在很多不足。以機(jī)器人組群的方式，通過(guò)互相通信提高探測(cè)和整體運(yùn)動(dòng)能力[1]，對(duì)于目標(biāo)搜索和人員搜救意義重大。

群機(jī)器人執(zhí)行搜索任務(wù)時(shí)，關(guān)鍵技術(shù)包括任務(wù)分工、避障規(guī)劃、相互協(xié)同方法等。自組織任務(wù)分工的常用方法有交換樹(shù)法、響應(yīng)閾值法、情感招募法等，文獻(xiàn)[2]提出了交換樹(shù)競(jìng)拍法，解決了帶任務(wù)偏序的負(fù)載平衡問(wèn)題；文獻(xiàn)[3]提出了帶閉環(huán)調(diào)節(jié)的任務(wù)動(dòng)態(tài)分工方法，提高了機(jī)器人搜索效率；文獻(xiàn)[4]將情感招募法與拍賣法結(jié)合，實(shí)現(xiàn)了完成全部任務(wù)最短和收益最高。避障規(guī)劃與相互協(xié)同需同時(shí)考慮，在協(xié)同搜索的同時(shí)，既要避開(kāi)障礙物又要避開(kāi)機(jī)器人，互相協(xié)同方法一般使用群體智能算法，包括菌群算法[5]、微粒群優(yōu)化算法[6]等，以上方法都實(shí)現(xiàn)了自身設(shè)定條件下的優(yōu)化與搜索效率提高。

本文研究了群機(jī)器人執(zhí)行搜索任務(wù)時(shí)的任務(wù)分工與目標(biāo)搜索問(wèn)題。在任務(wù)分工方面，為了實(shí)現(xiàn)任務(wù)分工均衡，提出了預(yù)分工與反饋調(diào)節(jié)的雙層分工方法。在目標(biāo)搜索方法，模擬鳥群覓食過(guò)程，使用粒子群算法更新機(jī)器人速度與位置，并建立了勢(shì)場(chǎng)力模型用于實(shí)現(xiàn)避障，最終實(shí)現(xiàn)了在工作區(qū)域的多目標(biāo)快速鎖定。

1 自組織任務(wù)分工

在群機(jī)器人系統(tǒng)中，單個(gè)機(jī)器人具有一定的探測(cè)能力和運(yùn)動(dòng)能力，且在一定范圍內(nèi)的機(jī)器人可以互相通信，本節(jié)研究群機(jī)器人系統(tǒng)的任務(wù)分工方法。為了實(shí)現(xiàn)分工的均衡，提出了預(yù)分工與反酷調(diào)節(jié)的雙層分工方法。

1.1 單機(jī)器人目標(biāo)獲取

單機(jī)器人通過(guò)自身攜帶傳感器探測(cè)周身一定范圍內(nèi)的障礙物信息和目標(biāo)信息。在機(jī)器人探測(cè)范圍內(nèi)，當(dāng)機(jī)器人與目標(biāo)距離不同時(shí)，機(jī)器人探測(cè)到的目標(biāo)信號(hào)強(qiáng)度也不同，本文使用目標(biāo)強(qiáng)度函數(shù)[7]進(jìn)行描述，定義為

(1)

式中：Iij為機(jī)器人Ri探測(cè)到目標(biāo)點(diǎn)Tj的強(qiáng)度，為兩者距離d的函數(shù)；dT為距離閾值，在dT范圍內(nèi)可以探測(cè)到目標(biāo)信號(hào)；Q0為目標(biāo)發(fā)出的功率；m∈(0,1) 為信號(hào)傳遞時(shí)功率衰減系數(shù)。

單機(jī)器人獲取目標(biāo)的方式除自身探測(cè)外，還可以通過(guò)互相通信獲得，規(guī)定機(jī)器人通過(guò)自身傳感器探測(cè)到的目標(biāo)為A類目標(biāo)，以通信方式獲得的目標(biāo)為B類目標(biāo)。

1.2 單機(jī)器人確定意向目標(biāo)

機(jī)器人探測(cè)過(guò)程中可能獲得多個(gè)目標(biāo)信息，包括A類和B類兩種，機(jī)器人要從目標(biāo)集合中確定一個(gè)意向目標(biāo)。依據(jù)信號(hào)強(qiáng)度Iij建立目標(biāo)選擇概率函數(shù)，為

(2)

式中：Pij為機(jī)器人Ri選擇目標(biāo)點(diǎn)Tj的概率，Gaini表示機(jī)器人Ri獲取的目標(biāo)集合，以目標(biāo)強(qiáng)度的開(kāi)平方構(gòu)造選擇概率，是為了使選擇概率與距離dij成比例關(guān)系。

機(jī)器人確定意向目標(biāo)時(shí)，目標(biāo)類型不同則優(yōu)先級(jí)也不同。如果目標(biāo)集合中包含A類目標(biāo)，則機(jī)器人只考慮A類目標(biāo)作為意向目標(biāo)；僅當(dāng)目標(biāo)集合中不包含A類目標(biāo)時(shí)，機(jī)器人才考慮B類目標(biāo)作為意向目標(biāo)。按照目標(biāo)優(yōu)先級(jí)，預(yù)選定的目標(biāo)可能有多個(gè)，此時(shí)按照式(2)計(jì)算各目標(biāo)的選擇概率，然后按照輪盤賭的方法確定一個(gè)目標(biāo)作為意向目標(biāo)。

1.3 子群形成與反饋調(diào)整

單機(jī)器人確定意向目標(biāo)后，向通信范圍內(nèi)的機(jī)器人發(fā)布信息，具有相同意向目標(biāo)的機(jī)器人組成一個(gè)子群，同時(shí)子群中目標(biāo)強(qiáng)度信號(hào)最強(qiáng)者為此子群的Leader，子群Lea-der 為子群代言人，對(duì)外發(fā)布子群信息，包括子群編號(hào)、子群規(guī)模、成員編號(hào)、目標(biāo)信息等。

通過(guò)以上方法，初步形成了若干子群，沒(méi)有編入子群的機(jī)器人繼續(xù)漫游行走探測(cè)目標(biāo)。但是這種方法極易出現(xiàn)某些子群過(guò)大、某些目標(biāo)無(wú)人搜索的情況，即機(jī)器人資源分配不平衡、不合理。為了解決這一問(wèn)題，本文提出了反饋調(diào)節(jié)機(jī)制，達(dá)到機(jī)器人資源配置“削多補(bǔ)少”的效果。搜索同一目標(biāo)點(diǎn)的機(jī)器人不能太少，否則搜索效率較低，甚至丟失目標(biāo)；同時(shí)搜索同一目標(biāo)點(diǎn)的機(jī)器人數(shù)也不易過(guò)大，不僅會(huì)造成資源浪費(fèi)，靠近目標(biāo)點(diǎn)時(shí)也會(huì)異常擁擠?；谝陨峡紤]，將搜索同一目標(biāo)點(diǎn)的機(jī)器人數(shù)上限設(shè)置為6。當(dāng)子群規(guī)模小于6時(shí)，子群Leader會(huì)對(duì)外發(fā)布招募信息；當(dāng)子群規(guī)模大于6時(shí)，對(duì)子群內(nèi)機(jī)器人進(jìn)行排序，只保留前6名，其余機(jī)器人被踢出子群轉(zhuǎn)為漫游搜索狀態(tài)。

對(duì)于同一子群的機(jī)器人，排序方法為：按照機(jī)器人獲得目標(biāo)的方式和信號(hào)強(qiáng)度進(jìn)行排序，具體地講，意向目標(biāo)為A類目標(biāo)的機(jī)器人排在B類目標(biāo)機(jī)器人之前，意向目標(biāo)同為A類或B類時(shí)，按照目標(biāo)強(qiáng)度進(jìn)行排序，保留排名靠前的6個(gè)機(jī)器人形成子群，其余被踢出。這種以反饋方式調(diào)節(jié)子群的方法，能夠保留離目標(biāo)較近的機(jī)器人，而離目標(biāo)相對(duì)較遠(yuǎn)的機(jī)器人被排除在子群之外，去搜索其它目標(biāo)點(diǎn)，保證了機(jī)器人資源的合理配置與任務(wù)平衡，提高了綜合搜索效率。

2 機(jī)器人協(xié)同控制

2.1 機(jī)器人狀態(tài)劃分

機(jī)器人在獲取目標(biāo)之前，以漫游搜索方式在工作區(qū)域中探測(cè)目標(biāo)，通過(guò)探測(cè)或通信獲取目標(biāo)后按照組群方式加入子群；加入子群的機(jī)器人由漫游搜索狀態(tài)轉(zhuǎn)為協(xié)同搜索狀態(tài)，未加入子群的機(jī)器人繼續(xù)漫游搜索狀態(tài)；當(dāng)機(jī)器人與目標(biāo)距離小于某一閾值時(shí)，認(rèn)為發(fā)現(xiàn)目標(biāo)，并向外發(fā)布目標(biāo)信息，機(jī)器人轉(zhuǎn)為目標(biāo)聲明狀態(tài)，對(duì)目標(biāo)位置標(biāo)記后，機(jī)器人自動(dòng)解散轉(zhuǎn)為漫游搜索狀態(tài)，繼續(xù)搜索其它目標(biāo)。具體轉(zhuǎn)換方法如圖1所示。

圖1 機(jī)器人狀態(tài)劃分方法

機(jī)器人漫游搜索時(shí)，以在最短時(shí)間內(nèi)覆蓋最大面積為目的，因此本文使用直線漫游搜索方式，漫游速度為機(jī)器人最大速度Vmax，搜索方向按照相鄰機(jī)器人搜索方向不同且保證最大搜索面原則確定。下面重點(diǎn)設(shè)計(jì)機(jī)器人協(xié)同搜索狀態(tài)下運(yùn)動(dòng)方式和避障方法。

2.2 模擬鳥群覓食的搜索方法

子群內(nèi)機(jī)器人作為一個(gè)團(tuán)隊(duì)搜索目標(biāo)，與鳥群搜索食物過(guò)程極為相似，基于這種類比，本文提出了帶慣性權(quán)重粒子群算法[8]的機(jī)器人協(xié)同搜索方法。機(jī)器人速度及位置更新方法為

(3)

位置的優(yōu)劣依據(jù)目標(biāo)信號(hào)強(qiáng)度進(jìn)行評(píng)判，分析式(3)可知，機(jī)器人在自身歷史最優(yōu)位置、子群最優(yōu)位置和慣性影響下，進(jìn)行速度和位置更新，不斷向目標(biāo)靠近而最終鎖定目標(biāo)。

2.3 基于勢(shì)場(chǎng)力的避障方法

在人工勢(shì)場(chǎng)算法中，依賴障礙物斥力與目標(biāo)點(diǎn)引力使機(jī)器人避開(kāi)障礙物而趨向目標(biāo)點(diǎn)[9]，參考這一思想，設(shè)計(jì)群機(jī)器人運(yùn)動(dòng)過(guò)程中的避障方法。機(jī)器人運(yùn)動(dòng)過(guò)程中，障礙物的斥力大小定義為

(4)

式中：fre(d) 表示障礙物斥力大小，為距離d的函數(shù)；lT為距離閾值，當(dāng)機(jī)器人與障礙物距離d小于lT時(shí)存在斥力作用，當(dāng)d大于lT時(shí)不存在斥力作用；c為一個(gè)常數(shù)；lm為避撞加強(qiáng)的距離，m取值不同時(shí)代表不同障礙物，m=1表示障礙物為其它機(jī)器人，m=2表示靜態(tài)障礙物。

圖2 勢(shì)場(chǎng)力模型

(5)

2.4 搜索與避障的協(xié)同控制方法

機(jī)器人在行走過(guò)程中，既要搜索目標(biāo)又要考慮避障，因此機(jī)器人的運(yùn)動(dòng)受“目標(biāo)搜索”和“避障”雙層因素的影響。機(jī)器人協(xié)同控制方法按照機(jī)器人狀態(tài)分以下兩種情況討論：

情況一：機(jī)器人處于漫游狀態(tài)

(1)當(dāng)機(jī)器人處于漫游狀態(tài)，且d>lT，即無(wú)需避障時(shí)，機(jī)器人速度和位置更新方法為

(6)

(2)當(dāng)器人處于漫游狀態(tài)，且d≤lT，即需要避障時(shí)，機(jī)器人速度和位置更新方法為

(7)

情況二：機(jī)器人處于協(xié)同搜索狀態(tài)

(1)當(dāng)機(jī)器人處于協(xié)同搜索狀態(tài)，且d>lT，即無(wú)需避障時(shí)，機(jī)器人速度和位置更新方法為

(8)

(2)當(dāng)機(jī)器人處于協(xié)同搜索狀態(tài)，且d≤lT，即需要避障時(shí)，機(jī)器人速度和位置更新方法為

(9)

3 仿真驗(yàn)證

3.1 仿真環(huán)境及參數(shù)設(shè)置

為了對(duì)本文設(shè)計(jì)的群機(jī)器人任務(wù)分工與協(xié)同搜索方法進(jìn)行驗(yàn)證，仿真出1000m×1000m的搜素區(qū)域，在此區(qū)域中放置6個(gè)目標(biāo)與30個(gè)機(jī)器人，機(jī)器人最大速度設(shè)置為5 m/s，最大感應(yīng)半徑100 m，最大通信半徑300 m，目標(biāo)發(fā)出的功率Q0=103，目標(biāo)信號(hào)功率衰減系數(shù)m=0.1，慣性系數(shù)α=0.1、λ=0.4、ω=0.4，目標(biāo)到達(dá)閾值為5 m。

在搜索區(qū)域中，障礙物與目標(biāo)分布情況如圖3所示，圖中帶有標(biāo)號(hào)的實(shí)心心型表示目標(biāo)點(diǎn)，標(biāo)號(hào)為目標(biāo)點(diǎn)編號(hào)；黑色實(shí)線表示障礙物；帶有方向的空心圓表示機(jī)器人，初始時(shí)刻30個(gè)機(jī)器人全部投置于搜索區(qū)域左下角。

3.2 搜索結(jié)果分析

使用本文設(shè)計(jì)的任務(wù)分工與協(xié)同搜索算法搜索區(qū)域內(nèi)目標(biāo)，為了形成對(duì)比，同時(shí)使用文獻(xiàn)[10]給出的搜索方法進(jìn)行搜索，兩種方法各運(yùn)行50次。隨機(jī)選取使用本文方法的一個(gè)搜索過(guò)程進(jìn)行分析，結(jié)果如圖4所示。

圖3 搜索區(qū)域

圖4 搜索過(guò)程

圖4(a)與圖4(b)展示了子群1形成后搜索目標(biāo)1的過(guò)程。在T=75s時(shí)，搜索目標(biāo)1的子群1形成，子群規(guī)模為6，參加子群1的機(jī)器人編號(hào)為22、27、14、6、28、1。加入子群1的機(jī)器人由漫游搜索狀態(tài)轉(zhuǎn)為協(xié)同搜索狀態(tài)，其余機(jī)器人繼續(xù)進(jìn)行漫游搜索。在T=115s，子群1成功鎖定目標(biāo)1，由子群Leader對(duì)外發(fā)布目標(biāo)信息，并對(duì)目標(biāo)位置進(jìn)行標(biāo)記，之后子群1成員解散，由協(xié)同搜索狀態(tài)轉(zhuǎn)為漫游搜索狀態(tài)，目標(biāo)1搜索結(jié)束。

圖4(c)展示了子群3形成后成功避障并鎖定目標(biāo)3的過(guò)程。在T=115s時(shí)子群3形成，在T=146s時(shí)子群3成功鎖定目標(biāo)3，圖4(c)中給出了子群內(nèi)機(jī)器人從結(jié)盟到鎖定目標(biāo)過(guò)程的運(yùn)動(dòng)軌跡，由運(yùn)動(dòng)軌跡可以看出，子群內(nèi)機(jī)器人成功完成了避障和目標(biāo)鎖定。目標(biāo)鎖定后，子群3解散，機(jī)器人轉(zhuǎn)入漫游搜索狀態(tài)，繼續(xù)搜索其它目標(biāo)。

圖4(d)給出了子群6從結(jié)盟到鎖定目標(biāo)6的軌跡，參加子群6的機(jī)器人包括27、6、10、23、17、17。從子群6各機(jī)器人的運(yùn)動(dòng)軌跡可以看出，子群6不僅成功實(shí)現(xiàn)了避障，而且成功鎖定目標(biāo)6，直至此時(shí)所有目標(biāo)搜索完畢，搜索過(guò)程結(jié)束。

在相同環(huán)境下、相同機(jī)器人規(guī)模和相同目標(biāo)數(shù)量下，使用文獻(xiàn)[10]給出的方法進(jìn)行目標(biāo)搜索，本文算法與文獻(xiàn)[10]算法各運(yùn)行50次。經(jīng)驗(yàn)證，50次搜索中本文算法與文獻(xiàn)[10]算法都能夠鎖定所有目標(biāo)，未出現(xiàn)遺失目標(biāo)的情況，統(tǒng)計(jì)50次算法耗時(shí)的均值、方差、最大值與最小值，結(jié)果見(jiàn)表1。

表1 算法耗時(shí)

由表1可以看出，在1000m×1000m仿真環(huán)境中設(shè)置6個(gè)目標(biāo)與30個(gè)機(jī)器人的情況下，本文算法搜索所有目標(biāo)平均耗時(shí)為435.722 s，比文獻(xiàn)[10]算法減少了17.14%；本文算法最優(yōu)耗時(shí)為411 s，比文獻(xiàn)[10]算法減少了18.61%，且本文算法耗時(shí)方差小于文獻(xiàn)[10]算法，說(shuō)明本文算法不僅耗時(shí)少，而且性能穩(wěn)定。這是因?yàn)樵谌蝿?wù)分工階段，子群形成過(guò)程與反饋調(diào)節(jié)過(guò)程中，文獻(xiàn)[10]以信號(hào)強(qiáng)度為依據(jù)進(jìn)行排序，確定最終組成子群的個(gè)體；本文不僅考慮了信號(hào)強(qiáng)度，而且考慮了目標(biāo)獲取方式的區(qū)別，將A類目標(biāo)排列在B類目標(biāo)之前，這種排序方法使得距離目標(biāo)最近的個(gè)體能夠被保留，更加符合實(shí)際情況，從而提高了搜索效率。

4 結(jié)束語(yǔ)

本文研究了群機(jī)器人執(zhí)行搜索任務(wù)時(shí)的任務(wù)分工與目標(biāo)搜索問(wèn)題。在任務(wù)分工方面，以目標(biāo)信號(hào)強(qiáng)度為依據(jù)，建立了目標(biāo)選擇概率函數(shù)，依據(jù)概率函數(shù)使用輪盤賭的方法確定機(jī)器人的意向目標(biāo)，具有相同意向目標(biāo)的機(jī)器人初步形成一個(gè)子群，而后使用反饋調(diào)節(jié)的方法調(diào)整子群組成。在目標(biāo)搜索方法，模擬鳥群覓食過(guò)程搜索目標(biāo)，使用勢(shì)力實(shí)現(xiàn)避障，建立了邊搜索邊避障的協(xié)同控制方法。經(jīng)仿真驗(yàn)證，本文算法能夠成功鎖定區(qū)域內(nèi)的所有目標(biāo)，且算法耗時(shí)優(yōu)勢(shì)明顯。