群機器人任務分工與協同搜索方法

劉 倩，陳嶷瑛，馮艷紅

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

0 引 言

就目前的機器人發展水平而言，單個機器人的探測能力和運動能力非常有限，在復雜環境下執行搜索等復雜任務存在很多不足。以機器人組群的方式，通過互相通信提高探測和整體運動能力[1]，對于目標搜索和人員搜救意義重大。

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

本文研究了群機器人執行搜索任務時的任務分工與目標搜索問題。在任務分工方面，為了實現任務分工均衡，提出了預分工與反饋調節的雙層分工方法。在目標搜索方法，模擬鳥群覓食過程，使用粒子群算法更新機器人速度與位置，并建立了勢場力模型用于實現避障，最終實現了在工作區域的多目標快速鎖定。

1 自組織任務分工

在群機器人系統中，單個機器人具有一定的探測能力和運動能力，且在一定范圍內的機器人可以互相通信，本節研究群機器人系統的任務分工方法。為了實現分工的均衡，提出了預分工與反酷調節的雙層分工方法。

1.1 單機器人目標獲取

單機器人通過自身攜帶傳感器探測周身一定范圍內的障礙物信息和目標信息。在機器人探測范圍內，當機器人與目標距離不同時，機器人探測到的目標信號強度也不同，本文使用目標強度函數[7]進行描述，定義為

(1)

式中：Iij為機器人Ri探測到目標點Tj的強度，為兩者距離d的函數；dT為距離閾值，在dT范圍內可以探測到目標信號；Q0為目標發出的功率；m∈(0,1) 為信號傳遞時功率衰減系數。

單機器人獲取目標的方式除自身探測外，還可以通過互相通信獲得，規定機器人通過自身傳感器探測到的目標為A類目標，以通信方式獲得的目標為B類目標。

1.2 單機器人確定意向目標

機器人探測過程中可能獲得多個目標信息，包括A類和B類兩種，機器人要從目標集合中確定一個意向目標。依據信號強度Iij建立目標選擇概率函數，為

(2)

式中：Pij為機器人Ri選擇目標點Tj的概率，Gaini表示機器人Ri獲取的目標集合，以目標強度的開平方構造選擇概率，是為了使選擇概率與距離dij成比例關系。

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

1.3 子群形成與反饋調整

單機器人確定意向目標后，向通信范圍內的機器人發布信息，具有相同意向目標的機器人組成一個子群，同時子群中目標強度信號最強者為此子群的Leader，子群Lea-der 為子群代言人，對外發布子群信息，包括子群編號、子群規模、成員編號、目標信息等。

通過以上方法，初步形成了若干子群，沒有編入子群的機器人繼續漫游行走探測目標。但是這種方法極易出現某些子群過大、某些目標無人搜索的情況，即機器人資源分配不平衡、不合理。為了解決這一問題，本文提出了反饋調節機制，達到機器人資源配置“削多補少”的效果。搜索同一目標點的機器人不能太少，否則搜索效率較低，甚至丟失目標；同時搜索同一目標點的機器人數也不易過大，不僅會造成資源浪費，靠近目標點時也會異常擁擠。基于以上考慮，將搜索同一目標點的機器人數上限設置為6。當子群規模小于6時，子群Leader會對外發布招募信息；當子群規模大于6時，對子群內機器人進行排序，只保留前6名，其余機器人被踢出子群轉為漫游搜索狀態。

對于同一子群的機器人，排序方法為：按照機器人獲得目標的方式和信號強度進行排序，具體地講，意向目標為A類目標的機器人排在B類目標機器人之前，意向目標同為A類或B類時，按照目標強度進行排序，保留排名靠前的6個機器人形成子群，其余被踢出。這種以反饋方式調節子群的方法，能夠保留離目標較近的機器人，而離目標相對較遠的機器人被排除在子群之外，去搜索其它目標點，保證了機器人資源的合理配置與任務平衡，提高了綜合搜索效率。

2 機器人協同控制

2.1 機器人狀態劃分

機器人在獲取目標之前，以漫游搜索方式在工作區域中探測目標，通過探測或通信獲取目標后按照組群方式加入子群；加入子群的機器人由漫游搜索狀態轉為協同搜索狀態，未加入子群的機器人繼續漫游搜索狀態；當機器人與目標距離小于某一閾值時，認為發現目標，并向外發布目標信息，機器人轉為目標聲明狀態，對目標位置標記后，機器人自動解散轉為漫游搜索狀態，繼續搜索其它目標。具體轉換方法如圖1所示。

圖1 機器人狀態劃分方法

機器人漫游搜索時，以在最短時間內覆蓋最大面積為目的，因此本文使用直線漫游搜索方式，漫游速度為機器人最大速度Vmax，搜索方向按照相鄰機器人搜索方向不同且保證最大搜索面原則確定。下面重點設計機器人協同搜索狀態下運動方式和避障方法。

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

子群內機器人作為一個團隊搜索目標，與鳥群搜索食物過程極為相似，基于這種類比，本文提出了帶慣性權重粒子群算法[8]的機器人協同搜索方法。機器人速度及位置更新方法為

(3)

位置的優劣依據目標信號強度進行評判，分析式(3)可知，機器人在自身歷史最優位置、子群最優位置和慣性影響下，進行速度和位置更新，不斷向目標靠近而最終鎖定目標。

