采用生物地理學算法的移動機器人路徑規劃研究

羅 丹，蔣兵兵

(1.湖南鐵道職業技術學院，湖南 株州 412000；2.湖南鐵路科技職業技術學院，湖南 株州 412000)

1 引言

隨著人工智能的發展，移動機器人的路徑規劃成為一個研究的熱點。路徑規劃算法分為兩類：一類是傳統算法，如人工勢場法、可視圖法、柵格法、自由空間法、A*算法等，另一類是仿生進化算法，如粒子群算法、蟻群算法、遺傳算法等。由于傳統算法在機器人路徑規劃中存在搜索效率低等情況[1]，而仿生進化算法在搜索速度方面有較大的優勢。因此，近年來，群智能算法是移動機器人路徑規中的一個研究熱點[3]。

生物地理學算法[2](Biogeography-Based Optimization，BBO)是美國學者Dan Simon將生物地理學的研究成果與工程研究相結合，提出的一種新型仿生進化算法。BBO算法的全局搜索性能較好，學者們對BBO算法進行了大量的研究，并將其廣泛應用到電力系統調度問題、非線性系統、0-1組合問題、PID參數整定等實際問題中，并取得了較好的測試效果，也有少部分學者將其用到路徑規劃中，并取得了一定的研究效果[4,5,8]?？紤]到生物地理學算法的存在收斂速度慢等不足，結合遺傳算法具有的快速收斂性，本文提出一種新的改進生物地理學算法。

文中將改進的生物地理學算法應用到機器人路徑規劃中，其本質是將路徑規劃問題轉變為函數優化問題。選取兩種不同靜態環境，通過MATLAB進行仿真實驗，仿真結果證明，生物地理學算法在路徑規劃中是具有可行性的。

2 環境模型

常用的環境建模方法有行車圖法、勢場法、單元分解法。為了編程簡單易實現，文中采用一種近似的單元分解法，即柵格法。柵格法是用大小相同的柵格單元對將機器人的工作環境進行劃分，形成柵格地圖，能夠處理任意形狀的障礙物。常用的柵格地圖表示方法有直角坐標法和序號法，序號法表述簡潔易懂，文中采用序號法進行柵格標識。如圖1所示，從柵格序號p從柵格地圖的左下角開始編號，序號p與每一個柵格一一對應，圖中黑色部分為障礙物柵格，黑色方格表示障礙物，白色是可行區間為自由柵格。

圖1 采用序號法的柵格地圖

3 機器人路徑優化的目標評價函數

在機器人路徑規劃中，選擇合適的目標函數對算法獲得的優化結果和收斂效果是非常關鍵的，目標函數的適應度值是評價棲息地好壞的一個依據。文中的研究對象是靜態環境中的機器人路徑優化，以獲得最短路徑距離為目標，考慮到同樣的路徑存在的拐點數不一樣，為了更好的達到路徑優化的效果，引入平滑度最小的優化目標。文中機器人路徑優化的目標評價函數選取如下：

(1)

式(1)中，α和β是路徑距離和平滑度的權重因子，d是一組無間斷可行路徑的路徑規劃距離，s表示路徑的平滑度，即路徑的拐點個數。

4 改進生物地理學算法在機器人路徑規劃中的應用

4.1 機器人路徑的編碼方式

BBO算法是采用實數進行編碼的一種優化算法，而機器人路徑規劃問題是一個離散問題。因此本研究提出一種改進生物地理學算法應用于求解機器人路徑規劃問題，以柵格標識號進行編碼確定一條可行路徑，以圖3為例，序號[1，2，3，4，15，24，35，36，46，47，48，50，60，70，80，90，100]夠成一條可行路徑。

4.2 種群初始化

(1)根據起始點到目標點的最短直線距離，獲得需要的自由柵格數，然后從每一行自由柵格中隨機選取一個可行的自由柵格，構成一組間斷的可行路徑。以圖3為例，一組間斷的可行路徑為[1，15，24，35，46，60，70，80，90，100]。

(2)通過按照一定的規律插入自由柵格將上述間斷可行路徑中的間斷節點之間轉變成無障礙物的連續可行路徑[1，15，24，35，46，60，70，80，90，100]。

4.3 生物地理學算法的改進

