機器人導航的自主選擇搜索策略蜂群規劃算法

王明超

（無錫工藝職業技術學院，江蘇 宜興 214200）

1 引言

當前機器人不僅應用領域越來越廣，而且相關的智能技術研究也越來越深，使機器人在人類生產和生活種日益重要。機器人導航技術是移動機器人一切工作的基礎，決定了機器人的安全和效率[1]。因此研究機器人智能導航問題具有明顯的安全意義和經濟意義。

導航技術分為目標定位、路徑規劃、環境建模等3 個子技術，研究導航路徑智能規劃問題。按照導航路徑規劃方法出現時間劃分，可以將路徑規劃分為傳統路徑規劃方法和智能算法規劃方法。傳統路徑規劃方法包括柵格法[2]、拓撲法[3]、可視圖法[4]、人工勢場法[5]等，其共同特點是使用簡單的幾何數學模型完成路徑規劃。智能算法規劃方法包括基于遺傳算法規劃方法、基于蟻群算法規劃方法、基于神經網絡規劃方法、基于粒子群算法規劃等，此類方法共同特點是將路徑規劃問題轉化為優化問題，使用智能仿生算法進行優化。文獻[6]改進了蟻群算法的轉移概率和信息素更新策略，提出了機器人路徑的自適應蟻群算法規劃策略，降低了工作路徑長度；文獻[7]使用萊維飛行優化粒子群算法，優化了焊接機器人工作路徑；文獻[8]建立了多個優化目標，分別為焊接質量函數、機器人運動平穩性函數、雙機器人碰撞函數，使用多目標遺傳算法進行求解，獲得了雙機器人協調焊接路徑?？傊?，機器人導航智能化程度越來越高，正朝著多傳感器融合、多算法融合、多機器人分工協作等方向發展。

為了提高機器人導航路徑的質量和規劃速度，提出了自主選擇搜索策略蜂群算法的規劃方法。通過坐標旋轉法將二維規劃問題轉化為一維，使用自主選擇搜索策略蜂群算法搜索最優路徑點，達到了減少路徑長度和提高規劃速度的目的。

2 自主選擇搜索策略蜂群算法

2.1 人工蜂群算法

人工蜂群算法將蜜蜂分為三類，分別為引領蜂、觀察蜂和偵查蜂，不同蜜蜂使用不同的蜜源搜索方式，通過分工協作發揮群體智能實現最優蜜源搜索。

（1）蜜蜂位置初始化。蜂群規模記為N，生存維度記為D，蜂群以隨機的方式進行位置初始化，為：

（2）引領蜂蜜源搜索策略。引領蜂使用交叉方式搜索蜜源，對于蜜蜂i，隨機選擇另一個體k≠i，則引領蜂蜜源搜索公式為：

（3）觀察蜂蜜源搜索策略。引領蜂通過搖擺舞將蜜源濃度信息傳遞給觀察蜂，觀察蜂依據蜜源濃度選擇觀察蜂，即：

式中：pi—引領蜂的被選概率；NB—引領蜂數量；fiti—第i 只引領蜂所在位置蜜源濃度。分析式（3）可知，引領蜂所在位置蜜源濃度越高則被選概率越大，保證了較優蜜源附近區域的細致搜索。觀察蜂選擇引領蜂后，與引領蜂一起進行小范圍細致搜索，蜜源搜索方式與引領蜂完全一致。

（4）偵查蜂蜜源搜索策略。當引領蜂或觀察蜂在某一蜜源附近搜索次數達到設定次數且蜜源濃度沒有明顯提高時，則蜜蜂放棄此處蜜源同時轉化為偵查蜂，在搜索區域內進行大范圍隨機搜索，即：

2.2 多方式搜索策略

進化論表明蜂群中蜜蜂的搜索行為受環境因素的影響，不同環境對應的搜索行為也不一致。蜜蜂對環境的認知信息有多種來源，包括個體自身認知信息、群體最佳個體的認知信息、種群平均認知信息和其他個體認知信息等，多種認知信息來源對應多種方式的蜜源搜索策略。在此需要強調的是，此多種方式的蜜源搜索策略適用于引領蜂或觀察蜂，偵查蜂的蜜源搜索方式保持不變。

（1）基于自身認知、最佳個體認知、其他個體認知的蜜源搜索方式。此方法參考粒子群算法中的信息獲取方式，種群中蜜蜂參考自身對環境的認知、種群中最優認知和其他個體的認知，綜合形成自身的蜜源搜索方式，為：

（2）基于群體平均認知的蜜源搜索方式。如同人類社會中的“從眾”心理，種群中的個體也具有一定的趨同性，也即蜜蜂的搜索行為受種群共同認知的影響。使用所有蜜蜂的位置質心表示種群平均認知，則基于種群平均認知的搜索方式為：

式中：pj—第j 維的質心。

（3）基于其他個體認知的蜜源搜索方式。這種隨機選取個體獲取認知信息的方式類似于遺傳算法中的個體變異，此種信息獲取方式與混沌理論相比更具有方向性，對應的蜜源搜索方式為：

