1、（申請工學碩士學位論文）動態環境下多移動機器人路徑規劃研究摘 要對多移動機器人系統而言，如何產生各個機器人的協調無碰運動路徑是對它的一項基本要求。因此，近年來多機器人路徑規劃逐漸成為機器人研究的一個熱點問題。本文通過對多機器人編隊問題的研究，從協調和協作兩個方面來研究多機器人路徑規劃問題。編隊控制是指多個機器人在到達目的地的過程中，保持某種隊形同時又要適應環境約束的控制技術。多機器人研究中的主要問題是機器人間的協調和合作，通常協調是為了解決機器人之間的沖突和矛盾，而合作指機器人通過一種機制合作完成一項任務。 對于自主移動機器人編隊問題來說，協調主要就是使機器人避免和障礙物以及機器人之間發生碰撞

2、；合作就是保持隊形。通過本課題的研究，得到如下的成果與結論：綜合國內外相關研究文獻，闡述了移動機器人研究現狀和主要內容。同時，詳細介紹了多機器人系統、路徑規劃及機器人編隊問題的研究現狀。介紹了幾種移動機器人路徑規劃的理論和算法，主要包括全局路徑規劃和局部路徑規劃。提出了一種基于模糊邏輯的行為融合路徑規劃方法。通過對多移動機器人編隊問題的研究，來闡述多機器人路徑規劃中的路徑沖突協調和協作問題，提出了一種在未知環境中基于觀察者的多機器人編隊控制方法。通過一種新的開源機器人仿真平臺Player/Stage建立仿真實驗環境，然后在Eclipse下利用java編程語言編寫客戶端算法，控制程序通過TCP

3、socket連接到Player機器人設備服務器端，實現對仿真機器人的控制。關鍵詞：路徑規劃，多機器人系統，機器人編隊，Playe/StageAbstractFor multiple mobile robots system，how to find a safe path without collosion for each robot is a basic requirement. Therefore，the multi-robots path planning approach is emerging as a key technology in the study of multiple

4、mobile robotics over recent years. Through the study of formation control of multi-robots，this thesis studies the problem of multiple mobile robots path planning from two aspects of coordination and cooperation.The formation problem in multi-robots systems is defined as the coordination of a group o

5、f robots to maintain a formation with a desired shape and reach a particular destination without collisions. The key problem of multiple robots system is the coordination and cooperation with each robot. Usually，coordination is used to resolve the conflicts and collosions among each robot and cooper

6、ation means that some robots collaborate to complete a task according to a mechanism. As for the formation of multi-robots，the coordination is the avoidance of obstacle and the resolvement of collsion with other robots，and the cooperation is used to maintain a formation with a desired shape. The mai

7、n contents of this thesis are as follows:1. Investigated the current research status and main contents of mobile robots，according to the domestic and foreign relevant references. At the same time，gave the detailed introduction of current research status of multi-robots system，path planning and forma

8、tion control.2. Introduced some kinds of theories and algorithms of path planning，mainly including the global path planning and the local path planning and presented a behavior fusion path planning method for mobile robots based on fuzzy logic.3. Through the study of formation control of multi-robot

9、s，explained the problem of coordination and cooperation in multi-robots path planning. Presented an observer based formation control algorithm for multi-robots. 4. Built the simulated environment for multi-robots formation control with the Player/Stage software and compiled java program to control t

10、he simulated robots through TCP Socket in the Eclipse.Keyword: Path Planning，Multi-Robots System，Formation Control，Player/Stage目 錄 TOC o 1-3 h z u HYPERLINK l _Toc134780208 第1章 緒論 PAGEREF _Toc134780208 h 1 HYPERLINK l _Toc134780209 1.1 課題研究背景及意義 PAGEREF _Toc134780209 h 1 HYPERLINK l _Toc134780210 1.

11、2 國內外研究歷史及現狀 PAGEREF _Toc134780210 h 2 HYPERLINK l _Toc134780211 1.3 本文內容與結構 PAGEREF _Toc134780211 h 6 HYPERLINK l _Toc134780212 第2章 移動機器人路徑規劃理論及算法 PAGEREF _Toc134780212 h 7 HYPERLINK l _Toc134780213 2.1 路徑規劃問題概述 PAGEREF _Toc134780213 h 7 HYPERLINK l _Toc134780214 2.2 常用路徑規劃算法 PAGEREF _Toc134780214

12、h 7 HYPERLINK l _Toc134780215 2.2.1 模糊邏輯法 PAGEREF _Toc134780215 h 7 HYPERLINK l _Toc134780216 2.2.2基于柵格法的自主機器人實時路徑規劃 PAGEREF _Toc134780216 h 9 HYPERLINK l _Toc134780217 2.2.3 人工勢場法 PAGEREF _Toc134780217 h 11 HYPERLINK l _Toc134780218 2.2.4 VFH方法 PAGEREF _Toc134780218 h 12 HYPERLINK l _Toc134780219 2

