基于魚群算法的智能機器人全覆蓋路徑規(guī)劃

鄧 紅，孫 栩

(黑龍江工程學(xué)院，哈爾濱 150050)

0 引言

隨著社會的發(fā)展，人們對生活品質(zhì)的需求也在不斷增高，對于環(huán)境也有了更高的清潔度需求。因此移動智能掃地機器人被研究出來，成為了清掃工作的代替者[1]。為保證道路上所有區(qū)域的干凈整潔，需要保證智能機器人可以做到全方位的路徑覆蓋，且在同樣的區(qū)域內(nèi)，行走路徑需要盡量減少，路徑重復(fù)率盡量降低[2-3]。

在現(xiàn)有的研究中，文獻[4]為獲取肉眼不可見區(qū)域的圖像信息，設(shè)計了一種針對圖像監(jiān)測的路徑規(guī)劃算法。該方法可以基于生物啟發(fā)神經(jīng)網(wǎng)絡(luò)模型，將結(jié)果直接指向活性增益趨勢，并獲取連續(xù)的圖像信息。對比原有的算法，該路徑規(guī)劃方法的準(zhǔn)確率和效率均有一定程度的提高。但是，該方法路徑規(guī)劃重復(fù)率有待驗證。文獻[5]使用無人機技術(shù)，在凸劃分優(yōu)化方法的基礎(chǔ)上，提出了一種針對復(fù)雜障礙物的路徑規(guī)劃方法，該方法可以準(zhǔn)確繪制復(fù)雜地塊的邊界輪廓，標(biāo)記凹凸點信息，并在隨機路標(biāo)算法的基礎(chǔ)上，尋找最短路徑。但是，該方法在計算算力方面有待進一步提高。文獻[6]提出了一種基于高校模版與動態(tài)窗口法的路徑規(guī)劃算法，結(jié)合全局路徑與位置的障礙物，在窗口柵格地圖中，對路徑的覆蓋率進行規(guī)劃分析。實驗結(jié)果顯示，該算法可以提高機器人在全覆蓋路徑中的工作效率和工作精度，具備較高的使用價值。但是，該方法在復(fù)雜環(huán)境下的路徑覆蓋率需要提升。

魚群算法是一種根據(jù)魚群覓食行為完成最優(yōu)數(shù)值計算的方式，使聚集區(qū)域內(nèi)魚群數(shù)目達到特定比例，其具有實現(xiàn)簡單、魯棒性強、使用靈活等優(yōu)點，且對初值要求不高，對參數(shù)選擇不敏感，只需獲取其目標(biāo)函數(shù)值即可[7]。通過魚群算法執(zhí)行追尾和聚群行為，降低遍歷重疊度，減少路徑冗余，在確保高收斂效率的基礎(chǔ)上降低時延，提升復(fù)雜環(huán)境下的路徑規(guī)劃精準(zhǔn)度，實現(xiàn)數(shù)值處理和智能規(guī)劃的高覆蓋、低重復(fù)、強算力?；诖?，結(jié)合上述文獻資料，本文基于魚群算法設(shè)計了一種智能機器人全覆蓋路徑規(guī)劃方法。根據(jù)機器人位姿關(guān)系計算目標(biāo)區(qū)域旋轉(zhuǎn)角，構(gòu)建智能機器人死區(qū)脫困模型，描述柵格周邊狀態(tài)，獲取未被覆蓋的柵格區(qū)域。在描述不同目標(biāo)魚個體之間距離的基礎(chǔ)上，依托三維坐標(biāo)系獲取移動目標(biāo)元素的坐標(biāo)向量，求解目標(biāo)點代價完成全路徑覆蓋的判定。運用魚群算法判斷機器人當(dāng)前位置是否為死區(qū)，獲取路徑規(guī)劃的全局最優(yōu)解，實現(xiàn)智能機器人的全覆蓋路徑規(guī)劃。在保證100%覆蓋率的基礎(chǔ)上，進一步優(yōu)化機器人路徑的重復(fù)率和路徑長度，以期提升機器人對復(fù)雜環(huán)境的適應(yīng)性。

