機器人路徑規劃算法研究

鄭美英，董 航

（遼寧工程職業學院，遼寧 鐵嶺 112008）

在機器人設計中，路徑規劃是最基礎也是最重要的因素之一，故對其算法研究尤為重要。本文將對傳統路徑規劃算法與智能路徑規劃算法進行詳細研究，并利用MATLAB軟件進行算法仿真實驗，驗證求解路徑規劃問題的可行性，最后通過對兩種算法進行的比較分析，確定最優算法。

一、機器人傳統路徑規劃算法

（一）障礙物分類

機器人設計傳統路徑規劃策略首先需要對環境中的障礙物進行分類，然后再根據障礙物的不同類型設計對應路徑規劃策略。在具體環境中，障礙物信息由機器人測距傳感器實時采集[1]。本文將障礙物信息分為以下四種基本類型（如圖1所示）。

圖1 障礙物4種基本類型示意圖

圖中DSL、DSR、DHL、DHR分別表示機器人車體左側、車體右側、車頭左側、車頭右側方向上與障礙物的距離。障礙物四種基本類型說明如下：

A類型：表示在機器人車體的前方有障礙物。

B類型：表示機器人車體的前方與車體右側有障礙物。

C類型：表示機器人車體的前方與車體左側有障礙物

D類型：表示機器人的前方、車體左側、車體右側都有障礙物。

（二）路徑規劃策略分析

在具體環境中，障礙物可能有多種類型，但都可概括為上述四種基本類型中的一種或幾種類型的不同組合，所以需要分別對這四種基本類型障礙物的路徑規劃策略進行分析。當機器人四個方向檢測不到障礙物時，沒有路徑規劃行為，機器人直行。

在機器人路徑規劃過程中，為避免機器人與障礙物發生碰撞而損壞機器人，它與障礙物之間必須保持一定距離，即安全距離[2]。安全距離選取過小，機器人在進入路徑規劃模式前，可能與障礙物發生碰撞，導致路徑規劃失敗；安全距離選取過大會造成機器人提前轉向，最終偏離目標點。因此在分析路徑規劃策略前需要先確定機器人的安全距離[3]。

本研究機器人的轉彎方式為兩主動輪同時反向旋轉帶動履帶運動從而實現機器人轉彎，因此轉彎中心即為機器人底盤的幾何中心。測得底盤幾何中心到履帶頂點距離約為200mm，該頂點即為最易先與障礙物發生碰撞的危險點。由于在停車過程中受到慣性的影響，機器人依然會向前運動一段距離，經過多次實驗測得此距離約為50mm。為了保險起見，機器人的安全距離選為300mm。

1．A類型障礙物路徑規劃策略分析

假設滿足DHL≤300mm或DHR≤300mm，且DSL≥300mm且DSR≥300mm，就斷定機器人此刻處于A類型障礙物環境中。

2．B類型或C類障礙物路徑規劃策略分析

假設滿足DHL≤300mm或DHR≤300mm，且DSL≥300mm且DSR≤300mm，就斷定機器人此刻處于B類型障礙物環境中。或者滿足DHL≤300mm或DHR≤300mm，且DSL≤300mm且DSR≥300mm，就斷定機器人此刻處于C類型障礙物環境中。由于B類型障礙物的路徑規劃策略與C類型類似，只是障礙物的分布導致機器人轉彎方向相反，所以此處以C類型障礙物為例討論路徑規劃策略，B類型可以此類推。

3．D類型障礙物路徑規劃策略分析

假設滿足DHL≤300mm或DHR≤300mm，且DSL≤300mm且DSR≤300mm，就斷定機器人此刻處于D類型障礙物環境中。

二、基于蟻群算法的機器人路徑規劃

（一）蟻群算法數學模型

20世紀90年代初，意大利得迪里戈博士團隊通過長期對自然界螞蟻覓食問題的研究提出了一種新型智能算法——蟻群算法（Ant Colony Algorithm，AG）[4]。他們在觀察蟻群覓食過程時發現，螞蟻在搜尋食物時，總是邊搜尋邊在路徑上分泌一種信息素，其它螞蟻通過識別該信息素來選擇距離更短的路徑。

（二）蟻群路徑規劃算法流程

蟻群路徑規劃算法的運算流程如圖2所示。

圖2 蟻群路徑規劃算法流程圖

（三）仿真實驗與分析

研究蟻群算法α、m、β、ρ、Q、Ncmax等主要參數的最優配置至關重要，但這些參數的配置方法至今未能形成完整的理論體系，所以只能借鑒仿真實驗的統計數據[5]。

本文參數設置為α=1、β=15、Q=0.95、m=30、Ncmax=20。設置起點柵格為柵格環境左下角（柵格序號為0），目標點柵格為柵格環境右上角（柵格序號為399）。

圖3所示為MATLAB仿真結果，規劃出的路徑用線條表示。由圖可知機器人能尋找到一條從起點出發避開障礙物到達目標點的全局最優路徑，同時此路徑也為該柵格環境下所能找到的最短路徑，路徑長度為32.382 m。

