畢業(yè)論文--多機(jī)器人系統(tǒng)的路徑規(guī)劃算法研究 （含外文翻譯）

1、<p><b>　　畢業(yè)設(shè)計(jì)（論文）</b></p><p>　　題 目： 多機(jī)器人系統(tǒng)的路徑規(guī)劃算法研究 </p><p>　　英 文 題 目： Research on Path Planning Algorithm of</p><p>　　Multi-robot System</p>

2、<p>　　畢業(yè)設(shè)計(jì)(論文)任務(wù)書</p><p>　　畢業(yè)設(shè)計(jì)（論文）開題報(bào)告書</p><p>　　課題類型：（1）A—工程設(shè)計(jì)；B—技術(shù)開發(fā)；C—軟件工程；D—理論研究；</p><p>　?。?）X—真實(shí)課題；Y—模擬課題；Z—虛擬課題</p><p>　?。?）、（2）均要填，如AY、BX等。</p><

3、;p>　　多機(jī)器人系統(tǒng)的路徑規(guī)劃算法研究</p><p><b>　　摘 要</b></p><p>　　移動(dòng)機(jī)器人路徑規(guī)劃的研究是機(jī)器人研究領(lǐng)域中的一個(gè)熱點(diǎn)，它對(duì)實(shí)現(xiàn)機(jī)器人導(dǎo)航制導(dǎo)及跟蹤控制起著無(wú)可替代的作用。路徑規(guī)劃是機(jī)器人有效完成任務(wù)的安全保障，同時(shí)也是反映機(jī)器人智能化水平的重要標(biāo)志。隨著信息技術(shù)，通信技術(shù)，傳感器技術(shù)和人工智能等相關(guān)學(xué)科的發(fā)展，許多新技術(shù)

4、和智能算法并入該領(lǐng)域，促進(jìn)了路徑規(guī)劃技術(shù)的提高。</p><p>　　本文基于粒子群算法開展移動(dòng)機(jī)器人路徑規(guī)劃問題的研究。</p><p>　　首先闡述了粒子群算法的原理及各個(gè)參數(shù)的物理意義，指出它作為一種智能優(yōu)化算法在函數(shù)優(yōu)化問題中的優(yōu)越性：進(jìn)化速度快，算法簡(jiǎn)單，且具有自適應(yīng)性和群體智能性。對(duì)于算法會(huì)引起的局部最小問題，創(chuàng)造性的提出了位置加權(quán)到無(wú)約束解和加變異算子兩種改進(jìn)方案。</

5、p><p>　　其次針對(duì)路徑規(guī)劃問題，采用區(qū)域劃分的環(huán)境建模思想，通過(guò)構(gòu)造簡(jiǎn)單的環(huán)境模型將該問題轉(zhuǎn)化為帶約束目標(biāo)函數(shù)優(yōu)化求解問題。</p><p>　　最后，通過(guò)仿真實(shí)現(xiàn)了基于粒子群算法的路徑優(yōu)化，比較了基本粒子群算法和各種改進(jìn)算法在解決固定初始化方式下局部極小值問題上的不同效果，證明了位置加權(quán)和加變異算子的方法在解決局部最優(yōu)問題上的有效性。</p><p>　　關(guān)鍵詞

6、: 移動(dòng)機(jī)器人; 路徑規(guī)劃; 粒子群算法; 位置加權(quán); 變異算子 </p><p>　　Research on Path Planning Algorithm of </p><p>　　Multi-robot System</p><p><b>　　ABSTRACT</b></p><p>　　The study o

7、f path planning for mobile robot is becoming increasingly popular in the field of robot. It plays an indispensable role in the achievements of navigation and locus follow control of the robot. Path planning can guarantee

8、s security of robot’s work, it can also shows intelligence level of the robot. The development of some coherent subjects (information technology, communication technology, transducer technology and artificial intelligenc

9、e) and incorporation of these new techniques give</p><p>　　In this paper, path planning for mobile robot based on particle swarm optimization algorithm is studied.</p><p>　　Firstly, the principl

10、e of PSO and physical meaning of its parameters are elaborated. As an intelligent algorithm, it shows the advantages of rapidity, simplicity, adaptivity and intelligence in application of function optimization. To solve

11、the problem of local optimum introduced by this method, two modified schemes, position weighted to the unconstraint best solution and adding mutation operator, are creatively proposed.</p><p>　　Secondly, a r

12、egion division conception is adopted to build environment model. In this way, path planning problem is changed to be a constraint function optimization problem.</p><p>　　The optimized path is obtained and di

13、fferent effects of path planning based on various modified algorithm are compared through simulation. Simulation results demonstrate the effectiveness of position weighted and mutation operator methods in solving local o

14、ptimum problem.</p><p>　　Keywords: mobile robot; path planning; particle swarm algorithm; position weighted;</p><p>　　mutation operator </p><p><b>　　目錄</b></p>

15、<p><b>　　1 緒論1</b></p><p>　　1.1課題研究的背景及意義1</p><p>　　1.2 移動(dòng)機(jī)器人路徑規(guī)劃研究現(xiàn)狀2</p><p>　　1.3 智能算法及其應(yīng)用3</p><p>　　1.4 課題研究的主要內(nèi)容及框架3</p><p>　　2

16、粒子群算法綜述5</p><p>　　2.1 粒子群算法的研究背景5</p><p>　　2.2 基本粒子群算法5</p><p>　　2.2.1 基本概念5</p><p>　　2.2.2 算法原理及流程6</p><p>　　2.3 改進(jìn)粒子群算法7</p><p>　　2.4

17、粒子群算法和其他進(jìn)化算法的比較8</p><p>　　3 移動(dòng)機(jī)器人路徑規(guī)劃10</p><p>　　3.1 環(huán)境建模10</p><p>　　3.2 路徑規(guī)劃的方法11</p><p>　　3.2.1傳統(tǒng)路徑規(guī)劃方法11</p><p>　　3.2.2 智能路徑規(guī)劃方法11</p><

18、p>　　3.3 約束優(yōu)化問題及處理方法13</p><p>　　3.3.1 約束優(yōu)化問題的描述13</p><p>　　3.3.2 約束優(yōu)化問題的處理方法13</p><p>　　4 基于粒子群優(yōu)化的路徑規(guī)劃算法及仿真14</p><p>　　4.1仿真平臺(tái)簡(jiǎn)介14</p><p>　　4.2 問題描述

19、與環(huán)境建模14</p><p>　　4.3 路徑初始化16</p><p>　　4.4 基于粒子群算法的路徑規(guī)劃仿真18</p><p>　　4.4.1 基于基本粒子群算法的路徑規(guī)劃仿真18</p><p>　　4.4.2 基于改進(jìn)粒子群算法的路徑規(guī)劃仿真21</p><p>　　4.5 仿真結(jié)果分析23&

20、lt;/p><p>　　4.6程序調(diào)試中的問題及處理24</p><p>　　5 結(jié)論與展望25</p><p>　　5.1 結(jié)論總結(jié)25</p><p>　　5.2 以后可做的工作和展望26</p><p><b>　　謝辭27</b></p><p><b&

21、gt;　　參考文獻(xiàn)28</b></p><p>　　附錄A 外文翻譯-原文部分29</p><p>　　附錄B 外文翻譯-譯文部分35</p><p>　　附錄C 流程圖及仿真圖形39</p><p>　　附錄D 主要源程序52</p><p><b>　　1 緒論</b>&

22、lt;/p><p>　　1.1課題研究的背景及意義</p><p>　　隨著計(jì)算機(jī)技術(shù)、信息技術(shù)、控制理論、人工智能和傳感器技術(shù)等學(xué)科的發(fā)展和成熟，以此交叉而形成的機(jī)器人學(xué)的研究也進(jìn)入了一個(gè)嶄新的階段。機(jī)器人的研究經(jīng)歷了從可編程的、示教再現(xiàn)型的工業(yè)機(jī)器人到具有一定傳感、適應(yīng)能力的機(jī)器人再到配備多種先進(jìn)傳感器，具有自學(xué)習(xí)和較強(qiáng)適應(yīng)能力的智能機(jī)器人；從結(jié)構(gòu)簡(jiǎn)單、功能單一的單機(jī)機(jī)器人到結(jié)構(gòu)復(fù)雜，適應(yīng)

23、復(fù)雜環(huán)境，功能多樣的多機(jī)器人系統(tǒng)的發(fā)展過(guò)程[1]。移動(dòng)機(jī)器人的研究始于20世紀(jì)60年代末期，斯坦福研究院的Nils Nilssen和Charles Rosen等人，在1966年至1972年間研究制造出了名為Shakey的自主移動(dòng)機(jī)器人，目的是研究應(yīng)用人工智能技術(shù)，在復(fù)雜環(huán)境下機(jī)器人系統(tǒng)的自主推理、規(guī)劃和控制問題。與此同時(shí)，最早的操作式步行機(jī)器人也研制成功，從而開始了機(jī)器人步行機(jī)構(gòu)方面的研究，以解決機(jī)器人在不平整地域內(nèi)的運(yùn)動(dòng)問題。70 年

