畢業(yè)設計--amigo機器人路徑規(guī)劃研究與實現(xiàn)

1、<p><b>　　畢業(yè)設計（論文）</b></p><p><b>　　目 錄</b></p><p><b>　　摘 要1</b></p><p>　　ABSTRACT1</p><p><b>　　一、 緒論3</b><

2、/p><p><b>　?。ㄒ唬┮?</b></p><p>　?。ǘ┭芯勘菊n題的背景和意義3</p><p>　　（三）課題研究現(xiàn)狀和發(fā)展趨勢4</p><p>　?。ㄋ模┍菊撐年U述內(nèi)容及論文的大體結(jié)構(gòu)4</p><p>　　二、移動機器人模型介紹5</p><p&

3、gt;　?。ㄒ唬?先鋒3系列機器人平臺介紹5</p><p>　　1. Amigo機器人硬件系統(tǒng)5</p><p>　　2. Amigo機器人軟件系統(tǒng)6</p><p>　?。ǘ┫蠕h3系列機器人工作原理6</p><p>　　1. Amigo機器人的C-S關(guān)系6</p><p>　　2. Amigo機器人的

4、通訊7</p><p>　　3． Amigo機器人的任務周期8</p><p>　?。ㄈ┮苿訖C器人的坐標系9</p><p>　　三、 基于柵格法的路徑規(guī)劃研究11</p><p>　?。ㄒ唬┏Ｓ寐窂揭?guī)劃算法11</p><p>　　1. 基于幾何構(gòu)造的路徑規(guī)劃方法11</p><p&

5、gt;　　2． 基于模糊邏輯的路徑規(guī)劃方法11</p><p>　　3． 基于神經(jīng)網(wǎng)絡的路徑規(guī)劃方法11</p><p>　　4． 基于人工勢場的路徑規(guī)劃方法12</p><p>　　（二）柵格法簡介12</p><p>　?。ㄈ〇鸥衲Ｐ驮O計13</p><p>　　1．柵格地圖設計13</p>

6、;<p>　　2．柵格之間可行性和優(yōu)先性的確定14</p><p>　　3．路徑選擇概率14</p><p>　?。ㄈ┧惴枋?4</p><p>　　1． 算法思想14</p><p><b>　　2．算法流程15</b></p><p>　　四、仿真實驗及結(jié)論17&

7、lt;/p><p>　?。ㄒ唬┧惴ㄐ阅芊治?7</p><p>　?。ǘ?實驗仿真驗證17</p><p><b>　?。ㄈ┙Y(jié)論18</b></p><p>　　五、總結(jié)于展望19</p><p><b>　?。ㄒ唬┛偨Y(jié)19</b></p><p

8、><b>　?。ǘ┱雇?9</b></p><p><b>　　參考文獻20</b></p><p><b>　　摘 要</b></p><p>　　路徑規(guī)劃問題是移動機器人技術(shù)研究的重要問題之一，是關(guān)于機器人人工智能問題的一個重要方面，路徑規(guī)劃的任務是在機器人的工作環(huán)境中按要求規(guī)劃出

9、一條最優(yōu)的可行路徑。本文主要闡述機器人在靜態(tài)已知環(huán)境下的路徑規(guī)劃問題。</p><p>　　本文綜述了移動機器人的國內(nèi)外研究現(xiàn)狀，Amigo機器人多線程工作原理，無線網(wǎng)絡連接方式，探討了路徑規(guī)劃的算法實現(xiàn)問題，首先對常用算法做簡單的介紹，然后詳細介紹柵格網(wǎng)絡搜索算法，最后通過仿真實驗，完成了在沒有障礙物和存在多種障礙物的情況下的仿真驗證，并對結(jié)果進行分析，仿真結(jié)果表明，該算法能夠成功地在各種復雜程度不同的環(huán)境里規(guī)

10、劃出一條近似最優(yōu)的路徑，證明了算法的有效性。</p><p>　　關(guān)鍵詞：移動機器人，路徑規(guī)劃，柵格搜索法</p><p><b>　　ABSTRACT</b></p><p>　　Path planning is an important problem in mobile robot research，it is also an impor

11、tant aspect of artificial intelligence robot. The path planning task in robot work environment is to plan out an optimal feasible path. This thesis focuses on the robot path planning in a static known environment. </

12、p><p>　　In the first two chapters, the research status of the mobile robot, Amigo robot works principle in multi-threading, and the wireless network mode are introduced respectively. Various path planning algor

13、ithms are analyzed in Chapter 3. First a brief introduction of the path planning algorithms is given and then grid network search algorithm is discussed in detail. Finally, simulation experiments are conducted for the gr

14、id search algorithm in circumstances with obstacles and without obstacle. Simu</p><p>　　Key words: Mobile robots, Path planning, Grid search algorithm</p><p><b>　　一、 緒論</b></p>

