《智能移動小車AGV簡介.ppt》由會員分享，可在線閱讀，更多相關(guān)《智能移動小車AGV簡介.ppt（49頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第七章 自動導引車,7.1 概述 自動導引小車是一種以電池為動力，裝有非接觸式導向裝置的無人駕駛自動運輸車(見圖7-1、7-2)。其主要功能是，在計算機控制下，通過復雜的路徑將物料按一定的停位精度輸送到指定的位置上。,,,7.1.1 AGV的發(fā)展現(xiàn)狀 20世紀50年代中期，Barret公司設計出無人駕駛卡車，也就是AGV的最早雛形。后來，美國物料搬運研究所將其定義為AGV，它是可充電的無人駕駛小車，可根據(jù)路徑和定位情況編程，而且行走的路線可以改變和擴展。據(jù)報導，到1960年時，歐洲就安裝了各種型號不同水平的自動搬運車系統(tǒng)，使用了13,000多臺AGV。1959年AGV開始用于倉庫自動化和工廠作

2、業(yè)中。日本也從這時開始引進AGV技術(shù)。日本是使用這種車輛最多的國家，在20世紀80年代末，擁有各種類型的自動搬運車超過一萬臺，其生產(chǎn)廠家達47家，廣泛應用于汽車制造、機械、電子、鋼鐵、化工、醫(yī)藥、印刷、倉儲、運輸業(yè)和商業(yè)上。 20世紀70年代，AGV作為生產(chǎn)組成部分進入了生產(chǎn)系統(tǒng)，并得到了迅速發(fā)展。1973年，瑞典VOLVO公司在KALMAR轎車廠的裝配線上大量采用了AGV進行計算機控制裝配作業(yè)，擴大了AGV的使用范圍,7.1.2 AGV在AS/RS中的作用 控制臺通過計算機網(wǎng)絡接受立體倉庫管理系統(tǒng)下達的AGV輸送任務，通過無線局域網(wǎng)通訊系統(tǒng)實時采集各AGV、拆箱機器人的狀態(tài)信息。根據(jù)需求情況

3、和當前AGV運行情況，將調(diào)度命令傳遞給選定的AGV。AGV完成一次運輸任務，在托盤回收站待命，等待下次任務。 各立體庫出貨口和拆箱機器人處均有光導通訊裝置。對運行中的AGV，控制臺將通過無線局域網(wǎng)通訊系統(tǒng)與AGV交換信息，實現(xiàn)AGV問的避碰調(diào)度、工作狀態(tài)檢測、任務調(diào)度。在立體倉庫和拆箱機器人處通過光導通訊與AGV交換任務和狀態(tài)，完成移載。 自動導航系統(tǒng)完成AGV的導引。充電系統(tǒng)由充電器和充電控制器組成，完成在線快速自動充電。AGV接受控制臺的任務，完成運輸。地面移載設備可實現(xiàn)AGV的自動移載、加載、交換空托盤。圖7-4為在青島海爾自動化立體倉庫中移載用的激光導引AGV。,7.1.3 AGV的組

4、成 AGV由以下各部分組成：車體、蓄電池、車上充電裝置、控制系統(tǒng)、驅(qū)動裝置、轉(zhuǎn)向裝置、精確定位裝置、移載機構(gòu)、通信單元和導引系統(tǒng)。 1車體。 由車架和相應的機械電氣結(jié)構(gòu)如減速箱、電機、車輪等組成。車架常采用焊接鋼結(jié)構(gòu)，要求有足夠的剛性。 2蓄電池與充電裝置。 常采用24V或48V直流工業(yè)蓄電池為動力。 3驅(qū)動裝置。 驅(qū)動裝置是一個伺服驅(qū)動的變速控制系統(tǒng)，可驅(qū)動AGV運行并具有速度控制和制動能力。它由車輪、減速器、制動器、電機及速度控制器等部分組成，并由計算機或人工進行控制。速度調(diào)節(jié)可采用脈寬調(diào)速或變頻調(diào)速等方法。直線行走速度可達1m/s，轉(zhuǎn)彎時為0.20.5m/s，接近停位點時為0.1m/s

