機器人路徑規(guī)劃研究與實現(xiàn)設計

1、機器人路徑規(guī)劃研究與實現(xiàn)設 計畢業(yè)設計（論文）設計（論文）題目 Amigo機器人路徑規(guī)劃研究與實現(xiàn)目錄 TOC o 1-5 h z 摘要0ABSTRACT1 HYPERLINK l bookmark0 o Current Document 一、緒論2（一）引言2（二）研究本課題的背景和意義2（三）課題研究現(xiàn)狀和發(fā)展趨勢3（四）本論文闡述內容及論文的大體結構二、移動機器人模型介紹（一）先鋒3系列機器人平臺介紹Z.Amigo機器人硬件系青2. Amigo機器人軟件系青（二）先鋒3系列機器人工作原理Amigo機器人的CS關系 TOC o 1-5 h z HYPERLINK l bookmark8 o

2、 Current Document Amigo機器人的通訐6Amigo機器人的任務周期7 HYPERLINK l bookmark10 o Current Document （三）移動機器人的坐標系8 HYPERLINK l bookmark12 o Current Document 三、基于柵格法的路徑規(guī)劃研究10（一）常用路徑規(guī)劃算法10.基于幾何構造的路徑規(guī)劃方泣10.基于模糊邏輯的路徑規(guī)劃方泣103,基于神經網(wǎng)絡的路徑規(guī)劃方泣104基于人工勢場的路徑規(guī)劃方泣11 HYPERLINK l bookmark14 o Current Document （二）柵格法簡介11（三）柵格模型設計1

3、2.柵格地圖設計.12.柵格之間可行性和優(yōu)先性的確兄13.路徑選擇概率14（三）算法描述14.算法思想14.算法流程14 HYPERLINK l bookmark36 o Current Document 四、仿真實驗及結論16（一）算法性能分析16（二）實驗仿真驗證16（三）結論17五、總結于展望18（一）總結18（二）展望18 HYPERLINK l bookmark38 o Current Document 參考文獻19路徑規(guī)劃問題是移動機器人技術研究的重要問題之一，是關于 機器人人工智能問題的一個重要方面，路徑規(guī)劃的任務是在機器人的 工作環(huán)境中按要求規(guī)劃出一條最優(yōu)的可行路徑。本文主要闡

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

5、, it is also an important 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.In the first two chapters, the research status of the mobile robot

6、, Amigo robot works principle in multi-threading, and the wireless network mode are introduced respectively. Various path planning algorithms 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.

7、Finally, simulation experiments are conducted for the grid search algorithm in circumstances with obstacles and without obstacle. Simulation results show that grid search algorithm is able to plan better path rapidly in complex environment only if the path exists and also show the effectiveness of t

8、he proposed approach.Key words: Mobile robots, Path planning, Grid search algorithm一、緒論（一）引言移動機器人作為一門綜合學科，近年來才發(fā)展起來，它代表了機電一體化的 最高成就，集中了計算機、電子、自動控制、機械、以及人工智能等多學科最 新研究成果。移動機器人集動態(tài)決策與規(guī)劃、環(huán)境感知、行為控制與執(zhí)行等多 種功能于一體，它的應用前景廣闊，在民用中的物料搬運上以及防核污染、掃 雷排險、軍事偵察等很多方面都有應用，到目前世界上很多國家都高度重視對 移動機器人的研究。如今人們愈來愈多的重視對移動機器人的研究，主要是由

9、于機器人可以幫 助人類完成目前人類無法獨立完成的工作，尤其在危險、惡劣的環(huán)境中甚至于 在目前人類不可到達的環(huán)境中；同時應用移動機器人還可以降低生產成本，提高 生產力，提高生產效率。移動機器人的應用將會越來越廣泛的滲透到國計民生的 諸多領域，隨著機器人研究及智能化程度的提高，將會具有更廣闊的市場前景。（二）研究本課題的背景和意義隨著科學技術的快速發(fā)展，像人工智能技術、集成電路技術、傳感器技術 等學科發(fā)展迅速，這使得機器人學這一由多學科交叉而形成的學科也進入一個 嶄新的發(fā)展階段。社會各界對移動機器人的研究高度重視，移動機器人發(fā)展迅 速。當今移動機器人技術發(fā)展的主要特點表現(xiàn)為:一是只要求機器人在某種