15、<p><b>　?。ㄒ唬┮?lt;/b></p><p>　　移動機器人作為一門綜合學科, 近年來才發(fā)展起來，它代表了機電一體化的最高成就，集中了計算機、電子、自動控制、機械、以及人工智能等多學科最新研究成果。移動機器人集動態(tài)決策與規(guī)劃、環(huán)境感知、行為控制與執(zhí)行等多種功能于一體，它的應用前景廣闊，在民用中的物料搬運上以及防核污染、掃雷排險、軍事偵察等很多方面都有應用，到目前世界上

16、很多國家都高度重視對移動機器人的研究。</p><p>　　如今人們愈來愈多的重視對移動機器人的研究，主要是由于機器人可以幫助人類完成目前人類無法獨立完成的工作，尤其在危險、惡劣的環(huán)境中甚至于在目前人類不可到達的環(huán)境中；同時應用移動機器人還可以降低生產(chǎn)成本, 提高生產(chǎn)力,提高生產(chǎn)效率。移動機器人的應用將會越來越廣泛的滲透到國計民生的諸多領域, 隨著機器人研究及智能化程度的提高,將會具有更廣闊的市場前景。</

17、p><p>　?。ǘ┭芯勘菊n題的背景和意義</p><p>　　隨著科學技術(shù)的快速發(fā)展，像人工智能技術(shù)、集成電路技術(shù)、傳感器技術(shù)</p><p>　　等學科發(fā)展迅速，這使得機器人學這一由多學科交叉而形成的學科也進入一個嶄新的發(fā)展階段。社會各界對移動機器人的研究高度重視，移動機器人發(fā)展迅速。當今移動機器人技術(shù)發(fā)展的主要特點表現(xiàn)為:一是只要求機器人在某種程度上具有自主處理

18、問題的能力，而不再不要求機器人具有像人類一樣的高智能，對機器人智能定位有了更加符合理性的標準；二是在機器人的研究中采用了許多新技術(shù)、新方法，比如虛擬現(xiàn)實、神經(jīng)網(wǎng)絡、高速度的并行處理機、傳感器融合等技術(shù)，機器人研究重點正在不斷地發(fā)生轉(zhuǎn)變，不斷地取得新的突破。</p><p>　　未來機器人將向著高度自動化和智能化的方向發(fā)展，在不需要人的參與下完成各種任務，由于機器人工作于自然環(huán)境中，必將遇到各種障礙物，為實現(xiàn)目標必

19、不可少的便是壁障和路徑規(guī)劃問題。要求機器人能夠?qū)崿F(xiàn)自主確定便捷和安全的行動路線。移動機器人路徑規(guī)劃是機器人研究領域的一個重要的問題，這被描述為：給出了一個移動機器人的環(huán)境（環(huán)境的移動機器人視覺系統(tǒng)，或其他方式等），一個起始點和一個期望的終止點，移動機器人的路徑規(guī)劃是基于一個特定的任務要求（最短路徑，最小能量消耗或使用的時間短等）尋求一條可行路徑，能夠成功實現(xiàn)目標。 </p><p>　　路徑規(guī)劃在移動機器人導航技

20、術(shù)中占有極其重要的地位，他是移動機器人智能化程度的重要標志，是移動機器人完成各項任務的安全保障。移動機器人的路徑規(guī)劃算法的深入研究，可以繼續(xù)提高導航性能和智能水平，并促進了移動機器人的進一步發(fā)展。</p><p>　　（三）課題研究現(xiàn)狀和發(fā)展趨勢</p><p>　　在20世紀70年代人們便開始機器人路徑規(guī)劃的研究，目前人們對路徑規(guī)劃問題研究仍然十分活躍。在國家計劃的支持下，國內(nèi)重點大學和

21、研究機構(gòu)都投入了大量的人力和相關(guān)的移動機器人領域一個研究資源。在移動機器人的導航和定位、互動技術(shù)的體系結(jié)構(gòu)、信息融合技術(shù)、智能化技術(shù)等方面的研究取得了大量的成果。隨著科學技術(shù)的不斷發(fā)展，移動機器人的路徑規(guī)劃問題研究發(fā)展迅速，已經(jīng)取得了很大進展。但仍舊存在一些問題，在以下方面需要作進一步研究： 1)局部路徑規(guī)劃與全局路徑規(guī)劃的有效結(jié)合；2)多傳感器信息融合的引入；3)智能算法引入路徑規(guī)劃；4)基于慎思/反應混合式的路徑規(guī)劃；5)多智能移動

22、機器人的路徑規(guī)劃。</p><p>　　（四）本論文闡述內(nèi)容及論文的大體結(jié)構(gòu)</p><p>　　本文主要研究移動機器人在靜態(tài)已知環(huán)境下尋求最優(yōu)路徑問題，采用的機器人為先鋒系列的Amigo作為研究對象。</p><p>　　首先講述了國內(nèi)外對于移動機器人的研究，以及以后移動機器人的發(fā)展趨勢，分析了路徑規(guī)劃在移動機器人研究中的重要地位，以及世界各國對于此的研究現(xiàn)狀，在

