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

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

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

3、socket連接到Player機器人設備服務器端，實現(xiàn)對仿真機器人的控制。關(guān)鍵詞：路徑規(guī)劃，多機器人系統(tǒng)，機器人編隊，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，F(xiàn)ormation 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 國內(nèi)外研究歷史及現(xiàn)狀 PAGEREF _Toc134780210 h 2 HYPERLINK l _Toc134780211 1.3 本文內(nèi)容與結(jié)構(gòu) PAGEREF _Toc134780211 h 6 HYPERLINK l _Toc134780212 第2章 移動機器人路徑規(guī)劃理論及算法 PAGEREF _Toc134780212 h 7 HYPERLINK l _Toc134780213 2.1 路徑規(guī)劃問題概述 PAGEREF _Toc134780213 h 7 HYPERLINK l _Toc134780214 2.2 常用路徑規(guī)劃算法 PAGEREF _Toc134780214

12、h 7 HYPERLINK l _Toc134780215 2.2.1 模糊邏輯法 PAGEREF _Toc134780215 h 7 HYPERLINK l _Toc134780216 2.2.2基于柵格法的自主機器人實時路徑規(guī)劃 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 基于模糊邏輯的行為融合路徑規(guī)劃方法 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 路徑規(guī)劃器結(jié)構(gòu) PAGEREF _Toc1

14、34780223 h 15 HYPERLINK l _Toc134780224 2.4 本章小結(jié) 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虛擬結(jié)構(gòu)法 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 編隊方法結(jié)構(gòu) PAGEREF _Toc134780234 h 25 HYPERLINK l _Toc134780235 3.4 本章小結(jié) 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 系統(tǒng)平臺要求 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 本章小結(jié) 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 客戶端開發(fā)工具介紹 PAGEREF _Toc134780248 h 39 HYPERLINK l _Toc134780249 5.2 傳感器參數(shù)分析及設置 PAGEREF _Toc134780249 h 41 HYPERLINK l _Toc134780250 5.3 客戶端與機器人服務器Player的通信 PAGER

20、EF _Toc134780250 h 44 HYPERLINK l _Toc134780251 5.4 基于模糊邏輯的行為融合路徑規(guī)劃方法仿真 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 仿真實驗結(jié)果與分析 PAGEREF _Toc134780256 h 52 HYPERLINK l _Toc134780257 5.6 本章小結(jié) PAGEREF _Toc134780257 h 53 HYPERLINK l _Toc134780258 第6章 工作總結(jié)和展望 PAGEREF _Toc134780258 h 54 HYPERLINK l _

22、Toc134780259 6.1 工作總結(jié) PAGEREF _Toc134780259 h 54 HYPERLINK l _Toc134780260 6.2 論文創(chuàng)新點 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 攻讀碩士期間參加的科研項目和發(fā)表的論文 PAGEREF _Toc134780264 h 61第1章 緒論中國工程院院長宋健指出：“機器人學的進步和應用是20世紀自動控制最有說服力的成就，是當代最高意義上的自動化”。機器人技術(shù)綜合了多學科的發(fā)展成果，代表了高技術(shù)的發(fā)展前沿，它在人類生活應用領域的不斷擴大，正引起國際上重新認識機器人技術(shù)的作用和影響1-9。1.1 課題研究背景及意義本課題來源于國家自然科學基金(60475031)：“傳感器網(wǎng)絡環(huán)境中移動機器人動態(tài)特征與可重構(gòu)控制框架”和湖北省青年杰出人才基金項目(2005ABB021)：“自治體系統(tǒng)的分布式智能傳感、控

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

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

26、責獲取自己周圍的環(huán)境信息，這樣就可以保證比較完整地獲得機器人群體當前活動區(qū)域的環(huán)境信息，對于實現(xiàn)偵察、搜尋、排雷及安全巡邏等任務是有利的?？梢栽鰪姷钟饨缛肭值哪芰?。作戰(zhàn)過程中，機器人士兵通過保持隊形，可以抵抗多方向的入侵，增加自身安全性，群居動物按一定隊形行進可以有效抵抗掠食者的現(xiàn)象就是一例?？梢蕴岣吖ぷ餍?，如果選擇的隊形適當，可以加快任務的完成。例如，多個機器人推箱子，機器人與箱子之間必須保持一定的幾何關(guān)系才能夠?qū)⑾渥油葡蚱谕姆较?，類似的任務還有農(nóng)作物收割、播種等。另外，研究多機器人的隊形保持問題，對于自動公路系統(tǒng)及戰(zhàn)斗機編隊等也有指導意義，因為它們的共同之處都是多個智能體協(xié)作實現(xiàn)共同

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

57、的實時性和魯棒性。同時，本系統(tǒng)根據(jù)需要還可以增加更多的行為，如緊急行為、跟墻行為等。2.3.2 移動機器人模型本文中，本文構(gòu)建了一個半徑為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、布示意圖同時，為了實現(xiàn)路徑規(guī)劃任務，本文做出如下假設：（1）機器人通過內(nèi)部傳感器總是知道自己當前位置坐標p(X ，Y)，并且目標點位置坐標pt (X t ，Y t)已知；（2）機器人通過裝備的聲納傳感器探測障礙物進行避障；（3）機器人的運動控制層按照制定的路徑運動，不考慮其中的誤差。2.3.3 坐標系和控制變量圖2.6 坐標系和控制變量本文構(gòu)建了兩個坐標系，一個是環(huán)境世界坐標系XOY，另一個是機器人局部坐標系xoy ，如圖2.6中所示。其中，機器人導向角，即X軸和y軸夾角；目標位置和機器人當前位置的連線與X軸夾角； 目標位置和機器人當前位置的連線與y軸夾角；障礙物和當前位置的連線與y軸夾角。2

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

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