10、程度 上具有自主處理問題的能力，而不再不要求機器人具有像人類一樣的高智能， 對機器人智能定位有了更加符合理性的標準；二是在機器人的研究中采用了許 多新技術、新方法，比如虛擬現(xiàn)實、神經網(wǎng)絡、高速度的并行處理機、傳感器 融合等技術，機器人研究重點正在不斷地發(fā)生轉變，不斷地取得新的突破。未來機器人將向著高度自動化和智能化的方向發(fā)展，在不需要人的參與下 完成各種任務，由于機器人工作于自然環(huán)境中，必將遇到各種障礙物，為實現(xiàn) 目標必不可少的便是壁障和路徑規(guī)劃問題。要求機器人能夠實現(xiàn)自主確定便捷 和安全的行動路線。移動機器人路徑規(guī)劃是機器人研究領域的一個重要的問題, 這被描述為：給出了一個移動機器人的環(huán)境（

11、環(huán)境的移動機器人視覺系統(tǒng)，或 其他方式等），一個起始點和一個期望的終止點，移動機器人的路徑規(guī)劃是基于 一個特定的任務要求（最短路徑，最小能量消耗或使用的時間短等）尋求一條 可行路徑，能夠成功實現(xiàn)目標。路徑規(guī)劃在移動機器人導航技術中占有極其重要的地位，他是移動機器人 智能化程度的重要標志，是移動機器人完成各項任務的安全保障。移動機器人 的路徑規(guī)劃算法的深入研究，可以繼續(xù)提高導航性能和智能水平，并促進了移 動機器人的進一步發(fā)展。（三）課題研究現(xiàn)狀和發(fā)展趨勢在20世紀70年代人們便開始機器人路徑規(guī)劃的研究，目前人們對路徑規(guī) 劃問題研究仍然十分活躍。在國家計劃的支持下，國內重點大學和研究機構都 投入了

12、大量的人力和相關的移動機器人領域一個研究資源。在移動機器人的導 航和定位、互動技術的體系結構、信息融合技術、智能化技術等方面的研究取 得了大量的成果。隨著科學技術的不斷發(fā)展，移動機器人的路徑規(guī)劃問題研究 發(fā)展迅速，已經取得了很大進展。但仍舊存在一些問題，在以下方面需要作進 一步研究：1）局部路徑規(guī)劃與全局路徑規(guī)劃的有效結合；2）多傳感器信息融合 的引入；3）智能算法引入路徑規(guī)劃；4）基于慎思/反應混合式的路徑規(guī)劃；5）多智 能移動機器人的路徑規(guī)劃。（四）本論文闡述內容及論文的大體結構本文主要研究移動機器人在靜態(tài)已知環(huán)境下尋求最優(yōu)路徑問題，采用的機 器人為先鋒系列的Amigo作為研究對象。首先講

13、述了國內外對于移動機器人的研究，以及以后移動機器人的發(fā)展趨 勢，分析了路徑規(guī)劃在移動機器人研究中的重要地位，以及世界各國對于此的 研究現(xiàn)狀，在此基礎上，提出本論文所提基于柵格搜索法的移動機器人路徑規(guī) 劃算法，即本課題研究的背景和意義。然后介紹了本研究所涉及的一些基礎知識，主要包括本文所采用的Amigo 機器人的軟硬件特性，軟件開發(fā)平臺的使用，以及Amigo機器人的工作原理。最后介紹了路徑規(guī)劃常用算法，詳細介紹了柵格搜索法路徑規(guī)劃問題，并 借助仿真軟件進行仿真。對仿真結果作進行分析。本論文各章節(jié)內容如下：第一章為文章綜述，講述了移動機器人的國內外研究現(xiàn)狀，論文選題的背景 與意義，以及本論文的結構