24、代末，隨著計(jì)算機(jī)的應(yīng)用和傳感技術(shù)的發(fā)展，移動(dòng)機(jī)器人研究又出現(xiàn)了新的高潮。特別是在80年代中期，設(shè)計(jì)和制造機(jī)器人的浪潮席卷全世界，一大批世界著名的公司開始研制移動(dòng)機(jī)器人平臺(tái)，這些移動(dòng)機(jī)器人主要作為大學(xué)實(shí)驗(yàn)室及研究機(jī)構(gòu)的移動(dòng)機(jī)器人實(shí)驗(yàn)平臺(tái)，</p><p>　　移動(dòng)機(jī)器人的路徑規(guī)劃是機(jī)器人導(dǎo)航系統(tǒng)中不可缺少的重要部分，導(dǎo)航系統(tǒng)是移動(dòng)機(jī)器人的研究核心，同時(shí)也是移動(dòng)機(jī)器人實(shí)現(xiàn)智能化及完全自主的關(guān)鍵技術(shù)。移動(dòng)機(jī)器人的導(dǎo)航問

25、題主要是由Durrant Whyte H F提出的三個(gè)問題 ①“我現(xiàn)在何處?”②“我要往何處去?”③“要如何到該處去?”[2]。大多數(shù)導(dǎo)航系統(tǒng)由兩級(jí)規(guī)劃組成，即局部規(guī)劃(Local Planning)和全局規(guī)劃(Global Planning)。前者主要解決①、③兩個(gè)問題,即機(jī)器人定位和路徑跟蹤問題，而后者主要解決問題②，即全局目標(biāo)分解成局部目標(biāo)，再由局部規(guī)劃實(shí)現(xiàn)局部目標(biāo)。 移動(dòng)機(jī)器人按照預(yù)先給出的任務(wù)命令，根據(jù)已知的環(huán)境信息做出全局路

26、徑規(guī)劃，并在行進(jìn)過(guò)程中，不斷感知周圍的局部環(huán)境信息，自主地做出各種決策，并隨時(shí)調(diào)整自身位置，引導(dǎo)自身安全行駛或跟蹤已知路徑達(dá)到目標(biāo)位置。移動(dòng)機(jī)器人要實(shí)現(xiàn)導(dǎo)航涉及到的基本行為有：自身位置和周圍環(huán)境的感知與識(shí)別、路徑規(guī)劃、路徑跟蹤、障礙回避等。</p><p>　　路徑規(guī)劃是移動(dòng)機(jī)器人導(dǎo)航技術(shù)中不可缺少的重要組成部分，它要求機(jī)器人根據(jù)給予的指令及環(huán)境信息自主地決定路徑，避開障礙物，實(shí)現(xiàn)任務(wù)目標(biāo)。 路徑規(guī)劃是移動(dòng)機(jī)器人

27、完成任務(wù)的安全保障，同時(shí)也是移動(dòng)機(jī)器人智能化程度的重要標(biāo)志。尤其是在機(jī)器人硬件系統(tǒng)的精度在短期內(nèi)不能得到解決的情況下，對(duì)路徑規(guī)劃算法的研究尤為重要，這將從根本上改變移動(dòng)機(jī)器人的導(dǎo)航性能，將提高移動(dòng)機(jī)器人的智力水平，減少移動(dòng)機(jī)器人在移動(dòng)過(guò)程中存在的不確定狀態(tài)，提高移動(dòng)機(jī)器人移動(dòng)的速度及靈活性，為開發(fā)高智能的遠(yuǎn)距離搬運(yùn)機(jī)器人、探測(cè)機(jī)器人、服務(wù)機(jī)器人、汽車自動(dòng)駕駛系統(tǒng)打下基礎(chǔ)。</p><p>　　多機(jī)器人系統(tǒng)的路徑規(guī)

28、劃意味著在同一工作空間中為系統(tǒng)中的每一個(gè)機(jī)器人找到一條合適的路徑，并保證每一時(shí)刻機(jī)器人與機(jī)器人之間無(wú)碰撞，機(jī)器人與環(huán)境之間無(wú)碰撞，這就涉及到機(jī)器人之間的路徑協(xié)調(diào)與避碰問題。多機(jī)器人系統(tǒng)路徑規(guī)劃的研究是機(jī)器人學(xué)路徑規(guī)劃領(lǐng)域中的一個(gè)非常活躍的分支，它對(duì)引導(dǎo)多個(gè)移動(dòng)機(jī)器人在復(fù)雜的工作環(huán)境下按何種路徑運(yùn)動(dòng)有著重要的理論指導(dǎo)意義，其現(xiàn)實(shí)的應(yīng)用價(jià)值也隨著移動(dòng)機(jī)器人在工業(yè)、航空、航天等領(lǐng)域的應(yīng)用越來(lái)越多的突顯出來(lái)。</p><p&

29、gt;　　1.2 移動(dòng)機(jī)器人路徑規(guī)劃研究現(xiàn)狀</p><p>　　移動(dòng)機(jī)器人路徑規(guī)劃（Path Planning of Mobil Robot）是機(jī)器人學(xué)的一個(gè)重要的研究領(lǐng)域，也是一個(gè)最基本的問題。它被描述為：給定一個(gè)移動(dòng)機(jī)器人所處的環(huán)境（環(huán)境可以通過(guò)移動(dòng)機(jī)器人傳感器系統(tǒng)或者別的途徑獲得），一個(gè)起始點(diǎn)和一個(gè)期望的終止點(diǎn)，規(guī)劃出一條移動(dòng)機(jī)器人可行的從起始點(diǎn)到達(dá)終止點(diǎn)，且避開環(huán)境中障礙物的最短的運(yùn)動(dòng)路徑。這個(gè)問題從表

30、面上看是一個(gè)簡(jiǎn)單易描述的問題，而實(shí)際上它的復(fù)雜度隨著移動(dòng)機(jī)器人的構(gòu)型空間維度的增加而不斷增長(zhǎng)。對(duì)移動(dòng)機(jī)器人路徑規(guī)劃的研究目前主要有兩類：一類是移動(dòng)機(jī)器人自主導(dǎo)航；另一種是根據(jù)移動(dòng)機(jī)器人所處的環(huán)境，由一個(gè)主機(jī)首先規(guī)劃好移動(dòng)機(jī)器人的路徑，然后設(shè)計(jì)相應(yīng)的控制器，控制移動(dòng)機(jī)器人跟蹤給定的規(guī)劃好的路徑。單移動(dòng)機(jī)器人路徑規(guī)劃的研究經(jīng)過(guò)多年的發(fā)展已成為一個(gè)日趨豐富、成熟的方向。近幾年，多移動(dòng)機(jī)器人系統(tǒng)路徑規(guī)劃的問題受到了眾多學(xué)者的重視，成為了一個(gè)比較

31、復(fù)雜而又獨(dú)具特色的優(yōu)化問題。在生產(chǎn)與科研中，如工廠的復(fù)雜裝配中，需由許多移動(dòng)機(jī)器人代替人類在惡劣的環(huán)境下合作完成繁重的裝配任務(wù)。在這種情況下，多個(gè)移動(dòng)機(jī)器人與所處的環(huán)境就構(gòu)成了一個(gè)系統(tǒng)，為完成給定的任務(wù)，就需要</p><p>　　路徑規(guī)劃是按照某一性能指標(biāo)搜索一條機(jī)器人從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或近似最優(yōu)的無(wú)碰路徑。進(jìn)行路徑規(guī)劃需要做兩大塊工作：構(gòu)建環(huán)境模型以及采用優(yōu)化技術(shù)優(yōu)化路徑。根據(jù)規(guī)劃過(guò)程中環(huán)境信息獲取方

32、式的不同和路徑優(yōu)化過(guò)程中采取的優(yōu)化算法的不同可對(duì)路徑規(guī)劃問題做出不同的分類。</p><p>　　在環(huán)境信息獲取方式方面，根據(jù)機(jī)器人的工作環(huán)境模型的不同可以分為兩種。一種是基于環(huán)境先驗(yàn)信息的路徑規(guī)劃，作業(yè)環(huán)境的全部信息都是預(yù)知的，也即全局路徑規(guī)劃；另一種是基于傳感器信息的路徑規(guī)劃，作業(yè)環(huán)境的信息是全部未知或部分未知的，即障礙物形狀、尺寸和位置等信息必須通過(guò)傳感器在線獲取，也即局部路徑規(guī)劃。常用的全局路徑規(guī)劃的方法

33、有可視圖法、自由空間法、環(huán)境地圖法和柵格法等。常用的局部路徑規(guī)劃的方法有人工勢(shì)場(chǎng)法等。</p><p>　　在算法優(yōu)化方面，可將路徑規(guī)劃分為傳統(tǒng)優(yōu)化和智能優(yōu)化兩種。傳統(tǒng)的優(yōu)化方法有自由空間法、圖搜索法、柵格解耦法等；智能優(yōu)化方法有模糊邏輯法、神經(jīng)網(wǎng)絡(luò)法、遺傳算法、粒子群算法等。</p><p>　　另外，根據(jù)機(jī)器人工作空間中障礙物的運(yùn)動(dòng)特點(diǎn)的不同還可將路徑規(guī)劃分為靜態(tài)確定環(huán)境下的路徑規(guī)劃和

