機(jī)器人路徑規(guī)劃

《機(jī)器人路徑規(guī)劃》由會(huì)員分享，可在線閱讀，更多相關(guān)《機(jī)器人路徑規(guī)劃（75頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、機(jī)器人路徑規(guī)劃 馮赟: 機(jī)器人路徑規(guī)劃方法研究 1 緒論 1.1 機(jī)器人簡介 1.1.1 什么是機(jī)器人 機(jī)器人一詞不僅會(huì)在科幻小說、動(dòng)畫片等上看到和聽到，有時(shí)也會(huì)在電視上看 到在工廠進(jìn)行作業(yè)的機(jī)器人，在實(shí)際中也有機(jī)會(huì)看到機(jī)器人的展示。今天，說不定 機(jī)器人就在我們的身過，但這里我們要討論的是什么是機(jī)器人學(xué)研究的機(jī)器人。 robot) 一詞來源下 1920 年捷克作家卡雷爾.查培克(Kapel Capek)機(jī)器人( 所編寫的戲劇中的人造勞動(dòng)者，在那里機(jī)器人被描寫成像奴隸那樣進(jìn)行勞動(dòng)的 機(jī)器。 后來作為一種虛構(gòu)的機(jī)械出現(xiàn)在許多作品中，代替人們?nèi)ネ瓿赡承┕ぷ鳌?20 世 紀(jì) 60 年代出現(xiàn)了作為可實(shí)用

2、機(jī)械的機(jī)器人。為了反這種機(jī)器人同虛構(gòu)的機(jī)器人及 玩具機(jī)器人加以區(qū)別，稱其為工業(yè)機(jī)器人。 工業(yè)機(jī)器人的興起促進(jìn)了大學(xué)及研究所開展機(jī)器人的研究。隨著計(jì)算機(jī)的普 及，又積極地開展了帶有智能的機(jī)器人的研究。到 70 年代，機(jī)器人作為工程對(duì)象 已經(jīng)被確認(rèn)，機(jī)器人一詞也受到公認(rèn)。目前，機(jī)器人學(xué)的研究對(duì)象已不僅僅是工業(yè) 機(jī)器人了。 即便是實(shí)際存在的機(jī)器人，也很難把它定義為機(jī)器人，而且其定義也隨著時(shí)代 在變化。這里簡單地反具有下述性質(zhì)的機(jī)械看作是機(jī)器人 : 1. 代替人進(jìn)行工作 : 機(jī)器人能像人那樣使用工具和機(jī)械，因此，數(shù)控機(jī)床和 汽車不是機(jī)器人。 2. 有通有性 : 既可簡單地變換所進(jìn)行的作為，又能按照工作

3、狀況的變化相應(yīng) 地進(jìn)行工作。一般的玩具機(jī)器人不能說有通用性。 3. 直接對(duì)個(gè)界作工作 : 不僅是像計(jì)算機(jī)那樣進(jìn)行計(jì)算，而且能依據(jù)計(jì)算結(jié)果 對(duì)外界結(jié)果對(duì)外界產(chǎn)生作用。 機(jī)器人學(xué)把這樣定義的機(jī)器人作為研究對(duì)象。 - 1 - 鄭州大學(xué)電氣工程學(xué)院畢業(yè)設(shè)計(jì) （ 論文） 1.1.2 機(jī)器人的分類 機(jī)器人的分類方法很多，這里我們依據(jù)三個(gè)有代表性的分類方法列舉機(jī)器人的 種類。 首先，由天機(jī)器人要代替人進(jìn)行作業(yè)，因此可根據(jù)代替人的哪一個(gè)器官來分類 操作機(jī)器人 （ 手）: 利用相當(dāng)于手臂的機(jī)械手、相當(dāng)于手指的手爪來使物體協(xié) 作。 移動(dòng)機(jī)器人 （腿）: 雖然已開發(fā)出了 2 足步行和 4 足步行機(jī)器人，但實(shí)用的卻是

4、 用車輪進(jìn)行移動(dòng)的機(jī)器人。 （ 本文以輪式移動(dòng)機(jī)器人作為研究對(duì)象 ） 視覺機(jī)器人 （ 眼）: 通過外觀檢查來除掉殘次品，觀看人的面孔認(rèn)出是誰。雖然 還有使用觸覺的機(jī)器人，但由于它不是為了操作，所以不能說是觸覺機(jī)器人。 也還有不僅代替單一器官的機(jī)器人，例如進(jìn)行移動(dòng)操作，或進(jìn)行視覺和操作的 機(jī)器人。 其次，按機(jī)器人的應(yīng)用來分類 : 工業(yè)機(jī)器人 : 可分為搬送、焊接、裝配、噴漆、檢查等機(jī)器人，主要用于工廠 內(nèi)。 極限作業(yè)器人 : 主要用在人們難以進(jìn)入的核電站、海底、宇宙空間等進(jìn)行作為 的機(jī)器人。也包括建筑、農(nóng)業(yè)機(jī)器人等。娛樂機(jī)器人 : 有彈奏樂器的機(jī)器人、舞蹈機(jī)器人、寵物機(jī)器人等，具有某種程 度的通

5、用性。也有適應(yīng)環(huán)境面改變行動(dòng)的寵物機(jī)器人。 最后則是按照基于什么樣的信息進(jìn)行動(dòng)作來分類 : 表 1 基于動(dòng)作信息的機(jī)器人分類 機(jī)器人的種類 特征 操縱機(jī)器人 (operating robot) 人在一定距離處直接操作 機(jī)器人時(shí)行作業(yè) 程序機(jī)器人 (sequence control robot) 機(jī)器人按預(yù)先給定的程 序、條件、位置進(jìn)行作 業(yè) 示教再現(xiàn)機(jī)器人 (playback robot) 由人操作機(jī)器人進(jìn)行示教后，機(jī)器人就重 復(fù)進(jìn) 行這個(gè)作業(yè) 數(shù)值控制機(jī)器人 (numerical control 通過數(shù)字和語言給定作為的順序、條 件、位置 robot) 等信息，機(jī)器人依據(jù)這一信息進(jìn)行作業(yè) 智

6、能機(jī)器人 (intelligent robot) 機(jī)器人依據(jù)智能 ( 感覺信息的識(shí)別、作業(yè)規(guī)劃、 學(xué)習(xí)等能力 ) 確定作業(yè) - 2 - 馮赟: 機(jī)器人路徑規(guī)劃方法研究 本文主要以室內(nèi)輪式移動(dòng)機(jī)器人作為研究對(duì)象，從安照的信處進(jìn)進(jìn)行動(dòng)作上來 分類屬于程序機(jī)器人。 1.2 移動(dòng)機(jī)器人 1.2.1 移動(dòng)機(jī)器人的發(fā)展概述 移動(dòng)機(jī)器人技術(shù)自上世紀(jì) 60 年代以來，經(jīng)歷 40 年的發(fā)展已經(jīng)取得了長足的進(jìn) 步。 60 年代末期，斯坦福研究院 (SRI) 的 Ni1SNi1SSen 和 CharleSRosen 等人以研 究在復(fù)雜環(huán)境下， 應(yīng)用人工智能技術(shù)實(shí)現(xiàn)機(jī)器人系統(tǒng)的自主推理、 規(guī)劃和控制為目 的， 在 1

7、966年至 1972 年期間制造出了取名 Shakey 的自主移動(dòng)機(jī)器人；70 年代 末，隨著計(jì)算機(jī)的應(yīng)用和傳感技術(shù)的發(fā)展，移動(dòng)機(jī)器人研究又出現(xiàn)了新的高潮 ;80 年代中期，設(shè)計(jì)和制造機(jī)器人的浪潮席卷了全世界 ；90 年代以來，以研制高水平的 環(huán)境信息傳感器和信息處理技術(shù)、高適應(yīng)性的移動(dòng)機(jī)器人控制技術(shù)、真實(shí)環(huán)境下的 規(guī)劃技術(shù)為標(biāo)志，開展了移動(dòng)機(jī)器人更高層次的研究。 移動(dòng)機(jī)器人控制技術(shù)、真實(shí)環(huán)境下的規(guī)劃技術(shù)為標(biāo)志，開展了移動(dòng)機(jī)器人更高 層次的研究。 移動(dòng)機(jī)器人按工作環(huán)境可分為 : 室內(nèi)移動(dòng)機(jī)器人、室外移動(dòng)機(jī)器人和特殊環(huán)境 下的機(jī)器人 ； 按移動(dòng)方式可分為 : 輪式移動(dòng)機(jī)器人、步行移動(dòng)機(jī)器人、蛇形

8、機(jī)器人、履帶式 移動(dòng)機(jī)器人、爬行機(jī)器人等 ； 按控制體系結(jié)構(gòu)可分為 : 功能式 （水平式 ） 結(jié)構(gòu)機(jī)器人、 行為式 （垂直式 ） 結(jié)構(gòu)機(jī)器人和混合式機(jī)器人 ； 按功能和用途可分為 : 醫(yī)療機(jī)器人、軍用機(jī)器人、助殘機(jī)器人、清潔機(jī)器人、 地下管道檢測移動(dòng)機(jī)器人、行星探測機(jī)器人等 ； 按作業(yè)空間可分為 : 陸地移動(dòng)機(jī)器人、水下機(jī)器人、無人飛機(jī)和空間機(jī)器人。 移動(dòng)機(jī)器人的研究涉及許多方面，首先，要考慮移動(dòng)方式，可以是輪式的、履 帶式、腿式的 ； 對(duì)于水下機(jī)器人，則是推進(jìn)器。其次，必需考慮驅(qū)動(dòng)器的控制，以 使機(jī)器人達(dá)到期望的行為。再次，必需考慮導(dǎo)航或路徑規(guī)劃，對(duì)于后者，有更多的 方面要考慮，如傳感器的融

