鄭美英，董 航

（遼寧工程職業(yè)學(xué)院，遼寧 鐵嶺 112008）

在機(jī)器人設(shè)計(jì)中，路徑規(guī)劃是最基礎(chǔ)也是最重要的因素之一，故對(duì)其算法研究尤為重要。本文將對(duì)傳統(tǒng)路徑規(guī)劃算法與智能路徑規(guī)劃算法進(jìn)行詳細(xì)研究，并利用MATLAB軟件進(jìn)行算法仿真實(shí)驗(yàn)，驗(yàn)證求解路徑規(guī)劃問(wèn)題的可行性，最后通過(guò)對(duì)兩種算法進(jìn)行的比較分析，確定最優(yōu)算法。

一、機(jī)器人傳統(tǒng)路徑規(guī)劃算法

（一）障礙物分類(lèi)

機(jī)器人設(shè)計(jì)傳統(tǒng)路徑規(guī)劃策略首先需要對(duì)環(huán)境中的障礙物進(jìn)行分類(lèi)，然后再根據(jù)障礙物的不同類(lèi)型設(shè)計(jì)對(duì)應(yīng)路徑規(guī)劃策略。在具體環(huán)境中，障礙物信息由機(jī)器人測(cè)距傳感器實(shí)時(shí)采集[1]。本文將障礙物信息分為以下四種基本類(lèi)型（如圖1所示）。

圖1 障礙物4種基本類(lèi)型示意圖

圖中DSL、DSR、DHL、DHR分別表示機(jī)器人車(chē)體左側(cè)、車(chē)體右側(cè)、車(chē)頭左側(cè)、車(chē)頭右側(cè)方向上與障礙物的距離。障礙物四種基本類(lèi)型說(shuō)明如下：

A類(lèi)型：表示在機(jī)器人車(chē)體的前方有障礙物。

B類(lèi)型：表示機(jī)器人車(chē)體的前方與車(chē)體右側(cè)有障礙物。

C類(lèi)型：表示機(jī)器人車(chē)體的前方與車(chē)體左側(cè)有障礙物

D類(lèi)型：表示機(jī)器人的前方、車(chē)體左側(cè)、車(chē)體右側(cè)都有障礙物。

（二）路徑規(guī)劃策略分析

在具體環(huán)境中，障礙物可能有多種類(lèi)型，但都可概括為上述四種基本類(lèi)型中的一種或幾種類(lèi)型的不同組合，所以需要分別對(duì)這四種基本類(lèi)型障礙物的路徑規(guī)劃策略進(jìn)行分析。當(dāng)機(jī)器人四個(gè)方向檢測(cè)不到障礙物時(shí)，沒(méi)有路徑規(guī)劃行為，機(jī)器人直行。

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

本研究機(jī)器人的轉(zhuǎn)彎方式為兩主動(dòng)輪同時(shí)反向旋轉(zhuǎn)帶動(dòng)履帶運(yùn)動(dòng)從而實(shí)現(xiàn)機(jī)器人轉(zhuǎn)彎，因此轉(zhuǎn)彎中心即為機(jī)器人底盤(pán)的幾何中心。測(cè)得底盤(pán)幾何中心到履帶頂點(diǎn)距離約為200mm，該頂點(diǎn)即為最易先與障礙物發(fā)生碰撞的危險(xiǎn)點(diǎn)。由于在停車(chē)過(guò)程中受到慣性的影響，機(jī)器人依然會(huì)向前運(yùn)動(dòng)一段距離，經(jīng)過(guò)多次實(shí)驗(yàn)測(cè)得此距離約為50mm。為了保險(xiǎn)起見(jiàn)，機(jī)器人的安全距離選為300mm。

1．A類(lèi)型障礙物路徑規(guī)劃策略分析

假設(shè)滿足DHL≤300mm或DHR≤300mm，且DSL≥300mm且DSR≥300mm，就斷定機(jī)器人此刻處于A類(lèi)型障礙物環(huán)境中。

2．B類(lèi)型或C類(lèi)障礙物路徑規(guī)劃策略分析

假設(shè)滿足DHL≤300mm或DHR≤300mm，且DSL≥300mm且DSR≤300mm，就斷定機(jī)器人此刻處于B類(lèi)型障礙物環(huán)境中?；蛘邼M足DHL≤300mm或DHR≤300mm，且DSL≤300mm且DSR≥300mm，就斷定機(jī)器人此刻處于C類(lèi)型障礙物環(huán)境中。由于B類(lèi)型障礙物的路徑規(guī)劃策略與C類(lèi)型類(lèi)似，只是障礙物的分布導(dǎo)致機(jī)器人轉(zhuǎn)彎方向相反，所以此處以C類(lèi)型障礙物為例討論路徑規(guī)劃策略，B類(lèi)型可以此類(lèi)推。

