軍事協同巡檢路線優化策略

韓宇星， 丁剛毅， 柴作鴻

(1.北京理工大學 軟件學院， 北京 100081； 2.天津工業大學 電氣工程與自動化學院， 天津 300387)

0 引言

智能巡檢在工業、民用、國防、軍事領域有著重要的應有價值[1-4]，例如，對軍事管轄區內的營房、軍械庫、保密地點以及其他監控地點等均需要進行周期性或不定時的巡檢作業[5-6]。由于軍事任務的特殊性，對智能巡檢系統的快速響應以及執行效率提出了更高要求[7]。為巡檢機器人(巡檢車)規劃最優的巡檢路線是提高巡檢效率的關鍵技術問題之一[8-9]。目前，許多智能優化算法均可用于求解機器人巡檢路線優化問題[10-11]。例如，對于小規模的路線優化問題，可采用模擬退火、神經網絡等方法進行優化求解[12-14]，而對于大規模路線優化問題，可采用遺傳算法、粒子群算法、蟻群算法等并行優化計算方法進行求解[15-18]。其中，蟻群算法采用信息素正反饋的原理實現并行優化計算，具有收斂速度快、全局尋優能力強等特點，在各類路線優化問題的求解中獲得了良好的應用效果[19-20]。不過，目前路線優化通常針對單機器人巡檢問題開展研究，即在給定的巡檢區域內，為單一的巡檢機器人進行路線優化。但在實際應用中，當巡檢點較多或巡檢區域較大時，為了盡快完成巡檢任務，往往采用多機器人共同協作完成巡檢任務，即由多個機器人同時對區域內的巡檢點進行檢測，當所有巡檢點都被檢測一次后，巡檢任務才最終完成。目前對于此類巡檢路線優化問題研究較少，常用方法是基于地圖分割的巡檢路線優化方法[21]，即將包括全部巡檢點的地圖劃分成若干區域，每個機器人獨立負責完成一個區域內的巡檢任務，當全部機器人均完成指定區域內的巡檢任務后，最終的巡檢任務才完成。這樣，多機器人的路線優化問題又可轉化為傳統的單機器人路線優化問題進行求解。不過，這類問題的巡檢效率不僅與每個機器人的路線優化有關，還與地圖分割方式有關。但對于大規模巡檢問題，由于巡檢節點分布的復雜性，很難按照先驗知識進行合理的地圖劃分。例如，常用基于等巡檢點數量的劃分或基于等巡檢面積的劃分，都無法保證劃分結果的全局優化性能，造成有些區域機器人很快完成巡檢任務而處于閑置狀態，而個別區域長時間無法完成巡檢任務導致整體巡檢耗時過長。因此，由于巡檢任務劃分不均衡導致巡檢機器人不能充分利用，是降低巡檢效率的重要因素。

為此，本文提出可應用于多機器人協同巡檢路線優化的改進蟻群優化算法，該算法可對多機器人巡檢任務實現巡檢區域的均衡劃分，提高巡檢機器人的利用率，減少巡檢整體任務量，提升巡檢系統的執行效率。

1 協同巡檢路線優化

1.1 問題描述

設給定的軍事巡檢區內，共有N個巡檢節點{n1,n2,…,nN}，使用M個巡檢機器人{m1,m2,…,mM}協同巡檢，各機器人對應的運行速度為{v1,v2,…,vM}，當所有節點都完成一次巡檢時任務完成。其中，巡檢機器人的起始位置固定，對巡檢終點位置不做要求，即不要求巡檢機器人重新回到起始位置。此時最優巡檢方案可表示為下列優化問題的求解：

J=min{max{ti=Li/vi|i=1,2,…,M}}，

(1)

式中：J為優化指標；ti為機器人mi的巡檢耗時；Li為機器人mi的巡檢路線。

如果所有機器人的速度相同，則該巡檢問題可簡化為如下路線優化問題：

J=min{max{Li|i=1,2,…,M}}.

(2)

對于此問題，通?？刹捎没诘貓D分割的方法進行路線優化，即將巡檢范圍分為M個區域，每個巡檢機器人負責一個區域的巡檢作業，然后對各巡檢區單獨進行路線優化。不過，由于巡檢節點分布的復雜性以及各區域路線優化的隨機性，這種方法無法保證地圖分割時巡檢任務分配的均衡性，同時，由于各個機器人獨立巡檢，缺少協同配合，造成不同機器人完成巡檢作業的時間差距較大，導致部分機器人利用不充分，從而降低整體巡檢效率。

1.2 協同蟻群優化算法