9、合、特征提取、避碰及環(huán)境映射。移動(dòng)機(jī)器人是一個(gè)集 環(huán)境感知、動(dòng)態(tài)決策與規(guī)劃、行為控制與執(zhí)行等多功能于一體的綜合系統(tǒng)。對(duì)移動(dòng) 機(jī)器人的研究，提出了許多新的或挑戰(zhàn)性的理論與工程技術(shù)課題，引起越來越多的 專家學(xué)者和工程技術(shù)人員的興趣，更由于它在軍事偵察、防核化污染、掃雷排險(xiǎn)等 危險(xiǎn)與惡劣環(huán)境以及民用中的物料搬運(yùn)上具有廣闊的應(yīng)用前景，使得對(duì)它的研究在世界各國受到普遍關(guān)注。目前，移動(dòng)機(jī)器人特別是自主移動(dòng)機(jī)器人的研究是一個(gè)十 分活躍、具有廣泛應(yīng)用前景的前沿研究領(lǐng)域。 - 3 - 鄭州大學(xué)電氣工程學(xué)院畢業(yè)設(shè)計(jì) （ 論文） 1.2.2 移動(dòng)機(jī)器人的國外發(fā)展概況 上世紀(jì) 80 年代開始，美國國防高級(jí)研究計(jì)劃局（

10、DA 即 A）專門立項(xiàng)，制定了地 面天人作戰(zhàn)平臺(tái)的戰(zhàn)略計(jì)劃。從此，室外移動(dòng)機(jī)器人的研究在全世界拉開了序幕， 如日本通產(chǎn)省組織的極限環(huán)境下作業(yè)的機(jī)器人計(jì)劃 ；DARPA 勺“戰(zhàn)略計(jì)算機(jī)”計(jì)劃 中的自主地面車輛（ALV）計(jì)劃；歐洲尤里卡中的機(jī)器人計(jì)劃等。初期的研究，主要從 學(xué)術(shù)角度研究室外機(jī)器人的體系結(jié)構(gòu)和信息處理，并建立實(shí)驗(yàn)系統(tǒng)進(jìn)行驗(yàn)證。隨著 技術(shù)的進(jìn)步，移動(dòng)機(jī)器人的研究開始轉(zhuǎn)向?qū)嵱没?，機(jī)器人技術(shù)被應(yīng)用到各個(gè)領(lǐng)域， 如美國 NASA研制的火星探測機(jī)器人索杰那于 1997 年登上火星；美國 NASA 資助研制 的“丹蒂 H八足行走機(jī)器人；德國研制了一種輪椅機(jī)器人，并在烏爾姆市中心車 站的客流高峰期

11、的環(huán)境和 1998 年漢諾威工業(yè)商品博覽會(huì)的展覽大廳環(huán)境中進(jìn)行了 實(shí)地現(xiàn)場表演，獲得了巨大的成功。 機(jī)器人正在從工廠的結(jié)構(gòu)化環(huán)境進(jìn)入人們?nèi)粘５纳瞽h(huán)境醫(yī)院、辦公室、家 庭、建筑工地和其它雜亂及不可控環(huán)境。機(jī)器人不僅要能自主完成工作，而且要能 與其他機(jī)器人或者與人共同協(xié)作完成任務(wù)或在人的指導(dǎo)下完成任務(wù)。美國 DARPA勺 戰(zhàn)術(shù)移動(dòng)機(jī)器人計(jì)劃是從 1998 年開始的一個(gè)為期 4 年研究計(jì)劃。該計(jì)劃研究的是 一個(gè)多機(jī)器人系統(tǒng)，研究分為技術(shù)開發(fā)和系統(tǒng)設(shè)計(jì)兩個(gè)階段 ；美國的 MDAR 項(xiàng)目是 在著名的保安機(jī)器人 ROBAR 的基礎(chǔ)上建立的一個(gè)多移動(dòng)機(jī)器人平臺(tái)，用來在指定 地面執(zhí)行隨機(jī)巡邏任務(wù)；美國的 F