13、.3 基于模糊邏輯的行為融合路徑規劃方法 PAGEREF _Toc134780219 h 13 HYPERLINK l _Toc134780220 2.3.1 方法概述 PAGEREF _Toc134780220 h 13 HYPERLINK l _Toc134780221 2.3.2 移動機器人模型 PAGEREF _Toc134780221 h 13 HYPERLINK l _Toc134780222 2.3.3 坐標系和控制變量 PAGEREF _Toc134780222 h 14 HYPERLINK l _Toc134780223 2.3.4 路徑規劃器結構 PAGEREF _Toc1

14、34780223 h 15 HYPERLINK l _Toc134780224 2.4 本章小結 PAGEREF _Toc134780224 h 20 HYPERLINK l _Toc134780225 第3章 多機器人編隊問題研究 PAGEREF _Toc134780225 h 21 HYPERLINK l _Toc134780226 3.1 多機器人編隊概述 PAGEREF _Toc134780226 h 21 HYPERLINK l _Toc134780227 3.2 常見的多機器人編隊方法 PAGEREF _Toc134780227 h 21 HYPERLINK l _Toc13478

15、0228 3.2.1跟隨領航者法 PAGEREF _Toc134780228 h 21 HYPERLINK l _Toc134780229 3.2.2基于行為法 PAGEREF _Toc134780229 h 22 HYPERLINK l _Toc134780230 3.2.3虛擬結構法 PAGEREF _Toc134780230 h 22 HYPERLINK l _Toc134780231 3.3 基于觀察者的多機器人編隊方法 PAGEREF _Toc134780231 h 23 HYPERLINK l _Toc134780232 3.3.1 l- 編隊控制法 PAGEREF _Toc134

16、780232 h 23 HYPERLINK l _Toc134780233 3.3.2 編隊方法基本思想 PAGEREF _Toc134780233 h 25 HYPERLINK l _Toc134780234 3.3.3 編隊方法結構 PAGEREF _Toc134780234 h 25 HYPERLINK l _Toc134780235 3.4 本章小結 PAGEREF _Toc134780235 h 27 HYPERLINK l _Toc134780236 第4章 開源機器人項目Player/Stage PAGEREF _Toc134780236 h 28 HYPERLINK l _To

17、c134780237 4.1 Player介紹 PAGEREF _Toc134780237 h 28 HYPERLINK l _Toc134780238 4.1.1 描述 PAGEREF _Toc134780238 h 28 HYPERLINK l _Toc134780239 4.1.2 Player的運行方式 PAGEREF _Toc134780239 h 29 HYPERLINK l _Toc134780240 4.1.3 系統平臺要求 PAGEREF _Toc134780240 h 29 HYPERLINK l _Toc134780241 4.1.4 總體框架的設計特點 PAGEREF

18、_Toc134780241 h 30 HYPERLINK l _Toc134780242 4.2 Stage介紹 PAGEREF _Toc134780242 h 35 HYPERLINK l _Toc134780243 4.3 本章小結 PAGEREF _Toc134780243 h 35 HYPERLINK l _Toc134780244 第5章 仿真實驗 PAGEREF _Toc134780244 h 36 HYPERLINK l _Toc134780245 5.1 仿真實驗的硬件和軟件 PAGEREF _Toc134780245 h 36 HYPERLINK l _Toc13478024

19、6 5.1.1 world文件 PAGEREF _Toc134780246 h 36 HYPERLINK l _Toc134780247 5.1.2 cfg文件 PAGEREF _Toc134780247 h 37 HYPERLINK l _Toc134780248 5.1.3 客戶端開發工具介紹 PAGEREF _Toc134780248 h 39 HYPERLINK l _Toc134780249 5.2 傳感器參數分析及設置 PAGEREF _Toc134780249 h 41 HYPERLINK l _Toc134780250 5.3 客戶端與機器人服務器Player的通信 PAGER

20、EF _Toc134780250 h 44 HYPERLINK l _Toc134780251 5.4 基于模糊邏輯的行為融合路徑規劃方法仿真 PAGEREF _Toc134780251 h 46 HYPERLINK l _Toc134780252 5.5 基于觀察者的多機器人編隊方法仿真 PAGEREF _Toc134780252 h 48 HYPERLINK l _Toc134780253 5.5.1 編寫多機器人仿真world文件 PAGEREF _Toc134780253 h 48 HYPERLINK l _Toc134780254 5.5.2 編寫多機器人仿真cfg文件 PAGERE

21、F _Toc134780254 h 49 HYPERLINK l _Toc134780255 5.5.3 多機器人編隊控制算法 PAGEREF _Toc134780255 h 51 HYPERLINK l _Toc134780256 5.5.4 仿真實驗結果與分析 PAGEREF _Toc134780256 h 52 HYPERLINK l _Toc134780257 5.6 本章小結 PAGEREF _Toc134780257 h 53 HYPERLINK l _Toc134780258 第6章 工作總結和展望 PAGEREF _Toc134780258 h 54 HYPERLINK l _

