基于柵格法的移動機器人路徑規(guī)劃研究

蔣浩+楊子江+儲旭+孫卓犖

摘要：在環(huán)境已知或易于獲得的前提下，利用柵格法對環(huán)境進行建模，建立機器人定位的數(shù)學模型，并對機器人的路徑規(guī)劃算法問題進行分析，最后介紹兩種優(yōu)化的路徑搜索算法。

關(guān)鍵詞：路徑規(guī)劃；柵格法；機器人定位；優(yōu)化算法

0引言

移動機器人在現(xiàn)代生產(chǎn)生活中扮演著日益重要的角色，在制造業(yè)、服務(wù)業(yè)中的應(yīng)用給人們的生活帶來了極大的便利[1]。移動機器人的路徑規(guī)劃問題始終是研究的熱點和難點，所謂機器人路徑規(guī)劃，是指在已知、部分已知或未知工作環(huán)境信息的情況下，機器能夠按照設(shè)定的任務(wù)要求，依據(jù)自身或全局傳感器獲得的數(shù)據(jù)信息，對自身位置以及當前環(huán)境進行辨識，通過相應(yīng)的算法，自主規(guī)劃出從起始點到達目標點的最優(yōu)路徑，同時要滿足安全、無碰撞等性能指標。

移動機器人的路徑規(guī)劃主要由環(huán)境建模、路徑搜索兩部分組成。路徑規(guī)劃的方法有很多，通常根據(jù)其所適用的工作環(huán)境的不同劃分為全局路徑規(guī)劃方法和局部路徑規(guī)劃方法。全局路徑規(guī)劃多用于工作環(huán)境已知的情況，典型方法有柵格法和拓撲法等；局部路徑規(guī)劃則常用于未知環(huán)境下移動方案設(shè)計，常用方法有模糊邏輯法、人工勢場法、神經(jīng)網(wǎng)絡(luò)算法等[2]。本文采用柵格法進行環(huán)境建模，并基于此介紹一些常用的路徑搜索算法。

1移動機器人定位

機器人移動動作主要為前進，后退，左轉(zhuǎn)，右轉(zhuǎn)。借助編碼器和陀螺儀，對基于雙驅(qū)動移動的機器人模型運動分析如圖 1 所示[3]（假設(shè)車輪不打滑、車身為剛體）：

式（1）、（2）中：W 為兩輪間距，D 為兩輪直徑，θ 為絕對坐標機器人的走向，S 為兩個位置機器人的移動距離，x 為橫坐標，y 為縱坐標，a 為編碼器轉(zhuǎn)一圈的脈沖數(shù)，ml 為左輪編碼器返回的脈沖數(shù)，mr 為右輪編碼器返回的脈沖數(shù)。左、右編碼器讀出返回的脈沖數(shù) ml 和 mr，陀螺儀讀取 θ+ θ 的角度值，上式即為相對定位的坐標計算公式。

2柵格法

在路徑規(guī)劃問題中，需要將機器人當作質(zhì)點來處理，以減少運算；描述障礙物時需要考慮一定的安全距離，這個安全距離與移動機器人的尺寸相關(guān)；由于移動機器人是在一個二維平面空間里運動，不需要考慮障礙物的高度信息。在已知環(huán)境基礎(chǔ)上，由于很容易得到全局坐標系，采用柵格法進行環(huán)境建模是最為適用的。柵格法路徑規(guī)劃一般分為三個步驟[4]：

（1）建立模型：它把移動機器人所在的二維平面空間劃分為一些列大小相同的矩形柵格。地圖中，供機器人移動的方向有八個，如圖 2 所示。柵格大小的確定是柵格法的首要問題，障礙物表示的精確程度跟柵格大小成正比關(guān)系，但柵格過于精細時，需要耗費大量的存儲空間，并影響處理速度。因此要考慮機器人尺寸、精度等多方面因素。在全局坐標系下進行柵格化，給每一個柵格標記序號，從開始進行標記，且每個柵格的中心點都有相應(yīng)的坐標，如圖 3 所示：

在規(guī)劃柵格后，需要將其轉(zhuǎn)換為坐標系中的點。第 A 個柵格的坐標為：