12、ETCHf 劃是在 BUGS+劃的基礎(chǔ)上，研究使用一群 小的、堅(jiān)固的自主的移動(dòng)機(jī)器人去清除地表上的未爆炸的 M42 炮彈。自從 1996 年成功地舉行了第一次世界機(jī)器人足球賽以來，一年一度的世界機(jī)器人足球賽己經(jīng)吸 引了越來越多的團(tuán)體參加，極大地推進(jìn)了多移動(dòng)機(jī)器人技術(shù)的研究。 1.2.3 移動(dòng)機(jī)器人國內(nèi)研究概況 我國己在“七五”計(jì)劃中把機(jī)器人列入國家重點(diǎn)科研規(guī)劃內(nèi)容，撥巨款在沈陽 建立了全國第一個(gè)機(jī)器人研究示范工程，全面展開了機(jī)器人基礎(chǔ)理論與基礎(chǔ)元器件 的研究了。目前國內(nèi)研究的幾種機(jī)器人如下 : 1( 全方位移動(dòng)地面清掃機(jī)器人 香港中文大學(xué)與清華大學(xué)合作，聯(lián)合研制開發(fā)出一種全方位移動(dòng)清掃機(jī)器人。

13、 該機(jī)器人具有如下特點(diǎn) :(1) 采用全方位輪來實(shí)現(xiàn)任意方向的移動(dòng)，使得機(jī)器人可執(zhí) 行對(duì)狹窄區(qū)域的清掃任務(wù)。 (2) 采用開放式機(jī)器人控制結(jié)構(gòu)，實(shí)現(xiàn)硬件可擴(kuò)展，軟 件可移植、可繼承，使機(jī)器人作為服務(wù)載體具有更好的功能適應(yīng)性。 (3) 機(jī)器人具 - 4 - 馮赟: 機(jī)器人路徑規(guī)劃方法研究 有在擁擠環(huán)境下的實(shí)時(shí)避障功能，能適應(yīng)不斷變化的清掃工作環(huán)境。 (4) 具有 遙控操作和自主運(yùn)動(dòng)兩種運(yùn)行方式。 (5) 吸塵機(jī)構(gòu)可實(shí)現(xiàn)吸塵路徑的自動(dòng)轉(zhuǎn)換，提 高了吸塵效率。 (6) 具有智能電源管理功能，延長了運(yùn)行時(shí)間，提高了對(duì)有限的移 動(dòng)動(dòng)力資源的利用率。 2( 壁面清洗爬壁機(jī)器人 目前高層建筑的清洗，都采用吊

14、凳、吊籃的手工清洗作業(yè)方式。哈爾濱工業(yè)大 學(xué)機(jī)器人研究所研制成功的壁面清洗爬壁機(jī)器人，可以實(shí)現(xiàn)清洗作業(yè)的自動(dòng)化，解 決了人工操作的危險(xiǎn)問題，將人從這種重復(fù)性的危險(xiǎn)勞動(dòng)中解放出來。壁面清洗爬 壁機(jī)器人由爬壁機(jī)器人本體、清洗機(jī)構(gòu)、控制柜、遙控盒、安全保護(hù)裝置等部分組 成。 爬壁機(jī)器人采用負(fù)壓吸附原理， 利用吸盤吸附于壁面。 采用雙輪驅(qū)動(dòng)， 可垂直 于壁面上下左右移動(dòng)，帶動(dòng)清洗機(jī)構(gòu)作業(yè)。該機(jī)器人工作有如下特點(diǎn) :(1) 負(fù)壓吸 附，可以適應(yīng)各種材料的平面或壁面。 (2) 速度可調(diào)，爬行靈活。 (3) 有線遙控，操 作方便，可在地面上觀察機(jī)器人運(yùn)行情況下進(jìn)行遠(yuǎn)距操作。 (4) 可安全跨越溝縫， 爬壁機(jī)

15、器人可安全跨越 10 一 201 nm 左右的溝縫。(5)清洗效率高，清洗效果好。 3(導(dǎo)游服務(wù)機(jī)器人 海爾一哈爾濱工業(yè)大學(xué)機(jī)器人技術(shù)公司推出了 DY型導(dǎo)游服務(wù)機(jī)器人，該機(jī) 器人由伺服驅(qū)動(dòng)系統(tǒng)、多傳感器信息避障及路徑規(guī)劃系統(tǒng)、語音識(shí)別及語音合成系 統(tǒng)組成。導(dǎo)游機(jī)器人由蓄電池供電，可連續(xù)運(yùn)行 4 小時(shí)，在一定的環(huán)境下自主行 走，并且能識(shí)別出障礙物是人還是路障，做出不同的反應(yīng)。遇到人時(shí)機(jī)器人會(huì) 說:“您好!歡迎您來到機(jī)器人世界?！庇慰屯ㄟ^語音識(shí)別系統(tǒng)可以和機(jī)器人進(jìn)行簡 單的對(duì)話，該機(jī)器人可應(yīng)用于科技館、商店和旅游場所進(jìn)行導(dǎo)游服務(wù)。 4( 智能移動(dòng)機(jī)器人 我國的中科院自動(dòng)化所研制研發(fā)的 CASIA-

16、I 是集多種傳感器、視覺、語音識(shí)別 與會(huì)話功能于一體的智能移動(dòng)機(jī)器人。它的基本結(jié)構(gòu)由傳感器、控制器以及運(yùn)動(dòng)機(jī) 構(gòu)構(gòu)成，其中傳感器由以下幾個(gè)部分組成 :位于機(jī)器人底層的 1 6 個(gè)觸覺紅外傳感 器，位于機(jī)器人中間兩層的 16 個(gè)超聲波傳感器和 16 個(gè)紅外傳感器，以及位于機(jī)器 人頂部的攝像機(jī)(CCD)。這些傳感器和 CCD 一起構(gòu)成了 CASIA-I 的多傳感器系統(tǒng)。 CASIA-I 身高 80cm直徑 45cm 運(yùn)行最大速度為 80cm/s。它可廣泛應(yīng)用于醫(yī)院、 辦公室、圖書館、科技館、展覽館等公共場合的服務(wù)、作業(yè)、展示與娛樂等，以及 個(gè)人家庭服務(wù)。 1.3 移動(dòng)機(jī)器人的主要研究方面 移動(dòng)機(jī)器

17、人的智能指標(biāo)為適應(yīng)性、自主性和交互性。適應(yīng)性是指機(jī)器人具有適 應(yīng)復(fù)雜工作環(huán)境的能力，不但能識(shí)別和測量周圍的物體，還有理解周圍環(huán)境和 - 5 - 鄭州大學(xué)電氣工程學(xué)院畢業(yè)設(shè)計(jì) (論文) 所要執(zhí)行任務(wù)的能力，并做出正確的判斷及操作和移動(dòng)等能力 ; 自主性是指機(jī) 器人能根據(jù)工作任務(wù)和周圍環(huán)境情況，確定工作步驟和工作方式 ; 交互性是智能產(chǎn) 生的基礎(chǔ)，交互包括機(jī)器人與環(huán)境、機(jī)器人與人以及機(jī)器人之間三種，主要涉及信 息的獲取、處理和理解。基于以上智能指標(biāo)，移動(dòng)機(jī)器人技術(shù)的主要研究內(nèi)容包括 如下幾項(xiàng)。 1.3.1 導(dǎo)航與定位 導(dǎo)航與定位是移動(dòng)機(jī)器人研究的兩個(gè)重要問題。根據(jù)環(huán)境信息的完整程度、導(dǎo) 航指示信號(hào)

18、類型、導(dǎo)航地域等因素的不同，移動(dòng)機(jī)器人的導(dǎo)航方式可分為 : 基于環(huán) 境信息的地圖模型匹配導(dǎo)航 ;基于路標(biāo)導(dǎo)航 ;基于視覺導(dǎo)航 ;基于傳感器導(dǎo)航等。 環(huán)境地圖模型匹配導(dǎo)航是在機(jī)器人內(nèi)部存儲(chǔ)關(guān)于環(huán)境的完整信息，并在預(yù)先規(guī) 劃出的一條全局路線的基礎(chǔ)上，采用路徑跟蹤和避障技術(shù)，實(shí)現(xiàn)機(jī)器人導(dǎo)航 ; 當(dāng)機(jī) 器人對(duì)周圍環(huán)境并不完全了解時(shí)，則可采用基于路標(biāo)的導(dǎo)航策略，也就是將環(huán)境中 具有明顯特征的景物存儲(chǔ)在機(jī)器人內(nèi)部，機(jī)器人通過對(duì)路標(biāo)的探測來確定自己的位 置，并將全局路線分解成路標(biāo)與路標(biāo)之間的片斷， 再通過一連串的路標(biāo)探測和路標(biāo) 制導(dǎo)來完成導(dǎo)航任務(wù) ; 在環(huán)境信息完全未知的情況下，可通過傳感器對(duì)周圍環(huán)境的 探

19、測來實(shí)現(xiàn)機(jī)器人導(dǎo)航。 作為移動(dòng)機(jī)器人導(dǎo)航的最基本環(huán)節(jié)，定位是確定機(jī)器人在工作環(huán)境中相對(duì)于全 局坐標(biāo)的位姿。定位方法根據(jù)機(jī)器人工作環(huán)境復(fù)雜性、配備傳感器的種類和數(shù)量等 不同有多種方法。主要方法有 : 慣性定位、路標(biāo)定位和聲音定位等。 慣性定位是在移動(dòng)機(jī)器人的車輪上裝有慣性傳感器，通過對(duì)車輪轉(zhuǎn)動(dòng)的記錄來 粗略地確定位置和姿態(tài)，該方法簡單，但缺點(diǎn)是存在累積誤差 ; 路標(biāo)定位是在移動(dòng) 機(jī)器人工作的環(huán)境里，人為地設(shè)置一些坐標(biāo)己知的路標(biāo)，通過對(duì)路標(biāo)的探測來確定 自身的位姿，它可獲得較高的計(jì)算精度且計(jì)算量小 ; 聲音定位用于物體超出視野之外或光線很暗時(shí)，視覺導(dǎo)航和定位失效的情況下，基于聲音的無方向性和時(shí)間分

20、辨 率高等優(yōu)點(diǎn)，采用最大似然法、時(shí)空梯度法和 MUSIC 法等方法實(shí)現(xiàn)機(jī)器人的定位。 1.3.2 路徑規(guī)劃 路徑規(guī)劃技術(shù)是機(jī)器人研究領(lǐng)域的一個(gè)重要分支。所謂機(jī)器人的最優(yōu)路徑規(guī)劃 問題，就是依據(jù)某個(gè)或某些優(yōu)化準(zhǔn)則 （ 如工作代價(jià)最小、行走路線最短、行走時(shí)間 最短等 ） ，在其工作空間中找到一條從起始狀態(tài)到目標(biāo)狀態(tài)的能避開障礙物的最優(yōu) 路徑。根據(jù)控制方法的不同，機(jī)器人路徑規(guī)劃方法大致可以分為兩類 : 傳統(tǒng)方法 - 6 - 馮赟: 機(jī)器人路徑規(guī)劃方法研究 和智能方法。 移動(dòng)機(jī)器人的路徑規(guī)劃是移動(dòng)機(jī)器人研究領(lǐng)域中非常重要的問題，總的控制目 標(biāo)是使移動(dòng)機(jī)器人運(yùn)動(dòng)到目標(biāo)點(diǎn)，總的約束是在整個(gè)過程中，機(jī)器人不

21、碰到任何一 個(gè)障礙物。該問題根據(jù)對(duì)環(huán)境信息的掌握程度可以分為兩類 : 一類是環(huán)境信息己知 的全局規(guī)劃，另一類是環(huán)境信息未知的局部規(guī)劃。全局規(guī)劃方法依照已獲取的環(huán)境 信息，給機(jī)器人規(guī)劃出一條路徑。規(guī)劃路徑的精確程度取決于獲取環(huán)境信息的準(zhǔn)確 程度。全局方法通常可以尋找最優(yōu)解，但是需要預(yù)先知道環(huán)境的準(zhǔn)確信息，并且計(jì) 算量很大。局部規(guī)劃方法側(cè)重于考慮機(jī)器人當(dāng)前的局部環(huán)境信息，讓機(jī)器人具有良 好的避碰能力。很多機(jī)器人導(dǎo)航方法通常是局部的方法，因?yàn)樗男畔@取僅僅依 靠傳感器系統(tǒng)獲取的信息，并且隨著環(huán)境的變化實(shí)時(shí)的發(fā)生變化。和全局規(guī)劃方法 相比較，局部規(guī)劃方法更具有實(shí)時(shí)性和實(shí)用性。缺陷是僅僅依靠局部信息，

22、有時(shí)會(huì) 產(chǎn)生局部極點(diǎn)，無法保證機(jī)器人能順利到達(dá)目的地。 1.3.3 運(yùn)動(dòng)控制 運(yùn)動(dòng)控制是研究自主移動(dòng)機(jī)器人技術(shù)較為活躍的課題之一。自主移動(dòng)機(jī)器人按 照存儲(chǔ)在其內(nèi)部的地圖信息，或根據(jù)外部環(huán)境所提供的引導(dǎo)信號(hào) （ 即通過對(duì)環(huán)境的 實(shí)時(shí)探測所獲得的信息 ） 規(guī)劃出一條路徑后，它還必須能夠沿著該路徑在沒有人工 干預(yù)的情況下，采用跟蹤控制和避障技術(shù)移動(dòng)到預(yù)定目標(biāo)點(diǎn)，實(shí)現(xiàn)機(jī)器人導(dǎo)航。跟 蹤控制是移動(dòng)機(jī)器人運(yùn)動(dòng)控制的一個(gè)重要問題，分為軌跡跟蹤控制和路徑跟蹤控制 兩種。在軌跡跟蹤控制中，移動(dòng)機(jī)器人要求跟蹤的期望軌跡是以時(shí)間關(guān)系曲線圖給 出的，而在路徑跟蹤控制中，期望軌跡是由幾何參數(shù) （ 如路徑的弧長 ） 來描

23、述的。當(dāng) 要求機(jī)器人必須在一個(gè)特定的時(shí)間內(nèi)到達(dá)一個(gè)特定的目標(biāo)點(diǎn)時(shí)，軌跡跟蹤控制是必 需的; 當(dāng)要求機(jī)器人以一個(gè)期望的速度跟蹤一條由幾何參數(shù)給出的路徑時(shí)，路徑跟 蹤控制是合適的。己有的軌跡跟蹤方法在數(shù)學(xué)上很精致，并且得到許多有意義的結(jié) 果，但對(duì)于設(shè)計(jì)跟蹤控制器來說，并不是最好的方法。事實(shí)上，在傳統(tǒng)的自動(dòng)化應(yīng) 用中，常常采用基于幾何路徑跟蹤概念的方法，控制器的設(shè)計(jì)更與人的直覺接近， 并且簡單、易于實(shí)現(xiàn)。 1.4 論文結(jié)構(gòu)安排 未來的機(jī)器人應(yīng)該具有感知、規(guī)劃和控制等高層能力。它們能從周圍的環(huán)境中 收集知識(shí)，構(gòu)造一個(gè)關(guān)于環(huán)境的符號(hào)化的世界模型，并使用這些模型來規(guī)劃、執(zhí)行 由使用者下達(dá)的高層任務(wù)。 其中

24、的規(guī)劃模塊能生成大部分的機(jī)器人要執(zhí)行的命令， 其目標(biāo)是實(shí)現(xiàn)機(jī)器人的使用者在較高的層次給機(jī)器人下達(dá)一些較宏觀的任 - 7 - 鄭州大學(xué)電氣工程學(xué)院畢業(yè)設(shè)計(jì) （ 論文） 務(wù)，由機(jī)器人系統(tǒng)自身來填充那些較底層的細(xì)節(jié)問題。路徑規(guī)劃可以說是機(jī)器 人完成其他高級(jí)任務(wù)的一個(gè)保障，它要求機(jī)器人根據(jù)給予的指令及環(huán)境信息自主地 決定路徑，避開障礙物，實(shí)現(xiàn)任務(wù)目標(biāo)。路徑規(guī)劃是移動(dòng)機(jī)器人智能化程度的重要 標(biāo)志，它將提高移動(dòng)機(jī)器人的智力水平，提高移動(dòng)機(jī)器人移動(dòng)的速度及靈活性。 本文是以自主移動(dòng)機(jī)器人為研究對(duì)象，主要研究了移動(dòng)機(jī)器人在環(huán)境信息完全 已知情況下的全局路徑規(guī)劃或者稱為基于模型的路徑規(guī)劃以及在環(huán)境未知的情況下

25、的局部路徑規(guī)劃或稱為基下傳感器的路徑規(guī)劃?；谀Ｐ偷穆窂揭?guī)劃以搜索算法進(jìn) 行介紹，基于傳感器的路徑規(guī)劃以彷生學(xué)的蟻群算法進(jìn)行介紹。本文各章的研究內(nèi) 容如下: 第一章: 緒論。主要對(duì)機(jī)器人的基本概念，以及分類方法進(jìn)行簡要的介紹。接 著對(duì)國內(nèi)外移動(dòng)機(jī)器人的發(fā)展一般性的介紹和總結(jié) ; 歸納了移動(dòng)機(jī)器人的主要研究 方向。 第二章: 機(jī)器人路徑規(guī)劃簡介。主要對(duì)機(jī)器人路徑規(guī)劃進(jìn)行簡要說明，并對(duì)規(guī) 劃時(shí)所需要導(dǎo)航技術(shù)，及機(jī)器人體系結(jié)構(gòu)給予介紹。最后是對(duì)現(xiàn)在的一些路徑規(guī)劃 方法簡要介紹。 第三章 : 基于模型的路徑規(guī)劃。本章首先說明了基于模型的與基于傳感器的路 徑規(guī)劃與基于傳感器的路徑規(guī)劃的分類原則。接著介紹

26、基于模型的路徑規(guī)劃的地圖 處理方法切線圖與 Voronoi 圖，然后對(duì)搜索算法的步驟加以說明。最后以一個(gè)簡單 的地圖模型對(duì)算法進(jìn)行彷真，以加深算法的認(rèn)識(shí)，并提出了采用本算法的實(shí)際意義 及存在的不足。 第四章 : 基于傳感器的路徑規(guī)劃。本章對(duì)全局未知的基于傳感器的路徑規(guī)劃以 蟻群算法加以解決，對(duì)蟻群算法的進(jìn)行了詳細(xì)介紹，算法首先用柵格法對(duì)機(jī)器人的 工作空間進(jìn)行建模，并用一個(gè)狀態(tài)矩陣表示其狀態(tài)，由此構(gòu)造出一個(gè)連通圖，由一 組螞蟻在圖上模擬螞蟻的覓食行為，從而得到避碰的優(yōu)化路徑。 - 8 - 馮赟: 機(jī)器人路徑規(guī)劃方法研究 2 機(jī)器人路徑規(guī)劃簡介 2.1 引言 路徑規(guī)劃是移動(dòng)機(jī)器人研究的一個(gè)重要方面

27、，是對(duì)移動(dòng)機(jī)器人進(jìn)行更深層次研 究和應(yīng)用的基礎(chǔ)，因?yàn)槠浠救蝿?wù)就是解決機(jī)器人在環(huán)境中如何安全行走的問題。 就如人一樣，只有知道怎么在環(huán)境中行走，不與其他物體相碰撞并且正確從起始地 到達(dá)目的地，才能去做其他的事。但是，即使是完成這樣一個(gè)在我們看來十分簡單 的任務(wù)，其實(shí)也是經(jīng)過了一個(gè)良好配合與正確分析的過程 : 首先眼睛要搜集環(huán)境信 息，把看到的環(huán)境狀態(tài)反饋給大腦，然后大腦根據(jù)眼睛反饋回來的環(huán)境信息和所要 到達(dá)的目的地做出一個(gè)綜合的分析，得到一個(gè)判斷和結(jié)果，然后指揮人的身體移 動(dòng)，從而實(shí)現(xiàn)在環(huán)境中的行走。機(jī)器人也是類似，只不過在這里傳感器充當(dāng)了機(jī)器 人的“眼睛”，而路徑規(guī)劃模塊就相當(dāng)于機(jī)器人的“大