22、Toc134780259 6.1 工作總結 PAGEREF _Toc134780259 h 54 HYPERLINK l _Toc134780260 6.2 論文創新點 PAGEREF _Toc134780260 h 54 HYPERLINK l _Toc134780261 6.3 工作展望 PAGEREF _Toc134780261 h 55 HYPERLINK l _Toc134780262 參考文獻 PAGEREF _Toc134780262 h 56 HYPERLINK l _Toc134780263 致 謝 PAGEREF _Toc134780263 h 60 HYPERLINK l

23、 _Toc134780264 攻讀碩士期間參加的科研項目和發表的論文 PAGEREF _Toc134780264 h 61第1章 緒論中國工程院院長宋健指出：“機器人學的進步和應用是20世紀自動控制最有說服力的成就，是當代最高意義上的自動化”。機器人技術綜合了多學科的發展成果，代表了高技術的發展前沿，它在人類生活應用領域的不斷擴大，正引起國際上重新認識機器人技術的作用和影響1-9。1.1 課題研究背景及意義本課題來源于國家自然科學基金(60475031)：“傳感器網絡環境中移動機器人動態特征與可重構控制框架”和湖北省青年杰出人才基金項目(2005ABB021)：“自治體系統的分布式智能傳感、控

24、制與協作”。機器人作為人類20世紀最偉大的發明之一，在短短的40年內發生了日新月異的變化。發展機器人技術己成為高技術領域中具有代表性的戰略目標之一。機器人技術的出現和發展，不但使傳統的工業生產面貌發生了根本性變化，而且將對人類的社會產生深遠的影響。就目前的機器人技術水平而言，單機器人在信息的獲取、處理及控制能力等方面都是有限的，對于復雜的工作任務及多變的工作環境，單機器人的能力尤顯不足。于是人們考慮由多個機器人組成的群體系統通過協調、協作來完成單機器人無法或難以完成的工作。進行多機器人系統的研究是機器人技術發展的必然趨勢，必將對機器人技術的發展起著重要作用。今后隨著科技的發展，多機器人系統的應

25、用領域將逐漸向工業、軍事領域發展，它的應用將越來越廣。在工業中，多機器人系統的柔性可極大地加快企業的轉產速度，實現柔性加工；在國防中，它可以實現無人飛機和無人坦克代替軍隊進行作戰，最大限度地減少人員傷亡。可以預見多機器人系統的應用將會對社會帶來巨大變革，能極大地提高人們的生活質量以及工農業和國防現代化程度。在多機器人系統的許多應用領域中，要求多機器人在作業和運動過程中保持一定的隊形，尤其是在完成軍事任務的過程中，保持隊形顯得更為重要。多移動機器人保持一定的隊形至少有以下幾點好處:充分獲取當前環境信息。單個機器人的傳感器獲取信息的能力是有限的，如果多個機器人保持一定的隊形，而每個機器人的傳感器負

26、責獲取自己周圍的環境信息，這樣就可以保證比較完整地獲得機器人群體當前活動區域的環境信息，對于實現偵察、搜尋、排雷及安全巡邏等任務是有利的。可以增強抵御外界入侵的能力。作戰過程中，機器人士兵通過保持隊形，可以抵抗多方向的入侵，增加自身安全性，群居動物按一定隊形行進可以有效抵抗掠食者的現象就是一例。可以提高工作效率，如果選擇的隊形適當，可以加快任務的完成。例如，多個機器人推箱子，機器人與箱子之間必須保持一定的幾何關系才能夠將箱子推向期望的方向，類似的任務還有農作物收割、播種等。另外，研究多機器人的隊形保持問題，對于自動公路系統及戰斗機編隊等也有指導意義，因為它們的共同之處都是多個智能體協作實現共同

27、的目標。對于含有多個移動機器人的系統而言，如何產生各個機器人的協調無碰撞運動路線是對它的一項基本要求，因此，本課題研究的路徑規劃和編隊問題對于多機器人系統的研究具有重要的和實際的應用價值和意義。1.2 國內外研究歷史及現狀移動機器人的研究始于60年代末期，斯坦福研究院(SRI)的Nils Nilssen和Charles Rosen等人，在1966年至1972年間研制出名為Shakey13移動機器人。目的是研究如何在復雜環境下將人工智能技術應用于機器人系統，以完成自主推理、規劃和控制的功能。該時期的移動機器人的研究，主要是集中在室內結構化環境下，移動機器人所有應用到的基本技術，包括機器人結構設計

28、、控制技術、傳感器技術、信息融合、路徑規劃等。進入20世紀80年代，人們研究方向逐漸轉向面向實際應用的室內移動機器人8，并逐步形成了自主式移動機器人AMR（Autonomous Mobile Robot）概念。這時期的研究成果有美國海軍研究的Robart-I&II，橡樹嶺國家實驗室的核電站機器人等。90年代以來，以研制高水平的環境信息傳感器和信息處理技術，高適應性的移動機器人控制技術，真實環境下的規劃技術為標志，開展了移動機器人更高層次的研究。一大批世界著名公司和大學也加入到移動機器人研究工作中，開發的較著名的機器人實驗平臺有Martin公司的ALVin，FMC公司的ARV，RWI公司的mic