23、此基礎上，提出本論文所提基于柵格搜索法的移動機器人路徑規(guī)劃算法，即本課題研究的背景和意義。</p><p>　　然后介紹了本研究所涉及的一些基礎知識，主要包括本文所采用的Amigo機器人的軟硬件特性，軟件開發(fā)平臺的使用，以及Amigo機器人的工作原理。</p><p>　　最后介紹了路徑規(guī)劃常用算法，詳細介紹了柵格搜索法路徑規(guī)劃問題，并借助仿真軟件進行仿真。對仿真結(jié)果作進行分析。</

24、p><p>　　本論文各章節(jié)內(nèi)容如下：</p><p>　　第一章為文章綜述，講述了移動機器人的國內(nèi)外研究現(xiàn)狀，論文選題的背景與意義，以及本論文的結(jié)構(gòu)。</p><p>　　第二章為基礎部分，主要圍繞著Amigo機器人展開敘述，講述了機器人軟硬件特性，和計算機建立連接方法以及多線程工作原理。</p><p>　　第三章講述了路徑規(guī)劃的算法實現(xiàn)問題

25、，首先對常用算法做簡單的介紹，然后詳細介紹柵格網(wǎng)絡搜索算法。</p><p>　　第四章為實驗驗證，主要為仿真實驗，完成了在沒有障礙物和存在多種障礙物的情況下的仿真驗證，并對結(jié)果進行分析，得出結(jié)論。</p><p>　　第五章對本論文作總結(jié)，對算法的優(yōu)缺點進行分析，提出進一步完善的內(nèi)容。</p><p>　　二、移動機器人模型介紹</p><p&

26、gt;　?。ㄒ唬?先鋒3系列機器人平臺介紹</p><p>　　先鋒3系列機器人是Mobile Robots生產(chǎn)的自主式室內(nèi)移動機器人。先鋒3系列機器人比大多數(shù)機器人小，如圖2-1，但是在它的內(nèi)部高度集成了智能移動機器人技術(shù)，而它的能力完全可以與那些體積笨重價格昂貴的設備相匹敵。</p><p>　　圖2-1 先鋒3系列機器人Amigo外形及物理尺寸</p><p>

27、;　　1. Amigo機器人硬件系統(tǒng)</p><p>　　Amigo機器人體積較小，靈活方便，功能強大，為廣大學校用于研究開發(fā)。其長為33cm，寬為28cm，高為13cm，重為3.6Kg，可載重30kg，最大平移速度750mm/sec，最大旋轉(zhuǎn)速度300deg/sec。它提供了內(nèi)嵌SH2微控制器，負責底層數(shù)據(jù)處理和命令執(zhí)行，如獲取傳感器信息，小車位置信息等等，具有更快捷的處理速度和更強大的擴展能力。</p&

28、gt;<p>　　Amigo機器人具有一個萬向輪和兩個驅(qū)動輪，其中萬向輪僅僅起到支撐作用，而驅(qū)動功能和導向作用則由驅(qū)動輪來完成。每個驅(qū)動輪配有一個電機，每臺電機配備高分辨率光學編碼器，可以準確定位，速度測量，以及更先進的計算。ARCOS 驅(qū)動服務器使用一個普通的比例－微分－積分（PID）控制系統(tǒng)來調(diào)節(jié)電機驅(qū)動器的PWM脈沖寬度以平滑電機的運動。電機運行周期為50微秒（20KHZ）；脈沖寬度由0-500表示0-100％的占空

29、比周期。ARCOS 驅(qū)動服務器每5毫秒便會根據(jù)車輪編碼器的反饋再次計算并且調(diào)整機器人的運動軌跡。</p><p>　　此外該機器人還配備有8個聲吶測距裝置，其分布如圖2-2所示，在前方不均勻的分布著6個聲吶裝置，用于檢測前方、左前方、左方、右前方、右方的障礙物，在后方有兩個聲吶裝置用于檢測后方的障礙區(qū)。Amigo機器人的聲吶測量距離的范圍為10cm（6 英寸）至5m，這決定于測量速度。</p>&l

30、t;p>　　圖2-2 Amigo 聲吶分布</p><p>　　2. Amigo機器人軟件系統(tǒng)</p><p>　　機器人控制器軟件系統(tǒng)包括ARIA 和ARNL，機器人客戶端軟件系統(tǒng)包括MobileSim、MobileEyes、Mapper3等等。</p><p>　　Aria軟件功能強大，使用方便，簡單，因而具有更強的適應性，可用于先鋒系列機器人的運動控制。