28、腦”，根據(jù)傳感器信息和任 務(wù)要求進(jìn)行分析和決策，指揮機(jī)器人的運(yùn)動(dòng)。導(dǎo)航技術(shù)是與路徑規(guī)劃密切相關(guān)的一 項(xiàng)關(guān)鍵技術(shù)，路徑規(guī)劃技術(shù)的發(fā)展要依賴于機(jī)器人導(dǎo)航技術(shù)的發(fā)展。 2.2 移動(dòng)機(jī)器人導(dǎo)航技術(shù) 2.2.1 機(jī)器人導(dǎo)航方式 移動(dòng)機(jī)器人的導(dǎo)航方式很多，有路標(biāo)導(dǎo)航、視覺導(dǎo)航、基于傳感器數(shù)據(jù)導(dǎo)航， 衛(wèi)星導(dǎo)航等。它們都不同程度地適用于各種不同的環(huán)境，包括室內(nèi)和室外環(huán)境，結(jié) 構(gòu)化環(huán)境與非結(jié)構(gòu)化環(huán)境。 (1) 路標(biāo)導(dǎo)航 將環(huán)境中具有明顯特征的景物存儲(chǔ)在機(jī)器人內(nèi)部，機(jī)器人通過對(duì)路標(biāo)的探測來 確定自己的位置，并將全局路線分解成路標(biāo)與路標(biāo)之間的片斷，再通過一連串的路 標(biāo)探測和路標(biāo)制導(dǎo)來完成導(dǎo)航任務(wù)。 (2) 視學(xué)導(dǎo)航

29、 由于計(jì)算機(jī)視覺理論及算法的發(fā)展，視覺導(dǎo)航成為導(dǎo)航技術(shù)中的一個(gè)重要發(fā)展 方向。通常，機(jī)器人利用裝配的攝像機(jī)拍攝周圍環(huán)境的局部圖像，然后通過圖 - 9 - 鄭州大學(xué)電氣工程學(xué)院畢業(yè)設(shè)計(jì) ( 論文)像處理技術(shù)，如特征識(shí)別、距離估計(jì)等，進(jìn)行機(jī)器人定位及規(guī)劃下一步的動(dòng) 作，從而實(shí)現(xiàn)機(jī)器人局部路徑規(guī)劃。 (3) 基于傳感器的數(shù)據(jù)導(dǎo)航 一般機(jī)器人都安裝了一些非視覺傳感器， 如超聲傳感器、 紅外傳感器、 接觸傳 感器等。利用這些傳感器使得機(jī)器人能夠在動(dòng)態(tài)非結(jié)構(gòu)化環(huán)境中實(shí)現(xiàn)自主導(dǎo)航。 (4) 衛(wèi)星導(dǎo)航 GPS 全球定位系統(tǒng)是以距離作為基本的觀測量，通過對(duì)四顆 GPS 衛(wèi)星同時(shí)進(jìn)行 距離測量計(jì)算出用戶 (接收機(jī)

30、)的位置。機(jī)器人通過安裝衛(wèi)星信號(hào)接收裝置，可以實(shí) 現(xiàn)自身定位。 2.2.2 機(jī)器人導(dǎo)般技術(shù)的發(fā)展 移動(dòng)機(jī)器人技術(shù)是傳感技術(shù)、控制技術(shù)、信息處理技術(shù)、機(jī)械加工技術(shù)、電子 技術(shù)、計(jì)算機(jī)技術(shù)等多門技術(shù)的結(jié)合。因此對(duì)于移動(dòng)機(jī)器人導(dǎo)航技術(shù)的發(fā)展也必然 建立在這些技術(shù)的高速發(fā)展之上的。 (1) 先進(jìn)的傳感技術(shù) 傳感器相當(dāng)于移動(dòng)機(jī)器人的感覺器官，只有先進(jìn)的傳感器技術(shù)才能有效的采集 環(huán)境信息，從而提高導(dǎo)航的效率和準(zhǔn)確性。 (2) 高效的信息處理技術(shù) 信息處理主要是指對(duì)于傳感器采集進(jìn)來的信息進(jìn)行處理，例如語音識(shí)別與理解 技術(shù)，圖像處理與模式識(shí)別技術(shù)等。由于目前移動(dòng)機(jī)器人的導(dǎo)航很多都采用基于視 覺或有視覺參與的導(dǎo)

31、航技術(shù)，因此計(jì)算機(jī)視覺和圖像處理技術(shù)的水平對(duì)于移動(dòng)機(jī)器 人導(dǎo)航的發(fā)展將起到至關(guān)重要的作用。 (3) 多傳感器的信息融合技術(shù) 多傳感器的導(dǎo)航方式是移動(dòng)機(jī)器人導(dǎo)航發(fā)展的必然趨勢。多傳感器的信息融合 技術(shù)充分利用了多個(gè)傳感器的資源，通過對(duì)這些傳感器及其觀測信息的合理支配和 利用，把多個(gè)傳感器在空間或時(shí)間上的冗余或互補(bǔ)信息根據(jù)一定的準(zhǔn)則進(jìn)行組合， 從而獲得對(duì)被測對(duì)象的一致性解釋或描述，因此它不但能夠提高導(dǎo)航精度，同時(shí)也 使整個(gè)導(dǎo)航系統(tǒng)具有了較高的魯棒性。 (4) 智能方法的發(fā)展與完善 目前在移動(dòng)機(jī)器人導(dǎo)航中，智能方法的應(yīng)用是一個(gè)重要的發(fā)展方向。但目前智 能算法在機(jī)器人導(dǎo)航中的應(yīng)用范圍卻受到了很大局限，

32、如神經(jīng)網(wǎng)絡(luò)應(yīng)用往往局限在 環(huán)境的建模和認(rèn)知上，例如機(jī)器人地圖構(gòu)建。同時(shí)由于目前在導(dǎo)航過程中主要采用 前饋網(wǎng)絡(luò)，需要教師信號(hào)進(jìn)行訓(xùn)練，因此難于實(shí)現(xiàn)在線應(yīng)用 ; 模糊邏輯應(yīng)用于復(fù)雜 未知?jiǎng)討B(tài)環(huán)境中，模糊規(guī)則很難提取，導(dǎo)航的效果也不理想。因此在移動(dòng)機(jī)器人導(dǎo) 航中，智能方法還有極大的發(fā)展空間。 - 10 - 馮赟: 機(jī)器人路徑規(guī)劃方法研究 2.3 路徑規(guī)劃方法 路徑規(guī)劃一直是機(jī)器人學(xué)研究領(lǐng)域的一個(gè)熱點(diǎn)，大多數(shù)國內(nèi)外文獻(xiàn)將此問題 ath Planning, Find-Path Problem ，Collision-Free, Obstacle Avoidance ，稱為 P Motion Plannin