29、roARTV9，ActivMedia公司的pioneer-2 DX。國內對移動機器人的研究起步較晚，但經過多年努力，也取得了一定成績。目前以清華大學研制THMR3系列比較著名。隨著機器人技術的發展，機器人的能力不斷提高，機器人應用領域也不斷開拓，尤其是一些危險的、特殊的領域，如核工業故障、太空作業等，迫切需要機器人的介入。由于單機器人的局限性，一些復雜任務需要通過多機器人協調來完成。多機器人系統的研究始于20 世紀70 年代。隨著機器人應用領域的不斷拓展、機器人工作環境復雜度、任務的加重，對機器人的要求不再局限于單個機器人，多機器人的研究已經成為機器人學研究的一個熱點。多機器人系統的研究分為多

30、機器人協調(Multi-robot Coordination) 和多機器人合作(Multi-robot Cooperation) 兩大類，主要研究給定一個多機器人系統任務后，如何組織多個機器人去完成任務，如何分解和分配任務以及如何保持機器人之間的運動協調一致。 近年來，國際上很多研究機構在該方面的研究取得了一定的成果。 美國Oak Ridge 國家實驗室的Cooperative Robotics 實驗系統26研究的協作機器人是集成了感知、推理、動作的智能系統，著重研究在環境未知且在任務執行過程中環境動態變化的情況下，機器人如何協作完成任務。 美國USC大學Socially Mobile 和Th

31、e Nerd Herd27實驗系統在多機器人學習、群行為、協調與協作等方面開展工作。日本Nagoya 大學的CEBOT 系統28的研究，涉及到系統的體系結構、通訊、信息交互許多方面。中國科學院沈陽自動化所的MRCAS系統29在多機器人協作理論研究的基礎上開展多機器人協作的實驗研究。目前，以多機器人為主體的系統大多采用集中性節拍同步控制，這存在對整個機器人系統的規劃算法過于復雜、已生成的系統擴充或修改困難、局部故障會造成系統癱瘓、系統負載過大而機器人本身的資源無法發揮其全部作用等一系列問題，故而有必要對多機器人系統進行研究，使之達到多機器人協調的目的。多機器人的協調是為了提高工作效率，完成復雜勞

32、動，并且由于單個機器人的獨立性及機器人之間的協調性，某一機器人發生故障其他機器人仍可以完成一定的工作，同時有良好的可擴充性，即加入某個機器人只需加入相應的控制程序即可使之與原機器人系統各機器人協調工作。多機器人系統并不是多個機器人的簡單堆疊自然產生的，簡單的堆疊不能發揮多機器人的優勢，反而會存在多機器人之間的沖突，使整體性能反而降低。因而需要研究多機器人的體系結構及它們之間的協調控制機制。多機器人協調最基本的問題是多機器人之間信息的傳遞，多機器人之間通過必要的信息交流實現多機器人的同步或協調，如坐標確定、路徑規劃、防止死鎖、避免碰撞等。路徑規劃是自主式移動機器人導航的基本環節之一，它是按照某一

33、性能指標搜索一條從起始狀態到目標狀態的最優或近似最優的無碰路徑。根據機器人對環境信息知道的程度不同，可分為兩種類型: 環境信息完全知道的全局路徑規劃和環境信息完全未知或部分未知，通過傳感器在線地對機器人的工作環境進行探測，以獲取障礙物的位置、形狀和尺寸等信息的局部路徑規劃。全局路徑規劃包括環境建模和路徑搜索策略兩個子問題。其中環境建模的主要方法有: 可視圖法(VGraph)、自由空間法(Free Space Approach) 和 柵格法(Grids) 等。 可視圖法13視機器人為一點，將機器人、目標點和多邊形障礙物的各頂點進行組合連接，要求機器人和障礙物各頂點之間、目標點和障礙物各頂點之間以

34、及各障礙物頂點與頂點之間的連線，均不能穿越障礙物，即直線是可視的。搜索最優路徑的問題就轉化為從起始點到目標點經過這些可視直線的最短距離問題。 運用優化算法，可刪除一些不必要的連線以簡化可視圖，縮短搜索時間。該法能夠求得最短路徑，但假設機器人的尺寸大小忽略不計，使得機器人通過障礙物頂點時離障礙物太近甚至接觸并且搜索時間長，對于N 條連線的搜索時間為T(N)。Voronoi Diagrams 法和Tangent Graph 法15對可視圖法進行了改進；自由空間法應用于機器人路徑規劃，采用預先定義的如廣義錐形和凸多邊形16等基本形狀構造自由空間，并將自由空間表示為連通圖，通過搜索連通圖來進行路徑規劃

35、。 該法比較靈活，起始點和目標點的改變不會造成連通圖的重構，但算法的復雜程度與障礙物的多少成正比，且不是任何情況下都能獲得最短路徑；柵格法17將機器人工作環境分解成一系列具有二值信息的網格單元，多采用四叉樹或八叉樹表示工作環境，并通過優化算法完成路徑搜索。該法以柵格為單位記錄環境信息，環境被量化成具有一定分辨率的柵格，柵格的大小直接影響著環境信息存儲量的大小和規劃時間的長短。柵格劃分大了，環境信息存儲量小，規劃時間短，但分辨率下降，在密集環境下發現路徑的能力減弱；柵格劃分小了，環境分辨率高，在密集環境下發現路徑的能力強，但環境信息存儲量大，規劃時間長，可以采用改進的柵格法18彌補柵格法的不足。

