基于A*改進算法的機器人移動路徑優化仿真

韓學行，頓向明，林子洋

(上海交通大學機械與動力工程學院，上海 200240)

1 引言

機器人是一種可接受人類指揮，并按照指揮命令，根據預先設置好的編排程序，自動化執行任務的機器裝置，以人工智能技術為基礎，可協助或取代人類工作。考慮機器人的外部結構完全模擬人體的關節結構，機器人本體的有關部位分別為基座、腕部、手部和行走部等，并安裝了對應的驅動裝置、檢測裝置以及控制系統等軟件執行設備，保證機器人可以正常的執行命令程序。隨著互聯網技術以及計算機技術的發展，為了保證機器人可以適應時代的發展，更加精確的完成指揮命令，目前通常使用計算機技術對機器人進行路徑規劃研究與設計[1]。移動機器人是多學科交融的高智能產品，必須考慮機器人的移動方式，可以通過各個程序執行單元，驅動全向移動機器人。機器人的路徑規劃是移動機器人自主導航的關鍵技術之一，所謂機器人路徑規劃指的是移動機器人按照某一性能指標，例如機器人執行任務時所需的時間、距離等指標，尋找出一條最優路徑。

在進行機器人移動路徑規劃時，需要解決自我定位、自我規劃以及自主控制等多個問題，在進行機器人路徑規劃過程中需要引入和利用多種規劃算法。傳統的機器人移動路徑規劃方法經常利用的算法包括：A*算法、粒子群算法以及模糊控制算法，其中利用A*算法的機器人移動路徑規劃方法，主要是通過靜態路網求解最有效的直接搜索方法，通過對初始點以及狀態空間的估價函數來得出目標節點的最佳路徑[2]。粒子群算法是一種進化計算技術，利用群體智能建立的簡化模型，粒子群算法在進行機器人路徑規劃時，在對集群活動行為觀察的基礎上，利用群體中的個體對信息的共享，從而得出最終的路徑最優解[3]。模糊控制算法是通過對機器人各項機械系數的控制，從而控制機器人系統，模糊控制的關鍵在于隸屬度和模糊級別的劃分[4]。經過長時間的研究發現，上述三種路徑規劃方法中，基于A*算法的移動機器人規劃方法準確率最高，但傳統方法的通病是撞擊率高、魯棒性低。為了延續機器人移動路徑規劃方法的準確性，并提升移動路徑方法的魯棒性，將A*算法的改進算法應用到路徑規劃方法中，得出機器人移動路徑優化方法。

2 機器人移動路徑優化方法

2.1 機器人移動環境模型描述

在機器人移動路線規劃優化的過程中，進行移動機器人工作環境的地圖建立，這是路徑優化的第一步，地圖環境的建立指的是通過多個環境傳感器獲得機器人移動的環境信息，將多傳感器檢測到的信息融合在一起，形成最終的抽象地圖模型[5]。將環境信息用柵格單位的形式來描述，以此來建立機器人移動的工作環境模型，如圖1所示。

圖1 機器人移動環境示意圖

按照圖1中的形式，使用柵格法將機器人的工作環境分割成為形狀大小相同的多個柵格，在環境模型的構建過程中，將柵格的形式劃分為可通過柵格與不可通過柵格兩種。通過對每一個柵格單元進行編碼，最后用不同的CV值賦予給每一個柵格單元，以此來表示出目標單元為障礙物區域或自由通行區域[6]。圖2當中空白柵格表示的是可通過柵格，也就是移動機器人可以自由通過的位置，而被黑色填充的柵格表示的是不可通過的柵格，也就是環境中的障礙物。將環境模型以坐標系的形式存儲在機器人存儲器當中，橫向向右的增加方向為X的正方向，而縱向向上的增加方向表示的是Y的正方向，并將柵格環境模型用序號法進行編碼并存儲。

假設在機器人移動環境模型中，機器人的移動不受機器人高度的影響，且在機器人的整個移動范圍內，周圍環境信息保持理想狀態，固定不變。定義柵格尺寸的計算公式為

(1)

式中，l是環境模型中的標準柵格邊長，lmin為環境中障礙物的最小邊長，nc為柵格數量，ltemp表示環境中障礙物的理想邊長。其中ltemp表達式如下

(2)

式中，Sobs為環境當中障礙物的面積之和，S表示的是機器人移動環境的總面積，lmax為環境中障礙物的最大邊長。

將柵格化完成的描述環境模型進行直角坐標法進行信息編碼，用直角坐標的形式表示柵格的位置，設定環境中的任意一個柵格的位置坐標為(nx，ny)，通過式(3)可以求出坐標nx值。