33、g ， etc. 所謂機(jī)器人的最優(yōu)路徑規(guī)劃問題，就是依據(jù)某個(gè)或某 些優(yōu)化準(zhǔn)則 ( 如工作代價(jià)最小、行走路線最短、行走時(shí)間最短等 ) ，在其工作空間中 找到一條從起始狀態(tài)到目標(biāo)狀態(tài)的能避開障礙物的最優(yōu)路徑。根據(jù)對(duì)環(huán)境信息的掌 握程度不同，路徑規(guī)劃可分為 :(l) 全局路徑規(guī)劃，環(huán)境信息完全己知，包括障礙物 的位置及其幾何性質(zhì) ;(2) 局部路徑規(guī)劃，環(huán)境信息完全未知或部分未知，通過傳感 器在線地對(duì)機(jī)器人的工作環(huán)境進(jìn)行探測，以獲取障礙物的位置和幾何性質(zhì)等信息， 這種規(guī)劃對(duì)于環(huán)境數(shù)據(jù)的搜集和該環(huán)境模型的動(dòng)態(tài)更新能夠隨時(shí)進(jìn)行校正。全局規(guī) 劃方法包括環(huán)境建模和路徑搜索兩個(gè)子問題。一般情況下先對(duì)環(huán)境信息進(jìn)

34、行建模， 然后采用某種搜索方法搜索最優(yōu)路徑。全局規(guī)劃是一種事前規(guī)劃，因此對(duì)機(jī)器人系 統(tǒng)的實(shí)時(shí)計(jì)算能力要求不高，規(guī)劃結(jié)果是全局的、較優(yōu)的，但是對(duì)環(huán)境模型的錯(cuò)誤 及噪聲魯棒性差。局部規(guī)劃方法將對(duì)環(huán)境的建模與搜索融為一體，要求機(jī)器人系統(tǒng) 具有高速的信息處理能力和計(jì)算能力，對(duì)環(huán)境誤差和噪聲有較高的魯棒性，能對(duì)規(guī) 劃結(jié)果進(jìn)行實(shí)時(shí)反饋和校正，但是由于缺乏全局環(huán)境信息，所以規(guī)劃結(jié)果有可能不 是最優(yōu)的，甚至可能找不到正確路徑或完整路徑。 機(jī)器人路徑規(guī)劃方法大致可以分為兩類 : 傳統(tǒng)方法和智能方法。 2.3.1 傳統(tǒng)路徑規(guī)劃 傳統(tǒng)方法包括以下幾種 : 可視圖法、自由空間法、柵格法、人工勢場法等。 (l) 可視圖

35、法是將機(jī)器人視為一點(diǎn)，把機(jī)器人、目標(biāo)點(diǎn)和多邊形障礙物的各個(gè) 頂點(diǎn)進(jìn)行連接，要求機(jī)器人和障礙物各頂點(diǎn)之間，目標(biāo)點(diǎn)和障礙物各頂點(diǎn)之間以及 各障礙物頂點(diǎn)與頂點(diǎn)之間的連線，都不能穿越障礙物，這樣就形成了一張圖，稱之 為可視圖。由于任意兩直線的頂點(diǎn)都是可視的，顯然移動(dòng)機(jī)器人從起點(diǎn)沿著這些連 線到達(dá)目標(biāo)點(diǎn)的所有路徑均是無碰路徑。對(duì)可視圖進(jìn)行搜索，并利用優(yōu)化算法刪除 一些不必要的連線以簡化可視圖，縮短了搜索時(shí)間，最終就可以找到一條無碰最優(yōu) 路徑。優(yōu)點(diǎn)是可以求得最短路徑，缺點(diǎn)是此法缺乏靈活性，即一旦機(jī)器人的起點(diǎn)和 目標(biāo)點(diǎn)發(fā)生改變，就要重新構(gòu)造可視圖，比較麻煩。 (2) 自由空間法的基本思想是采用預(yù)先定義的基本

36、形狀 ( 如廣義錐形，凸多邊形 等)構(gòu)造自由空間，并將自由空間表示為連通圖，然后通過對(duì)圖的搜索來規(guī)劃路 徑，其算法的復(fù)雜度往往與障礙物的個(gè)數(shù)成正比。自由空間的優(yōu)點(diǎn)是比較靈活， - 11 - 鄭州大學(xué)電氣工程學(xué)院畢業(yè)設(shè)計(jì) ( 論文) 機(jī)器人的起始點(diǎn)和目標(biāo)點(diǎn)的改變不會(huì)造成連通圖的重新構(gòu)造，缺點(diǎn)為不是任何 時(shí)候都可以獲得最短路徑。 (3) 柵格法是將移動(dòng)機(jī)器人工作環(huán)境分解成一系列具有二值信息的網(wǎng)格單元， 多采用二維笛卡兒矩陣柵格表示工作環(huán)境，每一個(gè)矩形柵格都有一個(gè)累積值 CV， 表示在此方位中存在障礙物的可信度。 CV 值越高，表征存在障礙物的可能性越 高。用柵格法表示格子環(huán)境模型中存在障礙物的可能

37、性的方法起源于美國 CMI 大 學(xué)。通過優(yōu)化算法在單元中搜索最優(yōu)路徑。由于該方法以柵格為單位記錄環(huán)境信 息，環(huán)境被量化成具有一定分辨率的柵格，因此柵格的大小直接影響著環(huán)境信息存 儲(chǔ)量的大小以及路徑搜索的時(shí)間，因此在實(shí)用上受到一定的限制。 (4) 人工勢場法是由 Khatib 提出的一種虛擬力場法。這種方法的基本思想是把 移動(dòng)機(jī)器人在環(huán)境中的運(yùn)動(dòng)視為一種在抽象的人工受力場中的運(yùn)動(dòng)，即在環(huán)境中建 立人工勢場的負(fù)梯度方向指向系統(tǒng)的運(yùn)動(dòng)控制方向。目標(biāo)點(diǎn)對(duì)移動(dòng)機(jī)器人產(chǎn)生引 力，障礙物對(duì)移動(dòng)機(jī)器人產(chǎn)生斥力。其結(jié)果是使移動(dòng)機(jī)器人沿“勢峰”間的“勢 谷”前進(jìn)，最后求出合力來控制移動(dòng)機(jī)器人的運(yùn)動(dòng)。這類方法的突出

38、的優(yōu)點(diǎn)是系統(tǒng) 的路徑生成與控制直接與環(huán)境實(shí)現(xiàn)了閉環(huán)，從而大大加強(qiáng)了系統(tǒng)的適應(yīng)性與避障性 能。但是人工勢場法也存在若干缺陷 : 如在陷阱區(qū)域容易陷入局部最小 ; 在相近的障 礙物之間不能發(fā)現(xiàn)路徑等。 上述前三種方法都是全局規(guī)劃方法，首先根據(jù)已知環(huán)境信息用不同的方法對(duì)環(huán) 境進(jìn)行建模，然后采用一定的搜索技術(shù)來搜索最優(yōu)路徑。但是以上這些傳統(tǒng)方法在 路徑搜索效率及路徑優(yōu)化方面尚有待于進(jìn)一步改善。而現(xiàn)在通常使用的搜索技術(shù)包 括：梯度法，A*等圖搜索方法，枚舉法、隨機(jī)搜索法等。這些方法中梯度法易陷入 局部最小點(diǎn)，圖搜索方法、枚舉法不能用于高維的優(yōu)化問題，而隨機(jī)搜索法則計(jì)算 效率太低。人工勢場方法則既可用于環(huán)

39、境己知的全局路徑規(guī)劃，也可用于環(huán)境未知 的局部路徑規(guī)劃。用于全局規(guī)劃時(shí)根據(jù)全局信息構(gòu)造環(huán)境勢場模型，而用于局部規(guī) 劃時(shí)根據(jù)傳感器實(shí)時(shí)檢測信息構(gòu)造環(huán)境勢場模型。 2.3.2 智能路徑規(guī)劃 近年來，隨著遺傳算法等智能方法的廣泛應(yīng)用，機(jī)器人路徑規(guī)劃方法也有了長 足的進(jìn)展，許多研究者把目光放在了基于智能方法的路徑規(guī)劃研究上。其中，應(yīng)用 較多的算法主要有模糊方法、神經(jīng)網(wǎng)絡(luò)和遺傳算法。 (l) 基于模糊邏輯的機(jī)器人路徑規(guī)劃 模糊控制算法模擬駕駛員的駕駛思想，將模糊控制本身所具有的魯棒性與基于 生理學(xué)上的“感知，動(dòng)作”行為結(jié)合起來，適用于時(shí)變未知環(huán)境下的路徑規(guī)劃，實(shí) 時(shí)性較好。 - 12 - 馮赟: 機(jī)器人

40、路徑規(guī)劃方法研究 在移動(dòng)機(jī)器人自主導(dǎo)航過程中，對(duì)于環(huán)境的描述經(jīng)常包含著不確定因素，不能 將其直接歸類到某一環(huán)境特征或采取某一明確的規(guī)則，這時(shí)就可采用模糊邏輯。模 糊邏輯由于符合人類思維習(xí)慣，不僅不需要建立系統(tǒng)的數(shù)學(xué)模型，而且易于將專家 知識(shí)直接轉(zhuǎn)換為控制信號(hào)。利用模糊邏輯可將不確定性直接表示在推理過程中?；?于模糊規(guī)則的目標(biāo)識(shí)別融合計(jì)算非常簡單，通過指定一個(gè) 0 到 1 之間的實(shí)數(shù)來表示 真實(shí)度，這相當(dāng)于隱式算子的前提。利用模糊邏輯對(duì)傳感器信息的精度要求不高， 對(duì)移動(dòng)機(jī)器人周圍環(huán)境以及本身位姿信息的不確定性也不敏感，這樣就使得移動(dòng)機(jī) 器人的行為體現(xiàn)出很好的一致性、穩(wěn)定性和連續(xù)性。然而由于實(shí)際環(huán)