在傳統蟻群算法中，每個人工蟻都擁有一個禁忌表，用于避免巡檢節點的重復搜索，人工蟻之間通過路線上留存的信息素進行信息交互，實現路線的全局優化，但這只能為單一機器人巡檢進行路線優化。為了解決多機器人協同巡檢問題，本文所提出的協同蟻群優化算法中，每個巡檢機器人都擁有一個蟻群，并采用共享禁忌表方式實現不同蟻群中人工蟻之間的信息共享，用于完成巡檢任務的全局優化。人工蟻群及共享禁忌表的分布如表1所示。表1中P為人工蟻的數量。

表1 人工蟻群與共享禁忌表

表1中每一列為一個蟻群，每個巡檢機器人都擁有一個由P個人工蟻構成的蟻群，例如機器人mi的蟻群為{ai,1,ai,2,…,ai,P}，因此，全部人工蟻的數量為M×P. 表1中最后一列為各個蟻群中的人工蟻所擁有的共享禁忌表，例如，第j行的所有人工蟻共同擁有共享禁忌表Tj. 另外，每個人工蟻均有一個代價表，用于累計當前該人工蟻所付出的尋優代價。協同蟻群優化算法的尋優過程可具體描述如下：

步驟1按照表1初始化M個蟻群，其中，每個蟻群中包含P個人工蟻，ai,j表示蟻群i中的第j個人工蟻，i=1,2,…,M，j=1,2,…,P. 每個人工蟻均擁有一個許可表和一個代價表，例如，Ai,j和Ci,j分別為人工蟻ai,j的許可表和代價表。Tj為M個蟻群中的人工蟻{a1,j,a2,j,…,aM,j}所共同擁有的共享禁忌表。最大迭代次數設為S，當前迭代次數設為s=1.

步驟2清空所有的共享禁忌表Tj和代價表Ci, j，將所有節點置入每個人工蟻ai, j的許可表Ai, j中。

步驟3每個蟻群的人工蟻均放置在對應巡檢機器人的初始節點上，即第j個蟻群的人工蟻均放置在第j個機器人的初始節點上。

步驟4將全部機器人初始節點從每個Ai, j中移出，并置入Tj中。

步驟5在各節點間的路線上初始化信息素濃度為隨機小數據。

步驟6將表1中的每行人工蟻組成一個協同尋優小組，例如，第j行的人工蟻{a1,j,a2,j,…,aM,j}組成第j個協同尋優小組，該小組尋優過程如下：

從表2中可以看出，隨著磨礦細度的增加，無論是一段選別還是二段選別，精礦品位均逐漸增加，弱磁選與強磁選的鐵綜合回收率僅略有下降。根據生產指標要求，精礦鐵品位必須達到62%以上，因此，綜合考慮選擇一段磨礦細度-0.07 4 mm占72.96%，二段磨礦細度-0.045 mm占74.58%。此時試驗綜合指標為：精礦產率51.41%、鐵品位62.61%、回收率88.12%，尾礦鐵品位8.92%。

1)每個人工蟻ai,j將當前所在節點置入代價表Ci, j中。

2)計算每個人工蟻ai, j的代價表Ci, j中的當前代價值ci, j，并求得具有當前最小代價值ck, j=min{ci,j,i=1,2,…,M}的人工蟻ak, j，ak,j為第j個協同尋優小組中的第k個人工蟻，其當前代價值最小。其中，代價值ci, j的計算方法為

(3)

式中：Li,j為代價表Ci, j中所存儲節點的路線長度。

3)設具有最小代價的人工蟻ak, j當前位于節點h，則t時刻從節點h向節點l的轉移概率ph, l為

(4)

式中：α和β為作用強度參數；τh,l為節點h與節點l之間的信息素濃度；τh,q為節點h與節點q之間的信息素濃度；ηh,l為節點h與節點l之間的啟發式信息；ηh,q為節點h與節點q之間的啟發式信息，

(5)

dh,l為節點h與節點l之間的距離。

4)將人工蟻ak, j移至按照轉移概率選中的新節點上，并將該節點從許可表Ai, j中移出，加入到代價表Ci, j和共享禁忌表Tj中。

5)若禁忌表Tj中包含了全部節點，則第j行的人工蟻所組成的協同尋優小組完成本次優化；否則返回2繼續優化，直到所有節點全部置入共享禁忌表Tj中。

步驟7若所有尋優小組完成尋優任務，則更新全部路線上的信息素濃度：

τh,l(t)=(1-ρ)τh,l(t)+Δτh,l，

(6)

式中：ρ為揮發系數；Δτh, l為節點h與節點l之間路線上的信息素增量，

(7)

(8)

Li,j為人工蟻ai,j當前尋優路線長度，Q為一個正常數。