5、。,4轉(zhuǎn)向裝置。 AGV常設計成三種運動方式：只能向前；能向前與向后；能縱向、橫向、斜向及回轉(zhuǎn)全方位運動。轉(zhuǎn)向裝置的結(jié)構(gòu)也有三種： (1) 鉸軸轉(zhuǎn)向式三輪車型。 車體的前部為一個鉸軸轉(zhuǎn)向車輪，同時也是驅(qū)動輪。轉(zhuǎn)向和驅(qū)動分別由兩個不同的電動機帶動，車體后部為兩個自由輪，由前輪控制轉(zhuǎn)向?qū)崿F(xiàn)單方向向前行駛。其結(jié)構(gòu)簡單、成本低，但定位精度較低(見圖7-5)。 (2) 差速轉(zhuǎn)向式四輪車型。 車體的中部有兩個驅(qū)動輪，由兩個電機分別驅(qū)動。前后部各有一個轉(zhuǎn)向輪(自由輪)。通過控制中部兩個輪的速度比可實現(xiàn)車體的轉(zhuǎn)向，并實現(xiàn)前后雙向行駛和轉(zhuǎn)向。這種方式結(jié)構(gòu)簡單，定位精度較高(見圖7-6)。 (3)全輪轉(zhuǎn)向式四輪車

6、型。 車體的前后部各有兩個驅(qū)動和轉(zhuǎn)向一體化車輪，每個車輪分別由各自的電動機驅(qū)動，可實現(xiàn)沿縱向、橫向、斜向和回轉(zhuǎn)方向任意路線行走，控制較復雜，見圖7-7。,,圖7-7 全輪轉(zhuǎn)向式四輪車型,5控制系統(tǒng)。 AGV控制系統(tǒng)包括車上控制器和地面(車外)控制器，均采用微型計算機，通過通信進行聯(lián)系。 輸入AGV的控制指令由地面(車外)控制器發(fā)出，存入車上控制器(計算機)；AGV運行時，車上控制器通過通信系統(tǒng)從地面站接受指令并報告自己的狀態(tài)。車上控制器可完成以下監(jiān)控：手動控制、安全裝置啟動、蓄電池狀態(tài)、轉(zhuǎn)向極限、制動器解脫、行走燈光、驅(qū)動和轉(zhuǎn)向電機控制與充電接觸器的監(jiān)控等。 控制臺與AGV間可采用定點光導

7、通訊和無線局域網(wǎng)通訊兩種通訊方式。采用無線通訊方式時，控制臺和AGV構(gòu)成無線局域通訊網(wǎng)，控制臺和AGV在網(wǎng)絡協(xié)議支持下交換信息。無線通訊要完成AGV的調(diào)度和交通管理。 在出庫站和拆箱機器人處移載站都設有紅外光通訊系統(tǒng)，其主要功能是完成移載任務的通訊。 AGV充電可以采用在線自動快速充電方式,6移載裝置。 AGV用移載裝置來裝卸貨物，即接受和卸下載荷。常見的AGV裝卸方式可分為被動裝卸和主動裝卸兩種。 被動裝卸方式的小車自己不具有完整的裝卸功能，而是采用助卸方式，即配合裝卸站或接收物料方的裝卸裝置自動裝卸。常見的助卸裝置有滾柱式臺面圖7-8(b)和升降式臺面圖7-8(a)兩種。采用滾柱式臺面的環(huán)

8、境要求是站臺必須帶有動力傳動輥道，AGV?？吭谡九_邊，AGV上的輥道和站臺上的輥道對接之后同步動作，實現(xiàn)貨物移送。升降式臺面的升降臺下設有液壓升降機構(gòu)，高度可以自由調(diào)節(jié)。為了順利移載，AGV必須精確停車才能與站臺自動交換。,圖7-8 被動裝卸裝置,主動裝卸方式是指自動小車自己具有裝卸功能。常見的主動裝卸方式有單面推拉式、雙面推拉式、叉車式圖7-9(a)和機器人式圖7-9(b)四種。,圖7-9 主動裝卸裝置,7安全裝置。 為確保AGV在運行過程中自身安全，現(xiàn)場人員及各類設備的安全，AGV將采取多級硬件、軟件的安全措施。在AGV的前面設有紅外光非接觸式防碰傳感器和接觸式防碰傳感器保險杠。AGV安裝