41、境的復(fù)雜性， 一方面很難預(yù)料到所有可能的情況，另一方面對(duì)于多輸入、多輸出系統(tǒng)，要構(gòu)造其 全部模糊規(guī)則也非常復(fù)雜和困難，而且模糊推理的運(yùn)算量隨著模糊規(guī)則的增長而按 指數(shù)級(jí)增長。因此讓移動(dòng)機(jī)器人能自己學(xué)會(huì)模糊規(guī)則是非常必要的。 (2) 基于神經(jīng)網(wǎng)絡(luò)方法的機(jī)器人路徑規(guī)劃 神經(jīng)網(wǎng)絡(luò)方法是一種仿效生物神經(jīng)系統(tǒng)的信息處理方法。它是一個(gè)高度并行的 分布式系統(tǒng)，處理速度高且不依賴于系統(tǒng)精確的數(shù)學(xué)模型，還具有自適應(yīng)和自學(xué)習(xí) 的能力。一個(gè)神經(jīng)網(wǎng)絡(luò)包括以各種方式聯(lián)接的多層處理單元。神經(jīng)網(wǎng)絡(luò)對(duì)輸入的數(shù) 據(jù)進(jìn)行非線性變換，從而完成了聚類分析技術(shù)所進(jìn)行的從數(shù)據(jù)到屬性的分類。目前 神經(jīng)網(wǎng)絡(luò)的類型很多，大多數(shù)的神經(jīng)網(wǎng)絡(luò)都用于

42、增強(qiáng)移動(dòng)機(jī)器人避障能力與路徑規(guī) 劃上，通常采用的是三層感知器模型和 BP 算法。禹建麗等提出了一種基于神經(jīng)網(wǎng) 絡(luò)的機(jī)器網(wǎng)絡(luò)結(jié)構(gòu)，根據(jù)路徑點(diǎn)位于障礙物內(nèi)外的不同位置選取不同的動(dòng)態(tài)運(yùn)動(dòng)方 程，規(guī)劃出的路徑達(dá)到了折線形的最短無碰路徑，計(jì)算簡單，收斂速度快。陳宗海 等提出了一種在不確定環(huán)境中移動(dòng)機(jī)器人的路徑規(guī)劃方法，將全局路徑規(guī)劃分解為 局部路徑規(guī)劃的組合，為了提高規(guī)劃的效率，在避障規(guī)劃中采用了基于案例的學(xué)習(xí) 方法，以 ARf-2 神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)案例的匹配學(xué)習(xí)和擴(kuò)充，滿足了規(guī)劃的實(shí)時(shí)性要求。 (3) 基于遺傳算法的機(jī)器人路徑規(guī)劃 遺傳算法是目前機(jī)器人路徑規(guī)劃研究中應(yīng)用較多的一種方法，無論是單機(jī)器人 靜態(tài)

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

44、規(guī)劃精 - 13 - 鄭州大學(xué)電氣工程學(xué)院畢業(yè)設(shè)計(jì) ( 論文) 度較低 ; 若柵格劃分太細(xì)，則數(shù)據(jù)量又會(huì)太大。 周明等提出一種連續(xù)空間下基于遺傳算法的機(jī)器人路徑規(guī)劃方法，該方法在規(guī) 劃空間利用鏈接圖建模的基礎(chǔ)上，先使用圖論中成熟算法粗略搜索出可選路徑，然 后再使用遺傳算法來調(diào)整路徑點(diǎn)，逐步得到較優(yōu)的行走路線。該方法的染色體編碼 不會(huì)產(chǎn)生無效路徑，且僅使用基本遺傳算法就可以完成路徑規(guī)劃。但是該方法對(duì)于 環(huán)境復(fù)雜、障礙物數(shù)目較多的情況，鏈接圖的建立會(huì)有一定的困難。在遺傳算法的 改進(jìn)上周明等 151 提出一種遺傳模擬退火算法，利用遺傳算法與模擬退火算法相結(jié) 合來解決機(jī)器人路徑規(guī)劃問題，有效地提高了路

45、徑規(guī)劃的計(jì)算速度，保證了路徑規(guī) 劃的質(zhì)量。 在多移動(dòng)機(jī)器人協(xié)調(diào)作業(yè)方面遺傳算法也得到了應(yīng)用，景興建等 161 提出一種 基于理性遺傳算法的協(xié)調(diào)運(yùn)動(dòng)行為合成算法，針對(duì)特定環(huán)境下的多機(jī)器人協(xié)調(diào)運(yùn)動(dòng) 問題，基于調(diào)速避碰的思想，借助 CMAC 申經(jīng)網(wǎng)絡(luò)，描述各機(jī)器人的運(yùn)動(dòng)行為與環(huán) 境狀態(tài)之間復(fù)雜的、非線性映射關(guān)系，利用遺傳算法來合成與優(yōu)化各機(jī)器人的運(yùn)動(dòng) 行為，從而實(shí)現(xiàn)多機(jī)器人己知環(huán)境下，運(yùn)動(dòng)行為的相互協(xié)調(diào)與優(yōu)化。 (4) 基于混合方法的機(jī)器人路徑規(guī)劃方法 L.H.Tsoukalas 等提出一種用于半自主移動(dòng)機(jī)器人路徑規(guī)劃的模糊申經(jīng)網(wǎng)絡(luò)方 法。所謂半自主移動(dòng)機(jī)器人就是具有在人類示教基礎(chǔ)上增加了學(xué)習(xí)功能的

46、器件的機(jī) 器人。這種方法采用模糊描述來完成機(jī)器人行為編碼，同時(shí)重復(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ò) 對(duì)這 5 層的參數(shù)進(jìn)行訓(xùn)練。在線學(xué)習(xí)部分為 3 部分:PE-性能鑒別;AS-行為搜索;RC- 規(guī)則構(gòu)造。性能鑒別部分主要是判斷機(jī)器人工作環(huán)境中是否有障礙物。 a 為判斷所 用

47、的性能指標(biāo)，若 a=1，則該位置無障礙物；反之若 a=0,則該位置有障礙物。行為 搜索部分是根據(jù)費(fèi)用最小原則，利用遺傳算法調(diào)整路徑。規(guī)則構(gòu)造部分則為模糊控制構(gòu)造規(guī)則庫，主要用于產(chǎn)生機(jī)器人的行為控制，如 向前、向后、左轉(zhuǎn)、右轉(zhuǎn)等。該方法是一種混合的機(jī)器人自適應(yīng)控制方法，可以自 適應(yīng)調(diào)整機(jī)器人的行走路線，達(dá)到避障和路徑最短的雙重優(yōu)化。 綜上所述，遺傳算法等智能方法在機(jī)器人路徑規(guī)劃技術(shù)中己受到廣泛的重視及 研究，在障礙物環(huán)境己知或未知情況下，均已取得一定的研究成果。機(jī)器人路徑規(guī) 劃是機(jī)器人應(yīng)用中的一項(xiàng)重要技術(shù)，采用良好的機(jī)器人路徑規(guī)劃技術(shù)可以節(jié)省大量 機(jī)器人作業(yè)時(shí)間，減少機(jī)器人磨損，同時(shí)也可以節(jié)約人

48、力資源，減小資金投入，為 機(jī)器人在多種行業(yè)中的應(yīng)用奠定良好的基礎(chǔ)。將遺傳算法、模糊邏輯以 - 14 - 馮赟: 機(jī)器人路徑規(guī)劃方法研究 及神經(jīng)網(wǎng)絡(luò)等方法相結(jié)合，可以組成新的智能型路徑規(guī)劃方法，從而提高機(jī)器 人路徑規(guī)劃的避障精度，加快規(guī)劃速度，滿足實(shí)際應(yīng)用的需要。同時(shí)， 多機(jī)器人協(xié)調(diào)作業(yè)環(huán)境下的路徑規(guī)劃技術(shù)也將是研究的熱點(diǎn)及難點(diǎn)問題，越來 越 受到人們的重視。由于障礙物及機(jī)器人數(shù)目的增加，極大地增加了路徑規(guī)劃的 難度，引入可以優(yōu)化約簡知識(shí)的粗糙集理論，簡化規(guī)劃條件，提取路徑規(guī)劃特征參 數(shù)，有可能進(jìn)一步解決諸如機(jī)器人路徑規(guī)劃速度等難題，因此，這將是一個(gè)有意義 的研究課題。 2.4 機(jī)器人體系結(jié)構(gòu)

49、機(jī)器人系統(tǒng)可以分為兩個(gè)子系統(tǒng) : 上層控制系統(tǒng)和底層控制系統(tǒng)。上層控制系 統(tǒng)與底層控制系統(tǒng)之間以及底層各系統(tǒng)之間采用 CAN 總線連成控制器局部網(wǎng)絡(luò)，能 夠較好的實(shí)現(xiàn)可靠的數(shù)據(jù)通信和實(shí)時(shí)、高效的任務(wù)調(diào)度。 其它機(jī)器人 地面控制計(jì)算機(jī) 無線通訊網(wǎng)卡 上層控制計(jì)算機(jī) CAN 總線適配卡 CAN 總線 超聲波傳感系統(tǒng) 其它傳感系統(tǒng) 定位及伺服控制系統(tǒng) 圖 2.1 機(jī)器人體系結(jié)構(gòu) (l) 上層控制系統(tǒng) 上層控制系統(tǒng)采用嵌入式工業(yè)計(jì)算機(jī)作為硬件平臺(tái)，由上層控制計(jì)算機(jī)、 CAN 總線適配卡、無線通訊卡等組成。 為了實(shí)現(xiàn)機(jī)器人內(nèi)部各層之間的實(shí)時(shí)通信，在上層控制系統(tǒng)中采用工業(yè)標(biāo)準(zhǔn)的 CAN 總線卡連接底層控制

