基于A*改進(jìn)算法的機(jī)器人移動(dòng)路徑優(yōu)化仿真

韓學(xué)行，頓向明，林子洋

(上海交通大學(xué)機(jī)械與動(dòng)力工程學(xué)院，上海 200240)

1 引言

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

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

2 機(jī)器人移動(dòng)路徑優(yōu)化方法

2.1 機(jī)器人移動(dòng)環(huán)境模型描述

在機(jī)器人移動(dòng)路線規(guī)劃優(yōu)化的過(guò)程中，進(jìn)行移動(dòng)機(jī)器人工作環(huán)境的地圖建立，這是路徑優(yōu)化的第一步，地圖環(huán)境的建立指的是通過(guò)多個(gè)環(huán)境傳感器獲得機(jī)器人移動(dòng)的環(huán)境信息，將多傳感器檢測(cè)到的信息融合在一起，形成最終的抽象地圖模型[5]。將環(huán)境信息用柵格單位的形式來(lái)描述，以此來(lái)建立機(jī)器人移動(dòng)的工作環(huán)境模型，如圖1所示。

圖1 機(jī)器人移動(dòng)環(huán)境示意圖

按照?qǐng)D1中的形式，使用柵格法將機(jī)器人的工作環(huán)境分割成為形狀大小相同的多個(gè)柵格，在環(huán)境模型的構(gòu)建過(guò)程中，將柵格的形式劃分為可通過(guò)柵格與不可通過(guò)柵格兩種。通過(guò)對(duì)每一個(gè)柵格單元進(jìn)行編碼，最后用不同的CV值賦予給每一個(gè)柵格單元，以此來(lái)表示出目標(biāo)單元為障礙物區(qū)域或自由通行區(qū)域[6]。圖2當(dāng)中空白柵格表示的是可通過(guò)柵格，也就是移動(dòng)機(jī)器人可以自由通過(guò)的位置，而被黑色填充的柵格表示的是不可通過(guò)的柵格，也就是環(huán)境中的障礙物。將環(huán)境模型以坐標(biāo)系的形式存儲(chǔ)在機(jī)器人存儲(chǔ)器當(dāng)中，橫向向右的增加方向?yàn)閄的正方向，而縱向向上的增加方向表示的是Y的正方向，并將柵格環(huán)境模型用序號(hào)法進(jìn)行編碼并存儲(chǔ)。

假設(shè)在機(jī)器人移動(dòng)環(huán)境模型中，機(jī)器人的移動(dòng)不受機(jī)器人高度的影響，且在機(jī)器人的整個(gè)移動(dòng)范圍內(nèi)，周圍環(huán)境信息保持理想狀態(tài)，固定不變。定義柵格尺寸的計(jì)算公式為

(1)

式中，l是環(huán)境模型中的標(biāo)準(zhǔn)柵格邊長(zhǎng)，lmin為環(huán)境中障礙物的最小邊長(zhǎng)，nc為柵格數(shù)量，ltemp表示環(huán)境中障礙物的理想邊長(zhǎng)。其中l(wèi)temp表達(dá)式如下

(2)

式中，Sobs為環(huán)境當(dāng)中障礙物的面積之和，S表示的是機(jī)器人移動(dòng)環(huán)境的總面積，lmax為環(huán)境中障礙物的最大邊長(zhǎng)。

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

(3)

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

(4)

式中mod為求余運(yùn)算函數(shù)，而n表示的是柵格序號(hào)[7]。按照?qǐng)D2所示，S為機(jī)器人移動(dòng)路徑的起點(diǎn)，而D為移動(dòng)路徑的終點(diǎn)，可以將環(huán)境中的所有柵格點(diǎn)進(jìn)行編碼存儲(chǔ)在機(jī)器人存儲(chǔ)器中。

2.2 柵格模型優(yōu)化處理