9、醒目的信號燈和聲音報警裝置，以提醒周圍的操作人員。一旦發(fā)生故障，AGV自動進行聲光報警，同時無線通訊通知AGV監(jiān)控系統(tǒng)。 障礙物接觸式緩沖器。障礙物接觸式緩沖器是一種強制停車安全裝置，它產(chǎn)生作用的前提是與其它物體相接觸，使其發(fā)生一定的變形，從而觸動有關(guān)限位裝置，強行使其斷電停車。 (2) 障礙物接近傳感器。 非接觸式檢測裝置是障礙物接觸式緩沖器的輔助裝置，是先于障礙物接觸式緩沖器發(fā)生作用的安全裝置。為了安全，障礙物接近傳感器是一個多級的接近檢測裝置，在預定距離內(nèi)檢測障礙物。在一定距離范圍內(nèi)，它會使AGV降速行駛，在更近的距離范圍內(nèi)，它會使AGV停車，而當解除障礙物后，AGV將自動恢復正常行駛狀

10、態(tài)。障礙物接近傳感器包括激光式，超聲波式，紅外線式等多種類型,如日本產(chǎn)的紅外線傳感器能檢測搬運車的前后方向、左右方向的障礙物，也能在二段內(nèi)設定慢行和停止，也即2m內(nèi)減速、lm內(nèi)停車。發(fā)射的光頻率數(shù)有4種或8種，能防止各搬運車間的相互干擾。 (3) 裝卸移載貨物執(zhí)行機構(gòu)的自動安全保護裝置。 AGV的主要功能是解決物料的全自動搬運，故除了其全自動運行功能外，還有移載貨物的裝置。移載裝置的安全保護裝置包括機械和電氣兩大類。如位置定位裝置、位置限位裝置、貨物位置檢測裝置、貨物形態(tài)檢測裝置、貨物位置對中結(jié)構(gòu)、機構(gòu)自鎖裝置等結(jié)構(gòu)。 7.1.4 AGV的典型產(chǎn)品,7.2 AGV的導引方式 AGV的導引方式，

11、所謂AGV導引方式是指決定其運行方向和路徑的方式。它不同于前面所說的一般通信。 常用的導引方式分兩大類：車外預定路徑方式和非預定路徑方式。 車外預定路徑導引方式是指在行駛的路徑上設置導引用的信息媒介物，AGV通過檢測出它的信息而得到導向的導引方式，如電磁導引、光學導引、磁帶導引(又稱磁性導引)等。 非預定路徑(自由路徑)導引方式其一是指在AGV上儲存著布局上的尺寸坐標，通過識別車體當前方位來自主地決定行駛路徑的導引方式，又稱車上軟件一編程路徑方式；其二是指激光導引。,AGV導引技術(shù)的研究十分活躍，具體體現(xiàn)為： 路徑的設定更加靈活機動。路徑變更簡單易行。 提高對路面或環(huán)境變化的適應能力。 精

12、確地實時檢測位置和方位值，提高引導性能。 賦予感知和回避障礙的性能(智能)。 具有人機對話功能 更強的信息通信功能。 系統(tǒng)盡量不依賴于中央計算機。 多輛AGV協(xié)調(diào)工作。 為此，需要解決好以下幾項關(guān)鍵技術(shù)： 高精度且廉價的位置、方向檢測手段。 信息通信手段。 圖像處理和圖像識別技術(shù)以及自動轉(zhuǎn)換器的實用化。 系統(tǒng)總體技術(shù)(特別是多輛AGV群控技術(shù))。,7.2.1 預定路徑方式 1車外連續(xù)標記 (1) 電磁導引 這是目前AGV采用最廣泛的一種導引方式(見圖7-10)。它需要在地面開槽(約51mm寬，15mm深)埋設電纜，接通低壓、低頻信號，在電線周圍產(chǎn)生磁場。車上需安裝有兩個感應線圈，并使其分別位