36、路徑搜索策略主要有:A* 算法19、D* 最優算法20等。局部路徑規劃的主要方法有: 人工勢場法(Artificial Potential Field )、遺傳算法( Genetic Algorithm )、模糊邏輯算法( Fuzzy Logic Algorithm ) 和神經網絡等。 人工勢場法是由K.hatib 提出的一種虛擬力法。其基本思想是將機器人在環境中的運動視為一種虛擬的人工受力場中的運動。障礙物對機器人產生斥力，目標點產生引力，引力和斥力的合力作為機器人的加速力，來控制機器人的運動方向和計算機器人的位置。 該法結構簡單，便于低層的實時控制，在實時避障和平滑的軌跡控制方面，得到了廣

37、泛的應用，但對存在局部最優解的問題，容易產生死鎖現象(Dead Lock)22，因而可能使機器人在到達目標點之前就停留在局部最優點；J. Holland23在60年代初提出了遺傳算法，以自然遺傳機制和自然選擇等生物進化理論為基礎，構造了一類隨機化搜索算法。它利用選擇、交叉和變異來培養控制機構的計算程序，在某種程度上對生物進化過程做數學方式的模擬。它不要求適應度函數是可導或連續的，而只要求適應度函數為正，同時作為并行算法，它的隱并行性適用于全局搜索。多數優化算法都是單點搜索算法，很容易陷入局部最優，而遺傳算法卻是一種多點搜索算法，因而更有可能搜索到全局最優解。由于遺傳算法的整體搜索策略和優化計算

38、不依賴于梯度信息，所以解決了一些其它優化算法無法解決的問題。但遺傳算法運算速度不快，進化眾多的規劃要占據較大的存儲空間和運算時間；基于實時傳感信息的模糊邏輯算法30參考人的駕駛經驗，通過查表得到規劃信息，實現局部路徑規劃。該方法克服了勢場法易產生的局部極小問題，適用于時變未知環境下的路徑規劃，實時性較好。神經網絡作為一個高度并行的分布式系統，對于解決機器人系統實時性要求很高的問題提供了可能性，它在智能自主移動機器人路徑規劃中的應用已顯示出其優越性。國內在移動機器人的研究起步較晚，大多數研究尚處于某個單項研究階段，主要的研究工作有清華大學智能移動機器人于1994年通過鑒定，涉及到五個方面的關鍵技

39、術:基于地圖的全局路徑規劃技術研究；基于傳感器信息的局部路徑規劃技術研究；路徑規劃的仿真技術研究；傳感技術、信息融合技術研究；軌跡跟蹤技術研究。近年來，機器人編隊控制已經成為了多移動機器人研究的一項關鍵技術。多機器人編隊控制比單機器人控制具有更強的優越性，如魯棒性、智能性、高性能、柔性等。這些優點使得它在大范圍搜索營救，監視，繪制環境地圖，遠距離地形空間探索，掃雷，以及衛星和無人機的控制等方面得到廣泛應用。編隊控制是指多個機器人在到達目的地的過程中，保持某種隊形同時又要適應環境約束(例如存在障礙物或者空間的物理限制) 的控制技術51。多機器人研究中的主要問題是機器人間的協調和協作，通常協調是為

40、了解決機器人之間的沖突和矛盾，而協作指機器人通過一種機制合作完成一項任務。 對于自主移動機器人編隊問題來說，解決沖突主要就是使機器人避免和障礙物以及機器人之間發生碰撞；合作就是保持隊形。廣義上，機器人編隊研究可以分為兩類。第一類是集中式控制，它通過一個集中控制單元來監督整組機器人并分別命令每個機器人的運動。第二類是分布式控制，每個機器人利用局部信息自主運動。本質上，目前多移動機器人編隊方法主要有以下三種：領導跟隨法（leader-following）、基于行為法(behavior-based)和虛結構法(virtual-structure)。文獻5152對這三種方法做了詳細介紹并列舉了相關參考

41、文獻。其中，虛結構法利用集中式控制器，而基于行為法和領導跟隨法通常使用分布式控制器。以上三種方法都可以控制機器人以一定隊形運動，但在復雜未知環境中，卻存在一定缺陷。領導跟隨法在靜態環境中可以獲得比較準確、穩定的隊形，但對動態環境的適應能力不強，機器人之間的避碰等問題沒有得到很好的解決。而基于行為的編隊方法對環境的適應能力較強，但保持隊形上存在一定缺陷。1.3 本文內容與結構 本文的主要內容是機器人路徑規劃方法和多機器人編隊控制的研究，利用Player/Stage建立服務器端多機器人仿真環境，在Eclipse下利用Java編寫客戶端控制算法程序，通過TCP Socket進行通信，控制服務器端仿真