3．D類(lèi)型障礙物路徑規(guī)劃策略分析

假設(shè)滿足DHL≤300mm或DHR≤300mm，且DSL≤300mm且DSR≤300mm，就斷定機(jī)器人此刻處于D類(lèi)型障礙物環(huán)境中。

二、基于蟻群算法的機(jī)器人路徑規(guī)劃

（一）蟻群算法數(shù)學(xué)模型

20世紀(jì)90年代初，意大利得迪里戈博士團(tuán)隊(duì)通過(guò)長(zhǎng)期對(duì)自然界螞蟻覓食問(wèn)題的研究提出了一種新型智能算法——蟻群算法（Ant Colony Algorithm，AG）[4]。他們?cè)谟^察蟻群覓食過(guò)程時(shí)發(fā)現(xiàn)，螞蟻在搜尋食物時(shí)，總是邊搜尋邊在路徑上分泌一種信息素，其它螞蟻通過(guò)識(shí)別該信息素來(lái)選擇距離更短的路徑。

（二）蟻群路徑規(guī)劃算法流程

蟻群路徑規(guī)劃算法的運(yùn)算流程如圖2所示。

圖2 蟻群路徑規(guī)劃算法流程圖

（三）仿真實(shí)驗(yàn)與分析

研究蟻群算法α、m、β、ρ、Q、Ncmax等主要參數(shù)的最優(yōu)配置至關(guān)重要，但這些參數(shù)的配置方法至今未能形成完整的理論體系，所以只能借鑒仿真實(shí)驗(yàn)的統(tǒng)計(jì)數(shù)據(jù)[5]。

本文參數(shù)設(shè)置為α=1、β=15、Q=0.95、m=30、Ncmax=20。設(shè)置起點(diǎn)柵格為柵格環(huán)境左下角（柵格序號(hào)為0），目標(biāo)點(diǎn)柵格為柵格環(huán)境右上角（柵格序號(hào)為399）。

圖3所示為MATLAB仿真結(jié)果，規(guī)劃出的路徑用線條表示。由圖可知機(jī)器人能尋找到一條從起點(diǎn)出發(fā)避開(kāi)障礙物到達(dá)目標(biāo)點(diǎn)的全局最優(yōu)路徑，同時(shí)此路徑也為該柵格環(huán)境下所能找到的最短路徑，路徑長(zhǎng)度為32.382 m。

圖3 蟻群算法最優(yōu)路徑

圖4為蟻群算法收斂結(jié)果。由圖4可知最短路徑長(zhǎng)度在迭代7次后收斂于最優(yōu)路徑長(zhǎng)度32.382 m，算法運(yùn)行所消耗的時(shí)間為8.515 s。仿真結(jié)果驗(yàn)證了蟻群算法解決機(jī)器人智能路徑規(guī)劃問(wèn)題的可行性。

圖4 蟻群算法收斂結(jié)果

三、基于遺傳算法的機(jī)器人路徑規(guī)劃

（一）遺傳算法數(shù)學(xué)模型

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

（二）遺傳路徑規(guī)劃算法流程

遺傳路徑規(guī)劃算法的運(yùn)算流程如圖5所示。

圖5 遺傳路徑規(guī)劃算法流程圖

（三）仿真實(shí)驗(yàn)與分析

與蟻群算法類(lèi)似，研究遺傳算法M、T、Pm、Pc等主要參數(shù)的最優(yōu)配置至關(guān)重要，但這些參數(shù)的配置方法至今未能形成完整的理論體系，所以只能借鑒仿真實(shí)驗(yàn)的統(tǒng)計(jì)數(shù)據(jù)[8]。

在仿真實(shí)驗(yàn)前，對(duì)種群的各項(xiàng)參數(shù)設(shè)置如下：種群規(guī)模M=60，最大進(jìn)化代數(shù)T=20，交叉概率Pc=0.8，變異概率Pm=0.2。設(shè)置起點(diǎn)為柵格環(huán)境左下角圓圈處（柵格序號(hào)為0），目標(biāo)點(diǎn)為右上角方格處（柵格序號(hào)為399）。

圖6所示為MATLAB仿真結(jié)果，規(guī)劃出的路徑用線條表示。由圖可知機(jī)器人能尋找到一條從起點(diǎn)出發(fā)避開(kāi)障礙物到達(dá)目標(biāo)點(diǎn)的全局最優(yōu)路徑，同時(shí)此路徑也為該柵格環(huán)境下所能找到的最短路徑，路徑長(zhǎng)度為30.971 m。

