【正文】 境按垂直于起始點(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ī)劃出來的構(gòu)型空間易于表示，減小了算法的復(fù)雜度，有利于路徑優(yōu)化的實(shí)現(xiàn)。 路徑規(guī)劃的方法 移動(dòng)機(jī)器人的路徑規(guī)劃研究是一個(gè)比較活躍的領(lǐng)域。其中對(duì)規(guī)劃方法的研究已經(jīng)形成了很多成熟的理論。路徑規(guī)劃的方法可分為傳統(tǒng)方法和智能方法兩大類，下面分別進(jìn)行闡述。（1）自由空間法為了簡(jiǎn)化問題,通常采用“結(jié)構(gòu)空間”來描述機(jī)器人及其周圍的環(huán)境。這種方法將機(jī)器人縮小成點(diǎn),將其周圍的障礙物及邊界按比例相應(yīng)地?cái)U(kuò)大,使機(jī)器人點(diǎn)能夠在障礙物空間中移動(dòng)到任意一點(diǎn),而不與障礙物及邊界發(fā)生碰撞。（2）圖搜索法圖搜索方法中的路徑圖由捕捉到的存在于機(jī)器人一維網(wǎng)絡(luò)曲線(稱為路徑圖)自由空間中的節(jié)點(diǎn)組成。建立起來的路徑圖可以看作是一系列的標(biāo)準(zhǔn)路徑。而路徑的初始狀態(tài)和目標(biāo)狀態(tài)同路徑圖中的點(diǎn)相對(duì)應(yīng),這樣路徑規(guī)劃問題就演變?yōu)樵谶@些點(diǎn)間搜索路徑的問題。通過起始點(diǎn)和目標(biāo)點(diǎn)及障礙物的頂點(diǎn)在內(nèi)的一系列點(diǎn)來構(gòu)造可視圖。連接這些點(diǎn),使某點(diǎn)與其周圍的某可視點(diǎn)相連(即使相連接的兩點(diǎn)間不存在障礙物或邊界)。然后機(jī)器人沿著這些點(diǎn)在圖中搜索最優(yōu)路徑。（3）人工勢(shì)場(chǎng)法　 人工勢(shì)場(chǎng)法是 Khatib 提出的 [6]。其基本思想是將機(jī)器人的工作空間看作一種虛擬力場(chǎng),障礙物產(chǎn)生對(duì)機(jī)器人的排斥力,使得機(jī)器人不會(huì)進(jìn)入障礙物范圍，目標(biāo)產(chǎn)生對(duì)機(jī)器人的吸引力,使得機(jī)器人奔向目標(biāo)。以吸引力和排斥力的合力作為機(jī)器人的加速力，用該力來控制機(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ī)器人系統(tǒng)的路徑規(guī)劃算法研究12部最小值，使機(jī)器人在到達(dá)目標(biāo)點(diǎn)之前就停留在局部最優(yōu)點(diǎn)。除此之外，勢(shì)場(chǎng)法還存在三個(gè)方面的問題：1）在相近障礙物之間不能發(fā)現(xiàn)路徑；2）在障礙物前面振蕩；3）在狹窄通道中擺動(dòng)。大部分機(jī)器人路徑規(guī)劃都是基于上述幾種方法進(jìn)行的,但是以上這些傳統(tǒng)方法在路徑搜索效率及路徑優(yōu)化方面尚有待于進(jìn)一步改善。而現(xiàn)在通常使用的搜索技術(shù)包括:梯度法,圖搜索方法,枚舉法、隨機(jī)搜索法等。這些方法中梯度法易陷入局部最小點(diǎn),圖搜索方法、枚舉法不能用于高維的優(yōu)化問題,而隨機(jī)搜索法則計(jì)算效率太低。 智能路徑規(guī)劃方法近年來,隨著粒子群等智能方法的廣泛應(yīng)用,機(jī)器人路徑規(guī)劃方法也有了長(zhǎng)足的進(jìn)展,許多研究者把目光放在了基于智能方法的路徑規(guī)劃研究上。其中,應(yīng)用較多的算法主要有模糊方法、神經(jīng)網(wǎng)絡(luò)、遺傳算法和粒子群算法等。（1）基于模糊邏輯的機(jī)器人路徑規(guī)劃模糊方法是在線規(guī)劃中通常采用的一種規(guī)劃方法，包括建模和局部規(guī)劃。莊曉東等提出一種基于模糊概念的動(dòng)態(tài)環(huán)境模型,參照物體的位置和運(yùn)動(dòng)信息構(gòu)造二維隸屬度函數(shù)，然后通過模糊綜合評(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)機(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è)不同的超聲傳感器來提供環(huán)境信息,然后利用基于模糊控制的導(dǎo)航器來計(jì)算這些信息,規(guī)劃?rùn)C(jī)器人路徑 [7]。其模糊規(guī)則建立見表 1。該方法在環(huán)境未知或發(fā)生變化的情況下,能夠快速而準(zhǔn)確地規(guī)劃?rùn)C(jī)器人路徑,對(duì)于要求有較少路徑規(guī)劃時(shí)間的機(jī)器人是一種很好導(dǎo)航方法。但是,其缺點(diǎn)是當(dāng)障礙物數(shù)目增加時(shí),該方法的計(jì)算量會(huì)很大,影響規(guī)劃結(jié)果。表 1　基于模糊控制的機(jī)器人導(dǎo)航模糊規(guī)則建立命令 模糊量 命令 模糊量停止面向前下個(gè)命令左轉(zhuǎn)下個(gè)命令右轉(zhuǎn)后退立即左轉(zhuǎn)0∈[ 015,015]1∈[015,115]2∈[115,215]3∈[215,315]4∈[315,415]5∈[415,515]立即右轉(zhuǎn)前行轉(zhuǎn)向新:前一個(gè)命令左轉(zhuǎn)新:前一個(gè)命令右轉(zhuǎn)—6∈[515,615]7∈[615,715]8∈[715,815]9∈[815,915]10∈[915,1015]—（2）基于神經(jīng)網(wǎng)絡(luò)方法的機(jī)器人路徑規(guī)劃 　禹建麗等提出了一種基于神經(jīng)網(wǎng)絡(luò)的機(jī)器人路徑規(guī)劃法,研究了障礙物形狀和位置已知情況下的機(jī)器人路徑規(guī)劃算法,其能量函數(shù)的定義利用了神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)根據(jù)路徑點(diǎn)位于障礙物內(nèi)外的不同位置選取不同的動(dòng)態(tài)運(yùn)動(dòng)方程,規(guī)劃出的路徑達(dá)到了折線形的最短無碰路徑,計(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ǔ)上,又引進(jìn)了線性再勵(lì)的自適應(yīng)變步長(zhǎng)算法。這種方法實(shí)現(xiàn)了步長(zhǎng)的自適應(yīng)選擇,使路徑規(guī)劃速度比原來的神經(jīng)網(wǎng)絡(luò)規(guī)劃提高了 10 倍左右。華東交通大學(xué)畢業(yè)設(shè)計(jì)13（3）基于遺傳算法的機(jī)器人路徑規(guī)劃 遺傳算法是一種借鑒生物界自然選擇和遺傳機(jī)制的搜索算法，采用從自然界選擇，群體進(jìn)化中抽象出來的幾個(gè)算子——復(fù)制、交叉和變異操作，對(duì)群體某項(xiàng)指標(biāo)進(jìn)行優(yōu)化。由于它具有簡(jiǎn)單、健壯、隱含并行性和全局優(yōu)化等優(yōu)點(diǎn)，對(duì)于傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性問題具有良好的適用性。應(yīng)用遺傳算法解決自主移動(dòng)機(jī)器人路徑規(guī)劃問題，可以避免困難的理論推導(dǎo),直接獲得問題的最優(yōu)解。（4）基于粒子群算法的機(jī)器人路徑規(guī)劃 粒子群算法是應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃中的一種新的方法，由于其計(jì)算簡(jiǎn)單，魯棒性強(qiáng)，規(guī)劃出的路徑好，已受到優(yōu)化領(lǐng)域?qū)＜业膹V泛重視。粒子群算法適宜于連續(xù)空間下機(jī)器人的路徑規(guī)劃，該算法在規(guī)劃空間上采用與遺傳算法相同的鏈接圖建模法，其次使用圖論中成熟的算法粗略搜索出可選路徑（多條） ，最后通過粒子群算法優(yōu)化各條路徑并得出全局最優(yōu)（群體最優(yōu)）解。有關(guān)用粒子群優(yōu)化進(jìn)行路徑規(guī)劃的細(xì)節(jié)，將在第四章重點(diǎn)闡述，它是本論文研究的重點(diǎn)內(nèi)容。 約束優(yōu)化問題及處理方法 約束優(yōu)化問題的描述在科學(xué)與工程領(lǐng)域中，許多極值問題的求解往往受到各種現(xiàn)實(shí)因素的制約，這些制約通常由一系列的約束條件來描述，求解帶約束條件的極值問題則被稱為約束優(yōu)化問題（Constrained Optimization） 。具體可由下述一般形式的非線性規(guī)劃來表示： （）miXgtsEfin,32,10)(.mn????　 　　 　 　 　 　 　　 　 　 　其中 表示問題的約束條件。)(Xgi由于約束條件的存在，使得約束極值問題的求解要比無約束極值的求解復(fù)雜、困難的多。對(duì)于約束極小值問題來說，不僅要使得目標(biāo)函數(shù)在迭代過程中不斷減小，而且還要注意解的可行性。為了簡(jiǎn)化約束優(yōu)化問題的尋優(yōu)過程，通常可用將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題、將非線性規(guī)劃問題轉(zhuǎn)化為線性優(yōu)化問題的方法，把復(fù)雜的問題簡(jiǎn)單化。移動(dòng)機(jī)器人路徑規(guī)劃問題就是一種帶約束的優(yōu)化問題，即是在滿足機(jī)器人不與障礙物相撞的條件下，尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑。約束條件為機(jī)器人路徑不與障礙物相交。為此需要尋求使得表示路徑長(zhǎng)度的目標(biāo)函數(shù)取得極小值的可行解（一個(gè)解表示機(jī)器人的一條路徑） 。對(duì)于不可行解，要通過約束優(yōu)化問題的處理方法，化之為無約束優(yōu)化問題。 約束優(yōu)化問題的處理方法處理約束優(yōu)化問題常用的方法有三種：搜索空間限定法，可行解變換法，罰函數(shù)法等。對(duì)于本課題中的約束優(yōu)化問題，我們采用罰函數(shù)法將它化為無約束優(yōu)化問題。罰函數(shù)法的基本思想是：對(duì)解空間中無對(duì)應(yīng)可行解的個(gè)體，計(jì)算其適應(yīng)度時(shí)，處以一個(gè)罰值，從而增加該個(gè)體的適應(yīng)度值，使得在最小優(yōu)化中該個(gè)體不被選為最優(yōu)。具體井雅潔：多機(jī)器人系統(tǒng)的路徑規(guī)劃算法研究14可用下式來對(duì)個(gè)體的適應(yīng)度值進(jìn)行調(diào)整： （）????? )()()( 不 滿 足 約 束 條 件　 　 　 　 　 滿 足 約 束 條 件　 　 　 　 　 　 　 　 XPXfF式中 f(X)為原適應(yīng)度函數(shù)，F(xiàn)(X)為考慮了罰函數(shù)之后新的適應(yīng)度函數(shù)，P(X)為罰函數(shù)。如何確定合理的罰函數(shù)是這種處理方法的難點(diǎn)之處，因?yàn)檫@時(shí)既要考慮如何度量解對(duì)約束條件的不滿足程度，又要考慮算法進(jìn)化的效率。罰函數(shù)的強(qiáng)度太小的話，部分個(gè)體仍有可能破壞約束條件，罰函數(shù)的強(qiáng)度太大的話，會(huì)影響優(yōu)化算法的運(yùn)行效率。在本論文中，對(duì)于不可行解，即與障礙物碰撞的路徑解，需要根據(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)化為無約束條件下的路徑尋優(yōu)。4 基于粒子群優(yōu)化的路徑規(guī)劃算法及仿真本章重點(diǎn)研究粒子群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用。主要內(nèi)容有問題描述與環(huán)境建模、生成初始化路徑、采用各種改進(jìn)粒子群進(jìn)化算法優(yōu)化路徑及仿真結(jié)果分析等。其中，針對(duì)局部極小問題，研究了改進(jìn)算法，如位置加權(quán)法和加變異算子法的解決效果。 本課題的研究是通過編程仿真實(shí)現(xiàn)的，使用的仿真平臺(tái)是 MATLAB 。MATLAB 意為矩陣實(shí)驗(yàn)室（matrix laboratory） ，是一種功能強(qiáng)、效率高、簡(jiǎn)單易學(xué)的科學(xué)計(jì)算語言。它以矩陣和數(shù)組為基本數(shù)據(jù)處理單元，能高效的處理大量的數(shù)據(jù)，有著強(qiáng)大的數(shù)值計(jì)算和數(shù)據(jù)分析功能。同時(shí)它也有強(qiáng)大的繪圖功能，通過調(diào)用不同的繪圖函數(shù)設(shè)置圖形的屬性，如坐標(biāo)范圍、圖形線型、圖題和繪制柵格等，用戶不需要過多地考慮繪圖細(xì)節(jié)，只需給出一些基本參數(shù)，就能繪制所需圖形。 MATLAB 命令有兩種執(zhí)行方式：一種是交互式的命令執(zhí)行方式，另一種是 M 文件執(zhí)行方式。仿真過程中的程序都存在 M 文件中，運(yùn)行程序，即可執(zhí)行文件中的命令。 作為一種演算式執(zhí)行語言，MATLAB 編程方便，使用靈活，容易掌握，已廣泛應(yīng)用于科學(xué)及工程計(jì)算領(lǐng)域 [8]。本次畢業(yè)設(shè)計(jì)主要利用 M 文件編寫程序，充分利用它強(qiáng)大的數(shù)華東交通大學(xué)畢業(yè)設(shè)計(jì)15據(jù)處理功能和繪圖功能進(jìn)行實(shí)驗(yàn)仿真。 問題描述與環(huán)境建模 在進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃時(shí)，首先必須用計(jì)算機(jī)語言描述機(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)確定，可用大小已知的圓形描述，半徑為機(jī)器人與障礙物碰撞半徑，在半徑以外即無碰撞危險(xiǎn)，且在機(jī)器人運(yùn)動(dòng)過程中障礙物的形狀、位置、大小均不發(fā)生變化；（3）忽略障礙物的高度信息，即用(x,y)平面來描述；（4）為了保證路徑不太接近障礙物，把障礙物的邊界向外擴(kuò)展機(jī)器人本體的長(zhǎng)寬方向上最大尺寸的 1/2加上傳感器最小傳感距離，機(jī)器人可看作質(zhì)點(diǎn)，尺寸大小忽略不計(jì)。圖 41 為所構(gòu)建的機(jī)器人運(yùn)動(dòng)空間的平面模型，S 為起始點(diǎn)，G 為目標(biāo)點(diǎn)（終止點(diǎn)） ，3 個(gè)圓為分布于機(jī)器人工作空間的障礙物。如此建立的工作空間模型是靜態(tài)的，對(duì)于動(dòng)態(tài)不確定環(huán)境中的移動(dòng)機(jī)器人路徑規(guī)劃問題，可以將它看成是分階段靜態(tài)環(huán)境規(guī)劃問題的疊加。即在兩次通過傳感器采樣環(huán)境信息的時(shí)間間隔內(nèi)，認(rèn)為環(huán)境信息是固定不變的，根據(jù)這些信息可以按靜態(tài)環(huán)境進(jìn)行路徑規(guī)劃。這時(shí)需要算法的實(shí)時(shí)性高、收斂速度快，以保證在環(huán)境信息沒有大的變化時(shí)就可規(guī)劃出機(jī)器人的路徑，否則規(guī)劃出的路徑是無效的。為減小算法的復(fù)雜度，這里研究固定障礙物環(huán)境下路徑規(guī)劃的問題，其算法可以應(yīng)用于動(dòng)態(tài)不確定環(huán)境機(jī)器人的路徑規(guī)劃。我們采用區(qū)域劃分的環(huán)境建模思想，對(duì)機(jī)器人的工作環(huán)境依實(shí)際情況的需要作縱向劃分 [9]。為了便于計(jì)算和研究，這里作縱向 n 等分，n 條豎線用 表示。移動(dòng)機(jī)nL,21?器人從起始點(diǎn) S 到目標(biāo)點(diǎn) G 的無碰路徑一定與每條豎線都有一個(gè)交點(diǎn)，從左到右依次記為 。那么路徑規(guī)劃即可表示在區(qū)域邊界確定的范圍內(nèi)，在每一條豎線 上找nP,21? i一個(gè)合適的點(diǎn) ，組成一個(gè)點(diǎn)的序列（S, ,G） ?？紤]到起始點(diǎn)與目標(biāo)點(diǎn)已經(jīng)固i nP,21?定，則序列（ ）可唯一確定移動(dòng)機(jī)器人的一條運(yùn)動(dòng)路徑，若用各個(gè)點(diǎn)的坐標(biāo)n,21?表示，則可用一個(gè) 的矩陣描述該條路徑，矩陣的第一行存儲(chǔ)各個(gè)點(diǎn)的橫坐標(biāo)，第二?行存儲(chǔ)各個(gè)點(diǎn)的縱坐標(biāo)。由于縱線作的是等分，各個(gè)點(diǎn)的橫坐標(biāo)有固定的等差關(guān)系，即每個(gè)相交點(diǎn)橫坐標(biāo)是已知的，可不必表示出來。那么一個(gè) 的向量 即n?1??nxX,21??可表示移動(dòng)機(jī)器人的一條路徑（一個(gè)個(gè)體） ，其中 為 點(diǎn)的縱坐標(biāo)，X 也稱作路徑規(guī)劃ixiP問題的一個(gè)解。井雅潔：多機(jī)器人系統(tǒng)的路徑規(guī)劃算法研究160 10 20 30 40 50 60 70 80 90 100504030201001020304050S GL1 L2 L3 L4 L5 L6 L7 L8 L9圖 41 構(gòu)建環(huán)境模型如果把 作為豎直線上可上下移動(dòng)的未知可變量，障礙物作為約束限制，這樣可得ix一個(gè)移