42、機器人。本文共分為6章，具體內容包括：第1章：緒論，介紹了本課題研究領域的背景及意義、國內外研究現狀，并安排論文的結構。第2章：移動機器人路徑規劃理論及算法，介紹了幾種常用的移動機器人路徑規劃理論及算法，在此基礎上提出一種基于模糊邏輯的行為融合路徑規劃方法。第3章：多機器人編隊問題研究，介紹了多機器人編隊相關理論及算法，提出一種基于觀察者的編隊方法。第 4 章：開源機器人項目Player/Stage，介紹一種新的開源機器人仿真項目Player/Stage。第 5 章：基于觀察者的機器人編隊仿真，在Player/Stage機器人仿真工具下構建仿真環境，并對所提出的編隊方法進行仿真實驗。第6章：工

43、作總結和展望，在這一章節中，對全文作了總結，并指出自己所作的工作和創新點，以及需要進一步改進的地方。第2章 移動機器人路徑規劃理論及算法2.1 路徑規劃問題概述路徑規劃是自主式移動機器人導航的基本環節之一。它的任務是按照某一性能指標搜索一條從起始狀態到目標狀態的最優或近似最優的無碰路徑。根據機器人對環境信息了解的程度不同，路徑規劃可分為兩種類型: （1）環境信息完全已知的離線全局路徑規劃；（2）環境信息完全未知或部分未知，通過傳感器對機器人的工作環境進行探測，以獲取障礙物位置、形狀和尺寸等信息的在線局部路徑規劃。目前，關于環境信息完全已知的全局路徑規劃方法已經得到了很好的發展，由于它是一種離線

44、靜態規劃方法，因此通常可以得到最優路徑。這類方法主要有：可視圖法(V-Graph)、自由空間法(Free Space Approach)以及柵格法(Grids)。但當移動機器人在環境信息完全未知或局部未知的環境下工作時，就無法使用這些離線方法了。因此，需要使用基于傳感器信息的局部路徑規劃方法。這類方法通常有：勢場法（Potential Field）41、VFH42、D*法43等。局部路徑規劃利用傳感器提供的信息來進行規劃，這些常用傳感器包括有:聲吶、超聲波傳感器、激光測距儀和視覺傳感器等。2.2 常用路徑規劃算法2.2.1 模糊邏輯法基于實時傳感信息的模糊邏輯算法參考人的駕駛經驗，通過查規則表

45、得到規劃信息，實現局部路徑規劃。該方法克服了勢場法易產生的局部極小問題，適用于時變未知環境下的路徑規劃，實時性較好。模糊邏輯控制是以模糊集合論、模糊邏輯、模糊語言變量以及模糊推理為基礎的一種非線性的計算機數字控制技術。模糊邏輯控制系統具有這樣的特點：它獲取不精確的數據，處理它，然后得到精確的數據結果；因此，可以作為一種解決環境信息不確定性問題的合適工具。2.2.1.1 模糊邏輯基礎概念在人們的思維中，有許多沒有明確外延的概念，這類概念就叫做模糊概念。模糊概念沒有明確的外延，因而不能用普通集合來描述，只能用模糊集合來描述。1965年，Zadeh教授發表的開創性論文“Fuzzy Set”中，首次提

46、出模糊集合的基本概念和基本理論31。模糊命題是含有模糊概念或模糊性的陳述句，而研究模糊命題的邏輯就是模糊邏輯。語言變量用以表征那些十分復雜或定義很不完善而又無法用通常的精確術語進行描述的現象。一個語言變量可定義為一個五維數組 ( X，T(X)，U，G，M )。其中: X語言變量的名稱；T（X）語言變量語言值名稱的集合；U論域；G語法規則；M語義規則。例如，圖2.1是以障礙物距離為論域的模糊語言變量五維數組的示意圖。距離近中遠211020.40.80.410.50.510.81論域U語義規則M語言變量X語言值T(X)圖2.1 模糊語言變量五維數組示意圖模糊推理是應用模糊關系表示模糊條件句，將推理

47、的判斷過程轉化為對隸屬度的合成及演算過程。它是模糊決策的前提條件，更是模糊控制規則生成的依據。2.2.1.2模糊控制基本原理模糊控制的基本原理可由圖2.2表示，它的核心部分為模糊控制器。模糊量化處理模糊推理去模糊化處理執行機構被控對象傳感器模糊控制器輸入變量精確控制量圖2.2 模糊控制基本原理圖由上圖可以概括出模糊控制的四個基本步驟：（1）根據本次采樣的系統輸出值，計算所選擇的系統輸入變量；（2）將輸入變量的精確值變為模糊量；（3）根據輸入變量（模糊量）及模糊控制規則，按模糊推理合成規則計算控制量（模糊量）；（4）將上面得到的控制量（模糊量）進行去模糊化處理，計算出精確的控制量（精確值）。2.