50、系統(tǒng)中各個(gè)工作模塊。 機(jī)器人上配有無線局域網(wǎng)卡，用于實(shí)現(xiàn)機(jī)器人與監(jiān)控人員的實(shí)時(shí)交互，傳送工 作指令。同時(shí)，機(jī)器人也可將傳感器探測結(jié)果等機(jī)器人狀態(tài)回送到主控臺(tái)，以 - 15 - 鄭州大學(xué)電氣工程學(xué)院畢業(yè)設(shè)計(jì) ( 論文) 便監(jiān)控人員進(jìn)一步下達(dá)指令，實(shí)現(xiàn)良好的人機(jī)和諧交互。 (2) 底層控制系統(tǒng) 底層控制系統(tǒng)包括超聲波傳感器系統(tǒng)、其它傳感器系統(tǒng)以及定位及伺服控制系 統(tǒng)等。 超聲波傳感器系統(tǒng)通過硬件中斷和輪回采集等方法實(shí)現(xiàn)超聲波傳感器數(shù)據(jù)采集 的實(shí)時(shí)性和可靠性。通過 CAN 總線通信，可以將測距值以很高的通信速率可靠的發(fā) 送給上層控制計(jì)算機(jī)。 定位及伺服控制系統(tǒng)用來實(shí)現(xiàn)移動(dòng)機(jī)器人的定位和馬達(dá)伺服控制兩

51、部分功能。 移動(dòng)機(jī)器人定位用于測定機(jī)器人當(dāng)前坐標(biāo)及方位。它首先根據(jù)電機(jī)光電碼盤的輸出 經(jīng)計(jì)算后得到粗定位，然后根據(jù)超聲波傳感器信息等其它信息來達(dá)到精確定位。驅(qū) 動(dòng)輪的伺服控制采用自適應(yīng)模糊 PID 控制方法來實(shí)現(xiàn)，在誤差較大時(shí)采用比例控 制，電機(jī)快速運(yùn)行，以使誤差迅速減小 ;在誤差較小時(shí)使用增益自動(dòng)調(diào)整的 PID 控 制，實(shí)現(xiàn)驅(qū)動(dòng)輪伺服控制的無超調(diào)運(yùn)行，以達(dá)到移動(dòng)機(jī)器人高速度、 精度移動(dòng)的 目的。 2.5 本章小結(jié) 本章主要對(duì)機(jī)器人路徑規(guī)劃進(jìn)行簡要說明， 并對(duì)規(guī)劃時(shí)所需要導(dǎo)航技術(shù)，及機(jī) 器人體系結(jié)構(gòu)包括上層控制系統(tǒng)各底層控制系統(tǒng)給予介紹。最后是對(duì)現(xiàn)在的一些路 徑規(guī)劃方法包括傳統(tǒng)的方法 : 可視

52、圖法、自由空間法、柵格法、人工勢場法等和智 能路徑規(guī)劃方法 : 模糊方法、神經(jīng)網(wǎng)絡(luò)和遺傳算法簡要介紹。 - 16 - 馮赟: 機(jī)器人路徑規(guī)劃方法研究 3 基于模型的路徑規(guī)劃 3.1 引言 3.1.1 研究對(duì)象說明 本文為簡單清晰的說明機(jī)器人的路徑規(guī)劃，移動(dòng)機(jī)器人只考慮 2 自由度時(shí)，生 成 2 自由度的點(diǎn)機(jī)器人。這里取可全方位移動(dòng)且用圓表不的移動(dòng)機(jī)器人為例。首 先，由天能全方位移動(dòng)，所以可忽略移動(dòng)機(jī)器人的方向 （姿勢的自由度 ） 。其次，由 于能用圓表示機(jī)器人，所以可把障礙物徑向擴(kuò)張，機(jī)器人縮成一個(gè)點(diǎn)。由此，在存 在擴(kuò)張了的障礙物的地圖（XY 平面）上，可以規(guī)劃成為點(diǎn)機(jī)器人 R 的路徑。如下圖

53、 所示: 圖 3.1 障礙物擴(kuò)張法和只考慮位置的導(dǎo)航 3.1.2 路徑規(guī)劃的兩大分類 移動(dòng)機(jī)器人的路徑規(guī)劃，由天地圖的有無會(huì)有很大的差別。一面看地圖一面運(yùn) 行，或機(jī)器人走過工廠及學(xué)校等人工構(gòu)造物時(shí)，存在有地圖。由于這個(gè)地圖是由機(jī) 器人各障礙物的模型作成的，所以這個(gè)路徑規(guī)劃稱為基于模型的路徑規(guī)劃。另一方 面，機(jī)器人穿行游樂場的迷宮、宇宙及受災(zāi)地區(qū)一類結(jié)構(gòu)未知的地主時(shí)， -17 - 鄭州大學(xué)電氣工程學(xué)院畢業(yè)設(shè)計(jì)（論文） 不存在地圖。這時(shí)，機(jī)器人用傳感器一面檢測，回避障礙物一面不得不把目的 地當(dāng)作目標(biāo)。所以這種路徑規(guī)劃稱為基于傳感器的路徑規(guī)劃。本章就先介紹基于模 型的路徑規(guī)劃。 3.2 基于模型的路

54、徑規(guī)劃地圖處理 基于模型的路徑規(guī)劃。為了快速選取路徑，用所謂圖的數(shù)據(jù)結(jié)構(gòu)表示地圖。所 謂圖就是用弧連接點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，節(jié)點(diǎn)意味著機(jī)器人的位置，弧意味著兩個(gè)位置間 的移動(dòng)。在圖上給出距離，工作量或時(shí)間等，把希望的最佳值作為費(fèi)用賦于弧上。 弧記憶進(jìn)入節(jié)點(diǎn)和輸出節(jié)點(diǎn)，總是回到原來的地方 （程序上稱為指針返回）。而且, 如里能在兩個(gè)方向移動(dòng)則用無向弧，只能單方向移動(dòng)的有有向弧。例如， -2，從節(jié)點(diǎn) A 到節(jié)點(diǎn) B 兩個(gè)方向上用費(fèi)用 7 移動(dòng)，但從節(jié)點(diǎn) C 到節(jié)點(diǎn) D 只一下 圖 3 個(gè)方向移動(dòng)其費(fèi)用是 3 B C 3 4 38 D F B 圖 3.2 圖（節(jié)點(diǎn)和?。?為將實(shí)際模型抽象成節(jié)點(diǎn)和弧，本小節(jié)介

55、紹兩中典型的圖。一個(gè)是管理從起始 點(diǎn) ns到目標(biāo)點(diǎn) ng 的最短路徑的切線圖（tangential graph）, 另一個(gè)是連接這些節(jié) 點(diǎn)的安全路徑，即管理盡量離開障礙路徑的 Voronoi 圖（Voronoi graph）。 *而且也說明從這些圖選擇最佳（滿足）路徑的算法（A）。A 這里，作為基于模型的路徑規(guī)劃的一個(gè)典型例子，我們來說明一個(gè)重視最短路 徑到達(dá)目的地的切線圖（圖 3-3）。以及重視安全回避障礙障礙物的 Voronoi 圖（圖 3-4）。 -18 - 馮赟：機(jī)器人路徑規(guī)劃方法研究 圖 3.3 切線圖 圖 3.4 voronoi 圖 切線圖用障礙物的切線表示弧。由此可選擇從起始節(jié)點(diǎn)

56、 ns 到目標(biāo)節(jié)點(diǎn) ng 的最 佳（最短）路徑。可是，若誤解了自己的位置而離開路徑，移動(dòng)機(jī)器人碰撞障礙物的 可能性會(huì)很高。另一方面，Voronoi 圖用盡可能遠(yuǎn)離障礙物和墻壁的路徑表示弧。 由此，雖然從起始點(diǎn) ns 到目標(biāo)點(diǎn) ng 的路徑有些加長，但即便誤解了自己的位置偏 離規(guī)定的路徑，也可避免碰撞障礙物這種最壞的事態(tài)。 無論哪一種圖都是由節(jié)點(diǎn)和弧構(gòu)成的，有節(jié)點(diǎn)表示起始點(diǎn)，經(jīng)過點(diǎn)、目標(biāo)點(diǎn) ； 用無向弧表示其間的路徑，其上附加有作為費(fèi)用的歐幾里得距離。最后，無論哪 *個(gè)圖都是有算法 A 選出任意路徑，有算法選出最短路徑。 A 切線圖 在切線圖上雖然可選擇從起始點(diǎn) ns 到目標(biāo)點(diǎn) ng 的最短路徑

57、，但移動(dòng)機(jī)器人 -19 - 鄭州大學(xué)電氣工程學(xué)院畢業(yè)設(shè)計(jì)（論文） 必須幾乎接近障礙物行走。即切線圖是反障礙物之間的切線圖形化得到的。所 以用節(jié)點(diǎn)表示切點(diǎn)，用弧表示連接兩切點(diǎn)的路徑。這時(shí)，弧上可附加兩端點(diǎn)間的歐 幾里得距離作為費(fèi)用。 這種路徑規(guī)劃首先把對(duì)應(yīng)起始點(diǎn) S 和目標(biāo)點(diǎn) G 的兩個(gè)節(jié)點(diǎn) ns 和 ng 標(biāo)注在新 *的切線圖上，然后用算法選出最佳（最短）路徑 P。最后，使點(diǎn)機(jī)器人 R 沿路 A 徑 P 進(jìn)行 PTP(point-to-point) 控制和 CP(continuous path) 控制。把機(jī)器人 引導(dǎo)到目的地。如果在這種控制過程中產(chǎn)生位置誤差，機(jī)器人磁撞障礙物的可能性 會(huì)高。

58、(2) Voronoi 圖 Voronoi 圖由于可以選擇從起始節(jié)點(diǎn) ns 到目標(biāo)節(jié)點(diǎn) ng 的安全路徑，所以移動(dòng) 機(jī)器人能夠在離障礙物足夠遠(yuǎn)的路徑上行走。即 Voronoi 圖可用弧表示距兩個(gè)以上 障礙物和墻壁表面等距離的點(diǎn)陣，有節(jié)點(diǎn)表示它們的交叉位置。這時(shí)，弧的費(fèi)用可 用連接節(jié)點(diǎn)點(diǎn)陣的歐幾里得距離給出。 這種路徑規(guī)劃首先把對(duì)應(yīng)起始點(diǎn) S 和目標(biāo)點(diǎn) G 的起始節(jié)點(diǎn) ns 和目標(biāo)節(jié)點(diǎn) ng *選出安全路徑 P。最后，使點(diǎn)機(jī)器人 R 沿著路徑 P 標(biāo)注在圖上，然后用搜索算 法 A 進(jìn)行 PTP 控制和 CP 控制，把移動(dòng)機(jī)器人引導(dǎo)到目的地。采用這種控制時(shí)即使 產(chǎn)生位置誤差，移動(dòng)機(jī)器人也不會(huì)碰撞障