式中：r1≠r2≠r3—隨機選擇的三個不同個體。

2.3 搜索策略自主選擇方法

2.2 節給出了3 種環境認知方式和相應的蜜源搜索方式，加上式（2）給出的原算法搜索方式，共有4 種蜜源搜索方式供引領蜂和觀察蜂選擇。在此提出不同蜜源搜索方法的即時價值和后效價值，通過即時價值和后效價值計算不同蜜源選擇策略的選擇概率，實現蜜蜂對搜索策略的自主選擇。

（1）不同蜜源搜索策略的即時價值。后文中將此算法應用于機器人導航路徑規劃，因此將目標函數f（x，t）定義為路徑長度，則蜜蜂i 對應的目標函數f（xi，t）越小說明蜜蜂i 越優。蜜源搜索策略的即時價值定義為迭代一次后目標函數的減小程度，即：

式中：Valik（t）—粒子i 選擇蜜源搜索策略k 迭代后的即時價值；f（xi，t-1）—粒子i 迭代t-1 次時的目標函數值；fk（xi，t）—粒子i 選擇搜索策略k 迭代t 次時的目標函數值。當Valik（t）＞0 時說明選擇搜索策略k 迭代一次后蜜源濃度有所提高，當Valik（t）=0 時說明選擇搜索策略k 迭代一次后蜜源濃度沒有提高。

（2）不同蜜源搜索策略的后效價值。信心上界算法[9]在計算機棋盤程序中用于計算不同落子點的未來價值，在圍棋程序中取得了很好的效果。參考這一思想，使用信息上界算法計算蜜源選擇策略的后效價值，為：

（3）搜索策略自主選擇方法。首先使用不同搜索策略的即時價值、后效價值和歷史經驗計算搜索策略的得分，而后根據得分構造不同搜索策略的選擇概率。使用即時價值、后效價值和歷史經驗構造搜索策略的得分，為：

蜜蜂i 根據式（11）計算不同搜索策略的選擇概率，并最終選擇概率最大的搜索策略為下一次迭代的搜索策略，從而在迭代時獲得最佳的即時價值和后效價值。通過以上方式，蜜蜂完成了對搜索策略的自主選擇。

2.4 自主選擇搜索策略蜂群算法流程

根據人工蜂群算法原理和多方式蜜源搜索自主選擇策略，制定自主選擇搜索策略蜂群算法流程為：

（1）初始化人工蜂群算法參數和蜜蜂初始位置；

（2）根據蜜蜂位置對應的目標函數值，將蜜蜂區分為引領蜂和觀察蜂；

（3）引領蜂和觀察蜂計算使用不同蜜源搜索策略的即時價值、后效價值和選擇概率；

（4）引領蜂和觀察蜂自主選擇概率最大的蜜源搜索策略更新位置，若新位置蜜源優于原位置則選擇新蜜源，否則選擇舊蜜源；

（5）引領蜂和觀察蜂是否滿足轉化為偵查蜂的條件？若滿足則轉化為偵查蜂，按照式（4）進行搜索；若不滿足則繼續按照多搜索策略進行搜索；

（6）算法是否達到最大迭代次數？若是則結束；若否則轉至（3）。

2.5 算法性能測試

為了驗證自主選擇搜索策略蜂群算法的搜索性能，選擇具有代表性的3 個測試函數，如表1 所示。3 個測試函數的空間維度均設置為n=30。分別使用自主選擇搜索策略蜂群算法（Choose Searching Strategy Independently Bee Colony Algorithm，CSSIBC）、人工蜂群算法（Artificial Bee Colony Algorithm，ABC）、改進人工蜂群算法[10]（Modified Artificial Bee Colony Algorithm，MABC）對測試函數進行尋優。

表1 測試函數Tab.1 Testing Function

性能測試的實驗環境為：Windows 7 操作系統，Intel 酷睿i5處理器，2.5Hz 主頻，4G 內存，仿真軟件為Matlab R2014a。算法參數設置為：種群規模N=30、迭代次數itermax=1000、個體未來價值和全局未來價值的平衡系數α=0.5；改進人工蜂群算法參數設置參照文獻[10]。每種算法對3 個測試函數獨立運行10 次，統計尋優結果的最優值、最差值、平均值、方差、迭代次數和運行時間，結果如表2 所示。

表2 對測試函數的尋優結果Tab.2 Optimizing Result for Testing Function

從表2 中對測試函數的尋優結果可以看出，在對3 個測試函數的尋優中，自主選擇搜索策略蜂群算法每次都能夠搜索到最優值，說明了其強大的尋優能力。從尋優精度和穩定性等方面看，CSSIBC 算法最優，其次為MABC 算法，ABC 算法最差。從迭代次數和運行時間看，CSSIBC 算法搜索到最優值時的迭代次數最小、耗時也最少，但是就耗時與迭代次數的比值來看，CSSIBC 算法最大，說明CSSIBC 算法單次迭代時的耗時最多，這是因為每次迭代時對搜索策略的選擇過程耗時較大。總的來講，自主選擇搜索策略蜂群算法的尋優精度最高、尋優穩定性最好，同時耗時也最少。