13、于此導引線的兩側(cè)。導向線中電流約為200300mA，頻率為2kHz35kHz。,(2) 反光帶或磁帶導引 1)反射式導向。如圖7-11所示，這種引導方式是在地面上連續(xù)鋪設一條用發(fā)光材料制作的帶子，或者用發(fā)光涂料涂抹在規(guī)定的運行路線上，在車輛的底部裝有檢測反射光傳感器，通過偏差測定裝置到驅(qū)動轉(zhuǎn)向電機來不斷調(diào)整車輛前進的方向 2)磁性式導向。是在地面上連續(xù)鋪設一條金屬磁帶，而在車輛上裝有磁性傳感器，檢測磁帶的磁場，通過磁場偏差測定控制驅(qū)動轉(zhuǎn)向電機來調(diào)整車輛行駛方向。,2車外間斷標志 標志跟蹤方式中有一種稱為視覺引導法，即在所經(jīng)路徑上斷續(xù)地設有若干引導標志或反射板(也可是玻璃球)，小車據(jù)此自動識別和

14、判斷路徑(見圖7-12)。 引導的標志除條形碼外，還可用圓形、方形、箭頭等圖形，,7.2.2 非預定路徑 1激光導引 (1)光掃描導引。 沿著路徑從高處用光束進行掃描，計算機根據(jù)光信息(掃描角度以及掃描裝置標號)，精密檢測出AGV現(xiàn)在的位置(圖7-13)。這種方法路徑變換容易，掃描方式最簡單。,(2)信標方式(激光導航)。 這種方式是在路徑上或沿著路徑設置多個標記，標記本身主動發(fā)出信號提供有關(guān)位置信息。信標方式是從現(xiàn)在位置尋找若干個信標，然后根據(jù)其方向和有關(guān)信標的位置信息，利用三角測量原理計算出現(xiàn)在的位置。,圖7-14 利用激光導航方式的高精度位置檢測原理,標記可用再現(xiàn)反射體(直角棱鏡等)，掃

15、描射線優(yōu)先采用激光，也可采用紅外線。根據(jù)求得的兩組兩個再現(xiàn)反射體之間的開度角計算出現(xiàn)在的位置、方位，這種方法稱為激光導航法。標記設置簡單、廉價，精度也非常好。,圖中參數(shù)的計算式如下： 式中，,代替檢測多個信標方向的方法，是通過從一個地方的信標發(fā)出掃描激光光束，用AGV上若干個傳感器來檢測的方法(稱為激光信標方法)。采取這種方法，在作為移動物體的AGV上設置的3個傳感器，如果都接收到激光站(即使是一個)的光就能檢測出位置，即便存在很多AGV，如果某AGV上的3個傳感器能接收到信標發(fā)出的光，這個AGV就能進行高精度的位置檢測。這種位置檢測法是強噪聲檢測法，可

16、作為用于自立分散型群控AGV的高精度位置檢測。,2數(shù)字地圖引導 把路徑畫在數(shù)字地圖上，作為人與機器的對話式系統(tǒng)，非常容易接近。此外，利用中央計算機的指令把路徑的設定作為串行數(shù)據(jù)給出的方法，對復雜、交叉路徑多的路線特別有效。是適合于控制復雜、多種、多量AGV的方法，是使工廠內(nèi)的物流系統(tǒng)高度自動化所必須的。 7.2.3 智能引導 智能引導方式有示教式（初級智能）和路徑規(guī)劃兩種。 示教式：當AGV沿著示教的路徑行走一次，即記住行走路線。它實際上還可學會新的行走路徑，并通知主控計算機所學到的東西。主控計算機可通知其他的AGV關(guān)于這條新的路徑的信息。,7.3 路徑規(guī)劃 AGV智能化的新發(fā)展在于自主回避障

17、礙物并達到目的地的路徑規(guī)劃。 首先，影響路徑規(guī)劃的是AGV的自由度數(shù)和地圖的有無。為了便于理解，以2自由度AGV為例，分別考慮有地圖時(環(huán)境已知時)和沒有地圖時(環(huán)境未知時)的路徑動作規(guī)劃。這里，假定AGV只考慮兩個位置自由度(X、Y軸上的位置)，不考慮姿態(tài)方面的一個自由度(繞中心的回轉(zhuǎn)) 由于地圖是由AGV和障礙物的模型，所以有地圖時的路徑規(guī)劃稱為基于模型的路徑規(guī)劃(Model-based Path-Planning)?；谀Ｐ偷穆窂揭?guī)劃稱為離線路徑規(guī)劃。 沒有地圖時的路徑規(guī)劃，AGV用外部傳感器(視覺、超聲波傳感器、光傳感器等)得到一面回避障礙一面到達目的地的路徑，由此稱為基于傳感器的