結(jié)合A*改進(jìn)算法對(duì)構(gòu)建的環(huán)境柵格模型做膨脹處理，通過(guò)增加環(huán)境障礙物周圍的柵格運(yùn)動(dòng)代價(jià)值來(lái)表示環(huán)境區(qū)域的危險(xiǎn)系數(shù)[8]。設(shè)定膨脹處理中map(nx，ny)表示(nx，ny)位置上的柵格CV值，膨脹處理過(guò)程如式(5)所示

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

(5)

式中W表示的是代價(jià)增加值。用CV值來(lái)表示環(huán)境障礙的安全等級(jí)，在進(jìn)行機(jī)器人移動(dòng)路徑優(yōu)化過(guò)程中，自動(dòng)選擇安全等級(jí)更高的位置作為優(yōu)化的規(guī)劃路徑。

2.3 獲得機(jī)器人移動(dòng)原始路徑

定義機(jī)器人用Ai來(lái)表示，Ai的中心為xi(t)，機(jī)器人在t時(shí)刻的姿態(tài)角為θi(t)，xi是一個(gè)指數(shù)位置的參數(shù)化多項(xiàng)式，使用xi參數(shù)來(lái)表示Ai的規(guī)劃路徑，定義tfi作為Ai的最終運(yùn)動(dòng)時(shí)間的一個(gè)實(shí)數(shù)值。將Ai規(guī)劃出的規(guī)劃路徑為xi，其表達(dá)式為

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

(6)

式中，x1i(t)與x2i(t)分別表示動(dòng)態(tài)和靜態(tài)運(yùn)動(dòng)方向，對(duì)應(yīng)指數(shù)為M和N。

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

2.3.1 無(wú)障礙下路徑規(guī)劃

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

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

(7)

機(jī)器人按照規(guī)劃完成的路徑進(jìn)行移動(dòng)，從該起始位姿無(wú)碰撞的移動(dòng)待終止位姿。

2.3.2 靜態(tài)障礙下路徑規(guī)劃

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

(8)

通過(guò)目標(biāo)函數(shù)給出不同區(qū)間上的規(guī)劃路徑，機(jī)器人以遠(yuǎn)離靜態(tài)障礙物為前提，從起始位置到達(dá)終止位置。

2.3.3 動(dòng)態(tài)障礙下路徑規(guī)劃

在動(dòng)態(tài)障礙環(huán)境下，對(duì)機(jī)器人的移動(dòng)路線進(jìn)行規(guī)劃，首先需要對(duì)障礙物的移動(dòng)路線進(jìn)行初步分析，得出有關(guān)于動(dòng)態(tài)障礙物的移動(dòng)規(guī)律。以障礙物的移動(dòng)情況作為路線規(guī)劃的參考，遵循遠(yuǎn)離障礙的原則得出動(dòng)態(tài)障礙下機(jī)器人移動(dòng)路徑的規(guī)劃結(jié)果，如圖2所示。

圖2 動(dòng)態(tài)障礙下路徑規(guī)劃結(jié)果

綜合上述分析步驟，可基于A*改進(jìn)算法來(lái)獲得原始機(jī)器人移動(dòng)規(guī)劃路徑，流程圖如圖3所示。

圖3 原始機(jī)器人移動(dòng)規(guī)劃路徑獲取流程圖

2.4 機(jī)器人移動(dòng)路徑優(yōu)化方法

2.4.1 計(jì)算路徑優(yōu)化約束條件

在得到原始路徑的基礎(chǔ)上，使用A*改進(jìn)算法得出機(jī)器人移動(dòng)路徑的優(yōu)化約束條件，其中優(yōu)化約束條件包括：運(yùn)動(dòng)學(xué)約束和避障約束[11]。運(yùn)動(dòng)學(xué)描述就是指機(jī)器人在沿著規(guī)劃路徑移動(dòng)時(shí)，需要控制機(jī)器人移動(dòng)的速度和加速度，避免機(jī)器人在移動(dòng)過(guò)程中的滑失情況。因此運(yùn)動(dòng)學(xué)約束可以表示為

(9)

式中，vi(t)和ai(t)表示約束條件函數(shù)，vmaxi和amaxi分別表示機(jī)器人移動(dòng)時(shí)的速度和加速度，t表示運(yùn)動(dòng)約束值，J表示最大約束取值。

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

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

