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

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

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

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

0引言

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

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

1移動機(jī)器人定位

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

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

2柵格法

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

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

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

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

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

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

標(biāo)記后就會形成集合可表示的障礙物群集。

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

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

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

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

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

4結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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