3 路徑規劃與仿真分析

3.1 路徑規劃方案與性能指標

機器人工作空間設定為二維空間且為靜態環境，本節使用坐標旋轉法將路徑的二維規劃問題轉化為一維規劃問題，如圖1所示。圖中OXY 坐標系為原始坐標系，稱其為慣性坐標系，S 為路徑起點，T 為路徑目標點。為了實現問題降維，以S 點為原點，以ST 方向為X′軸，以ST 垂直方向為Y′軸，從而建立局部坐標系SX′Y′。使用L1～LD共條平行線將ST 等分為D+1 段，那么路徑規劃可描述為在等分線L1～LD上確定各自的Y′坐標值，將規劃點順次連接后進行平滑處理就得到了規劃路徑，從而實現了路徑規劃由二維降為一維。

圖1 坐標轉換方法Fig.1 Coordinate Transform Method

記X′軸與X 軸夾角為θ，則以S 點為頂點順時針旋轉角度θ，并將坐標原點平移，就可以實現坐標間的轉換。

慣性坐標系任意一點（x，y）與局部坐標系相應點（x′，y′）間的轉換關系為：

式中：（xs，ys）—起始點S 坐標。

使用路徑長度作為機器人路徑規劃的唯一指標，根據上文的路徑規劃方案，得到平行線間距為△l=‖ST‖/（D+1），則機器人路徑長度為：

3.2 路徑規劃仿真分析

本節進行機器人路徑規劃的仿真環境和參數設置與2.5 節保持一致。設置了兩種環境下的仿真驗證，分別使用自主選擇搜索策略蜂群算法、人工蜂群算法進行路徑規劃，每種算法獨立運行10 次，兩種環境下搜索到的最優路徑，如圖2 所示。圖中實線為自主選擇搜索策略蜂群算法規劃的路徑，虛線為人工蜂群算法規劃的路徑。路徑起點設置為（20，20），路徑目標點設置為（190，190）。從圖中可以看出，自主選擇搜索策略蜂群算法規劃的路徑長度明顯短于人工蜂群算法，人工蜂群算法為躲避障礙物而規劃的路徑存在較多的冗余曲折路徑。為了進一步分析兩種算法在機器人路徑規劃中的性能，給出迭代過程中路徑長度隨迭代次數的變化曲線，如圖3 所示。圖中虛線為人工蜂群算法的迭代曲線，實線為自主選擇搜索策略蜂群算法的迭代曲線。

圖2 兩種環境下的規劃路徑Fig.2 Path Planned Under Two Environment

圖3 兩種環境下的迭代曲線Fig.3 Iterating Curve Under Two Environment

從圖3 可以看出，在環境一和環境二兩種情況下，自主選擇搜索策略蜂群算法搜索到最優值的迭代次數明顯少于人工蜂群算法，且收斂值也遠小于人工蜂群算法。經統計，在環境一中，自主選擇搜索策略蜂群算法規劃的最優路徑長度為389.12，人工蜂群算法規劃的最優路徑長度為441.36，比這里的算法增加了13.43%；自主選擇搜索策略蜂群算法搜索到最優值的迭代次數為176 次，人工蜂群算法搜索到最優值的迭代次數為289 次，比這里的算法增加了64.20%。在環境二中，自主選擇搜索策略蜂群算法規劃的最優路徑長度為263.72，人工蜂群算法規劃的最優路徑長度為321.56，比這里的算法增加了21.93%；自主選擇搜索策略蜂群算法搜索到最優值的迭代次數為195 次，人工蜂群算法搜索到最優值的迭代次數為302 次，比這里的算法增加了54.87%。綜合以上數據可以看出，在不同環境的路徑規劃中，自主選擇搜索策略蜂群算法規劃的路徑長度遠遠優于人工蜂群算法，搜索到最優值時的迭代次數也遠遠優于人工蜂群算法，這是因為自主選擇搜索策略蜂群算法設計了多種蜜源搜索方式，并根據不同蜜源搜索方式的即時價值和后效價值給出了自主選擇方法，使算法每次迭代均使用最有價值的搜索方式，因此規劃的路徑質量和迭代次數都遠遠優于人工蜂群算法。

4 結論

研究了全局靜態環境下的機器人導航路徑規劃問題，使用坐標旋轉法將二維問題轉化為一維，提出了自主選擇搜索策略蜂群算法用于路徑規劃，經驗證得出了以下結論：（1）自主選擇搜索策略蜂群算法的尋優速度和尋優精度遠遠優于人工蜂群算法；（2）多種蜜源搜索方式相結合，并根據即時價值和后效價值對搜索方式自主選擇，能夠提高算法的搜索性能。