34、動(dòng)態(tài)不確定環(huán)境下的路徑規(guī)劃。在靜態(tài)環(huán)境中，障礙物的位置、形狀、大小是確定不變的，這種情況下進(jìn)行路徑規(guī)劃不用過(guò)多考慮障礙物的運(yùn)動(dòng)情況和信息，相對(duì)于要實(shí)時(shí)分析障礙物運(yùn)動(dòng)情況的動(dòng)態(tài)環(huán)境路徑規(guī)劃算法要簡(jiǎn)單一些。</p><p>　　采用智能算法進(jìn)行復(fù)雜環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃的研究是當(dāng)今路徑規(guī)劃領(lǐng)域研究的熱點(diǎn)，其研究成果已經(jīng)應(yīng)用于復(fù)雜裝配車間、軍事、航空航天等多個(gè)領(lǐng)域，顯示出了巨大的經(jīng)濟(jì)價(jià)值和社會(huì)應(yīng)用價(jià)值。本篇論文重點(diǎn)研

35、究復(fù)雜障礙物環(huán)境下移動(dòng)機(jī)器人的路徑規(guī)劃。所采用的優(yōu)化算法是智能算法中的粒子群算法。</p><p>　　1.3 智能算法及其應(yīng)用</p><p>　　智能算法（Swarm Intelligence Algorithm）的研究開始于20世紀(jì)90年代初，其基本思想是模擬自然界生物的群體行為來(lái)構(gòu)造隨機(jī)優(yōu)化算法[3]。它是受自然界中生物的群體行為啟發(fā)，研究生物群體的生存、活動(dòng)特性的規(guī)則進(jìn)而建立數(shù)學(xué)

36、模型，抽象的表示群體行為的算法。智能算法主要采用“群體”、“選擇”、“進(jìn)化”、“學(xué)習(xí)”等概念表述群體的行為特性，通過(guò)建立相應(yīng)的數(shù)學(xué)算式，將對(duì)群體行為的研究生成的算法應(yīng)用到更廣泛的優(yōu)化領(lǐng)域。典型的智能算法有遺傳算法和粒子群算法。</p><p>　　遺傳算法(Genetic Algorithm)是美國(guó)Michigan大學(xué)的J.H. Holland教授和他的學(xué)生于20世紀(jì)六七十年代提出的，是一類基于自然界生物進(jìn)化和種

37、群基因原理的隨機(jī)搜索算法。作為一種新型參數(shù)優(yōu)化方法，80年代中期以來(lái)它獲得廣泛應(yīng)用。遺傳算法基于自然選擇原理和群體進(jìn)化機(jī)制，采用從自然界選擇，群體進(jìn)化中抽象出來(lái)的幾個(gè)算子——復(fù)制、交叉和變異操作，對(duì)參數(shù)編碼的字符串進(jìn)行操作，每一個(gè)字符串對(duì)應(yīng)于一個(gè)可行解，這種遺傳操作可對(duì)多個(gè)可行解組成的群體進(jìn)行優(yōu)化。作為一種進(jìn)化算法，遺傳算法具有魯棒性強(qiáng)，應(yīng)用靈活等特點(diǎn)，已被廣泛應(yīng)用于決策規(guī)劃、調(diào)度、機(jī)器學(xué)習(xí)等領(lǐng)域。</p><p&g

38、t;　　粒子群算法（Particle Swarm Optimizer）是在1995年由美國(guó)心理學(xué)家James Kennedy和電氣工程師 Russel Eberhart 共同提出的，其基本思想是受他們?cè)缙趯?duì)許多鳥類的群體行為進(jìn)行建模和仿真研究結(jié)果的啟發(fā)[3]。該算法是模擬鳥群飛行覓食的行為，通過(guò)鳥之間的集體協(xié)作使得群體達(dá)到最優(yōu)目的的基于群體智能（Swarm Intelligence）的隨機(jī)優(yōu)化方法。在粒子群優(yōu)化算法中，個(gè)體通過(guò)“認(rèn)知”和

39、“學(xué)習(xí)”兩個(gè)行為，動(dòng)態(tài)跟蹤兩個(gè)極值（個(gè)體最優(yōu)和群體最優(yōu)）來(lái)更新其速度和位置，經(jīng)過(guò)多次迭代，達(dá)到群體全局最優(yōu)的效果。作為一種仿生算法，粒子群算法有著個(gè)體數(shù)目少、計(jì)算簡(jiǎn)單、魯棒性好等特點(diǎn)，在各類多維連續(xù)空間優(yōu)化問題上均可取得非常好的效果。同時(shí)，因?yàn)橛兄羁痰闹悄鼙尘?，它既適合科學(xué)研究，又適合工程應(yīng)用。近幾年，已提出了多種PSO改進(jìn)的算法，并且PSO已廣泛應(yīng)用于目標(biāo)函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模式分類，模糊系統(tǒng)以及其他應(yīng)用領(lǐng)域。</p>

40、;<p>　　本篇論文重點(diǎn)研究采用粒子群算法進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃，同時(shí)也研究了加入變異算子改進(jìn)粒子群算法時(shí)路徑優(yōu)化的效果。</p><p>　　1.4 課題研究的主要內(nèi)容及框架</p><p>　　針對(duì)采用智能算法進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃研究的現(xiàn)狀，本論文主要討論了將粒子群算法應(yīng)用于復(fù)雜環(huán)境下機(jī)器人路徑規(guī)劃的問題。論文首先研究了受仿生群體行為啟發(fā)的粒子群優(yōu)化算法的原理和相關(guān)參

41、數(shù)的物理意義，隨后將其應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃問題中，并以MATLAB仿真平臺(tái)為基礎(chǔ)實(shí)現(xiàn)了基于粒子群優(yōu)化算法的移動(dòng)機(jī)器人路徑規(guī)劃的仿真實(shí)驗(yàn)，最后研究了位置加權(quán)改進(jìn)粒子群算法、加變異算子改進(jìn)粒子群算法在解決局部極小值問題上的應(yīng)用效果。具體的結(jié)構(gòu)編排如下：</p><p>　　第一章簡(jiǎn)單介紹了移動(dòng)機(jī)器人路徑規(guī)劃研究的背景、現(xiàn)狀并指出常用的規(guī)劃方法。講述了智能算法，尤其是粒子群算法及其應(yīng)用。</p>&l

42、t;p>　　第二章詳細(xì)闡述了粒子群算法的思想和原理，研究該算法中各個(gè)參數(shù)的物理意義及其對(duì)進(jìn)化過(guò)程的影響。針對(duì)優(yōu)化問題中出現(xiàn)的局部極小值問題提出采用位置加權(quán)改進(jìn)粒子群算法和加遺傳變異算子改進(jìn)粒子群算法兩種解決方案。通過(guò)與其它進(jìn)化算法的比較，進(jìn)一步研究了粒子群算法的特性。</p><p>　　第三章系統(tǒng)闡述了移動(dòng)機(jī)器人路徑規(guī)劃中的兩大塊內(nèi)容：環(huán)境建模和路徑規(guī)劃的方法。從傳統(tǒng)和智能兩種角度講述了常用的路徑規(guī)劃方法

43、及特點(diǎn)。最后提出約束優(yōu)化問題及其解決方案。</p><p>　　第四章研究了將粒子群算法應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃中的整個(gè)過(guò)程并進(jìn)行了實(shí)驗(yàn)仿真。其中主要內(nèi)容有問題描述與環(huán)境建模、生成初始化路徑、采用各種粒子群進(jìn)化算法優(yōu)化路徑及仿真結(jié)果分析等。其中，針對(duì)局部極小問題，研究了改進(jìn)算法，如位置加權(quán)法和加變異算子法的解決效果。</p><p>　　最后第五章我們對(duì)本篇論文做了總結(jié)。指明了本論文的創(chuàng)新

44、之處并對(duì)以后可做的工作進(jìn)行了展望。</p><p><b>　　2 粒子群算法綜述</b></p><p>　　2.1 粒子群算法的研究背景</p><p>　　尋求性能良好的全局優(yōu)化算法并使之能可靠收斂于問題的全局最優(yōu)解，這一直是優(yōu)化領(lǐng)域孜孜以求的研究目標(biāo)和熱點(diǎn)。所謂最優(yōu)化問題，就是在滿足一定的約束條件下，尋求一組參數(shù)值，以使某些最優(yōu)性能度量

45、得到滿足，即使系統(tǒng)的某些性能指標(biāo)達(dá)到最大或最小。最優(yōu)化的應(yīng)用可以說(shuō)涉及到工業(yè)，社會(huì)，經(jīng)濟(jì)，管理等各個(gè)領(lǐng)域，其重要性是不言而喻的。按照目標(biāo)函數(shù)，約束函數(shù)的性質(zhì)以及優(yōu)化變量的取值范圍等，可將最優(yōu)化問題分成許多類型，每一種類型根據(jù)其特征不同有特定的求解方法。</p><p>　　常見的優(yōu)化方法大多數(shù)為局部?jī)?yōu)化的方法，都是從一個(gè)給定的初始點(diǎn)開始，依據(jù)一定的方法尋找下一個(gè)使得目標(biāo)函數(shù)得到改善的更好解，直至滿足某種停止條件。

