動態(tài)環(huán)境下移動機(jī)器人路徑規(guī)劃研究

【摘 要】本論文主要任務(wù)是針對移動機(jī)器人技術(shù)領(lǐng)域中的動態(tài)環(huán)境下路徑規(guī)劃問題進(jìn)行深入研究。在動態(tài)結(jié)構(gòu)化環(huán)境中，通過設(shè)計(jì)不同的控制策略（算法），避開運(yùn)動的障礙物，最終為移動機(jī)器人規(guī)劃出一條從起始點(diǎn)到目標(biāo)點(diǎn)的可行路徑。然后基于MATLAB和VC++可視化編程語言，開發(fā)了基于遺傳算法的機(jī)器人的路徑規(guī)劃仿真系統(tǒng)。并在動態(tài)環(huán)境下開展了移動機(jī)器人的仿真實(shí)驗(yàn)，分析了實(shí)驗(yàn)結(jié)果。

【關(guān)鍵詞】移動機(jī)器人；動態(tài)環(huán)境；遺傳算法；路徑規(guī)劃

移動機(jī)器人路徑規(guī)劃就是移動機(jī)器人從初始出發(fā)點(diǎn)，在一個(gè)有障礙物的環(huán)境中，找到一條從初始點(diǎn)到目標(biāo)點(diǎn)的無碰撞最優(yōu)路徑。本文在分析了目前各種路徑規(guī)劃方法優(yōu)缺點(diǎn)的基礎(chǔ)上，采用遺傳算法來解決動態(tài)環(huán)境下移動機(jī)器人的路徑規(guī)劃問題。首先針對路徑規(guī)劃問題的特點(diǎn)，對遺傳算法的各個(gè)環(huán)節(jié)進(jìn)行了細(xì)致的分析，包括地圖環(huán)境的建立，染色體的表示和編碼、適應(yīng)度函數(shù)的設(shè)計(jì)，遺傳操作算子的設(shè)計(jì)，算法參數(shù)的分析和選取等。然后基于MATLAB和VC++可視化編程語言，開發(fā)了基于遺傳算法的機(jī)器人的路徑規(guī)劃仿真系統(tǒng)。并在動態(tài)環(huán)境下開展了移動機(jī)器人的仿真實(shí)驗(yàn)，分析了實(shí)驗(yàn)結(jié)果。

一、遺傳算法

遺傳算法是基于自然選擇和遺傳學(xué)原理的搜索算法。它將“適者生存”這一基本的達(dá)爾文進(jìn)化理論引入串結(jié)構(gòu)，并且在串之間進(jìn)行有組織但又隨機(jī)的信息交換。伴隨著信息交換的進(jìn)行，優(yōu)良的品質(zhì)被逐漸保留并加以組合，從而不斷產(chǎn)生出更佳的個(gè)體。遺傳算法的基本思想是：在問題的求解過程中，把搜索空間視為遺傳空間，把問題的每一個(gè)可能解看作一個(gè)個(gè)體，個(gè)體里面有基因，所有的個(gè)體組成群體。依據(jù)某種評價(jià)標(biāo)準(zhǔn)對每一個(gè)個(gè)體進(jìn)行評價(jià)，計(jì)算其適應(yīng)度，并根據(jù)適應(yīng)度對每一個(gè)個(gè)體進(jìn)行選擇、變異和交叉操作，淘汰適應(yīng)度小的個(gè)體，留下適應(yīng)度大的染色體，從而得到新的群體，新的群體優(yōu)于舊的群體。對新的群體再施加自然選擇法則，結(jié)果一代勝過一代，直到達(dá)到預(yù)定的優(yōu)化標(biāo)準(zhǔn)。以上就是遺傳算法的基本原理。

二、移動機(jī)器人路徑規(guī)劃建模

本文在對移動機(jī)器人路徑規(guī)劃時(shí)采用柵格法來表示，即用大小相同的柵格來劃分機(jī)器人的工作空間。首先，移動機(jī)器人通過勢場生成一個(gè)障礙物地圖，然后機(jī)器人利用障礙物地圖來規(guī)劃一條安全的路徑，該路徑是使機(jī)器人由起點(diǎn)運(yùn)動到終點(diǎn)的一條無碰路徑。障礙物的位置一旦被傳感系統(tǒng)如視覺傳感器探測到，則賦給與那些位置相對應(yīng)的柵格一定的初始值，并根據(jù)規(guī)定的減函數(shù)向相鄰柵格傳播，這樣就得到一張障礙物地圖。在地圖中，用“0”來代表開放的空間，“1”代表障礙物或墻壁，“8”為起始點(diǎn)，“5”為出口。整數(shù)表示的地圖數(shù)組如圖1所示：將環(huán)境空間劃分為獨(dú)立的柵格空間；首先將環(huán)境空間的每個(gè)柵格初始化為0；探測障礙物所占據(jù)的部分柵格；把1賦給障礙物所占據(jù)的柵格；在障礙物地圖中，被占柵格上、下、左、右的四個(gè)相鄰柵格的值neighbor通過規(guī)定的減函數(shù)decrease來計(jì)算，直到計(jì)算值小于或等于0，即neighbor [Edirection]=decrease（s，dtreclion），其中direction為0，1，2，3，表示賦值為0的左右四個(gè)相鄰柵格，s為當(dāng)前柵格的值，在屏幕上顯示的仿真效果圖如圖1～2所示：

三、基于遺傳算法的路徑規(guī)劃實(shí)現(xiàn)