(3)

式中，nx表示的是柵格中心位置的坐標表示方法。同理通過式(4)便可以得出柵格端點位置的坐標ny的值

(4)

式中mod為求余運算函數，而n表示的是柵格序號[7]。按照圖2所示，S為機器人移動路徑的起點，而D為移動路徑的終點，可以將環境中的所有柵格點進行編碼存儲在機器人存儲器中。

2.2 柵格模型優化處理

結合A*改進算法對構建的環境柵格模型做膨脹處理，通過增加環境障礙物周圍的柵格運動代價值來表示環境區域的危險系數[8]。設定膨脹處理中map(nx，ny)表示(nx，ny)位置上的柵格CV值，膨脹處理過程如式(5)所示

map(nx，ny)=map(nx-1，ny-1)+nyW

(5)

式中W表示的是代價增加值。用CV值來表示環境障礙的安全等級，在進行機器人移動路徑優化過程中，自動選擇安全等級更高的位置作為優化的規劃路徑。

2.3 獲得機器人移動原始路徑

定義機器人用Ai來表示，Ai的中心為xi(t)，機器人在t時刻的姿態角為θi(t)，xi是一個指數位置的參數化多項式，使用xi參數來表示Ai的規劃路徑，定義tfi作為Ai的最終運動時間的一個實數值。將Ai規劃出的規劃路徑為xi，其表達式為

xi=map(nx，ny)[x1i(t)+x2i(t)]

(6)

式中，x1i(t)與x2i(t)分別表示動態和靜態運動方向，對應指數為M和N。

借助環境傳感器以及機器人裝置上人工智能攝像機，可以在移動環境中偵測到障礙物的位置，可實時獲取障礙物的路徑信息。通常情況下，移動環境中的障礙物類型可以分為無障礙、靜態障礙和動態障礙三個方面，假設Ok(q)為障礙物的表示方法，其當k取值為0時表示環境內無障礙物，k為1表示環境內存在靜態障礙，取2表示存在動態障礙，而q表示的是障礙物的數量[9]。分別通過k的取值來判定機器人移動路徑上的環境類型，并分別針對不同的環境條件利用A*改進算法來獲得原始機器人移動規劃路徑，其規劃步驟如下所示：

2.3.1 無障礙下路徑規劃

通過傳感器檢測到環境中的障礙物體時，Ok(q)中k的值取0，那么在進行路徑規劃時，取起點與終點的最短距離路線即可[10]。使用A*改進算法選擇機器人運動距離最短的作為路徑極限，從而得到規劃路徑。假設路徑的橫向距離為0.25，縱向距離為0.035，則規劃的路徑結果可表示為

xi(t)=0.25+0.25t+…+0.25(xi)N+M

(7)

機器人按照規劃完成的路徑進行移動，從該起始位姿無碰撞的移動待終止位姿。

2.3.2 靜態障礙下路徑規劃

首先經過傳感器與攝像機得到障礙的位置信息Obsi(x，y)，那么可以得出規劃函數

(8)

通過目標函數給出不同區間上的規劃路徑，機器人以遠離靜態障礙物為前提，從起始位置到達終止位置。

2.3.3 動態障礙下路徑規劃

在動態障礙環境下，對機器人的移動路線進行規劃，首先需要對障礙物的移動路線進行初步分析，得出有關于動態障礙物的移動規律。以障礙物的移動情況作為路線規劃的參考，遵循遠離障礙的原則得出動態障礙下機器人移動路徑的規劃結果，如圖2所示。

圖2 動態障礙下路徑規劃結果

綜合上述分析步驟，可基于A*改進算法來獲得原始機器人移動規劃路徑，流程圖如圖3所示。

圖3 原始機器人移動規劃路徑獲取流程圖

2.4 機器人移動路徑優化方法

2.4.1 計算路徑優化約束條件

在得到原始路徑的基礎上，使用A*改進算法得出機器人移動路徑的優化約束條件，其中優化約束條件包括：運動學約束和避障約束[11]。運動學描述就是指機器人在沿著規劃路徑移動時，需要控制機器人移動的速度和加速度，避免機器人在移動過程中的滑失情況。因此運動學約束可以表示為

(9)

式中，vi(t)和ai(t)表示約束條件函數，vmaxi和amaxi分別表示機器人移動時的速度和加速度，t表示運動約束值，J表示最大約束取值。

另外避障約束的目的是為了保證正在移動的機器人需要與障礙物之間保持最小的安全距離。設定dobs和doik分別為機器人Ai與障礙物Ok(q)之間的安全距離與實際距離的值。那么在移動環境中機器人需要滿足式(10)中的避障約束條件