31、Aria基于C++編程語言，為面向?qū)ο蟮模歉叨塑浖帉懙睦硐脒x擇，Aria由Mobile Robots開發(fā)，作為應用程序接口（API），非常方便Amigo機器人應用程序的開發(fā)與研究。ARNL軟件開發(fā)包主要是用于Mobile Robots機器人平臺定位及自主導航。</p><p>　　移動機器人的仿真軟件種類較多，各有優(yōu)缺點，Amigo機器人使用的是操作簡單的MobileSim仿真軟件。MobileSim工作界面

32、簡單，容易上手。我們在進行機器人仿真之前首先應打開MobileSim仿真軟件，這樣才能和機器人建立連接，由于MobileSim主要加載工作環(huán)境地圖和機器人，并實時顯示機器人的運動軌跡，因此應先繪制地圖。借助Mapper3繪圖軟件，可以方便地繪制機器人的工作環(huán)境地圖，需要注意的是，為方便實物仿真，我們在繪制機器人的真實工作環(huán)境時，必須做到準確無誤，否則實驗結(jié)果就會出現(xiàn)偏差。MobileEyes是更為高級的仿真軟件，主要應用于機器人的導航與

33、定位，本文關(guān)于移動機器人的路徑規(guī)劃就用到了上述軟件，特別是MobileEyes仿真軟件。</p><p>　?。ǘ┫蠕h3系列機器人工作原理</p><p>　　1. Amigo機器人的C-S關(guān)系</p><p>　　機器人本體上包括所有的傳感器、執(zhí)行器、電源等附屬設備及SH2單片機構(gòu)成下位機，一般我們使用的PC作為上位機。上/下位機構(gòu)成Client/Server結(jié)

34、構(gòu)。如圖2-3所示。</p><p>　　圖2-3 Amigo機器人C-S結(jié)構(gòu)</p><p>　　下位機負責執(zhí)行底層任務，包括機器人運動指令，獲取傳感器信息，計算各種位置信息，驅(qū)動附件設備以及處理上位機發(fā)出的控制指令等等，上位機即主機主要執(zhí)行應用層次的任務，包括障礙物的檢測與避障，傳感器耦合，定位、導航等等。當上位機和下位機建立連接之后，上位機可以仿真一個網(wǎng)絡上的機器人服務器，或者直接利

35、用獲得的信息控制機器人。</p><p>　　2. Amigo機器人的通訊</p><p>　　Amigo機器人與計算機系統(tǒng)連接方式主要有三種（如圖2-4）：一是通過串行口建立連接，該方法連接簡單，只需要一條串口連接線，即可實現(xiàn)機器人與計算機系統(tǒng)連接，但受到串口線的限制，計算機對機器人控制不方便；二是通過無線網(wǎng)絡建立連接，機器人和計算機之間需要借助無線路由器建立連接，進而可實現(xiàn)對機器人的遠

36、程控制，該方法應用較多；第三，車載計算機系統(tǒng)，機器人配備了一個嵌入式計算機主板，主板上有一個傳統(tǒng)的鍵盤，鼠標，顯示器接口，0/100M自適應網(wǎng)卡，4個COM口，2個USB口，PC104/PC104+擴展總線等設備。</p><p>　　圖2-4 Amigo機器人連接方式</p><p>　　Aria幫助用戶實現(xiàn)上位機的應用程序與下位機Firmware的通訊以及應用程序與下位機Firmwar

37、e的通訊，其中也包含了對下位機附件設備的通訊和管理。ArRobot類是Aria的核心，管理著Client與Server的通訊周期、讀取機器人平臺的運行狀態(tài)信息、觸發(fā)通訊周期內(nèi)的特定任務等工作內(nèi)容。</p><p>　　機器人的通訊即為建立ArRobot實例與機器人平臺OS（也即Firmware）的連接關(guān)系。這里的機器人平臺包含了機器人本體以及從機器人本體上的AUX端</p><p>　　口

38、、模擬/數(shù)字IO擴展出的附件設備（例如：聲吶、抓持器、PTZ云臺、先鋒</p><p>　　手臂、羅盤等）。ArRobot實例可以與機器人Firmware建立連接，也可以與仿真器建立連接，建立連接的過程由ArRobotConnector類實現(xiàn)。</p><p>　　ArRobotConnector建立ArRobot的連接時，首先會嘗試通過本地TCP端口建立與MobileSim的連接，如果不

39、成功則會進一步建立與Firmware的本地串口（COM1）連接。</p><p>　　機器人Client與Server之間通訊傳輸?shù)幕締挝皇欠舷蠕h數(shù)據(jù)協(xié)議的數(shù)據(jù)包，基本過程：Client發(fā)送指令數(shù)據(jù)包（ Command Packets ）給機器人，來控制機器人平臺。Server端則將機器人狀態(tài)信息數(shù)據(jù)包（ Server Information Packets ，即“SIPs”) 發(fā)給Client端，應用程序解