59、礙物。 3.3 搜索算法 這里要說明的是把前面所說的切線圖和 Voronoi 圖作為搜索圖 G,選出從起始 *節(jié)點(diǎn) ns 到目標(biāo)節(jié)點(diǎn) ng 的最佳(或滿足)路徑算法 (或 A)。 A *A 算法(A) 面計(jì)算節(jié)點(diǎn)心 n 的費(fèi)用 f(n)，面搜索圖 G 這個(gè)費(fèi)用 f(n)是從 起始節(jié)點(diǎn)ns經(jīng)由當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)ng的最小費(fèi)用(最短距離)的估價(jià)函數(shù)。 可 用f(n)=g(n)+h(n)來計(jì)算。 式中， g(n)是起始節(jié)點(diǎn) ns 和當(dāng)前節(jié)點(diǎn) n 之間的現(xiàn)時(shí)點(diǎn) 上的最小費(fèi)用(最短距離)。而 h(n)是當(dāng)前節(jié)點(diǎn) n 和目標(biāo)節(jié)點(diǎn) ng 之間的最小費(fèi)用的 估計(jì)值，稱為啟發(fā)式函值。 hn*() OPEN 是

60、管理以后擴(kuò)展節(jié)點(diǎn)的明細(xì)表，所有節(jié)點(diǎn)按費(fèi)用 f 遞增順序排列， CLOSE 是管理已擴(kuò)展節(jié)點(diǎn)的明細(xì)表。 通常搜索算法(或 A)等)，從節(jié)點(diǎn) n 擴(kuò)展的所有節(jié)點(diǎn) n中，反必要的 A 節(jié)點(diǎn)同費(fèi)用 f(n )都標(biāo)注 OPEN 上，這個(gè)操作稱為“擴(kuò)展節(jié)點(diǎn) n”。 *下面是算法 (A) 的程序: A 1) 把起始節(jié)點(diǎn) ns 代入 OPEN。 2) 如果 OPEN 是空表，由于路徑不存在，所以算法終止。 3) 從 OPEN 取出先頭(費(fèi)用 f 最小)的節(jié)點(diǎn) n,并把它移到期 CLOSED 4) 如果節(jié)點(diǎn) n 是目標(biāo)節(jié)點(diǎn) ng,則順次返回到來自的節(jié)點(diǎn)上(程序上是追尋指 - 20 - 馮赟: 機(jī)器人路徑規(guī)劃方法

61、研究 針).然后，若是到達(dá)起始節(jié)點(diǎn) ns,則終止算法，得到一個(gè)路徑。 5) 如果不是這樣，擴(kuò)展節(jié)點(diǎn) n,把指針從其子孫節(jié)點(diǎn) n返回到節(jié)點(diǎn) n(記住 從哪來的)。然后，對(duì)所有的子孫節(jié)點(diǎn) n做以下工作： ,節(jié)點(diǎn) n如果不在 OPEN 或 CLOSE 表中，貝尼就是新的搜索節(jié)點(diǎn)。因此， 首先計(jì)算估計(jì)值 h(n )(從節(jié)點(diǎn) n到節(jié)點(diǎn) ng 的最短距離的估計(jì)值)，其 次計(jì)算評(píng)價(jià)值 f(n )=g(n )+h(n )( 這里， g(n )=g(n)+c(n 、 n ),g(ns)=0, c(n 、n)是連接節(jié)點(diǎn) n 和 n弧的費(fèi)用)。然后，把節(jié)點(diǎn) n同估計(jì)值 f(n )都代入 OPEN ,若節(jié)點(diǎn) n存在于

62、 OPEN 或 CLOSE 表中，貝尼就是已被搜索的節(jié)點(diǎn)。于是， 把指針換到帶來最小值 g(n )的路徑上 (變更來自的地方 )。然后，在這 個(gè)指針發(fā)生替換時(shí)，若節(jié)點(diǎn) n存在下 CLOSEI 中，則把它返回到 OPEF 后， 再計(jì)算值 f(n )=g(n )+h(n )。 6) 返回到 2) *估計(jì)值 h 比真值小或相等時(shí)，上述算法變?yōu)?，可選出從起始節(jié)點(diǎn) ns 到目 h*A 標(biāo)節(jié)點(diǎn) ng 的最佳路徑(總計(jì)費(fèi)用最小的路徑)。如不是這樣，算法變?yōu)?A,可選 出從起始節(jié)點(diǎn) ns 到目標(biāo)節(jié)點(diǎn) ng 的滿足要求的路徑(總計(jì)費(fèi)用不是最小的路徑)。因 XY,1,2XY, 此，機(jī)器人的路徑規(guī)劃多用從當(dāng)前地點(diǎn)

63、( 、)或，目的地， ppggpp 22 或(、)的平方范數(shù)定義估計(jì)值。這個(gè)估計(jì)值 h 常,1,2()()XXYY, , ,ggggpp * 常比小，成為算法，有它選擇最佳路徑。 h*A 圖 3.5 的搜索圖 G 存在估計(jì)值 h(在節(jié)點(diǎn)上用括號(hào)給出)比真值大的節(jié)點(diǎn)。h*例 如，節(jié)點(diǎn) A 和 H 的估計(jì)值 h 是 8 和 4,但到達(dá)目的地的最小真值是 7 和 2。由于這 個(gè)費(fèi)用評(píng)價(jià)過大，存在于最短路徑上的節(jié)點(diǎn) H 等可以忽略，算法錯(cuò)過了費(fèi)用 8 的最 佳路徑,最終得到費(fèi)用 9 的滿足要求的路徑。下面用圖 3.6 說明這個(gè)過程。 首先，起始節(jié)點(diǎn) S 被代入 OPEN 圖 3.6(a),擴(kuò)展后移到

64、CLOSE，節(jié)點(diǎn) A 和 B - 21 - 鄭州大學(xué)電氣工程學(xué)院畢業(yè)設(shè)計(jì) (論文) S (7) 3 2 (5) (8) B 2 A 3 3 1 2 (5) D F (5) C (3) E 2 3 (3) 4 1 H (4) 2 2 I G (1) 圖 3.5 搜索圖 G(有的地方估計(jì)值比真值大) 被代入 OPEN 圖 3.6(b)。由于節(jié)點(diǎn) A 和 B 的評(píng)價(jià)值分別為 10，8,所以擴(kuò)展節(jié) 點(diǎn)B,節(jié)點(diǎn)D, E，F(xiàn)評(píng)價(jià)值分別為9, 8， 10， 全都代入OPEN節(jié)點(diǎn)B被移到 CLOSE圖3.6(c) 。然后擴(kuò)展值 f 最小的節(jié)點(diǎn) E,節(jié)點(diǎn) H 同評(píng)價(jià)值 10 都代入 OPEN 節(jié)點(diǎn) E 被移到

65、CLOSED 其次，值 f 最小的節(jié)點(diǎn) D 擴(kuò)展后移到 CLOSED 節(jié)點(diǎn) H 被再次搜索。這時(shí)，如果 注意到節(jié)點(diǎn) H 的值 g,由于過去的費(fèi)用 6(經(jīng)由節(jié)點(diǎn) E, B 返回到節(jié)點(diǎn) S)比新的費(fèi)用 7(經(jīng)由節(jié)點(diǎn)D, B 返回到 S)小，所以不更換指針圖 3.6(d)。 由于 OPENt 存在評(píng)價(jià)值 f 為 10 的三個(gè)節(jié)點(diǎn) A,H,F,所以中斷連接擴(kuò)展節(jié)點(diǎn) A， 節(jié)點(diǎn) C同評(píng)價(jià)值 8 都代入 OPEN 節(jié)點(diǎn) A 被移到 CLOSED然后，擴(kuò)展值 f 最小的節(jié) 點(diǎn) C,被移到CLOSED而節(jié)點(diǎn) I 同評(píng)價(jià)值 10 都代入 OPEN 再次搜索節(jié)點(diǎn) H。這 時(shí)，如果注意到節(jié)點(diǎn)H 的值 g，由于過去的

66、費(fèi)用 6(經(jīng)由節(jié)點(diǎn) E、B 返回到節(jié)點(diǎn) S)比 新的費(fèi)用 8(經(jīng)由節(jié)點(diǎn) C A返回到 S)小。所以不用更換指針。由于 OPENt 存在評(píng) 價(jià)值 f 為 10 的三個(gè)節(jié)點(diǎn) F,H,I,所以用中斷連接擴(kuò)展節(jié)點(diǎn) F，節(jié)點(diǎn) G 連同評(píng)價(jià)值 9 都代入 OPEN 節(jié)點(diǎn) F 移到 CLOSED 圖3.6 (e). 最后，如果選擇節(jié)點(diǎn) G 作為值 f 最小的節(jié)點(diǎn)，將指針返回到節(jié)點(diǎn) F， B, S,最 終將得到費(fèi)用為 9 的路徑。 - 22 - 馮赟: 機(jī)器人路徑規(guī)劃方法研究 S7 S7 A10 B8 (a) (b) S7 A10 B8 S7 D9 F10 A10 B8 E8 D9 F10 (c) E8 S7 H10 (d) A10 B8 D9 F10 C8 E8 I10 H10 G9 （e） 圖 3.6 利用算法 A 選擇滿足路徑 另一方面，在圖 3.7 的搜索圖 G 上，所有節(jié)點(diǎn)的估計(jì)值（在節(jié)點(diǎn)上用括號(hào)給 h*出）常常比真值小或相等。因些，一定要調(diào)整最短路徑上的節(jié)點(diǎn)，以費(fèi)用 8 的最短路徑終止。圖 3.8 可說明這一過程。 首先，初始節(jié)點(diǎn) ns 被代入 OPEN 擴(kuò)展后移到 CLOSE，節(jié)點(diǎn) A