1 建立智能機器人死區(qū)脫困模型

在選擇智能機器人的目標(biāo)軌跡時，需要以活性值作為依據(jù)。每一個神經(jīng)元均存在感知域的響應(yīng)機制，因此可以結(jié)合智能機器人周邊的活性值獲取位姿關(guān)系[8-9]。在柵格地圖下，其自身的活性可以表示為：

(1)

式中，p(x，y)表示某目標(biāo)點的活性值；km表示目標(biāo)點與障礙物的覆蓋狀態(tài)，當(dāng)km=0時表示未覆蓋，當(dāng)km=1時表示已覆蓋；fd表示目標(biāo)點是否已經(jīng)被疊加，當(dāng)fd=1時表示已被疊加，當(dāng)fd=0時表示未被疊加[10]。在自身的活性影響范圍之外，還存在運動方向?qū)πD(zhuǎn)角度的影響，因此可以規(guī)定機器人在目標(biāo)區(qū)域的旋轉(zhuǎn)角度：

(2)

式中，h(x，y)表示智能機器人的旋轉(zhuǎn)角度對活性值影響；dj表示旋轉(zhuǎn)角度。通過上述兩個公式，可以對正常路線下以及前方出現(xiàn)障礙物情況下的智能機器人行走進行規(guī)劃與分析[11-12]。但是很多時候，如果障礙物較為密集，智能機器人很容易走入死區(qū)。通常將智能機器人周邊沒有未被覆蓋柵格的情況成為機器人陷入死區(qū)。死區(qū)與未被覆蓋區(qū)域的距離越遠，逃離死去的路徑就越長，智能機器人在全覆蓋路徑規(guī)劃過程中陷入死區(qū)的次數(shù)越多，其覆蓋重復(fù)率就越高。此時需要對整體地圖環(huán)境下的柵格數(shù)量進行計算：

(3)

式中，Nk表示該地圖環(huán)境的柵格總數(shù)；sd表示單位柵格的長度；Lh和Wh則分別表示該柵格地圖模型的長與寬、同時使用函數(shù)描述柵格地圖的狀態(tài)：

(4)

式中，Wsta表示某一柵格周邊所擁有的未被覆蓋區(qū)域的數(shù)量[13]；uij表示未被覆蓋柵格數(shù)量，在該狀態(tài)函數(shù)中，uij={0，1，2，3，4}，即表示單一柵格周邊可以有0～4個未被標(biāo)記的柵格。

當(dāng)智能機器人在某一活柵格中被逐漸引導(dǎo)到死區(qū)時，其想要脫困時的行駛角度差可以表示為：

(5)

式中，Δβdead表示智能機器人行走在死區(qū)時的角度差；β則表示方向引導(dǎo)角度[14-15]。通過該角度公式，可以得知智能機器人脫離死區(qū)的方法，只要朝著這個方向一直前進，就能夠以最短的距離進入未被覆蓋的柵格區(qū)域。

2 基于魚群算法的全路徑覆蓋判定

在該路徑規(guī)劃方法中，除盡快促進智能機器人脫離死區(qū)以外，還需要保證機器人的路徑覆蓋率達到100%，以實現(xiàn)全路徑覆蓋。制定需要一個判定機制，避免機器人在未完全覆蓋所有路徑時即停止運行[16]。在這個搜索空間中，可以假設(shè)存在一個人工魚群，該魚群內(nèi)包含N個個體，則可以對不同魚之間的距離進行描述：

(6)

式中，dij表示第i條魚和第j條魚之間的距離；Ni和Nj則分別表示兩條魚的感知范圍[17]。當(dāng)某條魚的當(dāng)前狀態(tài)良好且未達到完全覆蓋狀態(tài)，則其在單位時間內(nèi)的三維坐標(biāo)系如圖1所示。

圖1 移動目標(biāo)坐標(biāo)系