46、成熟的局部?jī)?yōu)化算法有Newton-Raphsonf法， Fletcher-Reeves法 Polar-Ribiere 法Davidon-Fletcher-Power(DFP)法 Broyden-Fletcher-Goldfarb-Shann (BFGS)方法等，所有這些局部?jī)?yōu)化算法都是針對(duì)無(wú)約束優(yōu)化問題提出的，而且對(duì)目標(biāo)函數(shù)均有一定的解析性要求。對(duì)于約束非線性優(yōu)化問題，最常用的方法是將約束問題通過(guò)罰函數(shù)轉(zhuǎn)換成無(wú)約束優(yōu)化問題，然后再采用無(wú)

47、約束優(yōu)化方法進(jìn)行求解。</p><p>　　全局優(yōu)化是另外一種優(yōu)化方法，它是在全局范圍內(nèi)尋求目標(biāo)的最優(yōu)解。到目前為止，全局優(yōu)化問題也已存在許多優(yōu)化方法，如填充函數(shù)法等，但比起局部?jī)?yōu)化問題的眾多成熟的方法，其間還有很大差距。解析性優(yōu)化是全局優(yōu)化的一種常用的方法，但它對(duì)目標(biāo)函數(shù)及約束域均有較強(qiáng)的解析性要求，對(duì)于諸如目標(biāo)函數(shù)不連續(xù)，約束域不連通，目標(biāo)函數(shù)難以用解析函數(shù)表達(dá)或者難以精確估計(jì)等問題，就難以適應(yīng)。為了可靠解決

48、全局優(yōu)化問題，人們?cè)噲D離開解析確定型的優(yōu)化算法研究，轉(zhuǎn)而探討對(duì)函數(shù)解析性質(zhì)要求較低甚至不做要求的隨機(jī)型優(yōu)化方法。最早的隨機(jī)優(yōu)化方法是基于Monte-Carlo方法的思想，針對(duì)具體問題性質(zhì)的特點(diǎn)，構(gòu)造以概率1收斂于全局最小點(diǎn)的隨機(jī)搜索算法。真正有效且具有普遍適應(yīng)性的隨機(jī)全局優(yōu)化方法是近十幾年人們模擬自然界的一些自然現(xiàn)象而發(fā)展起來(lái)的一系列仿生智能優(yōu)化算法，如模擬退火法，進(jìn)化類算法，群體智能等。群體智能算法（Swarm Intelligenc

49、e Algorithm）的研究開始于20世紀(jì)90年代初，其基本思想是模擬自然界生物的群體行為來(lái)構(gòu)造隨機(jī)優(yōu)化算法。典型的方法有M.Dorigo提出的蟻群算法和R.Eberthart提出的粒子</p><p>　　2.2 基本粒子群算法</p><p>　　2.2.1 基本概念</p><p>　　自然界中各種生物體均有一定的群體行為，而人工生命的主要研究領(lǐng)域之一就是探

50、索這種群體行為，從而在計(jì)算機(jī)上構(gòu)建其群體模型。通常，群體行為可由幾條簡(jiǎn)單的規(guī)則進(jìn)行建模，如魚群，鳥群等。雖然每個(gè)個(gè)體具有非常簡(jiǎn)單的行為規(guī)則，但群體的行為卻非常復(fù)雜。Reynolds將這種類型的個(gè)體稱為boid，并使用計(jì)算機(jī)圖形動(dòng)畫對(duì)復(fù)雜的群體行為進(jìn)行仿真，他在仿真中采用了下列三條簡(jiǎn)單的規(guī)則：（1）飛離最近的個(gè)體，以避免碰撞；（2）飛向目標(biāo)；（3）飛向群體中心。采用上述規(guī)則描述群體內(nèi)每個(gè)個(gè)體的行為，這是粒子群算法的基本概念之一。Boyd和

51、Richerson[2]在研究人類決策的過(guò)程中，提出了個(gè)體學(xué)習(xí)和文化傳遞的概念。根據(jù)他們的研究結(jié)果，人們?cè)跊Q策的過(guò)程中使用兩類重要的信息，一是自身的經(jīng)驗(yàn)，二是他人的經(jīng)驗(yàn)。也就是說(shuō)，人們根據(jù)自身的經(jīng)驗(yàn)和他人的經(jīng)驗(yàn)進(jìn)行自己的決策。這是粒子群算法的另一基本思想。</p><p>　　粒子群算法（Particle Swarm Optimizer）是在1995年由美國(guó)心理學(xué)家James Kennedy和電氣工程師Russe

52、l Eberhart 共同提出的，其基本思想是受他們?cè)缙趯?duì)許多鳥類的群體行為進(jìn)行建模和仿真研究結(jié)果的啟發(fā)。而他們的模型及仿真算法主要利用了生物學(xué)家Frank Hepper的模型。Frank Hepper模型是一種鳥類被吸引飛向棲息地的群體行為模型。飛行過(guò)程中，每一只鳥試圖停在鳥群而又不相互碰撞，一只鳥飛向棲息地，將導(dǎo)致它周圍的其他鳥也飛向棲息地，最終整個(gè)鳥群都落在棲息地。粒子群算法借助該模型將鳥群看作是粒子群，尋找使粒子飛向解空間最好解

53、（全局最優(yōu)）處的進(jìn)化算法。James Kennedy和Russel Eberhart 在1995年的IEEE國(guó)際神經(jīng)網(wǎng)絡(luò)學(xué)術(shù)會(huì)議上正式發(fā)表了題為“Particle Swarm Optimization”的文章，標(biāo)志著粒子群算法的誕生。</p><p>　　2.2.2 算法原理及流程</p><p>　　粒子群算法與其他進(jìn)化類算法相類似，也采用“群體”與“進(jìn)化”的概念，同樣也是依據(jù)個(gè)體的適應(yīng)

54、值大小進(jìn)行操作。所不同的是，粒子群算法不像其他進(jìn)化算法那樣，對(duì)個(gè)體使用進(jìn)化算子，而是將每個(gè)個(gè)體看作是在n維搜索空間中的沒有重量和體積的粒子，并在搜索空間中以一定的速度飛行。該飛行速度由個(gè)體的飛行經(jīng)驗(yàn)和群體的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整。設(shè)為粒子i的當(dāng)前位置，為粒子i的當(dāng)前飛行速度。為粒子i所經(jīng)歷的最好位置，也就是其所經(jīng)歷的具有最好適應(yīng)值的位置，稱為個(gè)體最優(yōu)位置。對(duì)于最小化問題，目標(biāo)函數(shù)值越小，對(duì)應(yīng)的適應(yīng)值越好。</p><p

55、>　　我們?nèi)(X)為最小化問題的目標(biāo)函數(shù)，則粒子i的當(dāng)前最好位置由下式確定：</p><p><b>　　(2.1)</b></p><p>　　設(shè)群體中的粒子個(gè)數(shù)為N，群體中所有粒子所經(jīng)歷過(guò)的最好位置為g(t),稱為全局最好位置，則</p><p><b>　　(2.2)</b></p><p

56、>　　有了以上定義，基本粒子群算法的進(jìn)化方程可描述為：</p><p><b>　　(2.3)</b></p><p><b>　　(2.4)</b></p><p>　　其中：下標(biāo)“j”表示粒子的第j維，“i”表示粒子i，t表示第t代，為加速常數(shù)，通常在0-2之間取值，為兩個(gè)相互獨(dú)立的隨機(jī)函數(shù)。式（2.3）表明，粒

57、子通過(guò)動(dòng)態(tài)跟蹤兩個(gè)極值（個(gè)體最優(yōu)和群體最優(yōu)g）來(lái)更新其速度和位置，速度決定了粒子在搜索空間單位迭代次數(shù)的位移，即位置的變化量。調(diào)節(jié)粒子飛向自身最好位置方向的步長(zhǎng)，稱為認(rèn)知系數(shù)；調(diào)節(jié)粒子飛向全局最好位置方向的步長(zhǎng)，稱為社會(huì)學(xué)習(xí)系數(shù)。</p><p>　　為了減少在進(jìn)化過(guò)程中粒子離開搜索空間的可能性，通常限定在一定范圍內(nèi)，即。粒子的速度在空間中的每一維上的最大速度限制值為，它用來(lái)限制粒子速度的邊界值。該值一般由使用者

58、自己設(shè)定，是一個(gè)非常重要的參數(shù)。如果取值太大，則粒子也許會(huì)飛過(guò)優(yōu)秀區(qū)域；另一方面，如果取值太小，則粒子可能無(wú)法對(duì)局部最優(yōu)區(qū)域以外的地方進(jìn)行充分的探測(cè)，從而問題求解容易陷入局部最優(yōu)，無(wú)法搜索到解空間更佳的粒子位置。通常設(shè)置，，每一維都用相同的設(shè)置方法。</p><p>　　加速常數(shù)，分別調(diào)節(jié)粒子向個(gè)體最優(yōu)和群體最優(yōu)方向飛行的最大步長(zhǎng)，決定個(gè)體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)對(duì)粒子運(yùn)行情況的影響大小，反映了粒子之間的信息交流與學(xué)習(xí)。如