圖3 蟻群算法最優路徑

圖4為蟻群算法收斂結果。由圖4可知最短路徑長度在迭代7次后收斂于最優路徑長度32.382 m，算法運行所消耗的時間為8.515 s。仿真結果驗證了蟻群算法解決機器人智能路徑規劃問題的可行性。

圖4 蟻群算法收斂結果

三、基于遺傳算法的機器人路徑規劃

（一）遺傳算法數學模型

20世紀70年代初，美國的霍蘭博士團隊通過長期對達爾文進化論的研究提出了一種新型人工智能算法——遺傳算法（Genetic Algorithm，GA）[6]。該算法是模仿自然界物競天擇思想而產生的一種基于遺傳理論的算法[7]。目前，在機器人的智能路徑規劃問題中遺傳算法也得到廣泛應用。

（二）遺傳路徑規劃算法流程

遺傳路徑規劃算法的運算流程如圖5所示。

圖5 遺傳路徑規劃算法流程圖

（三）仿真實驗與分析

與蟻群算法類似，研究遺傳算法M、T、Pm、Pc等主要參數的最優配置至關重要，但這些參數的配置方法至今未能形成完整的理論體系，所以只能借鑒仿真實驗的統計數據[8]。

在仿真實驗前，對種群的各項參數設置如下：種群規模M=60，最大進化代數T=20，交叉概率Pc=0.8，變異概率Pm=0.2。設置起點為柵格環境左下角圓圈處（柵格序號為0），目標點為右上角方格處（柵格序號為399）。

圖6所示為MATLAB仿真結果，規劃出的路徑用線條表示。由圖可知機器人能尋找到一條從起點出發避開障礙物到達目標點的全局最優路徑，同時此路徑也為該柵格環境下所能找到的最短路徑，路徑長度為30.971 m。

圖6 遺傳算法最優路徑

圖7為遺傳算法收斂結果，由圖可知最短路徑長度在迭代10次后收斂于最優路徑長度30.971 m，算法運行所消耗的時間為16.402 s。仿真結果驗證了遺傳算法解決機器人智能路徑規劃問題的可行性。

圖7 遺傳算法收斂結果

四、三種算法對比分析

利用智能算法在對機器人進行路徑規劃時，往往不是毫無要求的，還要附加一些路徑距離更短、算法搜索效率更高或算法穩定性更強等限制條件[9]。前面只對蟻群算法與遺傳算法進行了MATLAB仿真，驗證了蟻群算法與遺傳算法求解路徑規劃問題的可行性。下面將從最短路徑長度和最優路徑比例兩方面對兩種智能路徑規劃算法進行比較分析[10]。為避免一次仿真的偶然性，將這兩種算法分別按照之前的設置仿真100次，得到結果如表1所示。

表1 蟻群算法與遺傳算法性能比較

由表1可知在最短路徑長度方面，遺傳算法比蟻群算法所獲得的路徑更短，說明遺傳算法更顯智能；在獲得最優路徑比例方面，遺傳算法也遠高于蟻群算法說明遺傳算法搜索穩定性更好。通過實驗比較，遺傳算法比蟻群算法具有更智能、更穩定的優點，因此選用遺傳算法來解決機器人的路徑規劃問題。

根據設計要求，機器人應具有路徑規劃功能，此處可將遺傳算法算法應用于解決機器人自主運動過程中的路徑規劃問題。基于遺傳算法的機器人智能路徑規劃流程如圖8所示。

圖8 基于遺傳算法的機器人智能路徑規劃流程圖

機器人首先向上位機發送定位請求，由定位系統對機器人當前的位置和位姿進行初始標定。在獲得機器人位置和位姿信息后，通過獲取起始點和目標點及障礙物等信息，調用遺傳算法進行全局路徑規劃，分析規劃結果，調用機器人運行程序開始控制機器人行進。若機器人檢測到有障礙物，則進入避障處理子程序，最后判斷機器人是否已經到達目標點。若是，則本次路徑規劃任務結束；否則需要重新定位機器人位置信息，再依次進行以上過程，直到到達目標點。

要實現基于遺傳算法智能路徑規劃還需要能獲取環境信息的傳感器如視覺傳感器、激光傳感器，由于缺少此類傳感器，暫無法獲取和處理環境信息。在將來的研究當中將進一步完善機器人環境信息獲取和處理能力以實現基于遺傳算法的智能路徑規劃。因此本文最終選擇傳統路徑規劃算法來解決機器人自主運動過程中的路徑規劃問題。

五、結語

本文首先對傳統路徑規劃算法進行了詳細介紹，然后對智能路徑規劃算法研究現狀進行了簡單介紹，又著重分別對蟻群算法與遺傳算法的原理進行了闡述，并敘述了運用這兩種算法求解路徑規劃問題的流程，同時運用MATLAB軟件進行了算法仿真實驗，驗證了蟻群算法與遺傳算法求解路徑規劃問題的可行性。接著從最短路徑長度和最優路徑比例兩個方面對兩種算法進行了比較分析。發現遺傳算法比蟻群算法具有更智能、更穩定的優點。