改進人工魚群的移動機器人避障尋優算法

郭凡，何柳，侯媛彬，秦學斌，盧志強，王冕

西安科技大學 電氣與控制工程學院，陜西 西安 710054

近幾年來，隨著計算機、信息處理與智能控制的迅猛發展，人們對于機器人的研究也在逐漸加深，機器人的功能也在慢慢完善，而本文所研究的移動機器人也是其中的一種[1]。現在移動機器人的研究已進入較為成熟的階段，可以先前確定的任務地點為目標，提前對行走的地圖做出規劃，在移動的過程中根據周圍復雜環境障礙物的情況，進行最短距離的判斷，完美地避開障礙物。移動機器人按照運行環境，可分為海、陸、空3類[2?3]。本文主要解決如何使移動機器人在行走過程中可獲取最短路徑的問題，即移動機器人行進的路徑規劃問題。對此，國內外眾多專家學者已進行探究并提出對應的解決辦法。文獻[4]針對無人機的航路規劃問題，提出利用多個處理器來同時執行算法優化過程的思想，并通過仿真來對粒子群和遺傳算法進行對應方案的驗證，實驗結果表明，算法的執行效率明顯提升。文獻[5]提出將改進的人工蜂群算法應用至機器人的路徑規劃中，并通過仿真結果將其與差分進化算法相比較，從而驗證該改進蜂群算法的實用性。文獻[6]提出將傳統的ANN與蟻群算法相結合的優化算法運用到路徑規劃中，并進行相應的仿真實驗，驗證該優化算法在規劃速度和更優路徑上的優越性。文獻[7]以蟻群算法為基礎，引進人工勢場的作用，兩種算法之間優劣互補，在復雜的行走環境中共同作用以提升尋優能力。國際很多專家對人工魚群算法進行了改進，應用在不同的領域，文獻[8]將支持向量機與人工魚群算法結合，來解決孿生支持向量機的參數選擇問題；文獻[9]針對深度神經網絡AI研究的可解釋性瓶頸，給出了有價值的解釋；文獻[10?12]利用改進的人工魚群算法進行圖像量化、WSN覆蓋優化策略、資源調度算法；文獻[13?16]研究改進的人工魚群算法在時滯系統辨識和非線性優化問題中的應用，也有專家利用混合聚類或海洋流的流動功率對人工魚群算法進行改進。

國外的專家對移動機器人的控制、組隊進行了大量研究，美國專家研究攔截流氓機器人，捕獲具有多個追蹤器的多個逃逸者的算法[17]；韓國的專家們研究多障礙下移動機器人避障、路徑規劃及不穩定網絡下機器人的跟蹤質量問題[18?20]；印度專家對多機器人系統進行建模、實行分散控制[21?23]；德國、法國和加拿大等的專家研究多機器人系統的運動沖突、測量與優化控制問題[24?27]。通過分析國內外的研究現狀，可以發現現有的算法研究仍存在一些可優化項，例如：移動機器人的真實環境較為復雜，存在不定時的障礙物，這就要求機器人具備實時避免碰撞的能力。因此，利用更加即時的算法來實現該場景優化具有很強的實際應用意義。

本文針對復雜環境下尋找最短路徑問題，提出基于視野自適應的改進人工魚群(artificial fishswarm algorithm based on adaptive vision,AVAFSA)的機器人路徑規劃算法，分別引入衰減函數和自適應算子來改善視覺效果，增強步長的自適應能力，從而避免因視野太小而陷入局部最小的情況，由此來縮減機器人在行走過程中的路徑長度和時間。

1 系統描述

1.1 結構設計

本文研制的移動機器人設計主要由主控制器Arduino單片機、超聲波測距模塊、電機驅動模塊、攝像頭、RS232接口、光電感應以及電源等模塊組成。其系統總體框架如圖1所示。其中超聲波測距和光電感應模塊主要完成行走環境的信息獲取，包括障礙物的距離和路線檢測；Arduino可根據超聲波測距和光電感應模塊的輸送信息來進行判斷，從而驅動電機來合理地移動機器人。攝像機主要將機器人周邊的環境信息通過RS232接口傳送至上位機，由PC機來完成對路徑的優化選擇。圖2給出了自制的移動機器人底部設計示意圖。圖2中，底部的前面中間的超聲波傳感器用作小車避障，其他4個紅外傳感器(紅外對管)用作尋跡，左右車輪分別由2個12 V直流電機分別驅動，兩輪之間裝有型號為ST151的碼盤測速器，萬向輪配合左右車輪運動。