18、路徑規(guī)劃(Sensor-based Path-Planning)?；趥鞲衅鞯穆窂揭?guī)劃又稱為在線路徑規(guī)劃。,基于模型的路徑規(guī)劃 首先說明為了快速選擇最佳(最短)路徑，應采用怎樣的數(shù)據(jù)結(jié)構(gòu)來表現(xiàn)地圖。 最佳(最短)路徑由于接近障礙物，如果有位置誤差，AGV與障礙物碰撞的可能性很高。下面要說明的是，為防止碰撞，除了最佳性以外更重視安全性的方法，即為了選擇離障礙物足夠遠的安全路徑，應采用怎樣的數(shù)據(jù)結(jié)構(gòu)來表現(xiàn)地圖。這里由于采用一種OR表。 基于傳感器的路徑規(guī)劃 AGV用傳感器一面檢測障礙物一面進行回避并最終到達目的地的路徑規(guī)劃算法，即使存在位置誤差，AGV也不會迷失確定的路徑，而最終到達目的地附近

19、。,7.3.1 路徑規(guī)劃的模型 1幾何模型 AGV有2個位置自由度(X、Y軸上的位置)和1個姿態(tài)自由度(繞中心的旋轉(zhuǎn))。這里，取可全方位移動的AGV為例加以說明。由于AGV能全方位移動，所以可忽略AGV的方向(姿態(tài)的自由度)。這樣，就能用以最大回轉(zhuǎn)長度為半徑的圓表示AGV。在此基礎上，可以把障礙物的幾何尺寸徑向擴張一個AGV圓的半徑，同時把AGV縮成一個點(圖7-16)。由此，在存在擴張了的障礙物的地圖(XY平面)上，可以規(guī)劃成為幾何點的AGV的路徑。,2數(shù)學模型首先，說明基于模型的路徑規(guī)劃。 為了快速選取路徑，用所謂圖的數(shù)據(jù)結(jié)構(gòu)表示規(guī)劃的數(shù)學模型(俗稱“地圖”)。所謂圖就是用弧連接節(jié)點的數(shù)據(jù)

20、結(jié)構(gòu)，節(jié)點意味著AGV的位置，弧意味著兩個位置間的移動(圖7-17)。將移動的幾何距離、工作量或時間加權(quán)折算得出兩個位置間移動的模型費用，把模型費用希望值作為費用賦于該兩個位置間的弧上。,當所有節(jié)點間移動的工作量不變時，弧上賦于的費用可以直接用幾何距離標記。弧記憶進入節(jié)點和輸出節(jié)點，總是回到原來的地方(程序上稱為“指針返回”)。而且，如果能在兩個方向移動則用無向弧，只能單方向移動的用有向弧。,5,8,7,7.3.2 基于模型的路徑規(guī)劃 這里介紹兩個典型的圖。一個是管理從起始節(jié)點ns到目標節(jié)點ng的最短路徑的切線圖(Tangential Graph)，另一個是連接這些節(jié)點的安全路徑，即管理盡量離

21、開障礙物路徑的Voronoi圖(Voronoi Graph)。無論哪一種圖都是由節(jié)點和弧構(gòu)成的，用節(jié)點表示起始點、經(jīng)過點、目標點；用無向弧表示其間的路徑，其上附加有作為費用的歐幾里得距離。 最后，無論哪個圖，都是用算法A選出任意路徑，用算法A*選出最佳(滿足)路徑。 1切線圖 切線圖用障礙物的切線表示弧。由此可選擇從起始節(jié)點ns到目標節(jié)點ng的最佳(最短)路徑。即切線圖是把障礙物邊界切線化得到的。從起始節(jié)點ns開始，過兩相鄰節(jié)點向障礙物邊界作切線，每兩條切線的交點形成輔助節(jié)點。由主節(jié)點(起始點、經(jīng)過點、目標點)、輔助節(jié)點和節(jié)點間連線組成了切線圖。,首先把對應起始點S和目標點G的兩個節(jié)點ns和n

