智能移動機(jī)器人路徑規(guī)劃優(yōu)化方法研究論文(全)

1、智能移動機(jī)器人路徑規(guī)劃優(yōu)化方法研究一 引言(Introduction 移動機(jī)器人面對復(fù)雜的道路環(huán)境時,需要進(jìn)行路徑識別與決策。如何快速完成對復(fù) 雜環(huán)境的分析,并作出正確決策,是移動機(jī)器人程序設(shè)計(jì)中的一個重要環(huán)節(jié)。機(jī)器人路 徑規(guī)劃問題,可分為環(huán)境參數(shù)可知的路徑規(guī)劃和環(huán)境參數(shù)未知的路徑規(guī)劃。環(huán)境可知的 路徑規(guī)劃即路徑尋優(yōu)問題,能實(shí)現(xiàn)快速避障以及全局路徑最短等目的 錯誤!未找到引用 源。 ,全局路徑規(guī)劃方法采用可視圖法、圖搜索法、人工勢場法等 1.環(huán)境未知的路徑 規(guī)劃主要通過安裝在機(jī)器人身上的眾多傳感器,利用傳感器融合技術(shù)采集環(huán)境參數(shù),對 機(jī)器人的行動進(jìn)行判斷。人工神經(jīng)網(wǎng)絡(luò)的發(fā)展以及支持向量機(jī)的興起

2、,使得對環(huán)境參數(shù) 的判斷成為了系統(tǒng)辨識理論新的研究對象。環(huán)境可知的路徑規(guī)劃研究中,以往的研究方法集中在路徑搜索問題上,如文獻(xiàn) 2研究的改進(jìn)型遺傳算法,文獻(xiàn) 3所提出的神經(jīng)網(wǎng)絡(luò)快速優(yōu)化算法,都旨在從理論本身 上消除或者減小該理論所帶來的缺陷,從而保證算法的實(shí)現(xiàn)。達(dá)到優(yōu)化機(jī)器人路徑的優(yōu) 化,研究相對合理的優(yōu)化方案。二 選題背景及意義智能移動機(jī)器人(也稱自引導(dǎo)車,英文簡寫為ALV或AGV,后面簡稱移動機(jī)器 人是指室內(nèi)、道路或室外環(huán)境中無需人工干預(yù),可以自主完成行駛?cè)蝿?wù)的車輛。移動機(jī)器人是機(jī)器人學(xué)中的一個重要分支, 它集人工智能、 智能控制信息 處理、 圖像處理、監(jiān)測與轉(zhuǎn)換等專業(yè)技術(shù)為一體,跨計(jì)算機(jī)、

3、自動控制、機(jī)械、 電子等多學(xué) 科,成為當(dāng)前智能機(jī)器人研究的熱點(diǎn)之一。移動機(jī)器人是生的計(jì)算 機(jī)控制領(lǐng)域中的 最年輕一代,并在1985年后成為此領(lǐng)域中的主角被廣泛應(yīng)用于 社會生活的各方各面。移動機(jī)器人在移動過程中不可避免會遇到各式各樣的障礙物,靈活、實(shí)時的躲 開這些障礙物是衡量其性能的關(guān)鍵指標(biāo)。具有避障功能的移動機(jī)器人擁有相當(dāng)高的 社會價值,被大量應(yīng)用于航天、軍事、制造業(yè)、醫(yī)療 /交通等。路徑規(guī)劃技術(shù)是移動 機(jī)器人領(lǐng)域中的核心問題之一, 也是機(jī)器人學(xué)中研究人工智能問題的一個重要方面。 我們希望未來的機(jī)器人能具有感知、規(guī)劃和控制等高層能力。他們能從周圍的環(huán)境 中收集知識,構(gòu)造一個關(guān)于環(huán)境的符號化的世

4、界模型,并且利用這些模型來規(guī)劃、 執(zhí)行由應(yīng)用者下達(dá)的高層任務(wù)。 其中的規(guī)劃模塊能生成大部分機(jī)器人要執(zhí)行的命令, 其目標(biāo)是實(shí)現(xiàn)機(jī)器人的使用者在較高層次上給機(jī)器人下達(dá)一些較宏觀的任務(wù),由機(jī) 器人系統(tǒng)自身來填充那些較低層的細(xì)節(jié)三 復(fù)雜路徑規(guī)劃優(yōu)化方法分析在對機(jī)器人路徑規(guī)劃研究過程中,筆者發(fā)現(xiàn)對于不同的路徑規(guī)劃,會得到相同的優(yōu) 化效果。規(guī)劃路徑的多點(diǎn)重合、多周迂回、部分路段重合等因素,增加了規(guī)劃路徑的復(fù) 雜度,使通過神經(jīng)網(wǎng)絡(luò)或 n 次多項(xiàng)式擬合得到的全局優(yōu)化結(jié)果很難接近真實(shí)值,甚至出 現(xiàn)擬合曲線回歸原點(diǎn)等崩潰現(xiàn)象。如何防止這些現(xiàn)象的發(fā)生,除了引言部分提到的,將 智能算法與其他理論結(jié)合以外,還可以根據(jù)路