dobs-doik≤0，?k=1，…，J

(10)

2.4.2 平滑優化規劃路徑輸出

從路徑路線序列的第二個節點開始，若連續兩個節點存在一致的移動方向，則認為這兩個節點為冗余節點，可以刪除該節點，并更新路徑點的序列。按照順序依次遍歷所有的路徑點，最終得出起點、轉折點以及終點的路徑序列。具體的平滑優化輸出流程如圖4所示。

圖4 路徑平滑優化流程圖

通過計算獲得規劃優化路徑，在移動機器人r路徑規劃優化過程中，采用評價函數的最小節點作為優化節點并將該節點存入路徑列表當中，直到優化至目標節點為止[12]，由此則可以完成對機器人移動路徑的優化分析。

3 仿真對比實驗

為了驗證本文機器人移動路徑優化方法的有效性，進行仿真對比實驗，實驗過程中設立傳統方法作為實驗的對比方法。由于操作機器人實際移動的成本高，且操作過程復雜，因此此次驗證實驗借助計算機仿真技術，通過構建仿真環境以及安裝硬件設備等步驟，在仿真環境下對優化方法進行驗證。最終通過對移動路徑與移動時間等參數的對比，得出優化方法的有效性。

3.1 構建仿真環境

在進行實驗時，利用計算機仿真技術搭建所需的仿真環境，仿真環境的計算機參數為：CPU Intel Core2 Duo，內存32GB，編譯工具MATLAB8.0。選擇機器人移動的仿真環境，測量仿真環境的大小尺寸，并將實驗中機器人移動的環境數據輸入到路徑規劃顯示界面當中。如圖5所示。

圖5 路徑規劃顯示界面

假設隨機分布的環境障礙物，以相同的標識標記在移動環境中。選擇MobileRobots出廠的Pioneer3-DX型號的機器人作為實驗對象，將機器人的相關數據輸入到仿真環境當中。圖6為機器人虛擬環境仿真圖。

圖6 機器人虛擬環境仿真圖

通過路徑規劃顯示界面，采用本文方法將Pioneer3-DX型號機器人在有障礙物的空間中進行最短路徑規劃，淺色部分為障礙物，圖7為避開障礙物的路徑圖。

圖7 避開障礙物的最短路徑圖

根據圖7可知，采用本文基于A*改進算法可以有效避開障礙物后，再沿著全局最短路徑前進達到目標點，實現最短路徑規劃。

3.2 實驗過程

在實驗環境下，將本文基于A*改進算法的機器人移動路徑優化規劃方法設置為實驗方法，將傳統的路徑規劃方法、基于A*算法的機器人移動路徑規劃方法當做對比方法。利用三種規劃方法首先分析仿真環境，設立實驗中機器人的起始點與終止點。在仿真機器人上安裝傳感器，在機器人的移動過程中每當與障礙物發生碰撞，便記錄一次撞擊系數。與此同時，記錄機器人的移動路徑長度以及移動時間。

3.3 實驗對比結果與分析

通過仿真實驗得出對比方法與實驗方法輸出的路徑界面如圖8所示。

圖8 路徑輸出結果對比

從圖8中的輸出結果可以看出，經過優化的機器人移動路徑更加平滑，在移動過程中可以與障礙物保持安全距離。

建立一個 200 ×200 的柵格環境模型，每個柵格邊長為 1m，起點 S 坐標為(3，4)，終點 G 坐標為(195，190)，如圖9 所示。

圖9 復雜環境模型

通過復雜環境模型對移動時間、移動路徑長度以及撞擊次數、轉彎次數進行記錄，得出表1中的實驗對比結果。

從表中的數據可以看出，本文基于A*改進算法的機器人移動路徑優化規劃方法，其路徑長度比其它兩種方法的路徑長度節省約46米，在時間上也節省了約19分鐘。經過計算發現，與其它兩種路徑規劃方法相比，本文優化方法的路徑轉彎次數和撞擊次數均出現了較大的降低，明顯優于其它兩種方法，表明本文利用A*改進算法進行機器人移動路徑優化，能夠獲取較好的成果。

4 結束語

機器人學研究中，路徑規劃一直是廣受關注的研究熱點之一。本文將A*改進算法用于機器人移動路徑優化規劃中，并通過實驗驗證了所提方法的有效性，結果表明，所提方法能夠較好的完成機器人路徑規劃，節省時間和成本，且且能夠減輕機器人在移動過程中的消耗，具有較強的應用價值。