14、。第二章為基礎部分，主要圍繞著Amigo機器人展開敘述，講述了機器人軟 硬件特性，和計算機建立連接方法以及多線程工作原理。第三章講述了路徑規(guī)劃的算法實現(xiàn)問題，首先對常用算法做簡單的介紹，然 后詳細介紹柵格網(wǎng)絡搜索算法。第四章為實驗驗證，主要為仿真實驗，完成了在沒有障礙物和存在多種障礙 物的情況下的仿真驗證，并對結果進行分析，得出結論。第五章對本論文作總結，對算法的優(yōu)缺點進行分析,提出進一步完善的內容。二、移動機器人模型介紹（一）先鋒3系列機器人平臺介紹先鋒3系列機器人是Mobile Robots生產的自主式室內移動機器人。先鋒3 系列機器人比大多數(shù)機器人小，如圖2-1,但是在它的內部高度集成了

15、智能移動 機器人技術，而它的能力完全可以與那些體積笨重價格昂貴的設備相匹敵。圖2-1先鋒3系列機器人Amigo外形及物理尺寸Amigo機器人硬件系統(tǒng)Amigo機器人體積較小，靈活方便，功能強大，為廣大學校用于研究開發(fā)。 其長為33cm，寬為28皿，高為13cm，重為3.6Kg，可載重30kg，最大平移速 度750mm/sec，最大旋轉速度300deg/sec。它提供了內嵌SH2微控制器，負責 底層數(shù)據(jù)處理和命令執(zhí)行，如獲取傳感器信息，小車位置信息等等，具有更快 捷的處理速度和更強大的擴展能力。Amigo機器人具有一個萬向輪和兩個驅動輪，其中萬向輪僅僅起到支撐作 用，而驅動功能和導向作用則由驅動

16、輪來完成。每個驅動輪配有一個電機，每 臺電機配備高分辨率光學編碼器，可以準確定位，速度測量，以及更先進的計 算。ARCOS驅動服務器使用一個普通的比例一微分一積分（PID）控制系統(tǒng)來 調節(jié)電機驅動器的PWM脈沖寬度以平滑電機的運動。電機運行周期為50微秒 （20KHZ）;脈沖寬度由0-500表示0-100 %的占空比周期。ARCOS驅動服務 器每5毫秒便會根據(jù)車輪編碼器的反饋再次計算并且調整機器人的運動軌跡。此外該機器人還配備有8個聲吶測距裝置，其分布如圖2-2所示，在前方 不均勻的分布著6個聲吶裝置，用于檢測前方、左前方、左方、右前方、右方的 障礙物，在后方有兩個聲吶裝置用于檢測后方的障礙區(qū)

17、。Amigo機器人的聲吶 測量距離的范圍為10cm （6英寸）至5m，這決定于測量速度。8p圖2-2 Amigo聲吶分布Amigo機器人軟件系統(tǒng)機器人控制器軟件系統(tǒng)包括ARIA和ARNL,機器人客戶端軟件系統(tǒng)包括 MobileSim、MobileEyes、Mapper3 等等。Aria軟件功能強大，使用方便，簡單，因而具有更強的適應性，可用于先 鋒系列機器人的運動控制。Aria基于C+編程語言，為面向對象的，是高端軟 件編寫的理想選擇，Aria由Mobile Robots開發(fā)，作為應用程序接口（API）， 非常方便Amigo機器人應用程序的開發(fā)與研究。ARNL軟件開發(fā)包主要是用于 Mobile

18、 Robots機器人平臺定位及自主導航。移動機器人的仿真軟件種類較多，各有優(yōu)缺點，Amigo機器人使用的是操作 簡單的MobileSim仿真軟件。MobileSim工作界面簡單，容易上手。我們在進 行機器人仿真之前首先應打開MobileSim仿真軟件，這樣才能和機器人建立連 接，由于MobileSim主要加載工作環(huán)境地圖和機器人，并實時顯示機器人的運 動軌跡，因此應先繪制地圖。借助Mapper3繪圖軟件，可以方便地繪制機器人 的工作環(huán)境地圖，需要注意的是，為方便實物仿真，我們在繪制機器人的真實 工作環(huán)境時，必須做到準確無誤，否則實驗結果就會出現(xiàn)偏差。MobileEyes是 更為高級的仿真軟件，