圖6 遺傳算法最優(yōu)路徑

圖7為遺傳算法收斂結(jié)果，由圖可知最短路徑長(zhǎng)度在迭代10次后收斂于最優(yōu)路徑長(zhǎng)度30.971 m，算法運(yùn)行所消耗的時(shí)間為16.402 s。仿真結(jié)果驗(yàn)證了遺傳算法解決機(jī)器人智能路徑規(guī)劃問(wèn)題的可行性。

圖7 遺傳算法收斂結(jié)果

四、三種算法對(duì)比分析

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

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

由表1可知在最短路徑長(zhǎng)度方面，遺傳算法比蟻群算法所獲得的路徑更短，說(shuō)明遺傳算法更顯智能；在獲得最優(yōu)路徑比例方面，遺傳算法也遠(yuǎn)高于蟻群算法說(shuō)明遺傳算法搜索穩(wěn)定性更好。通過(guò)實(shí)驗(yàn)比較，遺傳算法比蟻群算法具有更智能、更穩(wěn)定的優(yōu)點(diǎn)，因此選用遺傳算法來(lái)解決機(jī)器人的路徑規(guī)劃問(wèn)題。

根據(jù)設(shè)計(jì)要求，機(jī)器人應(yīng)具有路徑規(guī)劃功能，此處可將遺傳算法算法應(yīng)用于解決機(jī)器人自主運(yùn)動(dòng)過(guò)程中的路徑規(guī)劃問(wèn)題。基于遺傳算法的機(jī)器人智能路徑規(guī)劃流程如圖8所示。

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

機(jī)器人首先向上位機(jī)發(fā)送定位請(qǐng)求，由定位系統(tǒng)對(duì)機(jī)器人當(dāng)前的位置和位姿進(jìn)行初始標(biāo)定。在獲得機(jī)器人位置和位姿信息后，通過(guò)獲取起始點(diǎn)和目標(biāo)點(diǎn)及障礙物等信息，調(diào)用遺傳算法進(jìn)行全局路徑規(guī)劃，分析規(guī)劃結(jié)果，調(diào)用機(jī)器人運(yùn)行程序開(kāi)始控制機(jī)器人行進(jìn)。若機(jī)器人檢測(cè)到有障礙物，則進(jìn)入避障處理子程序，最后判斷機(jī)器人是否已經(jīng)到達(dá)目標(biāo)點(diǎn)。若是，則本次路徑規(guī)劃任務(wù)結(jié)束；否則需要重新定位機(jī)器人位置信息，再依次進(jìn)行以上過(guò)程，直到到達(dá)目標(biāo)點(diǎn)。

要實(shí)現(xiàn)基于遺傳算法智能路徑規(guī)劃還需要能獲取環(huán)境信息的傳感器如視覺(jué)傳感器、激光傳感器，由于缺少此類(lèi)傳感器，暫無(wú)法獲取和處理環(huán)境信息。在將來(lái)的研究當(dāng)中將進(jìn)一步完善機(jī)器人環(huán)境信息獲取和處理能力以實(shí)現(xiàn)基于遺傳算法的智能路徑規(guī)劃。因此本文最終選擇傳統(tǒng)路徑規(guī)劃算法來(lái)解決機(jī)器人自主運(yùn)動(dòng)過(guò)程中的路徑規(guī)劃問(wèn)題。

五、結(jié)語(yǔ)

本文首先對(duì)傳統(tǒng)路徑規(guī)劃算法進(jìn)行了詳細(xì)介紹，然后對(duì)智能路徑規(guī)劃算法研究現(xiàn)狀進(jìn)行了簡(jiǎn)單介紹，又著重分別對(duì)蟻群算法與遺傳算法的原理進(jìn)行了闡述，并敘述了運(yùn)用這兩種算法求解路徑規(guī)劃問(wèn)題的流程，同時(shí)運(yùn)用MATLAB軟件進(jìn)行了算法仿真實(shí)驗(yàn)，驗(yàn)證了蟻群算法與遺傳算法求解路徑規(guī)劃問(wèn)題的可行性。接著從最短路徑長(zhǎng)度和最優(yōu)路徑比例兩個(gè)方面對(duì)兩種算法進(jìn)行了比較分析。發(fā)現(xiàn)遺傳算法比蟻群算法具有更智能、更穩(wěn)定的優(yōu)點(diǎn)。