結(jié)合圖1中的目標(biāo)點坐標(biāo)系，可以直接確定智能機器人在全局坐標(biāo)中的位姿，將本體與局部坐標(biāo)系聯(lián)合在儀器，就可以獲取一個元素坐標(biāo)向量：

(7)

式中，Gt表示元素坐標(biāo)向量；xi和yi分別表示該智能機器人到達的預(yù)期目標(biāo)點；ti則表示機器人轉(zhuǎn)換位姿的時間參數(shù)[18]。由此可以建立每個目標(biāo)點的求解代價和：

g(x，y)=k(x，y)Δβdead+d(x，y)Δβdead

(8)

式中，g(x，y)表示起點到當(dāng)前點的總代價；k(x，y)表示實際代價；d(x，y)表示預(yù)估代價。根據(jù)運動特性，可以獲取機器人向下一個目標(biāo)點行駛的最小距離：

(9)

式中，Dmn表示智能機器人向下一個目標(biāo)點行駛的最小距離，當(dāng)Dmn等于1時，表示該目標(biāo)點周邊有可用柵格，當(dāng)Dmn大于1時，表示該目標(biāo)點已進入死區(qū)，需要立即脫離，當(dāng)Dmn=0時，表示該地圖上已經(jīng)沒有為覆蓋柵格，即路徑已經(jīng)實現(xiàn)了全覆蓋[19]。vu表示行駛速度；ap表示機器人在目標(biāo)區(qū)域行駛的最小距離。通過上述公式，可以獲取全路徑覆蓋的判定依據(jù)。

3 設(shè)計機器人全覆蓋路徑規(guī)劃算法

根據(jù)采集到的全路徑覆蓋判定依據(jù)信息，劃定機器人搜索空間。將搜索空間設(shè)定為W維度，人工魚的尋優(yōu)變量為a[20]，人工魚個體之間的距離矢量為Ds=(ds1，ds2， ，dsw， ，dsW)，魚群移動速度矢量為Fs=(fs1，fs2， ，fsw)。當(dāng)人工魚當(dāng)前狀態(tài)為Gs=(gs1，gs2， ，gsw， ，gsW)時，魚種群則開始快速移動，并向食物中心聚集[21]。當(dāng)前人工魚最優(yōu)位置矢量為Gu=(gu1，gu2， ，guw， ，guW)，并且每個人工魚個體根據(jù)公式(10)更新覓食位置：

fsw=φfsw+φ1γ1(gsw-dsw)+φ2γ2(guw-dsw)

(10)

式中，φ表示慣性因素；φ1和φ2表示學(xué)習(xí)因素；隨機的[0，1]用γ1和γ2表示。通過不斷更新隨機位置和速度，尋找覓食最優(yōu)解。

(11)

圖2 算法流程

在該算法內(nèi)，首先需要隨機一個位置節(jié)點，即初始節(jié)點，并建立兩個不同的子群體，分別為已覆蓋群體和未覆蓋群體，對數(shù)據(jù)進行初始化處理。判斷此時的位置是否為死區(qū)，如果是死區(qū)，則需要重新隨機位置節(jié)點，如果不是死區(qū)，則使用魚群算法進行群體行為的執(zhí)行過程[24]。判斷此時的路徑規(guī)劃是否為局部最優(yōu)：

(12)

式中，Xi表示當(dāng)前的路徑規(guī)劃函數(shù)；Xp表示算法前期的更新位置[25]；Rand()表示周邊未覆蓋節(jié)點數(shù)；Xg表示搜索空間中極值點數(shù)量[26]。根據(jù)該方法，同步更新網(wǎng)絡(luò)信息，并判斷是否達到全局最優(yōu)。對魚群進行操作后，即可得到路徑全覆蓋規(guī)劃的最優(yōu)解，實現(xiàn)智能機器人全覆蓋路徑規(guī)劃。

4 實驗研究

4.1 實驗環(huán)境設(shè)置