40、讀分析機器人狀態(tài)信息進行計算。</p><p>　　SIPs包含了機器人及附件設備的狀態(tài)信息，每100ms由Server向Client發(fā)送一次。SIPs包含的具體內(nèi)容有機器人的當前位置以及預期位置、平移和旋轉(zhuǎn)速度、聲吶信息、電池電壓、模擬及數(shù)字I/O狀態(tài)信息等。這些數(shù)據(jù)信息通過ArRobot的狀態(tài)映射表來實現(xiàn)存儲和使用。</p><p>　　3． Amigo機器人的任務周期</p&g

41、t;<p>　　SIPs是以一定的周期發(fā)送的，Aria每收到一個SIP就會觸發(fā)一個ArRobot任務處理周期。每個任務周期處理的任務有：SIP數(shù)據(jù)包解析、傳感器數(shù)據(jù)處理、機器人行為處理、狀態(tài)映射、用戶任務處理。任務周期如圖2-5</p><p>　　圖2-5 Amigo機器人任務周期</p><p>　?。ㄈ┮苿訖C器人的坐標系</p><p>　　移

42、動機器人要完成避障，實現(xiàn)路徑規(guī)劃，首先需對移動機器人有一個準確的定位，這就要用到移動機器人的坐標系問題。常用的移動機器人坐標系有兩種，分絕對坐標系和相對坐標系，一般使用絕對坐標系。而Amigo機器人使用聲吶測距，光電編碼器確定位置，所測得位置信息多為相對于小車的，為相對坐標，因此需要進行坐標變化。由光電編碼器的值計算得到是移動機器人的內(nèi)部坐標位置，因此是相對坐標系中的位置。內(nèi)部坐標系如圖2-6所示</p><p>

43、;　　圖2-6 Amigo機器人內(nèi)部坐標系</p><p>　　Amigo機器人在默認情況下，其初始位置坐標和角度值均為零，即絕對坐標系和相對坐標系重合，當前移動機器人的位置信息就是相對于絕對坐標系的位置信息。移動機器人時刻處于運動當中，即相對坐標系一直在發(fā)生變化，而絕對坐標系始終保持不變，因此大多說情況，機器人相對坐標和絕對坐標不同，簡單坐標變換情況如圖2-7所示。</p><p>　　

44、前面介紹了移動機器人坐標變換的簡單情況，當機器人在運動時，有時候情況并非這么簡單，而是如圖2-8所示，兩個坐標系的X軸以及Y軸并非分別對應平行的，而是兩個坐標系的對應坐標軸軸之間存在著一個夾角θ， A點在局部坐標系的坐標值（x1，y1），A點與全局坐標系的X軸的夾角β，機器人在全局坐標中的坐標值為（x0，y0），由三角變換得:βθ﹢</p><p>　　圖2-7 機器人坐標系統(tǒng)簡單不重合情況 圖2-8

45、機器人復雜坐標變換</p><p>　　因此，A點在絕對坐標系下的坐標值（x，y）為：</p><p><b>　　x=x0+ </b></p><p><b>　　y=y0 + </b></p><p>　　三、 基于柵格法的路徑規(guī)劃研究</p><p>　?。ㄒ唬┏Ｓ寐窂?/p>

46、規(guī)劃算法</p><p>　　1. 基于幾何構(gòu)造的路徑規(guī)劃方法</p><p>　　圖3-1基于幾何構(gòu)造的路徑規(guī)劃</p><p>　　如圖3-1所示，要求順利從起始點運動到目標點，并能在成功避開障礙物的前提下，選擇出最短路徑。我們可以連接起始點和障礙物的頂點，再連接障礙物的頂點和目標點，障礙物的不同頂點對應了不同的路徑，從這些有限的路徑中選出的最短路徑就是我們要求

47、的最優(yōu)路徑。</p><p>　　2． 基于模糊邏輯的路徑規(guī)劃方法</p><p>　　在基于邏輯推理的路徑規(guī)劃方法的基礎上進行改進：</p><p>　　1、傳感器的一次測量值與多個狀態(tài)對應，每個狀態(tài)有一個隸屬度對應。</p><p>　　2、根據(jù)模糊推理結(jié)果確定行為。</p><p>　　3． 基于神經(jīng)網(wǎng)絡的路徑規(guī)

48、劃方法</p><p>　　圖3-2基于神經(jīng)網(wǎng)絡的路徑規(guī)劃</p><p>　　如圖3-2所示：首先按照上圖的方法，轉(zhuǎn)化為優(yōu)化問題。然后用神經(jīng)網(wǎng)絡表示懲罰函數(shù)。最后根據(jù)E遞減推導出相應的反向傳播算法用于神經(jīng)網(wǎng)絡的訓練。</p><p>　　4． 基于人工勢場的路徑規(guī)劃方法</p><p>　　圖3-4基于人工勢能場的路徑規(guī)劃</p>