圖1 自動搬運機器人系統框圖

圖2 自制的移動機器人底部設計示意

1.2 移動機器人的環境模型

柵格圖是目前在路徑規劃中應用較為廣泛的一種表達方法，因此本文通過柵格法來建立移動機器人的運行模型。柵格法把移動機器人的操作環境投射為柵格二維空間，其中黑色區域為障礙物所在地，白色為機器人可行區域[8]。分析移動機器人的運動環境，特作以下假設。

1)運行環境處于二維空間內，在一個靜態平面范圍中。

2)在運行空間內，靜態障礙物所處的初始位置、當前位置、目標位置與大小均知曉。

3)把移動機器人可看作質點。

4)移動機器人可以隨意變化方向[9]，其變化方向如圖3所示。

圖3 移動機器人移動方向

5)移動機器人可以隨意改變行走速度，加速、減速、勻速或者停止等。

2 AVAFSA路徑優化算法

2.1 AFSA的基本思想及步驟

人工魚群算法(artificial fish-swarm algorithm,AFSA)是由李曉磊博士在2002年提出的一種群體智能優化算法。其基本思想是仿照魚群在一片水域當中尋找最優解的覓食、聚群和追尾等行為，水域中的每一條魚都對應其中的一個優化解，該水域即為被優化問題的解空間。通過分析人工魚群的優化理念，可得其人工魚環境模型如圖4所示。假設水域中一條魚現時狀態是X，其可見范圍為Visual(公式中用Zvisual表示)，在某一時間點對應的視點位置為Xk，如果該方位較此時狀態更優，則可往該地點處向前一步，即抵達Xnext；若該方位無此時狀態更優，則一直在可見視線內找尋其他較優地點。

圖4 人工魚環境模型

AFSA在路徑規劃中的具體步驟如下。

1)初始化設置。對魚群中的各個參數進行初始設置，包括：該人工魚群的群體規模、視野、最大迭代次數、每一條魚的最大移動步長Step(公式中用Lstep)等參數。

2)此時迭代的次數是0，由N條魚組成初始魚群，每個魚表示從初始位置到目標位置的一條路徑。

3)對每一條人工魚都進行行為模擬：覓食、追尾、聚群與隨機移動行為，選取其中最優的一種行為來操作。4種行為算法的數學表達如下。

覓食行為

聚群行為

追尾行為

任意移動行為

式中Rand()為隨機函數，產生0到1之間的隨機數。

4)人工魚在每次行為之后，選取自身狀態和公告牌狀態較優的一種進行實時更新。

5)判斷是否已到最大迭代次數，若已到達，則輸出，否則，轉第3)繼續運行。

根據以上對于AFSA基本理論和操作步驟的描述中可看出，視野起到了至關重要的作用。在移動過程中，視野值若不變，易引起算法收斂速度變慢，計算量變大。

2.2 AVAFSA機器人路徑規劃算法

針對上述AFSA在路徑規劃中所存在的問題，本文提出基于視野自適應的改進人工魚群算法的機器人路徑規劃算法。

人工魚的4種行為中，覓食行為是決定算法是否收斂的關鍵，因此，僅對覓食行為采用自適應改進，其他的追尾、聚群以及隨機移動行為對應的視野保持不變。在覓食行為執行初期，給予其較大的視野，隨著過程迭代的進行慢慢減小。

但是，若行為執行到后期時，視野太小，易陷入局部最優。所以，設定在視野的當前值縮減至初始值的一半時，數值保持不變，停止減小。因此，現將覓食行為的數學表達式改寫成式(5)數學模型，即目標函數。

式中：k為迭代數；α為衰減因子，a∈(0,1)；β∈(0,1)為視野的下限因子；Vo代表視野初始值，即為優化后覓食行為中的。