選擇Roborock S7 MaxV Ultra型清潔機器人在40 m×60 m的空間內(nèi)完成全覆蓋路徑規(guī)劃實驗。清潔機器人導(dǎo)航技術(shù)為激光導(dǎo)航，避障類型為結(jié)構(gòu)光避障，續(xù)航時間為180 min。在Matlab R2022a的環(huán)境下，使用Matlab代碼編寫算法在主頻為1的環(huán)境下完成機器人全覆蓋路徑規(guī)劃仿真。

實時仿真過程包括七個步驟，具體如下。

步驟1：在simulink環(huán)境中，采用C++編程環(huán)境多樣化，編譯機器人軌跡法自動調(diào)節(jié)補償器參數(shù)，并且同時指定干擾參考跟蹤、穩(wěn)定裕度等多個調(diào)節(jié)目標(biāo)。

步驟2：對機器人系統(tǒng)進行高度細化建模，設(shè)計高級自主性和低級控制度量，連接ROS系統(tǒng)。

步驟3：根據(jù)建立的柵格地圖模型，使用MATLAB Coder對經(jīng)過維護的算法庫進行代碼自動生成及控制。

步驟4：采用Simulink Coder設(shè)定機器人傳感器(激光雷達、慣性姿態(tài)傳感IMU、攝像頭)數(shù)據(jù)，優(yōu)化機器人的外部物理環(huán)境感知效果。

步驟5：將ROS系統(tǒng)直接連接到傳感器，完成實驗對象的檢測跟蹤。利用RoboticsSystem Toolbox對傳感器提取的信息進行校準(zhǔn)、降噪等操作，完成特征提取和算法匹配等。

步驟6：通過Embedded coder對機器人進行最終執(zhí)行和決策功能設(shè)定，生成嵌入式代碼實現(xiàn)端到端的機器人控制策略。

步驟7：進行實時仿真證明。

4.2 實驗設(shè)備

為測試上文中魚群算法下智能機器人全覆蓋路徑規(guī)劃的性能，搭建實驗平臺。在linux系統(tǒng)下，根據(jù)各自的功能，實現(xiàn)話題和服務(wù)之間的信息傳遞。硬件部分使用Core-i5 5200U作為工控機，該工控機可以被網(wǎng)絡(luò)遠程控制，有一個對外接口，體積小，性能高，且支持windows平臺。軟件平臺則包括全覆蓋路徑規(guī)劃與點線之間的運動規(guī)劃兩個方面，在接受目標(biāo)點信息的基礎(chǔ)上，實現(xiàn)數(shù)據(jù)控制。測試過程中的硬件環(huán)境，軟件環(huán)境，軟件工具如表1所示。

表1 硬件、軟件參數(shù)詳情表

4.3 實驗準(zhǔn)備

具體的實驗參數(shù)設(shè)置為：選擇機器人定位避障的建圖數(shù)據(jù)作為實驗數(shù)據(jù)，設(shè)定機器人的線速度為0.2 m/s，角速度為0.3 rad/s，視場角為280°，角度分辨率為0.5°，最大響應(yīng)時間為1 s。在此條件下整合測試方案，驗證實驗可行性，實驗測試流程如圖3所示。

圖3 實驗流程圖

4.4 實驗工況

4.4.1 簡單環(huán)境下的全覆蓋路徑規(guī)劃

在該路徑規(guī)劃實驗中，簡單環(huán)境路徑效果如圖4所示。

圖4 路徑示意圖

如圖4所示，對該路徑圖進行預(yù)處理，圖(a)中的方格為遮擋物體，曲線則為不可到達區(qū)域的邊界，在柵格規(guī)劃效果圖中，將不可到達區(qū)域與遮擋部位剔除，就可以得到智能機器人全覆蓋路徑效果圖，其中黑色部位為不可達區(qū)域，白色部分為可達區(qū)域。在計算機上進行仿真，在障礙物之間，柵格活性函數(shù)值為0.6，每一個方格為一步。