49、;<p>　　如圖3-4所示，障礙物對機器人施加排斥力，目標點對機器人施加吸引力，合力形成勢場，機器人移動就像球從山上滾下來一樣，機器人在合力作用下向目標點移動。</p><p><b>　?。ǘ〇鸥穹ê喗?lt;/b></p><p>　　對于給定的機器人工作任務，其工作環(huán)境已知。工作環(huán)境已經(jīng)知道寬度，長度，分別是W，L, 網(wǎng)格尺度（長度，寬度）均是b，那

50、么網(wǎng)格的數(shù)為（L／b）×（W／b）環(huán)境Map由柵格構(gòu)成：Map＝{mapi, mapi=0或1} i為整數(shù)</p><p>　　當Map＝1 時表示該柵格為障礙區(qū)域，Map＝0 時表示該柵格為自由區(qū)域。</p><p>　　柵格搜索方法路徑規(guī)劃，就是將路徑規(guī)劃問題轉(zhuǎn)化成約束最優(yōu)化問題，首先將機器人的工作環(huán)境分解成一系列的柵格單元，然后采用某種算法，在被分解的單元中搜索

51、機器人的最優(yōu)路徑。通常我們把柵格劃分成許許多多小的柵格，以最小的柵格為基本元素，并對其賦予值0或者1，當小柵格落在障礙物區(qū)時為1，</p><p>　　小柵格落在非障礙物區(qū)時為0。柵格數(shù)據(jù)簡單，標準，相鄰柵格之間的關(guān)系也就簡單化了。利用上述思想，繪制出機器人的基于柵格的工作環(huán)境地圖。</p><p>　?。ㄈ〇鸥衲Ｐ驮O計</p><p><b>　　1

52、．柵格地圖設計</b></p><p>　　根據(jù)機器人的大小情況以及機器人工作環(huán)境的面積，將機器人的工作環(huán)境分解成一系列的柵格單元，以最小的柵格為基本元素。注意我們進行柵格劃分時，總是假定機器人的工作環(huán)境是矩形的，從而把柵格等分成許許多多的小矩形，這樣有利于對柵格進行編號。一般可以對柵格進行順序編號，如圖3-1所示，白色的方格表示機器人在此處對應的工作環(huán)境下可自由運動，而黑色方塊的柵格表示存在禁止運動

53、。</p><p>　　圖3-1用柵格法表示機器人場地</p><p>　　為了編程處理的方便，我們需要對柵格做出一些規(guī)定，將柵格分為中間柵格和邊界柵格，主要是用于判斷柵格位置。當機器人處于中間柵格時，下一步可以分別向東南、東、東北、北、西北、西、西南、南八個方位進行搜索；對柵格編號之后，求出當前位置柵格序號與這上述8個方位的序號的差值。通過建立數(shù)組的形式來描述下一步將要搜索的具體柵格的方

54、位：</p><p>　　Next_oritation[i]={9,-1,-11,-10,-9,1,11,10} 1i8</p><p>　　式子中數(shù)組元素順序?qū)诓煌姆轿?，其順序依此為東南、東、東北、北、西北、西、西南、南。</p><p>　　對于邊界上的柵格，其可行方位減少，再加上障礙物區(qū)，可行方位就更加少，為方便起見，對其做另行處理。如圖3-1中

55、的柵格51，其下一步可以選擇的柵格表示為：</p><p>　　Next_oritation[i]={10,9,-1,-11} 1i3</p><p>　　說明其下一步的搜索方向可以為向下、右下、右、右上。</p><p>　　2．柵格之間可行性和優(yōu)先性的確定 </p><p>　　當機器人處于當前柵格時，它下一步可選擇的方位可能有很

56、多，因此柵格搜索存在搜索方位優(yōu)先性的問題。以圖3-1為例，規(guī)定機器人的任務為機器人有當前柵格1運行到柵格100，要求路徑最優(yōu)，且不能碰到障礙物，根據(jù)柵格搜索法，需要一個柵格、一個柵格的逐次搜索，對于第一條路徑的確定，即選擇第二個柵格，原則上是向著指向目標的方向，同時還要考慮到障礙物，這樣就可以對8個方向的優(yōu)先性做出判斷，然后給予每個方位一個優(yōu)先值，當起始柵格變化時，優(yōu)先值發(fā)生變化。</p><p><b&g

57、t;　　3．路徑選擇概率</b></p><p>　　定義路徑選擇的概率公式為：</p><p>　　式子中u表示當前位置柵格，V表示u的臨近8個方位中完全可行方位的集合，v為V的元素，式中、由下式?jīng)Q定: </p><p>　　Next_oritation[]=u-v，vV 為相應的概率</p><p>　　Next_

58、oritation[]=u-k，kV 為相應的概率</p><p><b>　?。ㄈ┧惴枋?lt;/b></p><p><b>　　1． 算法思想</b></p><p>　　利用柵格搜索方法規(guī)劃機器人路徑時，為了使路徑盡可能的最優(yōu)化，我們對算法做了改進，增加了正反饋機制，使路徑不斷地逼近于最優(yōu)化。所謂的正反饋