59、果=0，則粒子只有表現(xiàn)社會(huì)行為，它的收斂速度更快，但對(duì)于復(fù)雜問題，容易陷入局部最優(yōu)；如果=0，則粒子沒有群體信息共享，這樣一個(gè)規(guī)模為N的粒子群等價(jià)于N個(gè)獨(dú)立的粒子，得到最優(yōu)解的概率非常小。一般設(shè)置=，改變這些常數(shù)會(huì)改變系統(tǒng)的“張力”，較低的、值使得粒子徘徊在遠(yuǎn)離目標(biāo)的區(qū)域，較高的、值產(chǎn)生陡峭的運(yùn)動(dòng)或越過(guò)目標(biāo)區(qū)域。為了平衡隨機(jī)因素的作用，一般情況下設(shè)置==2，大部分算法都采用這個(gè)建議。</p><p>　　基本粒子

60、群算法的初始化過(guò)程為：</p><p>　　（1）設(shè)定群體規(guī)模N；</p><p>　　（2）對(duì)任意i,j在內(nèi)隨機(jī)產(chǎn)生；</p><p>　　（3）對(duì)任意i,j在內(nèi)隨機(jī)產(chǎn)生；</p><p>　　（4）對(duì)任意i,設(shè)。</p><p>　　基本粒子群算法的流程如下：</p><p>　　（1）依據(jù)

61、初始化過(guò)程，對(duì)粒子群的隨機(jī)位置和速度進(jìn)行初始設(shè)定；</p><p>　　（2）計(jì)算每個(gè)粒子的適應(yīng)值；</p><p>　　（3）對(duì)于每個(gè)粒子，將其適應(yīng)值與所經(jīng)歷的最好位置的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前的最好位置；</p><p>　?。?）對(duì)于每個(gè)粒子，將其適應(yīng)值與全局所經(jīng)歷的最好位置g的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前的全局最好位置；</p&

62、gt;<p>　?。?）根據(jù)方程（2.3），（2.4）對(duì)粒子的速度和位置進(jìn)行進(jìn)化；</p><p>　　（6）如未達(dá)到結(jié)束條件（通常為足夠好的適應(yīng)值或達(dá)到一個(gè)預(yù)定最大代數(shù)），則返回步驟（2）。</p><p>　　2.3 改進(jìn)粒子群算法</p><p>　　基本粒子群算法存在收斂速度慢，易陷入局部極小點(diǎn)等問題。因此需要對(duì)基本粒子群算法進(jìn)行改進(jìn)，使得算法

63、在保持結(jié)構(gòu)簡(jiǎn)單特點(diǎn)的基礎(chǔ)上可以加快收斂速度，同時(shí)有效擺脫局部極小點(diǎn)的束縛。改進(jìn)粒子群算法的方法很多，本論文涉及到的方法有加慣性權(quán)重w改進(jìn)粒子群算法、位置加權(quán)到無(wú)約束解改進(jìn)粒子群算法、引入遺傳算法中變異算子改進(jìn)粒子群算法等。</p><p>　　加慣性權(quán)重w改進(jìn)粒子群算法的公式如下所示：</p><p><b>　?。?.5）</b></p><p&

64、gt;<b>　?。?.6）</b></p><p>　　比較公式（2.3）和（2.5）可見，當(dāng)慣性權(quán)重w=1時(shí)，兩式相同，從而表明帶慣性權(quán)重的粒子群算法是基本粒子群算法的擴(kuò)展。慣性權(quán)重w表明粒子原先的速度在多大程度上得到保留。較大的w可加強(qiáng)PSO算法的全局搜索能力，較快地定位最優(yōu)解的大致位置；較小的w有較強(qiáng)的局部搜索能力，即粒子速度及位置變化減慢，開始精細(xì)的局部搜索。隨著迭代次數(shù)的增加，慣

65、性權(quán)重w應(yīng)不斷的減少，從而使得粒子群算法在初期具有較強(qiáng)的全局收斂能力，而晚期具有較強(qiáng)的局部收斂能力。在文獻(xiàn)[4]中，慣性權(quán)重滿足：</p><p><b>　　（2.7） </b></p><p>　　這樣自適應(yīng)的調(diào)整w值，可使全局搜索能力和局部搜索能力得到良好的平衡，使得搜索快速收斂到全局最優(yōu)解。</p><p>　　位置加權(quán)到無(wú)約束解

66、改進(jìn)粒子群算法的公式如下：</p><p><b>　?。?.8）</b></p><p>　　比較（2.8）與（2.6）可見，（2.8）中多了一項(xiàng)，它表示粒子趨向無(wú)約束解的分量，稱為位置加權(quán)到無(wú)約束解項(xiàng)，其中“”表示粒子第j個(gè)維度在無(wú)約束條件下的最好位置。當(dāng)粒子第j維的位置在無(wú)約束最優(yōu)解的上面時(shí)，該項(xiàng)為負(fù)值；在無(wú)約束最優(yōu)解的下面時(shí)，該項(xiàng)為正值。可見，加入該項(xiàng)可使粒子

67、更快的趨向無(wú)約束最優(yōu)解。k的大小決定粒子位置趨向無(wú)約束解的步長(zhǎng)。這樣改進(jìn)之后，可加快粒子群的收斂速度。</p><p>　　另一種位置加權(quán)的方法是改進(jìn)群體最優(yōu)的位置，即令群體最優(yōu)更快的趨向無(wú)約束解，這樣整個(gè)群體中的粒子都會(huì)更快的趨向全局最優(yōu)解，具體公式如下：</p><p><b>　?。?.9）</b></p><p>　　其中的意義及用法同

68、（2.8）。速度進(jìn)化與位置進(jìn)化公式與基本粒子群進(jìn)化公式相同。以上幾種方法單獨(dú)使用時(shí)效果可能不是很明顯，因此可以結(jié)合起來(lái)使用，優(yōu)化粒子群算法的性能，加快算法的收斂速度。</p><p>　　借鑒遺傳算法中變異的思想是改進(jìn)粒子群算法的又一方法，它對(duì)于解決局部最小點(diǎn)的問題有著很好的效果。在使用基本粒子群算法優(yōu)化目標(biāo)函數(shù)時(shí)，對(duì)于局部最小問題的解決是一個(gè)研究的熱點(diǎn)，一些改進(jìn)的算法存在著復(fù)雜度高，不便于使用或收斂速度慢的特點(diǎn)

69、。使用遺傳算法中的變異算子，對(duì)于用基本粒子群算法進(jìn)化了的粒子位置信息，以一定的概率，將粒子某些維度的位置強(qiáng)制變異到無(wú)約束最優(yōu)解處，或變異粒子相鄰維度的位置信息，使得相近維度無(wú)尖峰值存在，再經(jīng)過(guò)選擇得到相同規(guī)模的適應(yīng)性較強(qiáng)的粒子。這樣處理，可使目標(biāo)函數(shù)快速跳出局部最小點(diǎn)的束縛，同時(shí)算法的復(fù)雜度也不是很高。</p><p>　　2.4 粒子群算法和其他進(jìn)化算法的比較</p><p>　　粒子群

70、算法與其他進(jìn)化算法有許多共同之處。首先，都使用了“群體”概念，用于表示一組解空間中的個(gè)體集合。如果把粒子所經(jīng)過(guò)的最好位置看作是群體的組成部分，則粒子群的每一步進(jìn)化呈現(xiàn)出弱化形式的“選擇”機(jī)制。在進(jìn)化策略算法中，子代與父代競(jìng)爭(zhēng)，若子代具有更好的適應(yīng)值，則用來(lái)代替父代，而PSO算法的進(jìn)化方程式（2.1）具有與此相類似的機(jī)制。其唯一的差別在于，只有當(dāng)粒子的當(dāng)前位置與所經(jīng)歷的最好位置P相比具有更好的適應(yīng)值時(shí)，粒子所經(jīng)歷的最好位置（父代）才會(huì)唯一

71、地被粒子的當(dāng)前位置（子代）所取代，即PSO算法隱喻著一定形式的“選擇”機(jī)制。</p><p>　　其次，式（2.3）所描述的速度進(jìn)化方程與實(shí)數(shù)編碼遺傳算法的算術(shù)交叉算子相類似。通常，算術(shù)交叉算子由兩父代個(gè)體的線性組合產(chǎn)生兩個(gè)子代個(gè)體，而在PSO算法的速度進(jìn)化方程中，假若先不考慮項(xiàng)，就可以將它理解為由兩個(gè)父代個(gè)體產(chǎn)生一個(gè)子代個(gè)體的算術(shù)交叉運(yùn)算。從另一個(gè)角度，不考慮項(xiàng)的情況下，速度進(jìn)化方程也可以看作是一個(gè)變異算子，其

72、變異的強(qiáng)度（大小）取決于兩個(gè)父代粒子間的距離，即代表個(gè)體最好和全局最好的兩個(gè)粒子位置的距離。至于項(xiàng)，也可理解為一種變異的形式，其變異的大小與粒子在當(dāng)前代中的位置相關(guān)。</p><p>　　在進(jìn)化算法中，人們習(xí)慣于將每一步進(jìn)化迭代理解為用一個(gè)新的個(gè)體（即子代）代替舊個(gè)體（即父代）的過(guò)程。如果我們將PSO算法的進(jìn)化迭代理解為一個(gè)自適應(yīng)過(guò)程，則粒子的位置就不是被新的粒子所取代，而是根據(jù)速度向量進(jìn)行自適應(yīng)變化。這樣，PS