如圖5所示，在簡單環(huán)境的全覆蓋路徑探索中，機器人從一個端口進入，采用單一變量控制的原則，將所有白色區(qū)域全部覆蓋。

圖5 簡單環(huán)境路徑覆蓋

4.4.2 復(fù)雜環(huán)境下的全覆蓋路徑規(guī)劃

在該路徑規(guī)劃實驗中，復(fù)雜環(huán)境路徑效果如圖6所示。

圖6 路徑示意圖

圖6為復(fù)雜路徑下的規(guī)劃效果與柵格示意圖，對比簡單路徑，該復(fù)雜路徑內(nèi)的障礙物為非規(guī)范圖形。因此智能機器人行走在該路徑中，會遇到更多的死角，其重復(fù)率和全面覆蓋所需要行走的路徑長度也會進一步增加。

如圖7所示，在復(fù)雜環(huán)境的路徑覆蓋規(guī)劃中，智能機器人從左上角出發(fā)，在右下角離開，并多次遇到大幅度的重復(fù)行走情況。相比起簡單環(huán)境，復(fù)雜環(huán)境雖然同樣可以實現(xiàn)全方位覆蓋，但其所經(jīng)歷過的重復(fù)路徑有了明顯的增加。

圖7 復(fù)雜環(huán)境路徑覆蓋

4.5 實驗結(jié)果與分析

為了驗證所提方法(基于魚群算法的智能機器人全覆蓋路徑規(guī)劃)的整體有效性，需要對其展開測試。以文獻[4]方法(基于生物啟發(fā)神經(jīng)網(wǎng)絡(luò)的水下壩面表觀裂縫檢測路徑規(guī)劃算法)、文獻[5]方法(基于復(fù)雜地塊凸劃分優(yōu)化的多無人機覆蓋路徑規(guī)劃)、文獻[6]方法(基于高效模板法與動態(tài)窗口法的服務(wù)機器人全覆蓋路徑規(guī)劃方法)作為對比方法，進行機器人全覆蓋路徑規(guī)劃仿真測試。分別計算簡單環(huán)境和復(fù)雜環(huán)境的路徑覆蓋率、路徑重復(fù)率、路徑長度，獲取不同算法下的路徑規(guī)劃對比結(jié)果。

4.5.1 路徑規(guī)劃覆蓋率對比分析

機器人路徑規(guī)劃覆蓋效果越優(yōu)，說明機器人復(fù)雜環(huán)境下的運行能力越穩(wěn)定。若機器人在簡單環(huán)境和復(fù)雜環(huán)境下的路徑規(guī)劃覆蓋率較高，則對應(yīng)方法的機器人控制精度越優(yōu)。路徑遍歷范圍越廣，則表明路徑規(guī)劃覆蓋率越高，測試結(jié)果如圖8所示。

圖8 路徑規(guī)劃覆蓋率結(jié)果

根據(jù)圖8可知，所提方法、文獻[4]方法、文獻[5]方法、文獻[6]方法均不存在機器人路徑規(guī)劃異常值，所有方法都可以完成簡單環(huán)境和復(fù)雜環(huán)境下的路徑遍歷。所提方法在簡單環(huán)境和復(fù)雜環(huán)境下的路徑覆蓋與規(guī)劃一致，覆蓋率為100%，由此證明所提方法可以完成復(fù)雜環(huán)境下全方位覆蓋。而文獻[4]方法、文獻[5]方法、文獻[6]方法在簡單環(huán)境和復(fù)雜環(huán)境的路徑規(guī)劃遍歷不全，無法實現(xiàn)全方位覆蓋。這是因為所提方法構(gòu)建了智能機器人死區(qū)脫困模型，通過計算柵格地圖模型中的目標(biāo)活性值可以優(yōu)化整體柵格參數(shù)，提高描述地圖中柵格狀態(tài)穩(wěn)定性，進而提高了機器人全覆蓋路徑規(guī)劃覆蓋率。