19、主要應用于機器人的導航與定位，本文關于移動機器人 的路徑規(guī)劃就用到了上述軟件，特別是MobileEyes仿真軟件。（二）先鋒3系列機器人工作原理Amigo機器人的C-S關系機器人本體上包括所有的傳感器、執(zhí)行器、電源等附屬設備及SH2單片機 構成下位機，一般我們使用的PC作為上位機。上/下位機構成Client/Server結 構。如圖2-3所示。ServerClient安裝了FirmwafiE 執(zhí)行底層任外wiN/unux os枇行應用層次執(zhí)仃運動強令 由里程計計算位置 壯以隹感群信息赭碼物檢測修避隙感位圖航械等 恃定制導機等（聲吶，羅盤等） 驅動附件設備（PTZ 攝像頭、TCM2等1圖2-3

20、Amigo機器人C-S結構下位機負責執(zhí)行底層任務，包括機器人運動指令，獲取傳感器信息，計算 各種位置信息，驅動附件設備以及處理上位機發(fā)出的控制指令等等，上位機即 主機主要執(zhí)行應用層次的任務，包括障礙物的檢測與避障，傳感器耦合，定位、 導航等等。當上位機和下位機建立連接之后，上位機可以仿真一個網(wǎng)絡上的機 器人服務器，或者直接利用獲得的信息控制機器人。Amigo機器人的通訊Amigo機器人與計算機系統(tǒng)連接方式主要有三種（如圖2-4）： 一是通過串 行口建立連接，該方法連接簡單，只需要一條串口連接線，即可實現(xiàn)機器人與 計算機系統(tǒng)連接，但受到串口線的限制，計算機對機器人控制不方便；二是通 過無線網(wǎng)絡建

21、立連接，機器人和計算機之間需要借助無線路由器建立連接，進 而可實現(xiàn)對機器人的遠程控制，該方法應用較多；第三，車載計算機系統(tǒng)，機 器人配備了一個嵌入式計算機主板，主板上有一個傳統(tǒng)的鍵盤，鼠標，顯示器 接口，0/100M自適應網(wǎng)卡，4個COM 口，2個USB 口，PC104/PC104+擴展總 線等設備。圖2-4 Amigo機器人連接方式Aria幫助用戶實現(xiàn)上位機的應用程序與下位機Firmware的通訊以及應用 程序與下位機Firmware的通訊，其中也包含了對下位機附件設備的通訊和管理。 ArRobot類是Aria的核心，管理著Client與Server的通訊周期、讀取機器人平 臺的運行狀態(tài)信息

22、、觸發(fā)通訊周期內的特定任務等工作內容。機器人的通訊即為建立ArRobot實例與機器人平臺OS （也即Firmware） 的連接關系。這里的機器人平臺包含了機器人本體以及從機器人本體上的AUX 端口、模擬/數(shù)字IO擴展出的附件設備（例如：聲吶、抓持器、PTZ云臺、先鋒 手臂、羅盤等）。ArRobot實例可以與機器人Firmware建立連接，也可以與仿 真器建立連接，建立連接的過程由ArRobotConnector類實現(xiàn)。ArRobotConnector建立ArRobot的連接時，首先會嘗試通過本地TCP端 口建立與MobileSim的連接，如果不成功則會進一步建立與Firmware的本地串 口（

23、COM1）連接。機器人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端，應用程序解讀分析機器人狀態(tài)信息進行計 算。SIPs包含了機器人及附件設備的狀態(tài)信息，每100ms由Server向Client 發(fā)送一次。SIPs包含的具體內容有機器人的當前位置以及預期位置、平移和旋 轉速度、聲吶信息、電池電壓、模擬及數(shù)字口。狀態(tài)信息等。這些數(shù)據(jù)信息通過

24、ArRobot的狀態(tài)映射表來實現(xiàn)存儲和使用。Amigo機器人的任務周期SIPs是以一定的周期發(fā)送的，Aria每收到一個SIP就會觸發(fā)一個ArRobot 任務處理周期。每個任務周期處理的任務有：SIP數(shù)據(jù)包解析、傳感器數(shù)據(jù)處理、 機器人行為處理、狀態(tài)映射、用戶任務處理。任務周期如圖2-5 AiKh4t Tadc圖2-5 Amigo機器人任務周期（三）移動機器人的坐標系移動機器人要完成避障，實現(xiàn)路徑規(guī)劃，首先需對移動機器人有一個準確的 定位，這就要用到移動機器人的坐標系問題。常用的移動機器人坐標系有兩種， 分絕對坐標系和相對坐標系，一般使用絕對坐標系。而Amigo機器人使用聲吶 測距，光電編碼器確