48、2.2基于柵格法的自主機器人實時路徑規劃2.2.2.1環境的柵格模型柵格模型采用二維矩形柵格表示環境，每個矩形柵格有一個累計值CV值(CV值是各種傳感器信自、融合后存在障礙的可能性)，表示此方位中存在障礙物的可信度，高的CV值表示存在障礙物的可能性高。傳感器不斷快速采樣環境，存在障礙物的柵格將會不斷地被檢測到，導致高的CV值。如果是環境的干擾信息被傳感器讀入，很少能導致高的CV值。采用這種方式表示環境信息不僅能將環境信息存儲在計算機中，更重要的是使用方便，使得問題的求解有較高的效率。2.2.2.2柵格大小的選取柵格大小的選取直接影響著路徑規劃算法的性能。柵格選得過小，環境分辨率高，但抗干擾能力

49、弱，環境信息存儲量大，決策速度慢；柵格選得過大，抗干擾能力強，環境信息存儲量小，決策速度快，但分辨率下降，在密集障礙物環境中發現路徑的能力減弱。柵格大小的選取也與傳感器的性能有關，如果傳感器精度高而且速度快，柵格可以選得小些。2.2.2.3方向的選擇在機器人前面開出一個以長度R為半徑的半圓形假想窗口，稱為活動窗口，環境坐標系中暫時屬于活動窗口的柵格稱為窗口柵格。窗口柵格是方向決策的主要依據。對于具有對稱形狀的機器人，窗口中心簡單地選在機器人的幾何中心。對于一般的矩形車體機器人，窗口中心定義在車體前方的1/2處。在活動窗口中，建立一個窗口坐標系，使柵格從環境坐標系中映象到窗口坐標系中。在活動窗口

50、中，分出k個角度為(180/k)的扇面，分別表示行駛方向，如圖2.3所示。 每個個扇面的障礙密度可以由公式(2-1)獲得： （2-1） 圖2.3環境的柵格表示和活動窗口Ci，j表示坐標為(i，j)的活動柵格的確信度；Hk反映出在扇面K中的障礙密集程度，即對扇面內的所有柵格的CV值求和。把有一定數量的幾個連續的扇面而且每個扇面的障礙密度Hk低于一個閥值的區域稱為侯選扇區。侯選扇區為移動機器人行駛的安全區域，通常存在有幾個侯選扇區，在這個情況下，選取最利于到達目標的侯選扇區作為行駛方向。2.2.2.4 環境信息的優化隨著機器人的移動，傳感器不斷對環境采樣，環境信息存儲量會越來越大，這不僅會造成存儲

51、器容量不足，而且對環境信息的處理時間會越來越長，這將不能滿足實時性的要求，因此，必須對環境信息進行優化。我們發現，隨著機器人的移動，在移動機器人后面一定距離的信息利用率是很低的，這部分信息如果被刪除，不會對決策產生大的影響。可以利用以下策略刪除此類環境信息: 1從環境坐標系取出一柵格； 2將其映像到窗口坐標系中； 3如果此柵格落后與機器人，且與窗口中心的距離大于一定值，則從環境坐標系中刪除此柵格。通過這樣的處理，使得所存儲的環境信息不至于隨著移動機器人的移動而無限增大，減少了處理時間，工作空間不再受到限制。2.2.3 人工勢場法人工勢場法41是將機器人在周圍環境中的運動，設計成在一種勢場中運動

52、，是對機器人運行環境的一種抽象描述，機器人在場中具有一定的抽象勢能，勢場的源有兩類；斥力極和引力極。機器人不希望進入的區域和障礙物屬于斥力極；目標及機器人系統建議通過的區域為引力極。在極的周圍由一定的算法產生相應的勢，在任何一點的勢為兩極在該點產生的勢之和，該勢的負梯度稱為有勢力。勢場的建立主要用于動態避障，此時的引力極是局部環境中的中間目標斥力極則是局部環境中的障礙物。 建立勢場的方法由實際需要而定。O. K Ratb提出一種只與系統位置有關的建立方法。對于目標引力極，定義抽象力為以該目標為參考位置的比例控制；對于斥力極，建立等勢線與障礙物邊緣形狀相似的斥力場。這種方法的主要困難在于，一般障

53、礙物的形狀不很規則，物體邊緣曲線方程難以建立，更為嚴重的是這種方法產生局部極點即零勢點。所有障礙物與目標在這些點上形成的抽象力之和為零，系統在這些點上受到零控制力而停止，以至沒有到達目標。為消除上述不利因素，可以設法將速度因子引入到勢場，建立位置速度相關勢場，克服極點，提高系統的穩定性。2.2.4 VFH方法VFH+方法54是一種用于機器人實時路徑規劃方法，它是對Borenstein 和Koren 在1991年開發的VFH（向量域直方圖）法的一種改良版本。和VFH方法一樣，該方法的輸入是局部環境的柵格圖，叫做直方圖（histogram）。圖2.4 VFH+方法的一個例子為了計算機器人新的運動方