4.5.2 路徑規(guī)劃重復(fù)率對比分析

在發(fā)布數(shù)據(jù)頻率為30 kN、分辨率為0.015%，加速度為0.8的條件下，獲取路徑規(guī)劃重復(fù)率結(jié)果，判別簡單環(huán)境和復(fù)雜環(huán)境下的路徑規(guī)劃效果，具體測試結(jié)果如圖9所示。

圖9 路徑規(guī)劃重復(fù)率結(jié)果

根據(jù)圖9可知，由于所提方法描述不同目標(biāo)魚個體之間的距離，在三重移動目標(biāo)坐標(biāo)系下獲取元素坐標(biāo)向量，進而降低了路徑規(guī)劃重復(fù)率。因此，在機器人路徑規(guī)劃重復(fù)率測試過程中，所提方法在簡單環(huán)境下的路徑重復(fù)率為5.23%，復(fù)雜環(huán)境下的路徑重復(fù)率為10.24%。而文獻[4]方法在簡單環(huán)境下的路徑重復(fù)率為6.99%，復(fù)雜環(huán)境下的路徑重復(fù)率為15.01%。文獻[5]方法在簡單環(huán)境下的路徑重復(fù)率為8.01%，復(fù)雜環(huán)境下的路徑重復(fù)率為22.05%。文獻[6]方法在簡單環(huán)境下的路徑重復(fù)率為8.91%，復(fù)雜環(huán)境下的路徑重復(fù)率為18.27%。由此表明，所提方法具有更強的實時性，更適合用于復(fù)雜環(huán)境下的智能機器人全覆蓋路徑規(guī)劃。

4.5.3 路徑規(guī)劃長度對比分析

在數(shù)據(jù)變化趨勢提升的環(huán)境下，路徑規(guī)劃干擾強度會呈現(xiàn)倍增趨勢，在機器人路徑規(guī)劃過程中規(guī)劃長度可以反映方法的優(yōu)劣性。在客觀環(huán)境一致的條件下，路徑規(guī)劃長度越小則方法效果越優(yōu)。在一階固有頻率下進行測試分析，結(jié)果如表2所示。

表2 不同方法路徑規(guī)劃長度結(jié)果

根據(jù)表2可知，所提方法的路徑長度在簡單環(huán)境與復(fù)雜環(huán)境下均小于文獻[4]方法、文獻[5]方法、文獻[6]方法。這是因為所提方法利用魚群算法判斷當(dāng)前位置是否為死區(qū)，完成路徑規(guī)劃全局最優(yōu)解，以此提高了算法的計算算力，縮短路徑規(guī)劃長度。實現(xiàn)智能機器人的全覆蓋路徑規(guī)劃。由此表明，所提方法在機器人全覆蓋路徑規(guī)劃中性能最優(yōu)。

5 結(jié)束語

本文設(shè)計了一種基于魚群算法的智能機器人全覆蓋路徑規(guī)劃方法，該方法可以獲取脫離死區(qū)的最快方法，并結(jié)合全覆蓋的判定機制，設(shè)計相應(yīng)算法優(yōu)化路徑最優(yōu)解，完成路徑規(guī)劃。實驗結(jié)果顯示，該路徑規(guī)劃算法在簡單環(huán)境與復(fù)雜環(huán)境下均可以實現(xiàn)全覆蓋路徑規(guī)劃，且路徑重復(fù)率較低，路徑長度較短。但是由于研究時間和研究條件的有限，本文僅選擇了一種清潔機器人作為測試對象，且在研究過程中未考慮計算的延遲。因此，下一步的研究方向為：在本次研究內(nèi)容的基礎(chǔ)上，引入多類型機器人操作設(shè)備完成路徑規(guī)劃任務(wù)，并在全覆蓋判定過程中加入時延矩陣，進一步優(yōu)化模型計算算力。以獲取的數(shù)據(jù)結(jié)果為依據(jù)，從多方面驗證路徑規(guī)劃效果。