25、定位置，所測得位置信息多為相對于小車的，為相對坐標， 因此需要進行坐標變化。由光電編碼器的值計算得到是移動機器人的內部坐標 位置，因此是相對坐標系中的位置。內部坐標系如圖2-6所示Q+XFro*il+1BD圖2-6 Amigo機器人內部坐標系Amigo機器人在默認情況下，其初始位置坐標和角度值均為零，即絕對坐 標系和相對坐標系重合，當前移動機器人的位置信息就是相對于絕對坐標系的 位置信息。移動機器人時刻處于運動當中，即相對坐標系一直在發(fā)生變化，而 絕對坐標系始終保持不變，因此大多說情況，機器人相對坐標和絕對坐標不同， 簡單坐標變換情況如圖2-7所示。前面介紹了移動機器人坐標變換的簡單情況，當機

26、器人在運動時，有時候 情況并非這么簡單，而是如圖2-8所示，兩個坐標系的X軸以及Y軸并非分別 對應平行的，而是兩個坐標系的對應坐標軸軸之間存在著一個夾角仇A點在 局部坐標系的坐標值51,以），A點與全局坐標系的X軸的夾角機器人在 全局坐標中的坐標值為（X0, y0）,由三角變換得/=。+ tan色y1因此，A點在絕對坐標系下的坐標值（X, y）為:X=X 0+ x；x12 + y12 cos py =y0 + qx12 + y12 sin p三、基于柵格法的路徑規(guī)劃研究（一）常用路徑規(guī)劃算法.基于幾何構造的路徑規(guī)劃方法圖3-1基于幾何構造的路徑規(guī)劃如圖3-1所示，要求順利從起始點運動到目標點，

27、并能在成功避開障礙物 的前提下，選擇出最短路徑。我們可以連接起始點和障礙物的頂點，再連接障 礙物的頂點和目標點，障礙物的不同頂點對應了不同的路徑，從這些有限的路 徑中選出的最短路徑就是我們要求的最優(yōu)路徑。.基于模糊邏輯的路徑規(guī)劃方法在基于邏輯推理的路徑規(guī)劃方法的基礎上進行改進：1、傳感器的一次測量值與多個狀態(tài)對應，每個狀態(tài)有一個隸屬度對應。2、根據(jù)模糊推理結果確定行為。.基于神經網(wǎng)絡的路徑規(guī)劃方法圖3-2基于神經網(wǎng)絡的路徑規(guī)劃如圖3-2所示：首先按照上圖的方法，轉化為優(yōu)化問題。然后用神經網(wǎng)絡 表示懲罰函數(shù)。最后根據(jù)E遞減推導出相應的反向傳播算法用于神經網(wǎng)絡的訓 練。.基于人工勢場的路徑規(guī)劃方法

28、圖3-4基于人工勢能場的路徑規(guī)劃如圖3-4所示，障礙物對機器人施加排斥力，目標點對機器人施加吸引力， 合力形成勢場，機器人移動就像球從山上滾下來一樣，機器人在合力作用下向 目標點移動。（二）柵格法簡介對于給定的機器人工作任務，其工作環(huán)境已知。工作環(huán)境已經知道寬度， 長度，分別是W, L,網(wǎng)格尺度（長度，寬度）均是瓦那么網(wǎng)格的數(shù)為（七/ b）x ( W / b)環(huán)境Map由柵格構成：Map=mapf, mapi=0或1i為整數(shù)當Map=1時表示該柵格為障礙區(qū)域，Map=0時表示該柵格為自由區(qū)域。柵格搜索方法路徑規(guī)劃，就是將路徑規(guī)劃問題轉化成約束最優(yōu)化問題，首 先將機器人的工作環(huán)境分解成一系列的柵