22、g標注在新的切線圖上， 然后用算法A*選出最佳(最短)路徑P， 最后，使點AGV沿著路徑P進行PTP(Point-To-Point)控制和CP(Continuous Path)控制，把AGV引導到目的地。,,如果在這種控制過程中產(chǎn)生位置誤差，機器人碰撞障礙物的可能性會較高，因為AGV幾乎接近障礙物行走,2Voronoi圖 Voronoi圖可用弧表示距兩個以上障礙物和墻壁表面等距離的點陣，用節(jié)點表示它們的交叉位置。 首先把對應起始點S和目標點G的起始節(jié)點ns和目標節(jié)點ng標注在圖上，然后用搜索算法A*選出安全路徑P，最后，使點AGV沿著路徑P進行PTP控制和CP控制，把AGV引導到目的地。由于選

23、擇的是安全路徑，所以，即使產(chǎn)生位置誤差，AGV也能夠在離障礙物足夠遠的路徑上走行,,3.搜索算法A* (A) 這里要介紹的是，把前面所說的切線圖和Voronoi圖作為搜索圖G，選出從起始節(jié)點ns到目標節(jié)點ng的最佳(或滿足)路徑的算法A*(或選出任意路徑的算法A)。 算法A*(或A)一面計算節(jié)點n的費用f(n)，一面搜索圖G。費用f(n)是從起始節(jié)點ns經(jīng)由當前節(jié)點n到目標節(jié)點ng的最小費用(最短距離)的估價函數(shù)?？捎孟率接嬎悖? f（n）= g(n)+h(n) 式中，g(n)是起始節(jié)點ns和當前節(jié)點n之間的現(xiàn)時點上的最小費用(最短距離)；而h(n)是當前節(jié)點n和目標節(jié)點ng之間的最小費用h

24、*(n)的估計值，稱為啟發(fā)式函值。 OPEN是管理以后擴展節(jié)點的明細表，所有節(jié)點按費用f（n）遞增順序排列，CLOSED是管理已擴展節(jié)點的明細表。 通常A*(或A)等搜索算法，從節(jié)點n擴展的所有節(jié)點n中，把必要的節(jié)點同費用f(n)都標注OPEN上(參看算法的第步)，這個操作稱為“擴展節(jié)點n”。,算法A*(A)的程序流程說明： 把起始節(jié)點ns代入OPEN。 如果OPEN是空表，由于路徑不存在，所以算法終止。 從OPEN取出先頭(費用f最小)的節(jié)點n，并把它移到CLOSED。 如果節(jié)點n是目標節(jié)點ng，則順次返回到來自的節(jié)點上(程序上是追尋(返回)指針)。然后，若是到達起始節(jié)點ns，則終止算法，得

25、到一個路徑。 如果不是這樣，擴展節(jié)點n，把指針從其子孫節(jié)點n返回到節(jié)點n(記住從哪來的)。然后，對所有的子孫節(jié)點n做以下工作: 節(jié)點n如果不在OPEN或CLOSED表中，則它就是新的搜索節(jié)點。因此，首先計算估計值h(n)(從節(jié)點n到節(jié)點ng的最短距離的估計值).其次,計算評價值 f(n)=g(n)+h(n) (這里g(n)=g(n)+c(n、n),g(ns)=0,c(n、n)是連接節(jié)點n和n弧的費用)。然后，把節(jié)點n同估計值f（n）都代入OPEN。 若節(jié)點n存在于OPEN或CLOSED表中，則它就是已被搜索的節(jié)點。于是，把指針換到帶來最小值g(n)的路徑上(變更來自的地方)。然后，在這個

26、指針發(fā)生替換時，若節(jié)點n存在于CLOSED中，則把它返回到OPEN后，再計算值f(n)=g(n)+h(n)。 返回到,算法A*(A)的程序流程,估計值h比真值h*小或相等時，上述的算法變?yōu)锳*，可選出從起始節(jié)點ns到目標節(jié)點ng的最佳路徑(總計費用最小的路徑)。 若估計值h比真值大， h*算法則變?yōu)锳，可選出從起始節(jié)點ns到目標節(jié)點ng的滿足要求的路徑(總計費用不是最小的路徑)。 因此，機器人的路徑規(guī)劃多用從當前地點( , , )到目的地( , )的平方范數(shù) 定義估計值。這個估計值h常常比h*小，成為算法A*，用它可選擇最佳路徑。 圖7-20的搜索圖G存在估計值h(在節(jié)點上用括號給出)