59、，就是在程序執(zhí)行時，增加一個反饋量。對于每一個可行路徑，其經(jīng)過的節(jié)點之間增加一個量ε，借助于ε關(guān)聯(lián)程度的反饋，來搜索到一條近似最優(yōu)路徑。對于第i-1條路徑中柵格u和v的關(guān)聯(lián)程度的更新方程為：</p><p>　　隨著某一節(jié)點u與節(jié)點v之間關(guān)聯(lián)程度的增加，則由該節(jié)點u選擇下一結(jié)點時，節(jié)點v被選擇通過的概率也會增加，與此同時若從某一個節(jié)點u選擇v通過的數(shù)目呈現(xiàn)增加趨勢，那么節(jié)點v和節(jié)點u之間關(guān)聯(lián)程度也會增加，則關(guān)聯(lián)程

60、度和通過的路徑數(shù)目之間形成正反饋機制，使得所選擇的路徑不斷地趨向于最優(yōu)路徑。</p><p><b>　　2．算法流程</b></p><p>　　基于柵格模型的路徑規(guī)劃算法執(zhí)行過程如圖3-2所示</p><p>　　圖3-2路徑搜索流程圖</p><p><b>　　四、仿真實驗及結(jié)論</b>&l

61、t;/p><p><b>　?。ㄒ唬┧惴ㄐ阅芊治?lt;/b></p><p>　　在柵格的搜索上，采用概率計算的方法，保證公平公正，由當前節(jié)點選擇下一結(jié)點時，都是按照比例概率，因此保證了在可行方向上的每一個柵格都有可能被選到。在路徑選擇上，我們采用分組的方法，將搜索過程分為m組，對每一組都可能會得到n條路徑，找到n中路徑中最短的路徑，然后利用它修改相鄰柵格之間的關(guān)聯(lián)性，不需要

62、每次尋找到一條可行路徑時，就修改障礙物地圖，這樣會照成某些節(jié)點關(guān)聯(lián)程度增長過快，被選擇的概率過大，使得路徑相對集中，路徑尋優(yōu)出現(xiàn)死區(qū)，對多樣性的選取路徑不利，無法找到最優(yōu)路徑。只有保證可行方向上的每個節(jié)點都有可能被選到，保證路徑選擇的多樣性，才能保證搜索到的路徑是最優(yōu)路徑。</p><p>　　（二） 實驗仿真驗證</p><p>　　本文進行的仿真實驗是借助于仿真軟件MobileSim和

63、Mobileeyes進行的。程序編寫是基于C++語言，利用Microsoft Visual Studio 2010建立項目，并生成可執(zhí)行文件。</p><p>　　機器人工作環(huán)境的繪制借助Mapper3軟件，繪制完地圖后就可以用仿真軟件進行仿真。然后啟動MobileSim仿真軟件，并加載繪制的環(huán)境地圖，此時便可以運行Visual Studio 2010 生成的可執(zhí)行文件，然后打開MobileEyes，自動建立連接

64、，進入仿真界面，選擇Tour Goals。仿真結(jié)果如圖3-3所示。</p><p><b>　　圖3-3 路徑規(guī)劃</b></p><p>　　從上圖的仿真結(jié)果可以看出，Amigo機器人規(guī)劃出了一條由起始點到目標點</p><p>　　的可行路徑，并沿著這條路徑順利到達目標點，不過在前進過程中，為了實現(xiàn)路徑最優(yōu)，機器人會對原來的路徑進行修改，直

65、到到達目標點為止。通過仿真分析，驗證了該算法的可行性。</p><p><b>　　結(jié)論</b></p><p>　　通過仿真驗證，該算法實現(xiàn)了以下功能：第一，在沒有障礙物的地圖工作</p><p>　　環(huán)境中，Amigo機器人能夠迅速的完成路徑規(guī)劃任務。第二，當在地圖工作環(huán)境中添加各種障礙物時，Amigo能迅速的規(guī)劃出一條路徑，但在行進中，為

66、了使路徑最優(yōu)，Amigo機器人會實時對路徑做出調(diào)整。此外，當目標點發(fā)生變化時，Amigo能夠迅速的由當前點規(guī)劃出到達目標點的路徑。</p><p>　　未能實現(xiàn)的功能：不能夠在障礙物位置變化的情況下由初始點成功到達目標點，即該算法未能實現(xiàn)動態(tài)路徑規(guī)劃。</p><p><b>　　五、總結(jié)于展望</b></p><p><b>　?。?/p>

67、一）總結(jié)</b></p><p>　　本文主要研究了在環(huán)境已知條件下，利用柵格搜索的方法對機器人的路徑進行規(guī)劃的問題。鑒于實驗室提供的機器人為Amigo，我們主要分析了關(guān)于Amigo機器人的路徑規(guī)劃問題。Amigo機器人使用特定的開發(fā)軟件Aria，Aria提供了Amigo機器人編程的一整套應用程序接口，因此我們主要是借助于Aria的API進行編程。在算法上，其思想是一樣的，在把算法轉(zhuǎn)化成程序時，同樣需