(10)

2.4.2 平滑優(yōu)化規(guī)劃路徑輸出

從路徑路線序列的第二個(gè)節(jié)點(diǎn)開(kāi)始，若連續(xù)兩個(gè)節(jié)點(diǎn)存在一致的移動(dòng)方向，則認(rèn)為這兩個(gè)節(jié)點(diǎn)為冗余節(jié)點(diǎn)，可以刪除該節(jié)點(diǎn)，并更新路徑點(diǎn)的序列。按照順序依次遍歷所有的路徑點(diǎn)，最終得出起點(diǎn)、轉(zhuǎn)折點(diǎn)以及終點(diǎn)的路徑序列。具體的平滑優(yōu)化輸出流程如圖4所示。

圖4 路徑平滑優(yōu)化流程圖

通過(guò)計(jì)算獲得規(guī)劃優(yōu)化路徑，在移動(dòng)機(jī)器人r路徑規(guī)劃優(yōu)化過(guò)程中，采用評(píng)價(jià)函數(shù)的最小節(jié)點(diǎn)作為優(yōu)化節(jié)點(diǎn)并將該節(jié)點(diǎn)存入路徑列表當(dāng)中，直到優(yōu)化至目標(biāo)節(jié)點(diǎn)為止[12]，由此則可以完成對(duì)機(jī)器人移動(dòng)路徑的優(yōu)化分析。

3 仿真對(duì)比實(shí)驗(yàn)

為了驗(yàn)證本文機(jī)器人移動(dòng)路徑優(yōu)化方法的有效性，進(jìn)行仿真對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)過(guò)程中設(shè)立傳統(tǒng)方法作為實(shí)驗(yàn)的對(duì)比方法。由于操作機(jī)器人實(shí)際移動(dòng)的成本高，且操作過(guò)程復(fù)雜，因此此次驗(yàn)證實(shí)驗(yàn)借助計(jì)算機(jī)仿真技術(shù)，通過(guò)構(gòu)建仿真環(huán)境以及安裝硬件設(shè)備等步驟，在仿真環(huán)境下對(duì)優(yōu)化方法進(jìn)行驗(yàn)證。最終通過(guò)對(duì)移動(dòng)路徑與移動(dòng)時(shí)間等參數(shù)的對(duì)比，得出優(yōu)化方法的有效性。

3.1 構(gòu)建仿真環(huán)境

在進(jìn)行實(shí)驗(yàn)時(shí)，利用計(jì)算機(jī)仿真技術(shù)搭建所需的仿真環(huán)境，仿真環(huán)境的計(jì)算機(jī)參數(shù)為：CPU Intel Core2 Duo，內(nèi)存32GB，編譯工具M(jìn)ATLAB8.0。選擇機(jī)器人移動(dòng)的仿真環(huán)境，測(cè)量仿真環(huán)境的大小尺寸，并將實(shí)驗(yàn)中機(jī)器人移動(dòng)的環(huán)境數(shù)據(jù)輸入到路徑規(guī)劃顯示界面當(dāng)中。如圖5所示。

圖5 路徑規(guī)劃顯示界面

假設(shè)隨機(jī)分布的環(huán)境障礙物，以相同的標(biāo)識(shí)標(biāo)記在移動(dòng)環(huán)境中。選擇MobileRobots出廠的Pioneer3-DX型號(hào)的機(jī)器人作為實(shí)驗(yàn)對(duì)象，將機(jī)器人的相關(guān)數(shù)據(jù)輸入到仿真環(huán)境當(dāng)中。圖6為機(jī)器人虛擬環(huán)境仿真圖。

圖6 機(jī)器人虛擬環(huán)境仿真圖

通過(guò)路徑規(guī)劃顯示界面，采用本文方法將Pioneer3-DX型號(hào)機(jī)器人在有障礙物的空間中進(jìn)行最短路徑規(guī)劃，淺色部分為障礙物，圖7為避開(kāi)障礙物的路徑圖。