27、比真值h*大的節(jié)點。例如，節(jié)點A和H的估計值h是8和4，但到達目的地的最小真值是7和2。由于這個費用評價過大，存在于最短路徑上的節(jié)點H等可以忽略，算法錯過了費用8的最佳路徑，最終得到費用9的滿足要求的路徑。,,B（8）,起始節(jié)點S被代入OPEN圖7-21(a)，子節(jié)點A和B被代人OPEN圖7-21(b)。起始節(jié)點S擴展后移到CLOSED， 由于節(jié)點A、B的評價值分別為10、8，所以選中擴展節(jié)點B 。B的子節(jié)點D、E、F，評價值分別為9、8、10，全都代人OPEN，擴展后節(jié)點B被移到CLOSED圖7-21(c)。 節(jié)點E評價值最小，選中擴展節(jié)點E。E的子節(jié)點H同評價值10都代入OPEN，擴展后節(jié)

28、點E被移到CLOSED。 OPEN中當前評價值最小的子節(jié)點是D，所以選中節(jié)點D。 D的子節(jié)點H被再次搜索 ，節(jié)點D被移到CLOSED。注意到節(jié)點H的值g，由于過去的費用6(經(jīng)由節(jié)點E、B返回到節(jié)點S)比新的費用7(經(jīng)由節(jié)點D、B返回到S)小，所以不更換指針圖7-21(d)。指針仍在E。由于當前OPEN上存在評價值f都為10的三個節(jié)點A、H、F，此時須對這三個節(jié)點A、H、F都分別向下擴展。,用中斷連接節(jié)點A，擴展節(jié)點C同評價值8都代人OPEN，節(jié)點A被移到CLOSED。然后， C的兩個擴展節(jié)點I、H中，選中值f最小的節(jié)點I （實際上，ACH路徑在先已經(jīng)被否定），節(jié)點I同評價值10都代人OPEN，

29、節(jié)點C同評價值8都被移到CLOSED。節(jié)點I的擴展節(jié)點即為目標， OPEN保持 節(jié)點H的擴展節(jié)點即為目標，OPEN保持 節(jié)點F的擴展節(jié)點即為目標，OPEN保持 當前OPEN上三個節(jié)點I 、H、F的評價值都為10,其后的擴展節(jié)點都是目標G。計算分別經(jīng)三個節(jié)點F、H、I到目標G的評價值,經(jīng)節(jié)點F到目標G的評價值最小。所以用中斷連接擴展節(jié)點F，節(jié)點G連同評價值9都代人OPEN，節(jié)點F移到CLOSED圖7-21(e)。,在圖7-22的搜索圖G上，所有節(jié)點的估計值h(在節(jié)點上用括號給出)常常比真值h*小或相等。,,,起始節(jié)點S被代入OPEN，子節(jié)點A、B連同評價值f6、8被代人OPEN，起始節(jié)點S擴展后

30、移到CLOSED。 由于節(jié)點A、B的評價值f分別為6、8，所以節(jié)點A擴展子節(jié)點C、D后移到CLOSED，節(jié)點B、C、D連同各自的評價值8、8、9都代入OPEN。 用中斷連接擴展節(jié)點B，節(jié)點B擴展子節(jié)點E、F。子節(jié)點E、F連同評價值8、9都代入OPEN，節(jié)點B擴展后代入CLOSED。再次搜索節(jié)點D。這時，如果注意到節(jié)點D的值g，由于新的費用值4(經(jīng)由節(jié)點B返回到節(jié)點S)比過去的費用5(經(jīng)由節(jié)點A返回到節(jié)點S)小，所以要更換指針，重新計算的評價值f變?yōu)?圖7-23(a)。 仍然用中斷連接擴展節(jié)點C，節(jié)點C擴展子節(jié)點I、H 。子節(jié)點I、H連同評價值10 、9都代入OPEN，節(jié)點C移到CLOSED 圖