步驟8s=s+1，如果迭代次數達到最大迭代次數，即s=S，則結束優化，否則返回步驟2繼續下一次優化。

傳統蟻群算法中，每只人工蟻按照預定規則獨立完成巡檢路線的優化搜索，人工蟻之間缺少有效的協同機制，無法求解多機器人協同巡檢的路線優化問題。改進蟻群算法中設置了共享禁忌表，為不同蟻群之間的人工蟻提供了信息共享機制，可實現不同蟻群之間的信息傳遞。而且，算法中引入了代價競爭機制，即同一優化小組中，當前優化代價最小的人工蟻優先獲得路線搜索權，由此建立了蟻群之間的協同合作機制，因此協同蟻群優化算法可應用于多機器人協同巡檢的路線優化問題求解。

2 仿真實驗

為驗證協同蟻群優化方法的有效性，將其應用于多機器人協同巡檢的路線優化問題求解中。采用TSP數據集作為巡檢測試數據，TSP公開數據集的網址為：http:∥elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html，設巡檢機器人數量為4. 由于多機器人巡檢問題的復雜性，當機器人初始位置不同時，優化結果也不同。這里設定機器人的初始位置分別位于地圖的4個角，并假設各機器人的移動速度相同，均為1 m/s. 分別針對eil51、eil76、kroa100、krob150和kroa200共5組數據進行系統巡檢路線優化，圖1～圖5分別給出了采用協同蟻群優化方法和基于地圖分割的蟻群優化算法求得的巡檢路線優化結果。

圖1 eil51路線尋優結果Fig.1 Optimized results of eil51 route

圖2 eil76路線尋優結果Fig.2 Optimized results of eil76 route

從實驗結果可見，由于蟻群算法具有較好的全局尋優能力，基于地圖分割的方法能夠根據給定區域內巡檢節點的分布情況確定出合理的巡檢路線。但地圖分割的合理性對于整體尋優性能影響很大，由于節點數量眾多，造成巡檢問題較為復雜，因此很難確定出最佳的地圖分割方案。而本文協同蟻群優化算法在路線優化過程中逐漸確定出各巡檢機器人的巡檢區域，也就是巡檢區域的劃分過程包含在路線優化過程內，因此能夠根據巡檢節點的整體分布給出符合全局優化的最佳巡檢方案，以此提高巡檢效率。

表2給出了上述巡檢結果的具體路線數值。表2中，4個蟻群分別為4個機器人進行路線尋優，所得路線最長的蟻群所對應的巡檢時間為最終巡檢任務所需時間。從實驗結果可見，上述5個協同優化問題中，基于協同蟻群優化算法的最終巡檢時間均優于基于地圖分割的蟻群優化算法所得巡檢時間。

尋優性能具體分析如表3所示。由表3可見，隨著巡檢節點數量的增加，協同蟻群優化算法的耗時明顯小于基于地圖分割的蟻群優化算法，因此巡檢效率也可得到明顯提升。兩種方法所得機器人的耗時均值相差并不大，但與基于地圖分割的蟻群優化算法相比，協同蟻群優化算法所得各機器人耗時的標準差明顯變小，最大空閑時間也明顯變小，說明各機器人所承擔的巡檢任務量較為均衡。另外，協同蟻群優化算法中機器人耗時均值均略小于基于地圖分割的蟻群優化算法，也說明協同蟻群優化算法能夠通過合理劃分巡檢區域，獲得更優的巡檢方案來減少協同巡檢總體任務量，從而進一步提高全局巡檢優化性能。

圖3 kroa100路線尋優結果Fig.3 Optimized results of kroa100 route

圖5 kroa200路線尋優結果Fig.5 Optimized results of kroa200 route

表4給出了巡檢機器人平均利用率及最大閑置率的性能指標。由表4可見，與基于地圖分割的蟻群優化算法相比，協同蟻群優化算法中機器人的平均利用率得到了明顯提高，最大閑置率則明顯降低，進一步說明各機器人能夠得到充分利用，有效提高了整體巡檢效率。

表4 巡檢機器人利用率

3 結論

針對多機器人協同巡檢問題，本文提出了改進的協同蟻群優化算法，將巡檢區域的劃分過程包含在路線優化過程中，從而能夠為機器人進行合理的巡檢區域劃分，由此提高了全局巡檢效率。實驗結果表明，對于大規模巡檢優化問題，協同蟻群優化算法能夠給出更加合理的巡檢方案，從而可有效提升系統的整體巡檢效率。與基于地圖分割的蟻群優化算法相比，整體巡檢量有所下降，機器人空閑時間縮短，利用率得到提高，巡檢效率得到提升。