圖7 避開(kāi)障礙物的最短路徑圖

根據(jù)圖7可知，采用本文基于A*改進(jìn)算法可以有效避開(kāi)障礙物后，再沿著全局最短路徑前進(jìn)達(dá)到目標(biāo)點(diǎn)，實(shí)現(xiàn)最短路徑規(guī)劃。

3.2 實(shí)驗(yàn)過(guò)程

在實(shí)驗(yàn)環(huán)境下，將本文基于A*改進(jìn)算法的機(jī)器人移動(dòng)路徑優(yōu)化規(guī)劃方法設(shè)置為實(shí)驗(yàn)方法，將傳統(tǒng)的路徑規(guī)劃方法、基于A*算法的機(jī)器人移動(dòng)路徑規(guī)劃方法當(dāng)做對(duì)比方法。利用三種規(guī)劃方法首先分析仿真環(huán)境，設(shè)立實(shí)驗(yàn)中機(jī)器人的起始點(diǎn)與終止點(diǎn)。在仿真機(jī)器人上安裝傳感器，在機(jī)器人的移動(dòng)過(guò)程中每當(dāng)與障礙物發(fā)生碰撞，便記錄一次撞擊系數(shù)。與此同時(shí)，記錄機(jī)器人的移動(dòng)路徑長(zhǎng)度以及移動(dòng)時(shí)間。

3.3 實(shí)驗(yàn)對(duì)比結(jié)果與分析

通過(guò)仿真實(shí)驗(yàn)得出對(duì)比方法與實(shí)驗(yàn)方法輸出的路徑界面如圖8所示。

圖8 路徑輸出結(jié)果對(duì)比

從圖8中的輸出結(jié)果可以看出，經(jīng)過(guò)優(yōu)化的機(jī)器人移動(dòng)路徑更加平滑，在移動(dòng)過(guò)程中可以與障礙物保持安全距離。

建立一個(gè) 200 ×200 的柵格環(huán)境模型，每個(gè)柵格邊長(zhǎng)為 1m，起點(diǎn) S 坐標(biāo)為(3，4)，終點(diǎn) G 坐標(biāo)為(195，190)，如圖9 所示。

圖9 復(fù)雜環(huán)境模型

通過(guò)復(fù)雜環(huán)境模型對(duì)移動(dòng)時(shí)間、移動(dòng)路徑長(zhǎng)度以及撞擊次數(shù)、轉(zhuǎn)彎次數(shù)進(jìn)行記錄，得出表1中的實(shí)驗(yàn)對(duì)比結(jié)果。

從表中的數(shù)據(jù)可以看出，本文基于A*改進(jìn)算法的機(jī)器人移動(dòng)路徑優(yōu)化規(guī)劃方法，其路徑長(zhǎng)度比其它兩種方法的路徑長(zhǎng)度節(jié)省約46米，在時(shí)間上也節(jié)省了約19分鐘。經(jīng)過(guò)計(jì)算發(fā)現(xiàn)，與其它兩種路徑規(guī)劃方法相比，本文優(yōu)化方法的路徑轉(zhuǎn)彎次數(shù)和撞擊次數(shù)均出現(xiàn)了較大的降低，明顯優(yōu)于其它兩種方法，表明本文利用A*改進(jìn)算法進(jìn)行機(jī)器人移動(dòng)路徑優(yōu)化，能夠獲取較好的成果。

4 結(jié)束語(yǔ)

機(jī)器人學(xué)研究中，路徑規(guī)劃一直是廣受關(guān)注的研究熱點(diǎn)之一。本文將A*改進(jìn)算法用于機(jī)器人移動(dòng)路徑優(yōu)化規(guī)劃中，并通過(guò)實(shí)驗(yàn)驗(yàn)證了所提方法的有效性，結(jié)果表明，所提方法能夠較好的完成機(jī)器人路徑規(guī)劃，節(jié)省時(shí)間和成本，且且能夠減輕機(jī)器人在移動(dòng)過(guò)程中的消耗，具有較強(qiáng)的應(yīng)用價(jià)值。