29、格單元，然后采用某種算法，在被分 解的單元中搜索機器人的最優(yōu)路徑。通常我們把柵格劃分成許許多多小的柵格， 以最小的柵格為基本元素，并對其賦予值0或者1,當小柵格落在障礙物區(qū)時為 1,小柵格落在非障礙物區(qū)時為0。柵格數(shù)據(jù)簡單，標準，相鄰柵格之間的關系也就 簡單化了。利用上述思想，繪制出機器人的基于柵格的工作環(huán)境地圖。(三)柵格模型設計1 .柵格地圖設計根據(jù)機器人的大小情況以及機器人工作環(huán)境的面積，將機器人的工作環(huán)境 分解成一系列的柵格單元，以最小的柵格為基本元素。注意我們進行柵格劃分 時，總是假定機器人的工作環(huán)境是矩形的，從而把柵格等分成許許多多的小矩 形，這樣有利于對柵格進行編號。一般可以對柵

30、格進行順序編號，如圖3-1所示， 白色的方格表示機器人在此處對應的工作環(huán)境下可自由運動，而黑色方塊的柵 格表示存在禁止運動。6圖3-1用柵格法表示處理的方便，我出一些規(guī)定，將格和邊界柵格，柵格位置。當機 格時，下一步可東、東北、北、機器人場地南八個方位進行 號之后，求出當為了編程 們需要對柵格做 柵格分為中間柵 主要是用于判斷 器人處于中間柵 以分別向東南、 西北、西、西南、 搜索；對柵格編 前位置柵格序號與這上述8個方位的序號的差值。通過建立數(shù)組的形式來描述 下一步將要搜索的具體柵格的方位：Next_oritationi =9,-1,-11,-10,-9,1,11,101 三 i 三 8式子

31、中數(shù)組元素順序對應于不同的方位，其順序依此為東南、東、東北、北、 西北、西、西南、南。對于邊界上的柵格，其可行方位減少，再加上障礙物區(qū)，可行方位就更加 少，為方便起見，對其做另行處理。如圖3-1中的柵格51,其下一步可以選擇 的柵格表示為：Next_oritationi =10,9,-1,-111 三 i 三 3說明其下一步的搜索方向可以為向下、右下、右、右上。.柵格之間可行性和優(yōu)先性的確定當機器人處于當前柵格時，它下一步可選擇的方位可能有很多，因此柵格 搜索存在搜索方位優(yōu)先性的問題。以圖3-1為例，規(guī)定機器人的任務為機器人有 當前柵格1運行到柵格100,要求路徑最優(yōu)，且不能碰到障礙物，根據(jù)柵

32、格搜索 法，需要一個柵格、一個柵格的逐次搜索，對于第一條路徑的確定，即選擇第 二個柵格，原則上是向著指向目標的方向，同時還要考慮到障礙物，這樣就可 以對8個方向的優(yōu)先性做出判斷，然后給予每個方位一個優(yōu)先值，當起始柵格 變化時，優(yōu)先值發(fā)生變化。.路徑選擇概率定義路徑選擇的概率公式為：map (u, v) x w(j ) x5(j )p = ivvuv map (u, k) x w(j ) x8 (j )V k eVikk式子中u表示當前位置柵格，V表示u的臨近8個方位中完全可行方位的集合, v為V的元素，式中、由下式決定：Next_oritation jv =u-v，vVpuv 為相應的概率Ne

33、xt_oritation jk =u-k，房 VPv 為相應的概率(三)算法描述.算法思想利用柵格搜索方法規(guī)劃機器人路徑時，為了使路徑盡可能的最優(yōu)化，我們 對算法做了改進，增加了正反饋機制，使路徑不斷地逼近于最優(yōu)化。所謂的正 反饋，就是在程序執(zhí)行時，增加一個反饋量。對于每一個可行路徑，其經過的 節(jié)點之間增加一個量,借助于E關聯(lián)程度的反饋，來搜索到一條近似最優(yōu)路徑。 對于第i-1條路徑中柵格U和V的關聯(lián)程度的更新方程為：map (u, v) = map 1 (u, v) + s隨著某一節(jié)點u與節(jié)點v之間關聯(lián)程度的增加，則由該節(jié)點u選擇下一結 點時，節(jié)點v被選擇通過的概率也會增加，與此同時若從某一