（1）問題定義。本文研究的移動機(jī)器人運(yùn)動環(huán)境為二維平面空間，環(huán)境中的靜態(tài)障礙物已知，動態(tài)障礙物可以探測。這樣使得問題便于著手，有利于把重點(diǎn)放在探索遺傳算法在這類問題的實(shí)際應(yīng)用上來，為今后研究三維空間內(nèi)機(jī)器人的運(yùn)動路徑規(guī)劃打下基礎(chǔ)。本文將移動機(jī)器人視作一個(gè)質(zhì)點(diǎn)，即不考慮機(jī)器人的尺寸。本文的目標(biāo)是要在靜態(tài)環(huán)境和具有少量動態(tài)障礙物出現(xiàn)或運(yùn)動的環(huán)境里，為機(jī)器人找到一條從當(dāng)前位置到目標(biāo)位置的行動路線，要求這條路徑滿足以下條件：該路徑不與任何障礙物發(fā)生沖突；該路徑應(yīng)盡可能短；該路徑應(yīng)與障礙物保持一定的安全距離；該路徑應(yīng)盡可能平滑。（2）遺傳算子設(shè)計(jì)。優(yōu)勝劣汰是設(shè)計(jì)遺傳算法的基本思想，它應(yīng)在選擇、交叉和變異等遺傳算子中得以體現(xiàn)，并考慮到對算法效率與性能的影響。一是輪盤賭法選擇。輪盤賭法是把種群中所有個(gè)體適應(yīng)度的總和比作一個(gè)輪子的圓周，每一個(gè)個(gè)體按其適應(yīng)度的大小占輪子不同大小的扇區(qū)。輪子隨即旋轉(zhuǎn)后停在哪個(gè)扇區(qū)，對應(yīng)的個(gè)體就被選中。具體步驟如下：計(jì)算每一個(gè)個(gè)體的適應(yīng)度值f（xi）；累加所有個(gè)體的適應(yīng)度值SUM=∑f（xi），并記錄每一個(gè)個(gè)體的中間累加值S_mid；產(chǎn)生一個(gè)隨機(jī)數(shù)N，0

三是變異算子。變異運(yùn)算模擬生物在自然界中因各種偶然因素而引起的基因突變。它提供了種群中遺傳基因類型的多樣性，當(dāng)交叉操作產(chǎn)生的適應(yīng)度值不再進(jìn)化且沒有達(dá)到最優(yōu)時(shí)，就意味著算法的早熟收斂。這種現(xiàn)象的根源在于有效基因的缺損，變異操作在一定程度上克服了這種情況，有利于增加種群的多樣性。

其程序如下所示：Mutate（vector vecBits）；{for（int curBit=0；curBit

四、路徑規(guī)劃仿真研究

移動機(jī)器人的動態(tài)環(huán)境路徑規(guī)劃是個(gè)相當(dāng)困難的問題。本文所研究的動態(tài)環(huán)境限于機(jī)器人運(yùn)動空間里一直存在一個(gè)或多個(gè)不斷移動的障礙物。與A*算法進(jìn)行比較圖4（a）為A*算法的仿真結(jié)果。圖4（b）為本文所用的遺傳路徑規(guī)劃方法的仿真結(jié)果。由圖4和表1數(shù)據(jù)可得，本文所研究的路徑規(guī)劃方法具有時(shí)間短，路程優(yōu)，可視性強(qiáng)的特點(diǎn)，并能有效的實(shí)現(xiàn)路徑規(guī)劃。

本文在分析比較目前各種移動機(jī)器人路徑規(guī)劃算法的優(yōu)缺點(diǎn)的基礎(chǔ)上，對采用遺傳算法解決靜態(tài)和動態(tài)環(huán)境里路徑規(guī)劃問題的方法作了進(jìn)一步的分析研究。通過在多個(gè)復(fù)雜程度不同的環(huán)境下，分別進(jìn)行靜態(tài)和動態(tài)情況下的仿真，仿真結(jié)果表明，該算法能夠成功地規(guī)劃出近似最優(yōu)的路徑。

參 考 文 獻(xiàn)

[1]徐國華，譚民．移動機(jī)器人的發(fā)展現(xiàn)狀及其趨勢[J]．機(jī)器人技術(shù)與應(yīng)用．2001，20（2）：45～51

[2]龔進(jìn)峰．?dāng)?shù)字勢場和遺傳算法的機(jī)器人路徑規(guī)劃的方法[J]．天津大學(xué)學(xué)報(bào)．2002，10（2）：75～78

[3][美]Mat Buckland.Ai Techniques for Game Programming[J]．北京：清華大學(xué)出版社，2006

[4]趙翊捷，陳衛(wèi)東．基于地圖的移動機(jī)器人定位技術(shù)研究[D]．上海：上海交通大學(xué)．2002

[5]王仲民，岳宏．一種移動機(jī)器人全局路徑規(guī)劃新型算法[J]．機(jī)器人．2003（2）：152～155

[6]王醒策，張汝波，顧國昌．基于勢場柵格法的機(jī)器人全局路徑規(guī)劃[J]．哈爾濱工程大學(xué)學(xué)報(bào)．2003，24（4）：170～172

[7]李智軍，呂恬生．遺傳算法在自主移動機(jī)器人局部路徑規(guī)劃中的應(yīng)用[J]．機(jī)械設(shè)計(jì)．2000，12（7）： 27～28

[8]楊正華，張秋生．Visual C++游戲編程導(dǎo)學(xué)[J]．北京：清華大學(xué)出版社，2004

[9]吳濤．移動機(jī)器人避障與路徑規(guī)劃研究[D]．武漢：華中科技大學(xué)．2004