73、O算法與其他進(jìn)化算法的最大不同點(diǎn)在于：PSO算法在進(jìn)化過(guò)程中同時(shí)保留和利用位置與速度（即位置變化程度）信息，而其他算法僅保留和利用位置的信息。</p><p>　　如果將式（2.4）看作一個(gè)變異算子，則PSO算法與進(jìn)化規(guī)劃很相似。所不同的是，在每一代，PSO算法中的每一個(gè)粒子只朝一些根據(jù)群體的經(jīng)驗(yàn)認(rèn)為是好的方向飛行，而在進(jìn)化規(guī)劃中可通過(guò)一個(gè)隨機(jī)函數(shù)變異到任何方向。也就是說(shuō)，PSO算法執(zhí)行一種有“意識(shí)（consci

74、ous）”的變異。從理論上講，進(jìn)化規(guī)則具有更多的機(jī)會(huì)在優(yōu)化點(diǎn)附近開發(fā)，而PSO在“意識(shí)”能提供的有用的信息的條件下，有更多的機(jī)會(huì)更快地飛向更好解的區(qū)域。</p><p>　　3 移動(dòng)機(jī)器人路徑規(guī)劃</p><p>　　移動(dòng)機(jī)器人路徑規(guī)劃是機(jī)器人學(xué)研究的一個(gè)重要分支。所謂機(jī)器人的最優(yōu)路徑規(guī)劃問題，就是依據(jù)某個(gè)或某些準(zhǔn)則（如工作代價(jià)最小，行走路徑最短，行走時(shí)間最短等），在其工作空間中找到一條從

75、起始狀態(tài)到目標(biāo)狀態(tài)的能避開障礙物的最優(yōu)路徑。這是一個(gè)帶約束條件的優(yōu)化問題，整個(gè)過(guò)程可以分為幾個(gè)塊來(lái)完成，包括問題描述與規(guī)劃空間建模，初始路徑生成和利用算法優(yōu)化路徑等。本章介紹了路徑規(guī)劃中的一些基本知識(shí)和方法，如環(huán)境建模、路徑規(guī)劃的方法和約束優(yōu)化問題的解決。</p><p><b>　　3.1 環(huán)境建模</b></p><p>　　進(jìn)行機(jī)器人路徑規(guī)劃首先必須對(duì)機(jī)器人所在

76、的自由空間進(jìn)行描述，即進(jìn)行規(guī)劃空間建模，也即環(huán)境建模。環(huán)境建模是機(jī)器人路徑規(guī)劃的第一步，也是非常重要的一步，建模方式的不同，會(huì)影響路徑優(yōu)化的效果，同時(shí)也會(huì)影響算法的復(fù)雜度和程序運(yùn)行的速度。環(huán)境建?？煞譃檫B續(xù)環(huán)境建模和離散環(huán)境建模兩種。</p><p>　　自由空間法是機(jī)器人連續(xù)環(huán)境建模的一種常用的方法。采用這種方法建立的機(jī)器人運(yùn)動(dòng)空間模型比較簡(jiǎn)單，且能得到較好的優(yōu)化路徑。自由空間法是采用預(yù)先定義的如廣義錐形和凸多

77、邊形等基本形狀構(gòu)造自由空間,并將自由空間表示為連通圖,通過(guò)搜索連通圖來(lái)進(jìn)行路徑規(guī)劃,其算法的復(fù)雜程度往往與障礙物的個(gè)數(shù)成正比。鏈接圖法就是這樣一種方法[5]。</p><p>　　圖搜索法是另外一種連續(xù)環(huán)境建模的方法。它機(jī)器人視為一點(diǎn)，將機(jī)器人、目標(biāo)點(diǎn)和多邊形障礙物的各頂點(diǎn)進(jìn)行組合連接，要求機(jī)器人和障礙物各頂點(diǎn)之間、目標(biāo)點(diǎn)和障礙物各頂點(diǎn)之間以及各障礙物頂點(diǎn)與頂點(diǎn)之間的連線，均不能穿越障礙物，即直線是可視的。搜索最

78、優(yōu)路徑的問題變?yōu)榍筮@些可視直線的最短距離問題，可運(yùn)用優(yōu)化算法，簡(jiǎn)化可視圖,縮短搜索時(shí)間。</p><p>　　柵格法是離散環(huán)境建模的一種常用的方法。它是目前研究最廣泛的路徑規(guī)劃方法。該方法將機(jī)器人的工作空間解耦為多個(gè)簡(jiǎn)單的區(qū)域,一般稱為柵格。由這些柵格構(gòu)成了一個(gè)連通圖,在這個(gè)連通圖上搜索一條從起始柵格到目標(biāo)柵格的路徑,這條路徑是用柵格的序號(hào)來(lái)表示的。在進(jìn)行環(huán)境建模時(shí)，首先要按照一定的規(guī)則將機(jī)器人工作空間劃分為用柵

79、格可以表示的小區(qū)域，然后采用一定的編碼機(jī)制對(duì)柵格進(jìn)行編碼，通常采用的是二進(jìn)制和十進(jìn)制兩種編碼機(jī)制。編碼機(jī)制必須要確保待求解問題的最優(yōu)解包含于編碼機(jī)制所確定的搜索空間中，同時(shí)，還必須便于適應(yīng)度函數(shù)的計(jì)算。經(jīng)過(guò)柵格編碼，可將移動(dòng)機(jī)器人的路徑表示為一定長(zhǎng)度的染色體串，染色體串中的某一位代表移動(dòng)機(jī)器人的路徑經(jīng)過(guò)該位所表示的相應(yīng)編碼的工作空間中的一點(diǎn)。這樣對(duì)染色體串進(jìn)行操作，就可以對(duì)路徑進(jìn)行優(yōu)化[6]。</p><p>　

80、　本篇論文采用區(qū)域劃分的環(huán)境建模思想。將機(jī)器人的工作環(huán)境按垂直于起始點(diǎn)到目標(biāo)點(diǎn)連線的方向進(jìn)行等分。在每一垂線上取一個(gè)自由點(diǎn)，依次連接從起始點(diǎn)到目標(biāo)點(diǎn)的這一系列點(diǎn)，即可表示出一條移動(dòng)機(jī)器人的運(yùn)動(dòng)路徑。這種環(huán)境建模的思想簡(jiǎn)單易行，規(guī)劃出來(lái)的構(gòu)型空間易于表示，減小了算法的復(fù)雜度，有利于路徑優(yōu)化的實(shí)現(xiàn)。</p><p>　　3.2 路徑規(guī)劃的方法</p><p>　　移動(dòng)機(jī)器人的路徑規(guī)劃研究是一個(gè)

81、比較活躍的領(lǐng)域。其中對(duì)規(guī)劃方法的研究已經(jīng)形成了很多成熟的理論。路徑規(guī)劃的方法可分為傳統(tǒng)方法和智能方法兩大類，下面分別進(jìn)行闡述。</p><p>　　3.2.1傳統(tǒng)路徑規(guī)劃方法</p><p><b>　?。?）自由空間法</b></p><p>　　為了簡(jiǎn)化問題,通常采用“結(jié)構(gòu)空間”來(lái)描述機(jī)器人及其周圍的環(huán)境。這種方法將機(jī)器人縮小成點(diǎn),將其周圍

82、的障礙物及邊界按比例相應(yīng)地?cái)U(kuò)大,使機(jī)器人點(diǎn)能夠在障礙物空間中移動(dòng)到任意一點(diǎn),而不與障礙物及邊界發(fā)生碰撞。</p><p><b>　　（2）圖搜索法</b></p><p>　　圖搜索方法中的路徑圖由捕捉到的存在于機(jī)器人一維網(wǎng)絡(luò)曲線(稱為路徑圖)自由空間中的節(jié)點(diǎn)組成。建立起來(lái)的路徑圖可以看作是一系列的標(biāo)準(zhǔn)路徑。而路徑的初始狀態(tài)和目標(biāo)狀態(tài)同路徑圖中的點(diǎn)相對(duì)應(yīng),這樣路徑規(guī)

83、劃問題就演變?yōu)樵谶@些點(diǎn)間搜索路徑的問題。通過(guò)起始點(diǎn)和目標(biāo)點(diǎn)及障礙物的頂點(diǎn)在內(nèi)的一系列點(diǎn)來(lái)構(gòu)造可視圖。連接這些點(diǎn),使某點(diǎn)與其周圍的某可視點(diǎn)相連(即使相連接的兩點(diǎn)間不存在障礙物或邊界)。然后機(jī)器人沿著這些點(diǎn)在圖中搜索最優(yōu)路徑。</p><p><b>　　（3）人工勢(shì)場(chǎng)法</b></p><p>　　人工勢(shì)場(chǎng)法是Khatib提出的[6]。其基本思想是將機(jī)器人的工作空間看作