為克服生物地理學算法在收斂速度上的不足，引入遺傳算法的操作算子，通過相互“取長補短”對算法進行改進，以期獲得更好的優化效果。其中，遺傳算法的選擇算子通常是采用輪盤賭法進行操作，存在較大的隨機性，文中采用BBO算法的遷入遷出率完成遺傳算法選擇和交叉操作，改進操作可以實現生物地理學算法進行離散編碼，增強BBO算法在搜索效率和精度上的優化性能。

4.3.1 遷移模型的選擇。BBO算法采用的是如圖4所示的線性遷移模型計算遷入率和遷出率，而文獻[6,7]有提出一種余弦遷移模型，通過數據驗證，在算法的優化性能上，余弦遷移模型要優于線性遷移模型。

文中采用余弦遷移模型進行物種遷移，設第s個島嶼擁有的物種數量是s個，余弦遷移模型計算[5]公式為：

(2)

式(2)中，表示島嶼之間物種最大遷入率，表示島嶼之間物種最大遷出率。

4.3.2 遷移操作

BBO算法的遷移操作主要是根據遷入遷出率確定需要遷入的棲息地和遷出的棲息地,然后將選定的兩個棲息地進行互換。這種全部信息交換機制容易丟失部分更優的子路徑，導致算法的收斂速度下降，文中引入遺傳算法的交叉機制，可以保留部分更優的路徑，從而使算法的優化性能進行提高。融入遺傳算法交叉機制的遷移操作偽代碼如下：

1：For i=1 to NP (棲息地數量) do

2: if rand < λithen

3: 選取Xi執行遷入操作

4： For j=1 to NP(棲息地數量)do

5： if rand<μjthen

6： 選取Xi執行遷出操作

7： 確定Xi和Xj存在的相同節點的子路徑

8： 根據遺傳算法的交叉算子對Xi和Xj進行交叉

9: End if

10： End for

11： End if

12: End for

4.3.3 變異操作

在基本BBO算法中[1,5]，采用的是隨機變異。隨機變異的隨機性較大，能夠增加物種跳出局部最優，但是隨機變異后獲得的路徑節點可能構成一條不可行的路徑。這將使機器人路徑優化的迭代次數增加。文中采用一種新的改進的路徑規劃變異算子，以減少變異后獲得不可行路徑的概率。變異操作的改進步驟如下。

(1)根據島嶼物種數量s的突變概率函數，選取需要突變的島嶼Xi，Xi=[x1,x2,x3,…xs]為第i個島嶼棲息的物種，即對應路徑規劃中的一條可行路徑。

(2)為提高種群的多樣性，采用基于高斯分布的變異操作。按高斯分布概率選擇兩個節點，將兩節點之間的無間斷可行路徑刪除，然后生成新的可行路徑替代。

4.4 求解機器人路徑規劃的生物地理學算法

將公式(1)作為路徑規劃的目標函數，每一個島嶼代表一條可行路徑，根據改進生物地理學算法的遷移操作和變異操作，可以確定求解機器人路徑規劃的算法流程如圖2所示。

圖2 基于BBO算法的機器人路徑規劃流程

5 仿真分析與比較

為了驗證該算法的可行性和有效性，選用簡單和復雜兩種工作環境，用MATLAB進行仿真驗證。

簡單環境下：障礙物數量為5，柵格地圖為10*10，機器人路徑規劃的算法參數設置如下：島嶼數量NP=20，迭代次數K=250，最大遷入遷出率I=E=1。采用MATLAB7.11進行仿真，在迭代20次左右可以的到獲得最優路徑如圖3所示(圖中綠色點是起始點，紅色點是目標點)。

圖3 10*10環境下最優路徑

復雜環境下：障礙物數量為16，柵格地圖為20*20，機器人路徑規劃的算法參數設置如下：島嶼數量NP=20，迭代次數K=300，最大遷入遷出率I=E=1。采用MATLAB7.11進行仿真，在迭代250次可以的到獲得最優路徑如圖4所示(圖中綠色點是起始點，紅色點是目標點)。

6 結論

通過上述的仿真結果可以看出，在上述的簡單環境下，相同的種群數量下，迭代20次左右就可以找到最優解；復雜環境下，迭代250次左右才能獲得最優解。仿真結果表明，BBO算法在機器人路徑規劃上是具有可行性和有效性的。但是對動態環境機器人路徑規劃效果還有待研究。

圖4 20*20環境下最優路徑