54、向，VFH+方法利用了一個四級數據縮減過程。在前三級里，機器人當前位置周圍信息由二維柵格圖縮減為一維極線直方圖。在第四級，該方法通過遮罩的極線直方圖（the masked polar histogram）和代價函數（cost function）來選擇一個最合適的方向。VFH+方法首先在遮罩的極線直方圖中選擇所有的開放區域（the openings），然后確定一組可能的候選方向。最后，利用代價函數來評價這些候選方向，選擇代價最低的那個候選方向作為機器人新的運動方向。在圖2.4所示的例子中，機器人會選擇通過障礙物A、B的方向運動，然后向左轉，而不是直接向左轉，因為這樣機器人會碰到障礙物A。VFH+

55、方法已經通過大量實際檢驗，并成功運用于一種導盲機器人GuideCane上。實驗表明，該方法可以得到高效、安全、平滑的運動軌跡。關于該方法的詳細介紹，可以參考文獻54。2.3 基于模糊邏輯的行為融合路徑規劃方法2.3.1 方法概述目前，在未知環境中的自治機器人路徑規劃問題正成為機器人研究的熱點之一。由于機器人周圍環境信息具有不完整性、不可預知性、近似性以及缺少相關數據信息等特點，因此，未知環境中機器人路徑規劃存在的一個很嚴重的問題是具有很大的不確定性。而且，這種不確定性還存在于傳感器測量數據以及計算過程中。為了使機器人能夠在未知環境中實現自主導航，就需要給它更多智能以及增加它的自主性。基于行為的

56、控制結構是把復雜的任務分解成很多簡單的可以并發執行的單元，每個單元有自己的感知器和執行器，這兩者緊耦合在一起的，構成感知動作行為，多個行為相互松耦合構成層次模型。這種方法的主要優點在于每個行為的功能比較簡單，對周圍環境的變化能做出快速的響應，實時性好。但也存在兩個缺點：（1）行為不易描述；（2）多個行為間的沖突和競爭難以協調。本文中的方法是將模糊邏輯控制和行為控制相結合，構建了一個基于模糊邏輯的行為控制路徑規劃器。利用模糊邏輯來構建這些基本行為的好處是它可以很容易的構建這些行為，并且可以通過一個行為合成過程來融合多個行為的輸出結果。這樣就能有效解決傳統行為控制方法的兩個缺點，使整個系統具有很好

57、的實時性和魯棒性。同時，本系統根據需要還可以增加更多的行為，如緊急行為、跟墻行為等。2.3.2 移動機器人模型本文中，本文構建了一個半徑為r =20厘米，裝備了10個聲納傳感器的圓形移動機器人，傳感器分布如圖2.5中所示。每個傳感器si (i=0，9)的測量距離li（10cmli400cm），測量角度為22.5。這些傳感器分為5組，用sgi (i=1，5)表示，如，sg1（s0，s1）。因此，機器人的總視角為225。每組傳感器測得的障礙物到機器人中心的距離di(i=1，5)由下面的公式計算：di = r min（l2i-2 ，l2i-1）;(i = 1，5) (2-2)圖2.5 機器人傳感器分

58、布示意圖同時，為了實現路徑規劃任務，本文做出如下假設：（1）機器人通過內部傳感器總是知道自己當前位置坐標p(X ，Y)，并且目標點位置坐標pt (X t ，Y t)已知；（2）機器人通過裝備的聲納傳感器探測障礙物進行避障；（3）機器人的運動控制層按照制定的路徑運動，不考慮其中的誤差。2.3.3 坐標系和控制變量圖2.6 坐標系和控制變量本文構建了兩個坐標系，一個是環境世界坐標系XOY，另一個是機器人局部坐標系xoy ，如圖2.6中所示。其中，機器人導向角，即X軸和y軸夾角；目標位置和機器人當前位置的連線與X軸夾角； 目標位置和機器人當前位置的連線與y軸夾角；障礙物和當前位置的連線與y軸夾角。2

59、.3.4 路徑規劃器結構移動機器人（MR）模糊行為監督器（FBS）避障行為（OA）目標導向（TS）模糊化規則庫模糊推理模糊化規則庫模糊推理去模糊處理行為融合去模糊處理模糊推理規則庫模糊化d i W d t，d min , d og行為加權（BWS）行為融合（BFS）Vo ，oVt ，tV ，圖2.7 基于模糊邏輯的行為控制路徑規劃器圖2.7詳細描述了該路徑規劃器（Path Planner）的結構。它主要由三部分組成：一個避障行為（Obstacle Avoidance），簡記為OA；一個目標導向行為（Target Steering），簡記為TS；以及一個模糊行為監督器（Fuzzy Behavio

60、r Supervisor），簡記為FBS。這三部分都是基于模糊邏輯構建的。OA的功能是在不考慮目標位置的情況下進行避障，模糊輸入變量為di，輸出為Vo和o 。TS的功能是不考慮避障而只考慮到達目標位置，模糊輸入變量為d t和，輸出為Vt和t 。FBS的功能是融合OA和TS而得到無碰平滑的路徑規劃路線。FBS包括兩個部分：行為加權部分（Behavior Weighting Section），簡記為BWS，和行為融合部分（Behavior Fusion Section），簡記為BFS。2.3.4.1避障行為（OA）避障行為是自治機器人的基本需要之一，它能幫助機器人在未知環境中自由運動而不發生碰撞。