84、一種虛擬力場(chǎng),障礙物產(chǎn)生對(duì)機(jī)器人的排斥力,使得機(jī)器人不會(huì)進(jìn)入障礙物范圍，目標(biāo)產(chǎn)生對(duì)機(jī)器人的吸引力,使得機(jī)器人奔向目標(biāo)。以吸引力和排斥力的合力作為機(jī)器人的加速力，用該力來(lái)控制機(jī)器人的運(yùn)動(dòng)方向和計(jì)算機(jī)器人的位置。該方法結(jié)構(gòu)簡(jiǎn)單,便于底層的實(shí)時(shí)控制，在實(shí)時(shí)避障和平滑的軌跡控制方面，得到了廣泛的應(yīng)用。但是，由于勢(shì)場(chǎng)法把所有信息壓縮為單個(gè)合力,這樣就存在把有關(guān)障礙物分布的有價(jià)值的信息拋棄的缺陷,因此易陷入局部最小值，使機(jī)器人在到達(dá)目標(biāo)點(diǎn)之前就停留

85、在局部最優(yōu)點(diǎn)。除此之外，勢(shì)場(chǎng)法還存在三個(gè)方面的問題：1）在相近障礙物之間不能發(fā)現(xiàn)路徑；2）在障礙物前面振蕩；3）在狹窄通道中擺動(dòng)。</p><p>　　大部分機(jī)器人路徑規(guī)劃都是基于上述幾種方法進(jìn)行的,但是以上這些傳統(tǒng)方法在路徑搜索效率及路徑優(yōu)化方面尚有待于進(jìn)一步改善。而現(xiàn)在通常使用的搜索技術(shù)包括:梯度法,圖搜索方法,枚舉法、隨機(jī)搜索法等。這些方法中梯度法易陷入局部最小點(diǎn),圖搜索方法、枚舉法不能用于高維的優(yōu)化問題,

86、而隨機(jī)搜索法則計(jì)算效率太低。</p><p>　　3.2.2 智能路徑規(guī)劃方法</p><p>　　近年來(lái),隨著粒子群等智能方法的廣泛應(yīng)用,機(jī)器人路徑規(guī)劃方法也有了長(zhǎng)足的進(jìn)展,許多研究者把目光放在了基于智能方法的路徑規(guī)劃研究上。其中,應(yīng)用較多的算法主要有模糊方法、神經(jīng)網(wǎng)絡(luò)、遺傳算法和粒子群算法等。</p><p>　　（1）基于模糊邏輯的機(jī)器人路徑規(guī)劃</p&

87、gt;<p>　　模糊方法是在線規(guī)劃中通常采用的一種規(guī)劃方法，包括建模和局部規(guī)劃。莊曉東等提出一種基于模糊概念的動(dòng)態(tài)環(huán)境模型,參照物體的位置和運(yùn)動(dòng)信息構(gòu)造二維隸屬度函數(shù)，然后通過(guò)模糊綜合評(píng)價(jià)對(duì)各個(gè)方向進(jìn)行綜合考察,得到搜索結(jié)果。該方法在移動(dòng)障礙物和移動(dòng)目標(biāo)的環(huán)境中能有效地實(shí)現(xiàn)機(jī)器人避碰和導(dǎo)航。李彩虹等提出了一種在未知環(huán)境下移動(dòng)機(jī)器人的模糊控制算法,并對(duì)此算法進(jìn)行了推導(dǎo)與仿真,證明該算法魯棒性強(qiáng),可消除傳統(tǒng)算法中存在的對(duì)移動(dòng)

88、機(jī)器人的定位精度敏感、對(duì)環(huán)境信息依賴性強(qiáng)等缺點(diǎn),使移動(dòng)機(jī)器人的行為表現(xiàn)出很好的一致性、連續(xù)性和穩(wěn)定性。Hartmut Surmann等提出一種未知環(huán)境下的高級(jí)機(jī)器人模糊導(dǎo)航方法,由8個(gè)不同的超聲傳感器來(lái)提供環(huán)境信息,然后利用基于模糊控制的導(dǎo)航器來(lái)計(jì)算這些信息,規(guī)劃?rùn)C(jī)器人路徑[7]。其模糊規(guī)則建立見表1。</p><p>　　該方法在環(huán)境未知或發(fā)生變化的情況下,能夠快速而準(zhǔn)確地規(guī)劃?rùn)C(jī)器人路徑,對(duì)于要求有較少路徑規(guī)劃

89、時(shí)間的機(jī)器人是一種很好導(dǎo)航方法。但是,其缺點(diǎn)是當(dāng)障礙物數(shù)目增加時(shí),該方法的計(jì)算量會(huì)很大,影響規(guī)劃結(jié)果。</p><p>　　表1　基于模糊控制的機(jī)器人導(dǎo)航模糊規(guī)則建立</p><p>　　（2）基于神經(jīng)網(wǎng)絡(luò)方法的機(jī)器人路徑規(guī)劃 　</p><p>　　禹建麗等提出了一種基于神經(jīng)網(wǎng)絡(luò)的機(jī)器人路徑規(guī)劃法,研究了障礙物形狀和位置已知情況下的機(jī)器人路徑規(guī)劃算法,其能量函數(shù)的

90、定義利用了神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)根據(jù)路徑點(diǎn)位于障礙物內(nèi)外的不同位置選取不同的動(dòng)態(tài)運(yùn)動(dòng)方程,規(guī)劃出的路徑達(dá)到了折線形的最短無(wú)碰路徑,計(jì)算簡(jiǎn)單,收斂速度快。陳宗海等提出了一種在不確定環(huán)境中移動(dòng)機(jī)器人的路徑規(guī)劃方法,將全局路徑規(guī)劃分解為局部路徑規(guī)劃的組合,為了提高規(guī)劃的效率,在避障規(guī)劃中采用了基于案例的學(xué)習(xí)方法, 以ART—2神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)案例的匹配學(xué)習(xí)和擴(kuò)充,滿足了規(guī)劃的實(shí)時(shí)性要求。為了提高機(jī)器人路徑規(guī)劃的速度,禹建麗等在利用神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃方法的基礎(chǔ)

91、上,又引進(jìn)了線性再勵(lì)的自適應(yīng)變步長(zhǎng)算法。這種方法實(shí)現(xiàn)了步長(zhǎng)的自適應(yīng)選擇,使路徑規(guī)劃速度比原來(lái)的神經(jīng)網(wǎng)絡(luò)規(guī)劃提高了10倍左右。</p><p>　　（3）基于遺傳算法的機(jī)器人路徑規(guī)劃 </p><p>　　遺傳算法是一種借鑒生物界自然選擇和遺傳機(jī)制的搜索算法，采用從自然界選擇，群體進(jìn)化中抽象出來(lái)的幾個(gè)算子——復(fù)制、交叉和變異操作，對(duì)群體某項(xiàng)指標(biāo)進(jìn)行優(yōu)化。由于它具有簡(jiǎn)單、健壯、隱含并行性和全局

92、優(yōu)化等優(yōu)點(diǎn)，對(duì)于傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性問題具有良好的適用性。應(yīng)用遺傳算法解決自主移動(dòng)機(jī)器人路徑規(guī)劃問題，可以避免困難的理論推導(dǎo),直接獲得問題的最優(yōu)解。</p><p>　?。?）基于粒子群算法的機(jī)器人路徑規(guī)劃</p><p>　　粒子群算法是應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃中的一種新的方法，由于其計(jì)算簡(jiǎn)單，魯棒性強(qiáng)，規(guī)劃出的路徑好，已受到優(yōu)化領(lǐng)域?qū)＜业膹V泛重視。粒子群算法適宜于連續(xù)空間

93、下機(jī)器人的路徑規(guī)劃，該算法在規(guī)劃空間上采用與遺傳算法相同的鏈接圖建模法，其次使用圖論中成熟的算法粗略搜索出可選路徑（多條），最后通過(guò)粒子群算法優(yōu)化各條路徑并得出全局最優(yōu)（群體最優(yōu)）解。有關(guān)用粒子群優(yōu)化進(jìn)行路徑規(guī)劃的細(xì)節(jié)，將在第四章重點(diǎn)闡述，它是本論文研究的重點(diǎn)內(nèi)容。</p><p>　　3.3 約束優(yōu)化問題及處理方法</p><p>　　3.3.1 約束優(yōu)化問題的描述</p>

94、<p>　　在科學(xué)與工程領(lǐng)域中，許多極值問題的求解往往受到各種現(xiàn)實(shí)因素的制約，這些制約通常由一系列的約束條件來(lái)描述，求解帶約束條件的極值問題則被稱為約束優(yōu)化問題（Constrained Optimization）。具體可由下述一般形式的非線性規(guī)劃來(lái)表示：</p><p><b>　?。?.1）</b></p><p>　　其中表示問題的約束條件。</

95、p><p>　　由于約束條件的存在，使得約束極值問題的求解要比無(wú)約束極值的求解復(fù)雜、困難的多。對(duì)于約束極小值問題來(lái)說(shuō)，不僅要使得目標(biāo)函數(shù)在迭代過(guò)程中不斷減小，而且還要注意解的可行性。為了簡(jiǎn)化約束優(yōu)化問題的尋優(yōu)過(guò)程，通?？捎脤⒓s束優(yōu)化問題轉(zhuǎn)化為無(wú)約束優(yōu)化問題、將非線性規(guī)劃問題轉(zhuǎn)化為線性優(yōu)化問題的方法，把復(fù)雜的問題簡(jiǎn)單化。</p><p>　　移動(dòng)機(jī)器人路徑規(guī)劃問題就是一種帶約束的優(yōu)化問題，即是在