AVAFSA機器人路徑規劃算法實現步驟為

1)初始化設置。結合柵格圖大小，設置每格的邊長、障礙物的個數、機器人起點S坐標和終點T坐標位置；為對魚群中的各個參數進行初始設置，包括：該人工魚群的群體規模、視野、最大迭代次數和擁擠度因子等參數，設每一條魚的最大移動步長Lstep=1、視野的下限因子β=0.5。

2)迭代的次數從0開始，由N條魚組成初始魚群，每個魚表示從初始位置到目標位置的一條路徑。

3)對每一個人工魚都進行行為模擬。包括覓食、追尾、聚群與隨機移動行為(此處覓食行為的視野是改進后的，采用目標函數公式(5)迭代)；在柵格圖上機器人的當前位置，選取當中最優的一種行為來操作。

4)人工魚在每次行為之后，選取自身狀態和公告牌狀態較優的一種進行實時更新。

5)判斷運行次數是否等于初始設置的最大迭代次數，若是，則繼續；否則，轉到步驟3)繼續。

6)判斷機器人是否到達柵格圖的終點T坐標位置，若是，則結束；否則，轉到步驟3)繼續。

3 實驗與分析

為了驗證本文所提改進的人工魚群算法與傳統人工魚群在移動機器人路徑規劃上的優越性，在此選擇相同的運行環境作對比仿真實驗。結合柵格法[28]，利用MATLAB進行仿真驗證，柵格圖大小設為120 cm×120 cm，其每格的邊長為4 cm，序號初始化值是0，在X、Y方向對各個柵格按照順序進行編號，把障礙物所在的柵格位置標記成黑色，其他區域為白色，貨物存放地47個，起點S坐標為 (2,2)，終點T坐標為 (118,118)，最大迭代次數均設定為100。2種算法在該相同環境下各自優化的最優路線與收斂曲線分別如圖5和圖6所示。相關數據總結見表1。圖7為自制的移動小車在實際運行的狀態，圖7(a)為避障選道，圖7(b)為右轉彎運行。

圖7 自制的移動小車在實際運行的狀態

表1中，Lf為最優路徑長度，Kmin為訓練次數。由仿真圖、實驗及表中數據可得，2種算法在移動機器人路徑規劃的應用中，本文所改進的人工魚群算法最優路徑長度與迭代次數上均優于傳統的人工魚群算法。由圖4可得，AVAFSA優化下的最優路徑長度明顯較AFSA短，為186 cm；從圖5可看出，在路徑尋優的整個過程中，AVAFSA最終找到最優路徑所需迭代的次數為35次，比AFSA少了15次；此外，當2種算法的最大迭代次數均設置為100時，AVAFSA會最先達到次數上限，迭代用時較短，僅為10.15 s，比AVAFSA縮短了2.18 s。總之，本文所提出的基于視野自適應的改進人工魚群優化算法較傳統的人工魚群算法在移動機器人的路徑規劃應用上存在明顯的優勢。

圖52 種算法的最優路徑搜索

圖62 種算法的收斂曲線

表1 2種算法最優路徑相關參數對比

4 結論

本文通過建立移動機器人的環境模型，分析傳統人工魚群在路徑優化方面存在的問題，提出基于視野自適應的改進人工魚群優化算法，結合柵格圖法的優點，形成了AVAFSA機器人避障和優化算法。該算法利用魚群視野自適應的形式來對可見視線值的下限進行設定，引入衰減函數來改善視覺效果，引入自適應算子來增強步長的自適應能力，從而避免因視野太小而導致易陷入局部最小。計算機仿真和通過自制的小車實驗結果表明，如果在環境中有未知障礙物，本文的AVAFSA機器人路徑規劃算法也能實時避障，重新優化運行的路徑。在同樣環境條件下，AVAFSA機器人避障和優化算法相比于傳統的人工魚群算法獲取最優路徑的迭代次數減少了，路徑長度縮短了8.82%，收斂速度提高了17.68%。由此可見，視野自適應的人工魚群優化算法在移動機器人的避障和路徑規劃上效果明顯。