{ = /2 + % × （3） = D / 2 + [A/COL] ×

式（3）中 為每個柵格的寬度，D 為每個柵格的高度。ROW 為每一行的柵格數(shù)，COL 為每一列的柵格數(shù)。利用對機器人定位獲得的數(shù)據(jù)，通過一定的計算，也可得到機器人所處的柵格號。

（2）生成障礙物地圖：柵格模型建立完成后，將開始對障礙物的位置進行相關(guān)檢測，并根據(jù)障礙物的位置確定所對應(yīng)柵格地圖中的序號，然后進行修改對應(yīng)序號的柵格值，并將不包含障礙物的那部分柵格歸為自由柵格，包障礙物的那部分柵格歸為障礙物柵格。考慮到障礙物的形狀不規(guī)則，人為對障礙物的標記做一下定義：①在兩個障礙物之間的距離小于機器人尺寸時，合并成一個障礙物；②進行柵格處理時，需要進行擴大處理，將擁有部分障礙物的柵格全部標記。為方便記錄，我們將有障礙物的地方標記為1，無障礙物的地方標記為0。示意圖如下：

標記后就會形成集合可表示的障礙物群集。

（3）最優(yōu)路徑規(guī)劃：即尋找一條滿足設(shè)計要求的機器人能夠連續(xù)自由、無碰撞移動的柵格道路。已有很多路徑規(guī)劃算法可供使用，如蟻群算法、人工勢場法、遺傳算法、快速隨機樹等。

3兩種路徑搜索算法優(yōu)化

一、柵格法與遺傳算法的結(jié)合遺傳算法[5][Genetic Algorithms] 是當代人工智能科學的一個重要研究分支，是一種模擬達爾文遺傳選擇過程中的計算模型。它是按照基因遺傳學原理而實現(xiàn)的一種迭代過程的隨機搜索算法。遺傳算法具有智能性，智能表現(xiàn)在自組織、自適應(yīng)和自學習的能力； 遺傳算法具有并行性， 一是內(nèi)含并行性， 二是搜尋對同一問題的最優(yōu)解上，可以利用若干計算機同時進行搜索計算。在激光導航定位儀的應(yīng)用中，全局坐標系的建立以及障礙物的描述都變得相對容易。利用硬件測量環(huán)境信息，通過柵格法完成對環(huán)境進行建模以及障礙物的柵格表示，然后利用遺傳算法高并行處理全的優(yōu)勢作為路徑優(yōu)化和搜索，最終獲得最優(yōu)路徑。

二、柵格法與蟻群算法的結(jié)合蟻群算法[4][Ant Colony Algorithm]，簡稱 ACA）的思想來自于對蟻群覓食行為

的探索，每個螞蟻覓食時都會在走過的道路上留下一定濃度的信息素，相同時間內(nèi)最短的路徑上由于螞蟻遍歷的次數(shù)多而信息素濃度高，加上后來的螞蟻在選擇路徑時會以信息素濃度為依據(jù)，起到正反饋作用，因此信息素濃度高的最短路徑很快就會被發(fā)現(xiàn)。算法通過迭代來模擬蟻群覓食的行為達到目的。具有良好的全局優(yōu)化能力、本質(zhì)上的并行性、易于用計算機實現(xiàn)等優(yōu)點，但計算量大、易陷入局部最優(yōu)解。在傳統(tǒng)的蟻群算法中，有效路徑規(guī)定為能夠從起點到達終點的單向路徑，限制了蟻群間的協(xié)調(diào)作用。為提升搜索效率，可在柵格法基礎(chǔ)上使用兩組螞蟻進行雙向搜索的方法來構(gòu)建最優(yōu)路徑。雙向搜索過程中，兩個規(guī)模相同的蟻群分別從起點和終點出發(fā)，會出現(xiàn)尋優(yōu)起點方向不同的兩只螞蟻相遇（包含同時相遇和不同時通過同一點兩種情況），通過結(jié)合兩只相遇的螞蟻各自攜帶的不同的內(nèi)在搜尋信息，連接它們所行走的路徑的方法構(gòu)造成為一條可行的路徑。

4結(jié)束語

本文利用相對定位方法為移動機器人的路徑規(guī)劃提供了思路。對柵格法進行了較為詳細的說明，同時介紹了基于柵格法的遺傳算法和蟻群算法的優(yōu)化實現(xiàn)，具有一定的參考價值。隨著科研的深入發(fā)展，柵格法會在路徑規(guī)劃中得到越來越多的應(yīng)用。

參考文獻：

[1]蔡自興，郭璠. 中國工業(yè)機器人發(fā)展的若干問題[J]. 機器人技術(shù)與應(yīng)用，2013，（03）：9-12.

[2]張廣林，胡小梅，等. 路徑規(guī)劃算法及其應(yīng)用綜述 [J] 現(xiàn)代機械，2011（5）：85-89

[3]尹力偉，梅志千，謝保春，等. 基于 MRDS 的清潔機器人室內(nèi)路徑規(guī)劃算法的仿真實現(xiàn)[J]機電工程，2014， 31（11）：1505-1506

[4]周磊. 改進蟻群算法在機器人路徑規(guī)劃中的應(yīng)用研究[D].華東理工大學碩士學位論文，2012：20-21

[5]朱天宇.移動機器人路徑規(guī)劃的研究[D].重慶大學碩士學位論文，2014：25-31