96、滿足機(jī)器人不與障礙物相撞的條件下，尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑。約束條件為機(jī)器人路徑不與障礙物相交。為此需要尋求使得表示路徑長(zhǎng)度的目標(biāo)函數(shù)取得極小值的可行解（一個(gè)解表示機(jī)器人的一條路徑）。對(duì)于不可行解，要通過(guò)約束優(yōu)化問題的處理方法，化之為無(wú)約束優(yōu)化問題。</p><p>　　3.3.2 約束優(yōu)化問題的處理方法</p><p>　　處理約束優(yōu)化問題常用的方法有三種：搜索空間限定法，可行

97、解變換法，罰函數(shù)法等。對(duì)于本課題中的約束優(yōu)化問題，我們采用罰函數(shù)法將它化為無(wú)約束優(yōu)化問題。</p><p>　　罰函數(shù)法的基本思想是：對(duì)解空間中無(wú)對(duì)應(yīng)可行解的個(gè)體，計(jì)算其適應(yīng)度時(shí)，處以一個(gè)罰值，從而增加該個(gè)體的適應(yīng)度值，使得在最小優(yōu)化中該個(gè)體不被選為最優(yōu)。具體可用下式來(lái)對(duì)個(gè)體的適應(yīng)度值進(jìn)行調(diào)整：</p><p><b>　　（3.2）</b></p>&

98、lt;p>　　式中f(X)為原適應(yīng)度函數(shù)，F(xiàn)(X)為考慮了罰函數(shù)之后新的適應(yīng)度函數(shù)，P(X)為罰函數(shù)。</p><p>　　如何確定合理的罰函數(shù)是這種處理方法的難點(diǎn)之處，因?yàn)檫@時(shí)既要考慮如何度量解對(duì)約束條件的不滿足程度，又要考慮算法進(jìn)化的效率。罰函數(shù)的強(qiáng)度太小的話，部分個(gè)體仍有可能破壞約束條件，罰函數(shù)的強(qiáng)度太大的話，會(huì)影響優(yōu)化算法的運(yùn)行效率。</p><p>　　在本論文中，對(duì)于不可

99、行解，即與障礙物碰撞的路徑解，需要根據(jù)位置碰撞點(diǎn)與障礙物中心的距離的關(guān)系定義合適的懲罰值函數(shù)。在碰撞發(fā)生的情況下，由于距離障礙物中心遠(yuǎn)的路徑要優(yōu)于近的路徑，它要加的懲罰值相對(duì)就要小一點(diǎn)；相應(yīng)的，距離障礙物中心近的路徑效果更差，它要加的懲罰值相對(duì)就要大一些。因此在對(duì)解空間中不可行解的個(gè)體，取罰函數(shù)為位置碰撞點(diǎn)與障礙物中心的距離倒數(shù)的函數(shù)。這樣定義罰函數(shù)，不容易損失最優(yōu)解，可以比較好的將約束條件下的路徑尋優(yōu)轉(zhuǎn)化為無(wú)約束條件下的路徑尋優(yōu)。&l

100、t;/p><p>　　4 基于粒子群優(yōu)化的路徑規(guī)劃算法及仿真</p><p>　　本章重點(diǎn)研究粒子群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用。主要內(nèi)容有問題描述與環(huán)境建模、生成初始化路徑、采用各種改進(jìn)粒子群進(jìn)化算法優(yōu)化路徑及仿真結(jié)果分析等。其中，針對(duì)局部極小問題，研究了改進(jìn)算法，如位置加權(quán)法和加變異算子法的解決效果。</p><p><b>　　4.1仿真平臺(tái)簡(jiǎn)介&l

101、t;/b></p><p>　　本課題的研究是通過(guò)編程仿真實(shí)現(xiàn)的，使用的仿真平臺(tái)是MATLAB 7.0。MATLAB意為矩陣實(shí)驗(yàn)室（matrix laboratory），是一種功能強(qiáng)、效率高、簡(jiǎn)單易學(xué)的科學(xué)計(jì)算語(yǔ)言。它以矩陣和數(shù)組為基本數(shù)據(jù)處理單元，能高效的處理大量的數(shù)據(jù)，有著強(qiáng)大的數(shù)值計(jì)算和數(shù)據(jù)分析功能。同時(shí)它也有強(qiáng)大的繪圖功能，通過(guò)調(diào)用不同的繪圖函數(shù)設(shè)置圖形的屬性，如坐標(biāo)范圍、圖形線型、圖題和繪制柵格等

102、，用戶不需要過(guò)多地考慮繪圖細(xì)節(jié)，只需給出一些基本參數(shù)，就能繪制所需圖形。</p><p>　　MATLAB命令有兩種執(zhí)行方式：一種是交互式的命令執(zhí)行方式，另一種是M文件執(zhí)行方式。仿真過(guò)程中的程序都存在M文件中，運(yùn)行程序，即可執(zhí)行文件中的命令。 </p><p>　　作為一種演算式執(zhí)行語(yǔ)言，MATLAB編程方便，使用靈活，容易掌握，已廣泛應(yīng)用于科學(xué)及工程計(jì)算領(lǐng)域[8]。本次畢業(yè)設(shè)計(jì)主要利用M

103、文件編寫程序，充分利用它強(qiáng)大的數(shù)據(jù)處理功能和繪圖功能進(jìn)行實(shí)驗(yàn)仿真。</p><p>　　4.2 問題描述與環(huán)境建模</p><p>　　在進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃時(shí)，首先必須用計(jì)算機(jī)語(yǔ)言描述機(jī)器人的工作環(huán)境，即進(jìn)行規(guī)劃空間建模。我們?cè)跈C(jī)器人運(yùn)動(dòng)空間建模時(shí)作如下假設(shè)：（1）移動(dòng)機(jī)器人在二維有限空間中運(yùn)動(dòng)，不考慮高度信息；（2）機(jī)器人的運(yùn)動(dòng)空間中分布著有限個(gè)已知的障礙物，障礙物的位置和形狀已經(jīng)確

104、定，可用大小已知的圓形描述，半徑為機(jī)器人與障礙物碰撞半徑，在半徑以外即無(wú)碰撞危險(xiǎn)，且在機(jī)器人運(yùn)動(dòng)過(guò)程中障礙物的形狀、位置、大小均不發(fā)生變化；（3）忽略障礙物的高度信息，即用(x,y)平面來(lái)描述；（4）為了保證路徑不太接近障礙物，把障礙物的邊界向外擴(kuò)展機(jī)器人本體的長(zhǎng)寬方向上最大尺寸的1/2加上傳感器最小傳感距離，機(jī)器人可看作質(zhì)點(diǎn)，尺寸大小忽略不計(jì)。圖4-1為所構(gòu)建的機(jī)器人運(yùn)動(dòng)空間的平面模型，S為起始點(diǎn)，G為目標(biāo)點(diǎn)（終止點(diǎn)），3個(gè)圓為分布于

105、機(jī)器人工作空間的障礙物。如此建立的工作空間模型是靜態(tài)的，對(duì)于動(dòng)態(tài)不確定環(huán)境中的移動(dòng)機(jī)器人路徑規(guī)劃問題，可以將它看成是分階段靜態(tài)環(huán)境規(guī)劃問題的疊加。即在兩次通過(guò)傳感器采樣環(huán)境信息的時(shí)間間隔內(nèi)，認(rèn)為環(huán)境信息是固定不變的，根據(jù)這些信息可以按靜態(tài)環(huán)境進(jìn)行路徑規(guī)劃。這時(shí)需要算法的實(shí)時(shí)性高、收斂速度快，以保證在環(huán)境</p><p>　　我們采用區(qū)域劃分的環(huán)境建模思想，對(duì)機(jī)器人的工作環(huán)境依實(shí)際情況的需要作縱向劃分[9]。為了便

106、于計(jì)算和研究，這里作縱向n等分，n條豎線用表示。移動(dòng)機(jī)器人從起始點(diǎn)S到目標(biāo)點(diǎn)G的無(wú)碰路徑一定與每條豎線都有一個(gè)交點(diǎn)，從左到右依次記為。那么路徑規(guī)劃即可表示在區(qū)域邊界確定的范圍內(nèi)，在每一條豎線上找一個(gè)合適的點(diǎn)，組成一個(gè)點(diǎn)的序列（S,,G）?？紤]到起始點(diǎn)與目標(biāo)點(diǎn)已經(jīng)固定，則序列（）可唯一確定移動(dòng)機(jī)器人的一條運(yùn)動(dòng)路徑，若用各個(gè)點(diǎn)的坐標(biāo)表示，則可用一個(gè)的矩陣描述該條路徑，矩陣的第一行存儲(chǔ)各個(gè)點(diǎn)的橫坐標(biāo)，第二行存儲(chǔ)各個(gè)點(diǎn)的縱坐標(biāo)。由于縱線作的是等