5、徑的特點(diǎn),選擇適當(dāng)?shù)淖鴺?biāo)原點(diǎn)并做合理 的坐標(biāo)變換,讓很難處理的復(fù)雜路徑變得容易處理,這樣,可以簡化路徑規(guī)劃中得算法 優(yōu)化問題,從而降低了理論模型的計(jì)算量。四 路徑規(guī)劃概述移動機(jī)器人路徑規(guī)劃是實(shí)現(xiàn)機(jī)器人智能的一個關(guān)鍵技術(shù),移動機(jī)器人路徑 規(guī)劃中設(shè)計(jì)的四個相關(guān)問題(1機(jī)器人如何從環(huán)境中獲取周圍的障礙物信息和其它相關(guān)信息;(2機(jī)器人如何根據(jù)內(nèi)部及外部傳感器來確定當(dāng)前處于地圖中什么位置;(3機(jī)器人如何根據(jù)其處于當(dāng)前地圖的位置和當(dāng)前地圖中信息確定行動略;(4如何產(chǎn)生合適的驅(qū)動信號使機(jī)器人運(yùn)動在預(yù)定的軌跡上。為了解決這些問題,要對相應(yīng)的四個技術(shù)進(jìn)行研究:傳感技術(shù):智能機(jī)器人的傳感器分為內(nèi)部傳感器和外部傳感

6、器,內(nèi)部傳感 器提供的信息對機(jī)器人的自定位是非常必要的。 外部傳感器用以檢測外部環(huán)境 的信 息,是建立環(huán)境的全局地圖和得到用以局部避障的機(jī)器人附近障礙信息的依據(jù)。 自定位技術(shù):,由于智能機(jī)器人得到的傳感信息是相當(dāng)于機(jī)器人的局部坐標(biāo)系 的, 而用于路徑規(guī)劃的地圖才用全局坐標(biāo)系。 如果沒有機(jī)器人的當(dāng)前位置信息, 也就沒 有局部坐標(biāo)系在地圖坐標(biāo)系中的位置,從而無法進(jìn)行運(yùn)動的規(guī)劃。運(yùn)動控制:涉及機(jī)器人的結(jié)構(gòu)、運(yùn)動學(xué)和動力學(xué)性質(zhì)。規(guī)劃和決策:規(guī)劃部分是智能機(jī)器人的智能部分,分為任務(wù)規(guī)劃和運(yùn)動規(guī)劃, 運(yùn) 動 規(guī) 劃 又 分 為 路 徑 規(guī) 劃 和 軌 跡 規(guī) 劃 。移動機(jī)器人路徑規(guī)劃是實(shí)現(xiàn)機(jī)器人智能的一個

7、關(guān)鍵技術(shù),移動機(jī)器人路徑規(guī) 劃 中涉及的四個相關(guān)問題“”:(1機(jī)器人如何從環(huán)境中獲取周圍的障礙物信息和其它相關(guān)信息;(2機(jī)器人如何根據(jù)內(nèi)部及外部傳感器來確定當(dāng)前處于地圖中什么位置;(3機(jī)器人如何根據(jù)其處于當(dāng)前地圖的位置和當(dāng)前地圖中信息確定行動策略;(4如何產(chǎn)生合適的驅(qū)動信號使機(jī)器人運(yùn)動在預(yù)定的軌跡上。五 本文的主要研究內(nèi)容本課題的核心任務(wù)就是對移動機(jī)器人路徑規(guī)劃問題的研究, 研究的目的是利用計(jì)算 機(jī)和通訊技術(shù),向行駛在道路上的機(jī)器人提供信息,引導(dǎo)機(jī)器人避開障礙物,沿著最佳的路線到達(dá)目的地,即在路段交通狀態(tài)實(shí)時動態(tài)變化的前提下,為機(jī)器人提供一條最優(yōu) 或者近似最優(yōu)的路徑解決方案。 研究的意義就是利

8、用蟻群算法來有效地解決移動機(jī)器人 的路徑規(guī)劃問題,并在計(jì)算機(jī)仿真中得到比較滿意的結(jié)果。目前蟻群算法的嚴(yán)格理論基礎(chǔ)尚未奠定,國內(nèi)外的相關(guān)研究還處于實(shí)驗(yàn)探索和初步應(yīng) 用階段。蟻群算法在機(jī)器人路徑規(guī)劃中的研究還不是很多,尤其是將其應(yīng)用于動態(tài)規(guī) 劃中更不多見。因此,本文首先提出了靜態(tài)環(huán)境下基于蟻群算法的路徑規(guī)劃方法,考 慮到移動機(jī)器人行駛過程中的實(shí)際路面情況,在靜態(tài)路徑規(guī)劃方法的基礎(chǔ)上提出了基 于蟻群算法解決動態(tài)路徑規(guī)劃的方法,并在仿真實(shí)驗(yàn)中證實(shí)了該算法的可行性和實(shí)用 性。六 路徑規(guī)劃方法路徑規(guī)劃是移動機(jī)器人導(dǎo)航技術(shù)中不可缺少的重要組成部分,它要求機(jī)器人根據(jù) 給予的指令及環(huán)境信息自主地決定路徑,避開障

9、礙物,按照某種優(yōu)化指標(biāo),使系統(tǒng)在 規(guī)定的時間內(nèi)從起始點(diǎn)轉(zhuǎn)移到目標(biāo)點(diǎn)。機(jī)器人路徑規(guī)劃方法大致可以分為兩類:傳統(tǒng) 方法和智能方法。1.傳統(tǒng)路徑規(guī)劃方法(1自由空間法。為了簡化問題,通常采用結(jié)構(gòu)空間來描述機(jī)器人及其周圍的環(huán)境。 這種方法將機(jī)器人縮小成點(diǎn),將其周圍的障礙物及邊界按比例相應(yīng)地?cái)U(kuò)大,使機(jī)器人點(diǎn) 能夠在自由空間中移動到任意一點(diǎn),而不與障礙物及邊界發(fā)生碰撞。(2圖搜索法。圖搜索方法中的路徑圖由捕捉到的存在于機(jī)器人一維網(wǎng)絡(luò)曲線(稱為 路徑圖自由空間中的節(jié)點(diǎn)組成。建立起來的路徑圖可以看作是一系列的標(biāo)準(zhǔn)路徑。而 路徑的初始狀態(tài)和目標(biāo)狀態(tài)同路徑圖中的點(diǎn)相對應(yīng), 這樣路徑規(guī)劃問題就演變?yōu)樵谶@些 點(diǎn)間搜索

10、路徑的問題。 通過起始點(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柵格解耦法。柵格解耦法是目前研究最廣泛的路徑規(guī)劃方法。該方法將機(jī)器人 的工作空間解耦為多個簡單的區(qū)域,一般稱為柵格。由這些柵格構(gòu)成了一個連通圖, 在這個連通圖上搜索一條從起始柵格到目標(biāo)柵格的路徑,這條路徑是用柵格的序號來 表示的。柵格解耦法包括確切的和不確切的兩種。確切的解耦法用來描述整個自由空 間,這將使復(fù)雜環(huán)境的解耦速度變慢,其原因是許多復(fù)雜的多邊形可能需要與障礙物 的邊界相匹配。這種方法可

11、以保證只要起始點(diǎn)到目標(biāo)點(diǎn)之間存在路徑,就完全能搜索 到這條路徑,在不確切的解耦法中,所有的柵格都是預(yù)定的形狀,為了研究方便假設(shè) 全部為矩形。整個圖被分割成多個較大的矩形,每個矩形之間都是連續(xù)的。如果大矩 形內(nèi)部包含障礙物或者邊界,則又被分割成4個小矩形,對所有較大的柵格都進(jìn)行這 種劃分,然后在劃分的最后界限內(nèi)形成的小柵格間重復(fù)執(zhí)行程序,直到達(dá)到解的界限 為止一條路徑,如果該路徑滿足起點(diǎn)到目標(biāo)點(diǎn)間無障礙物的要求則停止搜索。不確切 的解耦方法比確切的解耦方法在數(shù)學(xué)計(jì)算上要簡單的多,因此也比較容易實(shí)現(xiàn)。 (4人工勢場法。傳統(tǒng)的人工勢場法把移動機(jī)器人在環(huán)境中的運(yùn)動視為一種在抽象的 人造受力場中的運(yùn)動,

12、目標(biāo)點(diǎn)對移動機(jī)器人產(chǎn)生“引力”,障礙物對移動機(jī)器人產(chǎn)生 “斥力”,最后通過求合力來控制移動機(jī)器人的運(yùn)動,但是,由于勢場法把所有信息壓 縮為單個合力,這樣就存在把有關(guān)障礙物分布的有價值的信息拋棄的缺陷,容易陷入局 部最小值。大部分機(jī)器人路徑規(guī)劃中的全局規(guī)劃都是基于上述幾種方法進(jìn)行的,但是以 上這些傳統(tǒng)方法在路徑搜索效率及路徑優(yōu)化方面尚有待于進(jìn)一步改善。 而現(xiàn)在通常使用 的搜索技術(shù)包括:梯度法、A+等圖搜索方法、枚舉法、隨機(jī)搜索法等。這些方法中梯 度法易陷入局部最小點(diǎn),圖搜索方法、枚舉法不能用于高維的優(yōu)化問題,而隨機(jī)搜索法 則計(jì)算效率太低。2智能路徑規(guī)劃方法近年來,隨著遺傳算法等智能方法的廣泛應(yīng)用

13、,機(jī)器人路徑規(guī)劃方法也有了長足的 進(jìn)展,許多研究者把目光放在了基于智能方法的路徑規(guī)劃研究上。其中,應(yīng)用較多的算法主要有模糊方法、神經(jīng)網(wǎng)絡(luò)和遺傳算法。(1基于模糊邏輯的機(jī)器人路徑規(guī)劃模糊邏輯方法是在線規(guī)劃中通常采用的一種規(guī)劃方法,該方法根據(jù)不完整、模糊的環(huán) 境信息,參考人的駕駛經(jīng)驗(yàn)并利用模糊數(shù)學(xué)的理論,設(shè)計(jì)決策方案,以采取相應(yīng)的操 作。因此模糊控制算法的核心部分在于模糊決策表的建立。莊曉東等n”提出一種基 于模糊概念的動態(tài)環(huán)境模型,參照物體的位置和運(yùn)動信息構(gòu)造二維隸屬度函數(shù):然后 通過模糊綜合評價對各個方向進(jìn)行綜合考察,得到搜索結(jié)果。該方法在移動障礙物和 移動目標(biāo)的環(huán)境中能有效地實(shí)現(xiàn)機(jī)器人避碰和

14、導(dǎo)航。李彩虹等提出了一種在未知環(huán)境 下移動機(jī)器人的模糊控制算法, 并對此算法進(jìn)行了推導(dǎo)與仿真, 證明該算法魯棒性強(qiáng), 可消除傳統(tǒng)算法中存在的對移動機(jī)器人的定位精度敏感、 對環(huán)境信息依賴性強(qiáng)等缺點(diǎn), 使移動機(jī)器人的行為表現(xiàn)出很好的一致性、 連續(xù)性和穩(wěn)定性。 Hartmut Sur mann等提出一種未知環(huán)境下的高級機(jī)器人模糊導(dǎo)航方法,由8個不同的超聲傳感 器來提供環(huán)境信息,然后利用基于模糊控制的導(dǎo)航器來計(jì)算這些信息,規(guī)劃機(jī)器人路 徑。該方法在環(huán)境未知或發(fā)生變化的情況下能夠快速而準(zhǔn)確地規(guī)劃機(jī)器人路徑,對于 要求有較少路徑規(guī)劃時間的機(jī)器人是一種很好的導(dǎo)航方法。但是其缺點(diǎn)是沒有學(xué)習(xí)和 自適應(yīng)能力。它要

15、求設(shè)計(jì)者能定義一系列有效的避障控制規(guī)則,但事實(shí)上環(huán)境非常復(fù) 雜,突發(fā)事件也非常多,設(shè)計(jì)者不可能把所有的行為表示出來,且當(dāng)障礙物數(shù)目增加 時該方法的計(jì)算量會很大,影響規(guī)劃結(jié)果。(2基于神經(jīng)網(wǎng)絡(luò)方法的機(jī)器人路徑規(guī)劃禹建麗等n”提出了一種基于神經(jīng)網(wǎng)絡(luò)的 機(jī)器人路徑規(guī)劃算法,研究了在障礙物形狀和位置已知情況下的機(jī)器人路徑規(guī)劃算法,其 能量函數(shù)的定義利用了神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu), 根據(jù)路徑點(diǎn)位于障礙物內(nèi)外的不同位置選取不同 的動態(tài)運(yùn)動方程, 規(guī)劃出的路徑達(dá)到了折線形的最短無碰路徑, 計(jì)算簡單, 收斂速度快。 陳宗海等nm提出了一種在不確定環(huán)境中移動機(jī)器人的路徑規(guī)劃方法, 將全局路徑規(guī)劃 分解為局部路徑規(guī)劃的組合,

16、為了提高規(guī)劃的效率,在避障規(guī)劃中采用了基于案例的學(xué)習(xí)方法, 以ART-2神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)案例的匹配學(xué)習(xí)和擴(kuò)充, 滿足了規(guī)劃的實(shí)時性要求。 為了提高機(jī)器人路徑規(guī)劃的速度,禹建麗等在利用神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃方法的基礎(chǔ)上,又 引進(jìn)了線性再勵的自適應(yīng)變步長算法。這種方法實(shí)現(xiàn)了步長的自適應(yīng)選擇,使路徑規(guī)劃 速度比原來的神經(jīng)網(wǎng)絡(luò)規(guī)劃提高了10倍。但是神經(jīng)網(wǎng)絡(luò)也存在一些缺點(diǎn),神經(jīng)網(wǎng)絡(luò)中 的映射規(guī)則在網(wǎng)絡(luò)中是隱含而無法直接理解的, 因此想從神經(jīng)網(wǎng)絡(luò)內(nèi)部去調(diào)整它的權(quán)值 參數(shù)進(jìn)而改進(jìn)性能具有一定的難度。(3基于遺傳算法的機(jī)器人路徑規(guī)劃遺傳算法是目前機(jī)器人路徑規(guī)劃研究中應(yīng)用較多的一種方法,無論是單機(jī)器 人靜態(tài)工作空間,還是

17、多機(jī)器人動態(tài)工作空間,遺傳算法及其派生算法都取得了良好的路徑規(guī)劃結(jié)果。孫樹棟等“”用遺傳算法完成了離散空間下機(jī)器人的路徑規(guī) 劃,并獲得了較好的仿真結(jié)果。但是,該路徑規(guī)劃是基于確定環(huán)境模型的,即工作空 間中的障礙物位置是己知的、確定的。Kazuo Sugihara和John S mith在采用離散空間進(jìn)行路徑規(guī)劃的同時,將問題更深入化,柵格序號采用二進(jìn) 制編碼,統(tǒng)一確定其個體長度隨機(jī)產(chǎn)生障礙物位置及數(shù)目,并在搜索到最優(yōu)路徑后, 再在環(huán)境空間中隨機(jī)插入障礙物,模擬環(huán)境變化,通過仿真結(jié)果驗(yàn)證了算法的有效性 和可行性。但是,規(guī)劃空間柵格法建模還存在缺陷,若柵格劃分過粗,則規(guī)劃精度較 低:若柵格劃分太細(xì)

18、,則數(shù)據(jù)又會太大。周明等“”提出一種連續(xù)空間下基于遺傳算 法的機(jī)器人路徑規(guī)劃方法,該方法在規(guī)劃空間利用鏈接圖建模的基礎(chǔ)上,先使用圖論 中成熟算法粗略搜索出可選路徑,然后再使用遺傳算法來調(diào)整路徑點(diǎn),逐步得到較優(yōu) 的行走路線。該方法的染色體編碼不會產(chǎn)生無效路徑,且僅使用基本遺傳算法就可以 完成路徑規(guī)劃。但是該方法對于環(huán)境復(fù)雜、障礙物數(shù)目較多的情況,鏈接圖的建立會 有一定的困難。在遺傳算法的改進(jìn)上周明等提出一種遺傳模擬退火算法,利用遺傳算 法與模擬退火算法相結(jié)合來解決機(jī)器人路徑規(guī)劃問題。有效地提高了路徑規(guī)劃的計(jì)算 速度, 保證了路徑規(guī)劃的質(zhì)量。 在多移動機(jī)器人協(xié)調(diào)作業(yè)方面遺傳算法也得到了應(yīng)用, 景興

19、建等提出一種基于理性遺傳算法的協(xié)調(diào)運(yùn)動行為合成算法,針對特定環(huán)境下的多機(jī)器人協(xié)調(diào)運(yùn)動問題,基于調(diào)速避碰的思想,借助CMAC神經(jīng)網(wǎng)絡(luò),描述各機(jī)器人 的運(yùn)動行為與環(huán)境狀態(tài)之間復(fù)雜的、非線性映射關(guān)系,利用遺傳算法來合成與優(yōu)化各 機(jī)器人的運(yùn)動行為,從而實(shí)現(xiàn)多機(jī)器人己知環(huán)境下,運(yùn)動行為的相互協(xié)調(diào)與優(yōu)化。遺 傳算法由于具有優(yōu)良的全局尋優(yōu)能力和隱含的并行計(jì)算特性,所以是一個較好的路徑 規(guī)劃方法。但由于常規(guī)遺傳算法本身所存在的一些缺陷(如解的早熟現(xiàn)象、局部尋優(yōu) 能力差等 ,保證不了對路徑規(guī)劃問題的求解質(zhì)量和求解效率。(4基于混合方法的機(jī)器人路徑規(guī)劃方法L.H.Tsoukalas等提出一種用于半自主移動機(jī)器人路

20、徑規(guī)劃的模糊 神經(jīng)網(wǎng)絡(luò)方法。所謂半自主移動機(jī)器人就是具有在人類示教基礎(chǔ)上增加了學(xué)習(xí)功能的 器件的機(jī)器人。這種方法采用模糊描述來完成機(jī)器人行為編碼,同時重復(fù)使用神經(jīng)網(wǎng) 絡(luò)自適應(yīng)技術(shù)。由機(jī)器人上的傳感器提供局部的環(huán)境輸入,由內(nèi)部模糊神經(jīng)網(wǎng)絡(luò)進(jìn)行 環(huán)境預(yù)測,進(jìn)而可以在未知環(huán)境下規(guī)劃機(jī)器人路徑。此外,也有人提出基于模糊神經(jīng) 網(wǎng)絡(luò)和遺傳算法的機(jī)器人自適應(yīng)控制方法。將規(guī)劃過程分為離線學(xué)習(xí)和在線學(xué)習(xí)兩部 分。其中離線學(xué)習(xí)部分主要為模糊神經(jīng)網(wǎng)絡(luò)方法,將模糊方法分為5層:輸入、模糊 化、操作、規(guī)則、輸出,然后用神經(jīng)網(wǎng)絡(luò)對這5層的參數(shù)進(jìn)行訓(xùn)練。綜上所述,遺傳 算法等智能方法在機(jī)器人路徑規(guī)劃技術(shù)中己受到廣泛的重視及

21、研究,在障礙物環(huán)境己 知或未知情況下,均已取得一定的研究成果。而其應(yīng)用特點(diǎn)總結(jié)如下:(1在全局規(guī)劃的基礎(chǔ)上,進(jìn)行局部微調(diào),提高規(guī)劃速度及精度。(2具有一定的靈活性,可以互相結(jié)合,取長補(bǔ)短。(3具有一定的擴(kuò)展性,每種研究方法都可以完成自身的擴(kuò)展及完善。(4性能穩(wěn)定。機(jī)器人路徑規(guī)劃是機(jī)器人應(yīng)用中的一項(xiàng)重要技術(shù),采用良好的機(jī)器人路徑規(guī)劃技 術(shù)可以節(jié)省大量機(jī)器人作業(yè)時間、減少機(jī)器人磨損,同時也可以節(jié)約人力資源,減小 資金投入,為機(jī)器人在多種行業(yè)中的應(yīng)用奠定良好的基礎(chǔ)。將遺傳算法、模糊邏輯以 及神經(jīng)網(wǎng)絡(luò)等方法相結(jié)合,可以組成新的智能型路徑規(guī)劃方法,從而提高機(jī)器人路徑規(guī)劃的避障精度,加快規(guī)劃速度,滿足實(shí)際

22、應(yīng)用的需要。同時,多機(jī)器人協(xié)調(diào)作業(yè)環(huán) 境下的路徑規(guī)劃技術(shù)也將是研究的熱點(diǎn)及難點(diǎn)問題,越來越受到人們的重視。由于障 礙物及機(jī)器人數(shù)目的增加,極大地加了路徑規(guī)劃的難度引入可以優(yōu)化約簡知識的粗糙 集理論,簡化規(guī)劃條件,提取路徑規(guī)劃特征參數(shù),有可能進(jìn)一步解決諸如機(jī)器人路徑 規(guī)劃速度等難題。蟻群算法是繼模糊方法、神經(jīng)網(wǎng)絡(luò)、遺傳算法之后的又一種新興的 啟發(fā)式搜索算法。蟻群算法雖然是從研究旅行商問題(TSP提出的,但它在求解 多 種組合優(yōu)化問題中獲得了廣泛的應(yīng)用, 如二次分配、 大規(guī)模集成電路設(shè)計(jì)、 車輛調(diào) 度問題、 網(wǎng)絡(luò)路由以及負(fù)載平衡問題等一, 。 它不僅用于離散系統(tǒng)的優(yōu)化, 而且也用 于連續(xù)時間系統(tǒng)的

23、優(yōu)化。 根據(jù)蟻群算法創(chuàng)立者M(jìn). Dorigo 等人的研究實(shí)驗(yàn)表明, 蟻群算法在求解節(jié)點(diǎn)數(shù)為5100的組合優(yōu)化問題上,選用適合的參數(shù),其優(yōu)化結(jié) 果普遍好于遺傳算法(GA 、進(jìn)化算法(EP和模擬退火算法(sA 。大量問題 的求解表明,蟻群算法具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特征,本質(zhì)上是進(jìn) 化算法中的一種新型啟發(fā)式優(yōu)化算法。正反饋過程使得該方法能很快發(fā)現(xiàn)較好解;分 布式計(jì)算法使得該方法易于發(fā)現(xiàn)較好解。并且一些改進(jìn)型與混合型的蟻群算法相繼出 現(xiàn)“如引入蟻群中螞蟻分工與協(xié)同學(xué)習(xí)、協(xié)同工作的思想;將蟻群算法與遺傳算法及 免疫算法結(jié)合等,這些研究成果都推動了蟻群算法研究的深入發(fā)展。七 蟻 群 算 法

24、 研 究1. 概述生物學(xué)家通過對螞蟻的長期觀察研究發(fā)現(xiàn),每只螞蟻的智能并不高,看起來沒有集 中的指揮,但它們卻能協(xié)同工作,集中食物,建起堅(jiān)固漂亮的蟻穴并撫恤后代,依靠群 體能力發(fā)揮出超出個體的智能。 蟻群算法 (ant colony algorithm, ACA是最新發(fā)展的一種模擬昆蟲王國中螞蟻群體智能行為的仿生優(yōu)化算法,它具有 強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制、易于與其他方法相結(jié)合等優(yōu)點(diǎn)。盡管蟻群算法的 嚴(yán)格理論基礎(chǔ)尚未奠定,國內(nèi)外的相關(guān)研究還處于實(shí)驗(yàn)探索和初步應(yīng)用階段,但是目前人們對蟻群算法的研究已經(jīng)由當(dāng)初單一的旅行商問題(travelin gsalesman problem,TSP領(lǐng)域滲

25、透到了多個應(yīng)用領(lǐng)域,由解決 一維靜態(tài)優(yōu)化問題發(fā)展到解決多維動態(tài)組合優(yōu)化問題, 由離散域范圍內(nèi)的研究逐漸拓展 到了連續(xù)域范圍內(nèi)的研究, 而且在蟻群算法的硬件實(shí)現(xiàn)上也取得了很多突破性的研究進(jìn) 展,從而使這種新興的仿生優(yōu)化算法展現(xiàn)出勃勃生機(jī)和廣闊的發(fā)展前景。2.基本蟻群算法的原理(1蟻群行為描述根據(jù)仿生學(xué)家的長期研究發(fā)現(xiàn):螞蟻雖沒有視覺,但運(yùn)動時會通過在路徑上 釋放出一種特殊的分泌物信息素來尋找路徑m”。當(dāng)它們碰到一個還沒有走過的路口時, 就隨機(jī)地挑選一條路徑前行, 同時釋放出與路徑長度有關(guān)的信息素。 螞蟻?zhàn)叩穆窂皆介L,則釋放的信息量越小。當(dāng)后來的螞蟻再次碰到這個路口的時候, 選擇信息量較大路徑的概

26、率相對較大,這樣便形成了一個正反饋機(jī)制。最優(yōu)路徑上的 信息量越來越大,而其他路徑上的信息量卻會隨著時問的流逝而逐漸消減,最終整個 蟻群會找出最優(yōu)路徑。同時蟻群還能夠適應(yīng)環(huán)境的變化,當(dāng)蟻群的運(yùn)動路徑上突然出 現(xiàn)障礙物時,螞蟻也能很快地重新找到最優(yōu)路徑?？梢?在整個尋徑過程中,雖然單 只螞蟻的選擇能力有限,但是通過信息素的作用使整個蟻群行為具有非常高的自組織 性,螞蟻之問交換著路徑信息,最終通過蟻群的集體自催化行為找出晟優(yōu)路徑(2基本蟻群算法的機(jī)制原理模擬螞蟻群體覓食行為的蟻群算法是作為一種新的計(jì)算智能模式引入的,該 算法基于如下基本假設(shè):(1螞蟻之間通過信息素和環(huán)境進(jìn)行通信。每只螞蟻僅根據(jù)其周圍

27、的局部環(huán)境做出反應(yīng),也只對其周圍的局部環(huán)境產(chǎn)生影響。(2螞蟻對環(huán)境的反應(yīng)由其內(nèi)部模式?jīng)Q定。因?yàn)槲浵伿腔蛏?螞蟻的行為實(shí)際上是其基因的適應(yīng)性表現(xiàn),即螞蟻是反應(yīng)型適應(yīng)性主體。(3在個體水平上,每只螞蟻僅根據(jù)環(huán)境做出獨(dú)立選擇;在群體水平上,單只螞蟻的行為是隨機(jī)的,但蟻群可通過自組織過程形成高度有序的群體行為。由上述假設(shè)和分析可見,基本蟻群算法的尋優(yōu)機(jī)制包含兩個基本階段:適應(yīng)階段和協(xié)作階段。在適應(yīng)階段,各候選解根據(jù)積累的信息不斷調(diào)整自身結(jié)構(gòu),路徑上 經(jīng)過的螞蟻越多, 信息量越大, 則該路徑越容易被選擇; 時間越長, 信息量會越小t”, ; 在協(xié)作階段,候選解之間通過信息交流,以期望產(chǎn)生性能更好的解

28、,類似于學(xué)習(xí)自動 機(jī)的學(xué)習(xí)機(jī)制。蟻群算法實(shí)際上是一類智能多主體系統(tǒng),其自組織機(jī)制使得蟻群算法 不需要對所求問題的每一方面都有詳盡的認(rèn)識。八動態(tài)路徑規(guī)劃介紹在以前我們具體研究了基于蟻群算法的靜態(tài)路徑規(guī)劃,但是在實(shí)際的路徑規(guī)劃問題中,用戶不僅需要在出發(fā)前尋求一條從起始點(diǎn)到目的地之間的最佳路線,而 且還需要在機(jī)器人的行駛過程中,隨時接收路況信息,并動態(tài)地調(diào)整當(dāng)前所在位置到 目的地之間的最佳路線,這就是動態(tài)路徑規(guī)劃所要解決的問題。研究移動機(jī)器人的路 徑規(guī)劃,僅從機(jī)器人本身來考慮是不夠的,還要研究環(huán)境的狀態(tài)。從環(huán)境模型和障礙 物的狀態(tài)來分析,可以考慮以下四種情況:(1已知環(huán)境下的靜態(tài)障礙物,其環(huán)境中的障

29、礙物的形狀、大小和位置對規(guī)劃系統(tǒng)都是精確已知的,其障礙物是靜止不動的;(2已知環(huán)境下的動態(tài)障礙物,其環(huán)境中的障礙物的形狀、大小和位置對規(guī)劃系統(tǒng)都是精確己知的,但其位置是動態(tài)的;(3未知環(huán)境下的靜態(tài)障礙物,對機(jī)器人系統(tǒng)而言,環(huán)境信息事先是未知的或部分未知的,其障礙物的形狀和大小是未知的,但其障礙物是靜止不動的;(4未知環(huán)境下的動態(tài)障礙物,對機(jī)器人系統(tǒng)而言,環(huán)境信息事先是未知的或部分未知的,其障礙物的形狀和大小是未知的,同時其位置是動態(tài)的。移動機(jī)器人在已知環(huán)境下對靜態(tài)障礙物的避障研究,已經(jīng)趨于較為成熟的階段,但在未知環(huán)境下對動態(tài)障礙物的避障研究,仍然是移動機(jī)器人路徑規(guī)劃的研 究熱點(diǎn)。九 實(shí)驗(yàn)及仿真

30、分析 極 軸 坐 標(biāo) (m 極 軸 坐 標(biāo) (m 極 角 坐 標(biāo) (rad 極 軸 坐 標(biāo) (m X 軸 坐 標(biāo) (m 圖 10近似螺旋路徑坐標(biāo)平移轉(zhuǎn)換仿真優(yōu)化比較圖 8(a、 圖 9(a、 圖 10(a為在極坐標(biāo)展開坐標(biāo)系下, 神經(jīng)網(wǎng)絡(luò)擬合曲線與原路徑 的對比圖, 圖 8(b、 圖 9(b、 圖 10(b為轉(zhuǎn)換到直角坐標(biāo)系下神經(jīng)網(wǎng)絡(luò)擬合曲線與原路 徑的對比圖。十 結(jié)論目前人們對蟻群算法的研究已由當(dāng)初單一的TSP領(lǐng)域滲透到了多個應(yīng)用領(lǐng)域。 由解決一維靜態(tài)優(yōu)化問題發(fā)展 到 解決多維動態(tài)組合優(yōu)化問題, 由離散領(lǐng)域內(nèi)研究逐漸拓展到了連續(xù)域范圍內(nèi)研究, 而且在蟻群算法的硬件實(shí)現(xiàn)上取得了突破性進(jìn)展,同時

31、在蟻群算法的模型改 進(jìn)及與其它仿生優(yōu)化算法的融合方面也取得了相當(dāng)豐富的研究成果,從而使 這種新興。的仿生優(yōu)化算法展現(xiàn)出前所未有的勃勃生機(jī),并已經(jīng)成為一種完 全可與遺傳算法相媲美的仿生優(yōu)化算法。 并避免了因路徑復(fù)雜帶來的各種智能 算法局部最小問題。訓(xùn)練穩(wěn)定,逼近精度高,能夠應(yīng)用于機(jī)器人路徑規(guī)劃的優(yōu)化中去。個 體 智 能 不 高 的 螞 蟻 通 過 協(xié) 同 工 作 , 依 靠 群 體 能 力 發(fā) 揮出 超 出 個 體 的 智 能 。蟻群算法就是一種模擬螞蟻群體智能行為的仿生優(yōu)化算法,它具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制、易于與其他方法相結(jié)合等優(yōu)點(diǎn)。本文主要研究了基于蟻 群算法的移動機(jī)器人路徑規(guī)

32、劃方法,在對靜態(tài)環(huán) 境下機(jī)器人的路徑規(guī)劃研究的基礎(chǔ)上提出了動態(tài)規(guī)劃方法。具體地,本論文主 要進(jìn)行了 以下方面的工作:(1介紹了移動機(jī)器人路徑規(guī)劃的發(fā)展歷程及其相關(guān)應(yīng)用。(2詳細(xì)研究了各種路徑規(guī)劃方法,并對各種方法進(jìn)行了優(yōu)缺點(diǎn)比較及分析;同時對蟻群算法也進(jìn)行了研究。(3在基于柵格的機(jī)器人環(huán)境中,將蟻群算法應(yīng)用于移動機(jī)器人路徑規(guī)劃問題上,并在對靜態(tài)環(huán)境下機(jī)器人的路徑規(guī)劃研究的基礎(chǔ)上提出了動態(tài)規(guī)劃方法。(4最后,在MATLAB仿真環(huán)境中對該算法進(jìn)行了分析和研究,通過實(shí)驗(yàn)證明了該算法的可行性,并對動態(tài)規(guī)劃進(jìn)行了仿真,證明了其可行性及有效性。在整個研究過程中,本文得到了如下四個結(jié)論:(1將蟻群算法應(yīng)用于

33、移動機(jī)器人的路徑規(guī)劃問題中是可行的和有效的。(2規(guī)劃方法的選擇對路徑規(guī)劃有很大的影響。對某一種方法而言,它可能在某些環(huán)境下規(guī)劃效果非常好,而在其它一些環(huán)境下另外一種規(guī)劃方法卻非常好。在本文的研究中可以發(fā)現(xiàn),相同環(huán)境下,本文提出的基于蟻群算法的機(jī)器人路徑規(guī)劃方法在搜索時間上比遺傳算法至少節(jié)約5%的時間;而在空間復(fù)雜度上該算法(3等參數(shù)的最佳配置對發(fā)揮蟻群算法在實(shí)際問題中的作用是非常重要的,參數(shù)的設(shè)置主要依賴于實(shí)驗(yàn)的統(tǒng)計(jì)數(shù)據(jù)和經(jīng)驗(yàn)值。(4 螞蟻具有適應(yīng)環(huán)境變化的能力, 當(dāng)蟻群的運(yùn)動路徑上突然出現(xiàn)障礙物時, 螞蟻能及時的重新找到最優(yōu)路徑?；谙伻旱倪@個能力,我們將其應(yīng)用于機(jī) 器人的動態(tài)路徑規(guī)劃中。在

34、仿真實(shí)驗(yàn)中我們可以看到,當(dāng)行駛過程中突然出 現(xiàn)障礙物時,機(jī)器人可以迅速避開并以至少節(jié)省10%的通行時 間的新路 徑行駛到終點(diǎn)。目前蟻群算法的嚴(yán)格理論基礎(chǔ)尚未奠定,國內(nèi)外的相關(guān)研究 還處于實(shí)驗(yàn)探索和初步應(yīng)用階段。蟻群算法在機(jī)器人 路徑規(guī)劃中的研究還 不是很多,尤其是將其應(yīng)用于動態(tài)規(guī)劃中更不多見。因此,將蟻群算法應(yīng)用 于機(jī)器入的路徑規(guī)劃研究具有很高的研究價值。由于本人水平及時間的限 制,本文的工作還有許多地方需要進(jìn)一步改進(jìn):(1基于蟻群算法的路徑規(guī)劃存在一些不足之處,如搜索速度較參數(shù)選取不穩(wěn)定等缺點(diǎn)。為了克服這些缺點(diǎn)。希望后期可以提出一些有效 的改進(jìn)方案。(2本課題只進(jìn)行了特定情況下的方法仿真,整個仿真過程中將機(jī)器人當(dāng)作了一個