68、要借助于軟件自帶的一些庫文件，最后再利用軟件進行仿真驗證算法的可行性，通過仿真分析，我們可以斷定，柵格搜索方法對Amigo機器人的路徑規(guī)劃完全可行。</p><p><b>　　（二）展望</b></p><p>　　本次畢業(yè)設計的要求是：在Amigo機器人工作環(huán)境已知的條件下，規(guī)定環(huán)境中某一目標點，要求該機器人能夠規(guī)劃出一條路徑，是該機器人能夠在環(huán)境中的任意一點成功

69、到達目標點，且該路徑具有最優(yōu)性。用到的柵格法并非路徑規(guī)劃的最佳選擇，還有各種先進、更為智能的算法，也可運用到路徑規(guī)劃算法的設計上。即使是同樣運用柵格法，不同的考慮方向、不同的編程思想，也會有不同的效果。</p><p>　　還需完善的地方：（1）柵格法只是大體上選擇出了最優(yōu)路徑，但并不能在一個柵格到下一個臨近的柵格之間選擇最短路徑。柵格法將一個柵格作為路程的最小單位，很明顯，兩個相鄰的柵格之間也存在最短路徑。2）

70、不能夠?qū)崿F(xiàn)動態(tài)避障，即障礙物為靜止的。因為所用柵格法，第一步就要求對所給地圖劃分柵格，相應的障礙物的位子和形狀早已為給定。（3）機器人由可行路徑到達目標點的時間過長。（4）Amigo機器人無法避開體積較小的障礙物。</p><p>　　在算法上的問題，可以用更為高級的算法來取代柵格法，以彌補柵格法的不足。因為硬件原因出現(xiàn)的問題，如不能感應出體積偏小的障礙物，可以用更為高級精確的傳感器。比方說用激光傳感器，它的定位

71、效果比聲吶傳感器好，測量速度也比聲吶傳感器快。這樣不僅能感應更小的障礙物，也能讓移動機器人選擇路徑的時間縮短，減少整個路徑規(guī)劃的時間。</p><p><b>　　參考文獻</b></p><p>　　[1] 于金霞，王璐.未知環(huán)境中移動機器人自定位技術(shù).北京:電子工業(yè)出版社, 2011.</p><p>　　[2] 蔡自興.機器人學.北京

72、:清華大學出版社,2000.</p><p>　　[3] 李團結(jié).機器人技術(shù).電子工業(yè)出版社,2009.</p><p>　　[4] 蔡自興,劉健勤.面向21世紀的智能機器人技術(shù)[J].機器人技術(shù)與應用，1998(6).</p><p>　　[5] Pioneer 3 Operation Manual.</p><p>　　[6] m

73、igoBot Technical Manual.</p><p>　　[7] 張穎,吳成東,原寶龍.機器人路徑規(guī)劃方法綜述[J].控制工程,2003,5(10).</p><p>　　[8] 于紅斌，李孝安.基于柵格法的機器人快速路經(jīng)規(guī)劃．微電子學與計算機．2005（6）．</p><p>　　[9] 魯慶．基于柵格法的移動機器人路徑規(guī)劃研究．電腦與信息技術(shù)．

74、2007（6）．</p><p>　　[10] 張捍東，董保華，岑豫皖，鄭睿. 柵格編碼新方法在機器人路徑規(guī)劃中的應用.華中科技大學學報，2007.</p><p>　　[11] 郝博，秦麗娟，姜明洋.基于改進遺傳算法的移動機器人路徑規(guī)劃方法研究[J]. 計算機工程與科學，2010</p><p>　　[12] 李人厚譯，自主移動機器人導論，西安交通大學出版社，20

75、06.</p><p>　　[13] 杜軍平譯，人工智能機器人導論，電子工業(yè)出版社，2004.</p><p>　　[14] 戴博，移動機器人路徑規(guī)劃技術(shù)的研究現(xiàn)狀與展望，控制工程，2005</p><p>　　[15] 鄭利君，基于超聲傳感器的機器人路徑規(guī)劃和避障算法的研究，浙江理工大學學位論文，2007</p><p>　　[16] 黃興

76、華, 基于改進人工勢場法的移動機器人路徑規(guī)劃研，重慶大學，2010</p><p>　　[17] 孫秀云，移動機器人的路徑規(guī)劃及其運動控制器研究，山東大學，2005</p><p>　　[18] 張曉麗,基于微分進化算法的機器人路徑規(guī)劃方法,大連理工大學，2006</p><p>　　[19] 張洪亮，多機器人編隊技術(shù)的研究與應用，北京工業(yè)大學，2009</p