31、7-23(b) ，,當前OPEN上五個節(jié)點I 、H、 D、 E 、F。所以選中評價值f最小的擴展節(jié)點E。然后，把節(jié)點E代入CLOSED，再次搜索節(jié)點H。 這時，注意到節(jié)點H的值g，比起過去的費用7(經(jīng)由節(jié)點C，A返回節(jié)點S)來新的費用6(經(jīng)由節(jié)點E、B返回到節(jié)點S)要小，所以更換指針，重新計算H的評價值f為8圖7-23(c) 當前OPEN上擴展值f最小的節(jié)點H，其后的擴展節(jié)點是目標G，節(jié)點G以評價值8代人OPEN，節(jié)點H代入CLOSED 最后，節(jié)點G如果選擇作為值f最小的節(jié)點，則把指針返回到節(jié)點H、E、B、S，最終得到費用8的最短路徑。這里，由于節(jié)點H的估計值h與真值h*相比過小，所以這個最佳

32、路徑上的節(jié)點必須調(diào)整。,4AGV的路徑規(guī)劃實例 Dijkstra最短路徑確定法。圖7-24中的節(jié)點15是AGV運行路線上的岔口，618是貨物裝卸點，6是系統(tǒng)的入口，9、15、16是系統(tǒng)的出口，19是AGV停車處。在圖7-24(b)中，將AGV可能的運行方向用箭頭進行了表示。,,(1) 因為節(jié)點15是找出618貨物裝卸點間最短距離的關(guān)鍵點，故先只考慮系統(tǒng)中的各岔口即節(jié)點l5間的最短路徑。為此，將相應箭頭所表示的距離填人下面的距離矩陣。因節(jié)點1、 3之間無直接連接的箭頭，但兩者之間可通過16、18連在一起，所以C1,3=C1,16+C16,18+Cl8,3=84。C3,4=表示所連兩點間無直接聯(lián)系

33、，之間的聯(lián)系要通過岔口節(jié)點。由此得到系統(tǒng)的距離矩陣(表7-2)。,表7-2 距離矩陣,,(2)搜索過程 最短路徑法首先要求找到搜索的起始點i，起始點i必須是通過一個單箭頭就能和其余節(jié)點相連最多的節(jié)點。很顯然，圖7-24(b)中的節(jié)點1符合這個要求，將此節(jié)點作為第一層。 在找出由該i點出發(fā)的最短距離Ci，k后，令di，k=Ci，k再以k節(jié)點作為第2次搜索的起點。 根據(jù)距離矩陣中與k節(jié)點對應的行，計算由起始點出發(fā)，經(jīng)此k點到其余節(jié)點的最短距離，若到節(jié)點j的距離最短，則計算di，k+Ck，j 若di，k+Ck，jCi，j 再取i j路徑的j點作為第3次搜索的起點。 重復上面搜索過程（將j替換k

34、） 若di，k+Ck，j

35、有空位(脫離點)，記錄該脫離點Li,若是脫離點Li比碰撞點Hi更接近目的地，AGV就離開障礙物向目的地直進(圖7-26)。 若是脫離點Li比碰撞點Hi更遠離目的地，AGV就返回碰撞點Hi,反向搜索比碰撞點Hi更接近目的地的脫離點 按照這個程序，脫離點Li和碰撞點Hi單調(diào)接近目的地G AGV可看成點機器人。點機器人可能與障礙物碰撞的領域Ri單調(diào)減少(領域R1R2R3R4)。由此，AGV最終到達目的地G。,算法Class2的程序： 初始設定L0=S=R，i=0。 點機器人R向目的地直進。 如果點機器人到達目的地，由于得到了解，算法終止； 如果向量RG被障礙物妨礙，取i=i+1，把當前地點作為碰撞點Hi，執(zhí)行。 點機器人R順時針或反時針方向繞過障礙物進行追尋。 如果點機器人到達目的地G，由于得到了解，算法終止； 如果歐幾里得距離|RG|比|HiG|小，并且向量RG不受障礙物妨礙，把當前地點作為脫離點Li,,回到； 若點機器人R返回到碰撞點Hi，由于不存在解，所以算法終止。,,