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

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

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

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

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

6、: 移動機(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 移動機(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 移動機(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仿真平臺簡介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ī)技術(shù)、信息技術(shù)、控制理論、人工智能和傳感器技術(shù)等學(xué)科的發(fā)展和成熟，以此交叉而形成的機(jī)器人學(xué)的研究也進(jìn)入了一個嶄新的階段。機(jī)器人的研究經(jīng)歷了從可編程的、示教再現(xiàn)型的工業(yè)機(jī)器人到具有一定傳感、適應(yīng)能力的機(jī)器人再到配備多種先進(jìn)傳感器，具有自學(xué)習(xí)和較強適應(yīng)能力的智能機(jī)器人；從結(jié)構(gòu)簡單、功能單一的單機(jī)機(jī)器人到結(jié)構(gòu)復(fù)雜，適應(yīng)

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

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

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

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

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

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

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

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

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

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

33、有可視圖法、自由空間法、環(huán)境地圖法和柵格法等。常用的局部路徑規(guī)劃的方法有人工勢場法等。</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ī)器人工作空間中障礙物的運動特點的不同還可將路徑規(guī)劃分為靜態(tài)確定環(huán)境下的路徑規(guī)劃和

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

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

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

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

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

39、“學(xué)習(xí)”兩個行為，動態(tài)跟蹤兩個極值（個體最優(yōu)和群體最優(yōu)）來更新其速度和位置，經(jīng)過多次迭代，達(dá)到群體全局最優(yōu)的效果。作為一種仿生算法，粒子群算法有著個體數(shù)目少、計算簡單、魯棒性好等特點，在各類多維連續(xù)空間優(yōu)化問題上均可取得非常好的效果。同時，因為有著深刻的智能背景，它既適合科學(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>　　本篇論文重點研究采用粒子群算法進(jìn)行移動機(jī)器人路徑規(guī)劃，同時也研究了加入變異算子改進(jìn)粒子群算法時路徑優(yōu)化的效果。</p><p>　　1.4 課題研究的主要內(nèi)容及框架</p><p>　　針對采用智能算法進(jìn)行移動機(jī)器人路徑規(guī)劃研究的現(xiàn)狀，本論文主要討論了將粒子群算法應(yīng)用于復(fù)雜環(huán)境下機(jī)器人路徑規(guī)劃的問題。論文首先研究了受仿生群體行為啟發(fā)的粒子群優(yōu)化算法的原理和相關(guān)參

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

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

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

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

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

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

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

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

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

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

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

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

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

54、值大小進(jìn)行操作。所不同的是，粒子群算法不像其他進(jìn)化算法那樣，對個體使用進(jìn)化算子，而是將每個個體看作是在n維搜索空間中的沒有重量和體積的粒子，并在搜索空間中以一定的速度飛行。該飛行速度由個體的飛行經(jīng)驗和群體的飛行經(jīng)驗進(jìn)行動態(tài)調(diào)整。設(shè)為粒子i的當(dāng)前位置，為粒子i的當(dāng)前飛行速度。為粒子i所經(jīng)歷的最好位置，也就是其所經(jīng)歷的具有最好適應(yīng)值的位置，稱為個體最優(yōu)位置。對于最小化問題，目標(biāo)函數(shù)值越小，對應(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è)群體中的粒子個數(shù)為N，群體中所有粒子所經(jīng)歷過的最好位置為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之間取值，為兩個相互獨立的隨機(jī)函數(shù)。式（2.3）表明，粒

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

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

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

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

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

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

63、在保持結(jié)構(gòu)簡單特點的基礎(chǔ)上可以加快收斂速度，同時有效擺脫局部極小點的束縛。改進(jìn)粒子群算法的方法很多，本論文涉及到的方法有加慣性權(quán)重w改進(jìn)粒子群算法、位置加權(quán)到無約束解改進(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時，兩式相同，從而表明帶慣性權(quán)重的粒子群算法是基本粒子群算法的擴(kuò)展。慣性權(quán)重w表明粒子原先的速度在多大程度上得到保留。較大的w可加強PSO算法的全局搜索能力，較快地定位最優(yōu)解的大致位置；較小的w有較強的局部搜索能力，即粒子速度及位置變化減慢，開始精細(xì)的局部搜索。隨著迭代次數(shù)的增加，慣

65、性權(quán)重w應(yī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)到無約束解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

89、時間的機(jī)器人是一種很好導(dǎo)航方法。但是,其缺點是當(dāng)障礙物數(shù)目增加時,該方法的計算量會很大,影響規(guī)劃結(jié)果。</p><p>　　表1　基于模糊控制的機(jī)器人導(dǎo)航模糊規(guī)則建立</p><p>　?。?）基于神經(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ù)路徑點位于障礙物內(nèi)外的不同位置選取不同的動態(tài)運動方程,規(guī)劃出的路徑達(dá)到了折線形的最短無碰路徑,計算簡單,收斂速度快。陳宗海等提出了一種在不確定環(huán)境中移動機(jī)器人的路徑規(guī)劃方法,將全局路徑規(guī)劃分解為局部路徑規(guī)劃的組合,為了提高規(guī)劃的效率,在避障規(guī)劃中采用了基于案例的學(xué)習(xí)方法, 以ART—2神經(jīng)網(wǎng)絡(luò)實現(xiàn)案例的匹配學(xué)習(xí)和擴(kuò)充,滿足了規(guī)劃的實時性要求。為了提高機(jī)器人路徑規(guī)劃的速度,禹建麗等在利用神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃方法的基礎(chǔ)

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

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

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

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

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

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

97、解變換法，罰函數(shù)法等。對于本課題中的約束優(yōu)化問題，我們采用罰函數(shù)法將它化為無約束優(yōu)化問題。</p><p>　　罰函數(shù)法的基本思想是：對解空間中無對應(yīng)可行解的個體，計算其適應(yīng)度時，處以一個罰值，從而增加該個體的適應(yīng)度值，使得在最小優(yōu)化中該個體不被選為最優(yōu)。具體可用下式來對個體的適應(yīng)度值進(jìn)行調(diào)整：</p><p><b>　?。?.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ù)是這種處理方法的難點之處，因為這時既要考慮如何度量解對約束條件的不滿足程度，又要考慮算法進(jìn)化的效率。罰函數(shù)的強度太小的話，部分個體仍有可能破壞約束條件，罰函數(shù)的強度太大的話，會影響優(yōu)化算法的運行效率。</p><p>　　在本論文中，對于不可

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

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

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

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

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

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

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

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