34、個節(jié)點u選擇v 通過的數(shù)目呈現(xiàn)增加趨勢，那么節(jié)點v和節(jié)點u之間關聯(lián)程度也會增加，則關 聯(lián)程度和通過的路徑數(shù)目之間形成正反饋機制，使得所選擇的路徑不斷地趨向 于最優(yōu)路徑。.算法流程基于柵格模型的路徑規(guī)劃算法執(zhí)行過程如圖3-2所示圖3-2路徑搜索流程圖四、仿真實驗及結論（一）算法性能分析在柵格的搜索上，采用概率計算的方法，保證公平公正，由當前節(jié)點選擇 下一結點時，都是按照比例概率，因此保證了在可行方向上的每一個柵格都有 可能被選到。在路徑選擇上，我們采用分組的方法，將搜索過程分為m組，對 每一組都可能會得到n條路徑，找到n中路徑中最短的路徑，然后利用它修改 相鄰柵格之間的關聯(lián)性，不需要每次尋找到一

35、條可行路徑時，就修改障礙物地 圖，這樣會照成某些節(jié)點關聯(lián)程度增長過快，被選擇的概率過大，使得路徑相 對集中，路徑尋優(yōu)出現(xiàn)死區(qū)，對多樣性的選取路徑不利，無法找到最優(yōu)路徑。 只有保證可行方向上的每個節(jié)點都有可能被選到，保證路徑選擇的多樣性，才 能保證搜索到的路徑是最優(yōu)路徑。（二）實驗仿真驗證本文進行的仿真實驗是借助于仿真軟件MobileSim和Mobileeyes進行的。 程序編寫是基于C+語言，利用Microsoft Visual Studio 2010建立項目，并生成 可執(zhí)行文件。機器人工作環(huán)境的繪制借助Mapper3軟件，繪制完地圖后就可以用仿真軟 件進行仿真。然后啟動MobileSim仿真

36、軟件，并加載繪制的環(huán)境地圖，此時便 可以運行Visual Studio 2010生成的可執(zhí)行文件，然后打開MobileEyes，自動建 立連接，進入仿真界面，選擇Tour 6?；蛞卜抡娼Y果如圖3-3所示。 MobileEves - IoLalhost R&bac Map Mi ImIe圖3-3路徑規(guī)劃從上圖的仿真結果可以看出，Amigo機器人規(guī)劃出了一條由起始點到目標 點的可行路徑，并沿著這條路徑順利到達目標點，不過在前進過程中，為了實現(xiàn) 路徑最優(yōu)，機器人會對原來的路徑進行修改，直到到達目標點為止。通過仿真 分析，驗證了該算法的可行性。（三）結論通過仿真驗證，該算法實現(xiàn)了以下功能：第一，在沒有

37、障礙物的地圖工作 環(huán)境中，Amigo機器人能夠迅速的完成路徑規(guī)劃任務。第二，當在地圖工作環(huán) 境中添加各種障礙物時，Amigo能迅速的規(guī)劃出一條路徑，但在行進中，為了 使路徑最優(yōu)，Amigo機器人會實時對路徑做出調整。此外，當目標點發(fā)生變化 時，Amigo能夠迅速的由當前點規(guī)劃出到達目標點的路徑。未能實現(xiàn)的功能：不能夠在障礙物位置變化的情況下由初始點成功到達目 標點，即該算法未能實現(xiàn)動態(tài)路徑規(guī)劃。五、總結于展望（一）總結本文主要研究了在環(huán)境已知條件下，利用柵格搜索的方法對機器人的路徑 進行規(guī)劃的問題。鑒于實驗室提供的機器人為Amigo,我們主要分析了關于 Amigo機器人的路徑規(guī)劃問題。Amigo機器人使用特定的開發(fā)軟件Aria，Aria 提供了 Amigo機器人編程的一整套應用程序接口，因此我們主要是借助于Aria 的API進行編程。在算法上，其思想是一樣的，在把算法轉化成程序時，同樣 需要借助于軟件自帶的一些庫文件，最后再利用軟件進行仿真驗證算法的可行 性，通過仿真分析，我們可以斷定，柵格搜索方法對Amigo機器人的路徑規(guī)劃 完全可行。（二）展望本次畢業(yè)設計的要求是：在Amigo機器人工作環(huán)境已