2.3 基于勢場力的避障方法

在人工勢場算法中，依賴障礙物斥力與目標點引力使機器人避開障礙物而趨向目標點[9]，參考這一思想，設計群機器人運動過程中的避障方法。機器人運動過程中，障礙物的斥力大小定義為

(4)

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

圖2 勢場力模型

(5)

2.4 搜索與避障的協同控制方法

機器人在行走過程中，既要搜索目標又要考慮避障，因此機器人的運動受“目標搜索”和“避障”雙層因素的影響。機器人協同控制方法按照機器人狀態分以下兩種情況討論：

情況一：機器人處于漫游狀態

(1)當機器人處于漫游狀態，且d>lT，即無需避障時，機器人速度和位置更新方法為

(6)

(2)當器人處于漫游狀態，且d≤lT，即需要避障時，機器人速度和位置更新方法為

(7)

情況二：機器人處于協同搜索狀態

(1)當機器人處于協同搜索狀態，且d>lT，即無需避障時，機器人速度和位置更新方法為

(8)

(2)當機器人處于協同搜索狀態，且d≤lT，即需要避障時，機器人速度和位置更新方法為

(9)

3 仿真驗證

3.1 仿真環境及參數設置

為了對本文設計的群機器人任務分工與協同搜索方法進行驗證，仿真出1000m×1000m的搜素區域，在此區域中放置6個目標與30個機器人，機器人最大速度設置為5 m/s，最大感應半徑100 m，最大通信半徑300 m，目標發出的功率Q0=103，目標信號功率衰減系數m=0.1，慣性系數α=0.1、λ=0.4、ω=0.4，目標到達閾值為5 m。

在搜索區域中，障礙物與目標分布情況如圖3所示，圖中帶有標號的實心心型表示目標點，標號為目標點編號；黑色實線表示障礙物；帶有方向的空心圓表示機器人，初始時刻30個機器人全部投置于搜索區域左下角。

3.2 搜索結果分析

使用本文設計的任務分工與協同搜索算法搜索區域內目標，為了形成對比，同時使用文獻[10]給出的搜索方法進行搜索，兩種方法各運行50次。隨機選取使用本文方法的一個搜索過程進行分析，結果如圖4所示。

圖3 搜索區域

圖4 搜索過程

圖4(a)與圖4(b)展示了子群1形成后搜索目標1的過程。在T=75s時，搜索目標1的子群1形成，子群規模為6，參加子群1的機器人編號為22、27、14、6、28、1。加入子群1的機器人由漫游搜索狀態轉為協同搜索狀態，其余機器人繼續進行漫游搜索。在T=115s，子群1成功鎖定目標1，由子群Leader對外發布目標信息，并對目標位置進行標記，之后子群1成員解散，由協同搜索狀態轉為漫游搜索狀態，目標1搜索結束。

圖4(c)展示了子群3形成后成功避障并鎖定目標3的過程。在T=115s時子群3形成，在T=146s時子群3成功鎖定目標3，圖4(c)中給出了子群內機器人從結盟到鎖定目標過程的運動軌跡，由運動軌跡可以看出，子群內機器人成功完成了避障和目標鎖定。目標鎖定后，子群3解散，機器人轉入漫游搜索狀態，繼續搜索其它目標。

圖4(d)給出了子群6從結盟到鎖定目標6的軌跡，參加子群6的機器人包括27、6、10、23、17、17。從子群6各機器人的運動軌跡可以看出，子群6不僅成功實現了避障，而且成功鎖定目標6，直至此時所有目標搜索完畢，搜索過程結束。

在相同環境下、相同機器人規模和相同目標數量下，使用文獻[10]給出的方法進行目標搜索，本文算法與文獻[10]算法各運行50次。經驗證，50次搜索中本文算法與文獻[10]算法都能夠鎖定所有目標，未出現遺失目標的情況，統計50次算法耗時的均值、方差、最大值與最小值，結果見表1。

表1 算法耗時

由表1可以看出，在1000m×1000m仿真環境中設置6個目標與30個機器人的情況下，本文算法搜索所有目標平均耗時為435.722 s，比文獻[10]算法減少了17.14%；本文算法最優耗時為411 s，比文獻[10]算法減少了18.61%，且本文算法耗時方差小于文獻[10]算法，說明本文算法不僅耗時少，而且性能穩定。這是因為在任務分工階段，子群形成過程與反饋調節過程中，文獻[10]以信號強度為依據進行排序，確定最終組成子群的個體；本文不僅考慮了信號強度，而且考慮了目標獲取方式的區別，將A類目標排列在B類目標之前，這種排序方法使得距離目標最近的個體能夠被保留，更加符合實際情況，從而提高了搜索效率。

4 結束語

本文研究了群機器人執行搜索任務時的任務分工與目標搜索問題。在任務分工方面，以目標信號強度為依據，建立了目標選擇概率函數，依據概率函數使用輪盤賭的方法確定機器人的意向目標，具有相同意向目標的機器人初步形成一個子群，而后使用反饋調節的方法調整子群組成。在目標搜索方法，模擬鳥群覓食過程搜索目標，使用勢力實現避障，建立了邊搜索邊避障的協同控制方法。經仿真驗證，本文算法能夠成功鎖定區域內的所有目標，且算法耗時優勢明顯。