第七章第七章 自動(dòng)導(dǎo)引車自動(dòng)導(dǎo)引車?7.1 概述自動(dòng)導(dǎo)引小車是一種以電池為動(dòng)力，裝有非接觸式導(dǎo)向裝置的無人駕駛自動(dòng)運(yùn)輸車(見圖7-1、7-2)其主要功能是，在計(jì)算機(jī)控制下，通過復(fù)雜的路徑將物料按一定的停位精度輸送到指定的位置上7.1.1 AGV的發(fā)展現(xiàn)狀的發(fā)展現(xiàn)狀20世紀(jì)50年代中期，Barret公司設(shè)計(jì)出無人駕駛卡車，也就是AGV的最早雛形后來，美國物料搬運(yùn)研究所將其定義為AGV，它是可充電的無人駕駛小車，可根據(jù)路徑和定位情況編程，而且行走的路線可以改變和擴(kuò)展據(jù)報(bào)導(dǎo)，到1960年時(shí)，歐洲就安裝了各種型號不同水平的自動(dòng)搬運(yùn)車系統(tǒng)，使用了13,000多臺AGV1959年AGV開始用于倉庫自動(dòng)化和工廠作業(yè)中日本也從這時(shí)開始引進(jìn)AGV技術(shù)日本是使用這種車輛最多的國家，在20世紀(jì)80年代末，擁有各種類型的自動(dòng)搬運(yùn)車超過一萬臺，其生產(chǎn)廠家達(dá)47家，廣泛應(yīng)用于汽車制造、機(jī)械、電子、鋼鐵、化工、醫(yī)藥、印刷、倉儲、運(yùn)輸業(yè)和商業(yè)上20世紀(jì)70年代，AGV作為生產(chǎn)組成部分進(jìn)入了生產(chǎn)系統(tǒng)，并得到了迅速發(fā)展1973年，瑞典VOLVO公司在KALMAR轎車廠的裝配線上大量采用了AGV進(jìn)行計(jì)算機(jī)控制裝配作業(yè)，擴(kuò)大了AGV的使用范圍7.1.2 AGV在在AS/RS中的作用中的作用控制臺通過計(jì)算機(jī)網(wǎng)絡(luò)接受立體倉庫管理系統(tǒng)下達(dá)的AGV輸送任務(wù)，通過無線局域網(wǎng)通訊系統(tǒng)實(shí)時(shí)采集各AGV、拆箱機(jī)器人的狀態(tài)信息。

根據(jù)需求情況和當(dāng)前AGV運(yùn)行情況，將調(diào)度命令傳遞給選定的AGVAGV完成一次運(yùn)輸任務(wù)，在托盤回收站待命，等待下次任務(wù)各立體庫出貨口和拆箱機(jī)器人處均有光導(dǎo)通訊裝置對運(yùn)行中的AGV，控制臺將通過無線局域網(wǎng)通訊系統(tǒng)與AGV交換信息，實(shí)現(xiàn)AGV問的避碰調(diào)度、工作狀態(tài)檢測、任務(wù)調(diào)度在立體倉庫和拆箱機(jī)器人處通過光導(dǎo)通訊與AGV交換任務(wù)和狀態(tài)，完成移載自動(dòng)導(dǎo)航系統(tǒng)完成AGV的導(dǎo)引充電系統(tǒng)由充電器和充電控制器組成，完成在線快速自動(dòng)充電AGV接受控制臺的任務(wù)，完成運(yùn)輸?shù)孛嬉戚d設(shè)備可實(shí)現(xiàn)AGV的自動(dòng)移載、加載、交換空托盤圖7-4為在青島海爾自動(dòng)化立體倉庫中移載用的激光導(dǎo)引AGV7.1.3 AGV的組成的組成AGV由以下各部分組成：車體、蓄電池、車上充電裝置、控制系統(tǒng)、驅(qū)動(dòng)裝置、轉(zhuǎn)向裝置、精確定位裝置、移載機(jī)構(gòu)、通信單元和導(dǎo)引系統(tǒng)1．車體?由車架和相應(yīng)的機(jī)械電氣結(jié)構(gòu)如減速箱、電機(jī)、車輪等組成車架常采用焊接鋼結(jié)構(gòu)，要求有足夠的剛性2．蓄電池與充電裝置?常采用24V或48V直流工業(yè)蓄電池為動(dòng)力?????3．驅(qū)動(dòng)裝置?驅(qū)動(dòng)裝置是一個(gè)伺服驅(qū)動(dòng)的變速控制系統(tǒng)，可驅(qū)動(dòng)AGV運(yùn)行并具有速度控制和制動(dòng)能力它由車輪、減速器、制動(dòng)器、電機(jī)及速度控制器等部分組成，并由計(jì)算機(jī)或人工進(jìn)行控制。

速度調(diào)節(jié)可采用脈寬調(diào)速或變頻調(diào)速等方法直線行走速度可達(dá)1m/s，轉(zhuǎn)彎時(shí)為0.2～0.5m/s，接近停位點(diǎn)時(shí)為0.1m/s?4．轉(zhuǎn)向裝置?AGV常設(shè)計(jì)成三種運(yùn)動(dòng)方式：只只能能向向前前；能能向向前前與與向向后后；能縱向、橫向、斜向及回轉(zhuǎn)全全方方位位運(yùn)運(yùn)動(dòng)動(dòng)轉(zhuǎn)向裝置的結(jié)構(gòu)也有三種：(1)?鉸軸轉(zhuǎn)向式三輪車型?車體的前部為一個(gè)鉸軸轉(zhuǎn)向車輪，同時(shí)也是驅(qū)動(dòng)輪轉(zhuǎn)向和驅(qū)動(dòng)分別由兩個(gè)不同的電動(dòng)機(jī)帶動(dòng)，車體后部為兩個(gè)自由輪，由前輪控制轉(zhuǎn)向?qū)崿F(xiàn)單方向向前行駛其結(jié)構(gòu)簡單、成本低，但定位精度較低(見圖7-5)2)?差速轉(zhuǎn)向式四輪車型?車體的中部有兩個(gè)驅(qū)動(dòng)輪，由兩個(gè)電機(jī)分別驅(qū)動(dòng)前后部各有一個(gè)轉(zhuǎn)向輪(自由輪)通過控制中部兩個(gè)輪的速度比可實(shí)現(xiàn)車體的轉(zhuǎn)向，并實(shí)現(xiàn)前后雙向行駛和轉(zhuǎn)向這種方式結(jié)構(gòu)簡單，定位精度較高(見圖7-6)3)全輪轉(zhuǎn)向式四輪車型 車體的前后部各有兩個(gè)驅(qū)動(dòng)和轉(zhuǎn)向一體化車輪，每個(gè)車輪分別由各自的電動(dòng)機(jī)驅(qū)動(dòng)，可實(shí)現(xiàn)沿縱向、橫向、斜向和回轉(zhuǎn)方向任意路線行走，控制較復(fù)雜，見圖7-7?圖7-5 鉸軸轉(zhuǎn)向式三輪車型圖7-6 差速轉(zhuǎn)向式四輪車型圖7-7 全輪轉(zhuǎn)向式四輪車型5．控制系統(tǒng)?AGV控制系統(tǒng)包括車上控制器和地面(車外)控制器，均采用微型計(jì)算機(jī)，通過通信進(jìn)行聯(lián)系。

?????輸入AGV的控制指令由地面(車外)控制器發(fā)出，存入車上控制器(計(jì)算機(jī))；AGV運(yùn)行時(shí)，車上控制器通過通信系統(tǒng)從地面站接受指令并報(bào)告自己的狀態(tài)車上控制器可完成以下監(jiān)控：手動(dòng)控制、安全裝置啟動(dòng)、蓄電池狀態(tài)、轉(zhuǎn)向極限、制動(dòng)器解脫、行走燈光、驅(qū)動(dòng)和轉(zhuǎn)向電機(jī)控制與充電接觸器的監(jiān)控等??????控制臺與AGV間可采用定點(diǎn)光導(dǎo)通訊和無線局域網(wǎng)通訊兩種通訊方式采用無線通訊方式時(shí)，控制臺和AGV構(gòu)成無線局域通訊網(wǎng)，控制臺和AGV在網(wǎng)絡(luò)協(xié)議支持下交換信息無線通訊要完成AGV的調(diào)度和交通管理? 在出庫站和拆箱機(jī)器人處移載站都設(shè)有紅外光通訊系統(tǒng)，其主要功能是完成移載任務(wù)的通訊? AGV充電可以采用在線自動(dòng)快速充電方式 6．移載裝置?AGV用移載裝置來裝卸貨物，即接受和卸下載荷常見的AGV裝卸方式可分為被動(dòng)裝卸和主動(dòng)裝卸兩種?被動(dòng)裝卸方式的小車自己不具有完整的裝卸功能，而是采用助卸方式，即配合裝卸站或接收物料方的裝卸裝置自動(dòng)裝卸常見的助卸裝置有滾柱式臺面常見的助卸裝置有滾柱式臺面[圖圖7-8(b)]和升降式臺面和升降式臺面[圖圖7-8(a)]兩種兩種采用滾柱式臺面的環(huán)境要求是站臺必須帶有動(dòng)力傳動(dòng)輥道，AGV停靠在站臺邊，AGV上的輥道和站臺上的輥道對接之后同步動(dòng)作，實(shí)現(xiàn)貨物移送。

升降式臺面的升降臺下設(shè)有液壓升降機(jī)構(gòu)，高度可以自由調(diào)節(jié)為了順利移載，AGV必須精確停車才能與站臺自動(dòng)交換圖7-8 被動(dòng)裝卸裝置?主動(dòng)裝卸方式是指自動(dòng)小車自己具有裝卸功能常見的主動(dòng)裝卸方式有單面推拉式、雙面推拉式、叉車式[圖7-9(a)]和機(jī)器人式[圖7-9(b)]四種 ?圖7-9??主動(dòng)裝卸裝置7．安全裝置?為確保AGV在運(yùn)行過程中自身安全，現(xiàn)場人員及各類設(shè)備的安全，AGV將采取多級硬件、軟件的安全措施在AGV的前面設(shè)有紅外光非接觸式防碰傳感器和接觸式防碰傳感器——保險(xiǎn)杠AGV安裝醒目的信號燈和聲音報(bào)警裝置，以提醒周圍的操作人員一旦發(fā)生故障，AGV自動(dòng)進(jìn)行聲光報(bào)警，同時(shí)無線通訊通知AGV監(jiān)控系統(tǒng)1)障礙物接觸式緩沖器障礙物接觸式緩沖器是一種強(qiáng)制停車安全裝置，它產(chǎn)生作用的前提是與其它物體相接觸，使其發(fā)生一定的變形，從而觸動(dòng)有關(guān)限位裝置，強(qiáng)行使其斷電停車?(2)?障礙物接近傳感器?非接觸式檢測裝置是障礙物接觸式緩沖器的輔助裝置，是先于障礙物接觸式緩沖器發(fā)生作用的安全裝置為了安全，障礙物接近傳感器是一個(gè)多級的接近檢測裝置，在預(yù)定距離內(nèi)檢測障礙物在一定距離范圍內(nèi)，它會使AGV降速行駛，在更近的距離范圍內(nèi)，它會使AGV停車，而當(dāng)解除障礙物后，AGV將自動(dòng)恢復(fù)正常行駛狀態(tài)。

障礙物接近傳感器包括激光式，超聲波式，紅外線式等多種類型? 如日本產(chǎn)的紅外線傳感器能檢測搬運(yùn)車的前后方向、左右方向的障礙物，也能在二段內(nèi)設(shè)定慢行和停止，也即2m內(nèi)減速、lm內(nèi)停車發(fā)射的光頻率數(shù)有4種或8種，能防止各搬運(yùn)車間的相互干擾3) 裝卸移載貨物執(zhí)行機(jī)構(gòu)的自動(dòng)安全保護(hù)裝置 AGV的主要功能是解決物料的全自動(dòng)搬運(yùn)，故除了其全自動(dòng)運(yùn)行功能外，還有移載貨物的裝置移載裝置的安全保護(hù)裝置包括機(jī)械和電氣兩大類如位置定位裝置、位置限位裝置、貨物位置檢測裝置、貨物形態(tài)檢測裝置、貨物位置對中結(jié)構(gòu)、機(jī)構(gòu)自鎖裝置等結(jié)構(gòu)7.1.4 AGV的典型產(chǎn)品 ?7.2 AGV的導(dǎo)引方式的導(dǎo)引方式AGV的導(dǎo)引方式，所謂AGV導(dǎo)引方式是指決定其運(yùn)行方向和路徑的方式它不同于前面所說的一般通信常用的導(dǎo)引方式分兩大類：車外預(yù)定路徑方式和非預(yù)定路徑方式??????車外預(yù)定路徑導(dǎo)引方式是指在行駛的路徑上設(shè)置導(dǎo)引用的信息媒介物，AGV通過檢測出它的信息而得到導(dǎo)向的導(dǎo)引方式，如電磁導(dǎo)引、光學(xué)導(dǎo)引、磁帶導(dǎo)引(又稱磁性導(dǎo)引)等??????非預(yù)定路徑(自由路徑)導(dǎo)引方式其一是指在AGV上儲存著布局上的尺寸坐標(biāo)，通過識別車體當(dāng)前方位來自主地決定行駛路徑的導(dǎo)引方式，又稱車上軟件一編程路徑方式；其二是指激光導(dǎo)引。

?AGV導(dǎo)引技術(shù)的研究十分活躍，具體體現(xiàn)為：①路徑的設(shè)定更加靈活機(jī)動(dòng)②路徑變更簡單易行③提高對路面或環(huán)境變化的適應(yīng)能力④④精確地實(shí)時(shí)檢測位置和方位值，提高引導(dǎo)性能精確地實(shí)時(shí)檢測位置和方位值，提高引導(dǎo)性能⑤⑤賦予感知和回避障礙的性能賦予感知和回避障礙的性能(智能智能)⑥具有人機(jī)對話功能⑦更強(qiáng)的信息通信功能⑧系統(tǒng)盡量不依賴于中央計(jì)算機(jī)⑨⑨多輛多輛AGV協(xié)調(diào)工作協(xié)調(diào)工作????????為此，需要解決好以下幾項(xiàng)關(guān)鍵技術(shù)：①高精度且廉價(jià)的位置、方向檢測手段②信息通信手段③圖像處理和圖像識別技術(shù)以及自動(dòng)轉(zhuǎn)換器的實(shí)用化④系統(tǒng)總體技術(shù)(特別是多輛AGV群控技術(shù))7.2.1 預(yù)定路徑方式預(yù)定路徑方式1．車外連續(xù)標(biāo)記(1)?電磁導(dǎo)引這是目前AGV采用最廣泛的一種導(dǎo)引方式(見圖7-10)它需要在地面開槽(約51mm寬，15mm深)埋設(shè)電纜，接通低壓、低頻信號，在電線周圍產(chǎn)生磁場車上需安裝有兩個(gè)感應(yīng)線圈，并使其分別位于此導(dǎo)引線的兩側(cè)導(dǎo)向線中電流約為200～300mA，頻率為2kHz～35kHz(2)?反光帶或磁帶導(dǎo)引1)反射式導(dǎo)向如圖7-11所示，這種引導(dǎo)方式是在地面上連續(xù)鋪設(shè)一條用發(fā)光材料制作的帶子，或者用發(fā)光涂料涂抹在規(guī)定的運(yùn)行路線上，在車輛的底部裝有檢測反射光傳感器，通過偏差測定裝置到驅(qū)動(dòng)轉(zhuǎn)向電機(jī)來不斷調(diào)整車輛前進(jìn)的方向?2)磁性式導(dǎo)向。

是在地面上連續(xù)鋪設(shè)一條金屬磁帶，而在車輛上裝有磁性傳感器，檢測磁帶的磁場，通過磁場偏差測定控制驅(qū)動(dòng)轉(zhuǎn)向電機(jī)來調(diào)整車輛行駛方向2．車外間斷標(biāo)志標(biāo)志跟蹤方式中有一種稱為視視覺覺引引導(dǎo)導(dǎo)法法，即在所經(jīng)路徑上斷續(xù)地設(shè)有若干引導(dǎo)標(biāo)志或反射板(也可是玻璃球)，小車據(jù)此自動(dòng)識別和判斷路徑(見圖7-12)引導(dǎo)的標(biāo)志除條形碼外，還可用圓形、方形、箭頭等圖形，7.2.2 非預(yù)定路徑非預(yù)定路徑1．激光導(dǎo)引(1)光掃描導(dǎo)引?沿著路徑從高處用光束進(jìn)行掃描，計(jì)算機(jī)根據(jù)光信息(掃描角度以及掃描裝置標(biāo)號)，精密檢測出AGV現(xiàn)在的位置(圖7-13)這種方法路徑變換容易，掃描方式最簡單(2)信標(biāo)方式(激光導(dǎo)航)?這種方式是在路徑上或沿著路徑設(shè)置多個(gè)標(biāo)記，標(biāo)記本身主動(dòng)發(fā)出信號提供有關(guān)位置信息信標(biāo)方式是從現(xiàn)在位置尋找若干個(gè)信標(biāo)，然后根據(jù)其方向和有關(guān)信標(biāo)的位置信息，利用三角測量原理計(jì)算出現(xiàn)在的位置圖7-14 利用激光導(dǎo)航方式的高精度位置檢測原理標(biāo)記可用再現(xiàn)反射體(直角棱鏡等)，掃描射線優(yōu)先采用激光，也可采用紅外線根據(jù)求得的兩組兩個(gè)再現(xiàn)反射體之間的開度角計(jì)算出現(xiàn)在的位置、方位，這種方法稱為激光導(dǎo)航法標(biāo)記設(shè)置簡單、廉價(jià)，精度也非常好。

圖中參數(shù)的計(jì)算式如下：???????????????????????????????????????????????????????????????????????????????式中，???代替檢測多個(gè)信標(biāo)方向的方法，是通過從一個(gè)地方的信標(biāo)發(fā)出掃描激光光束，用AGV上若干個(gè)傳感器來檢測的方法(稱為激光信標(biāo)方法)采取這種方法，在作為移動(dòng)物體的AGV上設(shè)置的3個(gè)傳感器，如果都接收到激光站(即使是一個(gè))的光就能檢測出位置，即便存在很多AGV，如果某AGV上的3個(gè)傳感器能接收到信標(biāo)發(fā)出的光，這個(gè)AGV就能進(jìn)行高精度的位置檢測這種位置檢測法是強(qiáng)噪聲檢測法，可作為用于自立分散型群控AGV的高精度位置檢測2．?dāng)?shù)字地圖引導(dǎo)把路徑畫在數(shù)字地圖上，作為人與機(jī)器的對話式系統(tǒng)，非常容易接近此外，利用中央計(jì)算機(jī)的指令把路徑的設(shè)定作為串行數(shù)據(jù)給出的方法，對復(fù)雜、交叉路徑多的路線特別有效是適合于控制復(fù)雜、多種、多量AGV的方法，是使工廠內(nèi)的物流系統(tǒng)高度自動(dòng)化所必須的7.2.3 智能引導(dǎo)智能引導(dǎo)智能引導(dǎo)方式有示教式（初級智能）和路徑規(guī)劃兩種示教式：當(dāng)AGV沿著示教的路徑行走一次，即記住行走路線它實(shí)際上還可學(xué)會新的行走路徑，并通知主控計(jì)算機(jī)所學(xué)到的東西。

主控計(jì)算機(jī)可通知其他的AGV關(guān)于這條新的路徑的信息7.3 路徑規(guī)劃路徑規(guī)劃AGV智智能能化化的的新新發(fā)發(fā)展展在在于于自自主主回回避避障障礙礙物物并并達(dá)達(dá)到到目目的的地地的的路路徑徑規(guī)劃首先，影響路徑規(guī)劃的是AGV的自由度數(shù)和地圖的有無為了便于理解，以2自由度AGV為例，分別考慮有地圖時(shí)(環(huán)境已知時(shí))和沒有地圖時(shí)(環(huán)境未知時(shí))的路徑·動(dòng)作規(guī)劃這里，假定AGV只考慮兩個(gè)位置自由度(X、Y軸上的位置)，不考慮姿態(tài)方面的一個(gè)自由度(繞中心的回轉(zhuǎn))?????由于地圖是由AGV和障礙物的模型，所以有地圖時(shí)的路徑規(guī)劃稱為基于模型的路徑規(guī)劃(Model-based?Path-Planning)基于模型的路徑規(guī)劃稱為離線路徑規(guī)劃?????沒有地圖時(shí)的路徑規(guī)劃，AGV用外部傳感器(視覺、超聲波傳感器、光傳感器等)得到一面回避障礙一面到達(dá)目的地的路徑，由此稱為基于傳感器的路徑規(guī)劃(Sensor-based?Path-Planning)基于傳感器的路徑規(guī)劃又稱為在線路徑規(guī)劃基于模型的路徑規(guī)劃 首先說明為了快速選擇最佳最佳(最短最短)路徑路徑，應(yīng)采用怎樣的數(shù)據(jù)結(jié)構(gòu)來表現(xiàn)地圖?最佳最佳(最短最短)路徑由于接近障礙物，如果有位置誤差，AGV與障礙物碰撞的可能性很高。

下面要說明的是，為防止碰撞，除了最佳性以外更重視安全性的方法，即為了選擇離障礙物足夠遠(yuǎn)的安全路徑，應(yīng)采用怎樣的數(shù)據(jù)結(jié)構(gòu)來表現(xiàn)地圖這里由于采用一種OR表基于傳感器的路徑規(guī)劃 AGV用傳感器一面檢測障礙物一面進(jìn)行回避并最終到達(dá)目的地的路徑規(guī)劃算法，即使存在位置誤差，AGV也不會迷失確定的路徑，而最終到達(dá)目的地附近 7.3.1 路徑規(guī)劃的模型路徑規(guī)劃的模型1．幾何模型AGV有2個(gè)位置自由度(X、Y軸上的位置)和1個(gè)姿態(tài)自由度(繞中心的旋轉(zhuǎn))這里，取可全方位移動(dòng)的AGV為例加以說明由于AGV能全方位移動(dòng)，所以可忽略AGV的方向(姿態(tài)的自由度)這樣，就能用以最大回轉(zhuǎn)長度為半徑的圓表示AGV在此基礎(chǔ)上，可以把障礙物的幾何尺寸徑向擴(kuò)張一個(gè)AGV圓的半徑，同時(shí)把AGV縮成一個(gè)點(diǎn)(圖7-16)由此，在存在擴(kuò)張了的障礙物的地圖(XY平面)上，可以規(guī)劃成為幾何點(diǎn)的AGV的路徑2．?dāng)?shù)學(xué)模型首先，說明基于模型的路徑規(guī)劃為了快速選取路徑，用所謂圖的數(shù)據(jù)結(jié)構(gòu)表示規(guī)劃的數(shù)學(xué)模型(俗稱“地圖”)所謂圖就是用弧連接節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，節(jié)點(diǎn)意味著AGV的位置，弧意味著兩個(gè)位置間的移動(dòng)(圖7-17)將移動(dòng)的幾何距離、工作量或時(shí)間加權(quán)折算幾何距離、工作量或時(shí)間加權(quán)折算得出兩個(gè)位置間移動(dòng)的模型費(fèi)用，把模型費(fèi)用希望值作為費(fèi)用賦于該兩個(gè)位置間的弧上。

ABEDCF9圖7-17 ?圖(節(jié)點(diǎn)和弧)當(dāng)所有節(jié)點(diǎn)間移動(dòng)的工作量不變時(shí)，弧上賦于的費(fèi)用可以直接用幾何距離標(biāo)記弧記憶進(jìn)入節(jié)點(diǎn)和輸出節(jié)點(diǎn)，總是回到原來的地方(程序上稱為“指針返回”)而且，如果能在兩個(gè)方向移動(dòng)則用無向弧，只能單方向移動(dòng)的用有向弧5877.3.2 基于模型的路徑規(guī)劃基于模型的路徑規(guī)劃這里介紹兩個(gè)典型的圖一個(gè)是管理從起始節(jié)點(diǎn)ns到目標(biāo)節(jié)點(diǎn)ng的最短路徑的切線圖(Tangential?Graph)，另一個(gè)是連接這些節(jié)點(diǎn)的安全路徑，即管理盡量離開障礙物路徑的Voronoi圖(Voronoi?Graph)無論哪一種圖都是由節(jié)點(diǎn)和弧構(gòu)成的，用節(jié)點(diǎn)表示節(jié)點(diǎn)表示起始點(diǎn)、經(jīng)過點(diǎn)、目標(biāo)點(diǎn)；用無向弧表示其間的路徑，其上附加有作為費(fèi)用的歐幾里得距離最后，無論哪個(gè)圖，都是用算法都是用算法A選出任意路徑選出任意路徑，用算法A*選出最佳(滿足)路徑1．切線圖切線圖用障礙物的切線表示弧由此可選擇從起始節(jié)點(diǎn)ns到目標(biāo)節(jié)點(diǎn)ng的最佳(最短)路徑即切線圖是把障礙物邊界切線化得到的從起始節(jié)點(diǎn)ns開始，過兩相鄰節(jié)點(diǎn)向障礙物邊界作切線，每兩條切線的交點(diǎn)形成輔助節(jié)點(diǎn)由主節(jié)點(diǎn)(起始點(diǎn)、經(jīng)過點(diǎn)、目標(biāo)點(diǎn))、輔助節(jié)點(diǎn)和節(jié)點(diǎn)間連線組成了切線圖。

?首先把對應(yīng)起始點(diǎn)S和目標(biāo)點(diǎn)G的兩個(gè)節(jié)點(diǎn)ns和ng標(biāo)注在新的切線圖上，?然后用算法算法A*選出最佳(最短)路徑P，?最后，使點(diǎn)AGV沿著路徑P進(jìn)行PTP(Point-To-Point)控制和CP(Continuous?Path)控制，把AGV引導(dǎo)到目的地?如果在這種控制過程中產(chǎn)生位置誤差，機(jī)器人碰撞障礙物的可能性會較高，因?yàn)锳GV幾乎接近障礙物行走?2．Voronoi圖Voronoi圖可用弧表示可用弧表示距兩個(gè)以上障礙物和墻壁表面距兩個(gè)以上障礙物和墻壁表面等距離的點(diǎn)等距離的點(diǎn)陣陣，用用節(jié)點(diǎn)表示節(jié)點(diǎn)表示它們的它們的交叉位置交叉位置首先首先把對應(yīng)起始點(diǎn)S和目標(biāo)點(diǎn)G的起始節(jié)點(diǎn)ns和目標(biāo)節(jié)點(diǎn)ng標(biāo)注在圖上，然后然后用搜索算法算法A*A*選出安全路徑安全路徑P P，，最后，使點(diǎn)AGV沿著路徑P進(jìn)行PTP控制和CP控制，把AGV引導(dǎo)到目的地由于選擇的是安全路徑，所以，即使產(chǎn)生位置誤差，AGV也能夠在離障礙物足夠遠(yuǎn)的路徑上走行 ?3.搜索算法A*?(A)這里要介紹的是，把前面所說的切線圖和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費(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ù)可用下式計(jì)算： f（n）= g(n)+h(n) 式中，g(n)是起始節(jié)點(diǎn)ns和當(dāng)前節(jié)點(diǎn)n之間的現(xiàn)現(xiàn)時(shí)時(shí)點(diǎn)點(diǎn)上上的的最最小小費(fèi)費(fèi)用用(最最短短距距離離)；而h(n)是當(dāng)前節(jié)點(diǎn)n和目標(biāo)節(jié)點(diǎn)ng之間的最最小小費(fèi)用費(fèi)用h*(n)的估計(jì)值的估計(jì)值，稱為啟發(fā)式函值OPEN是管理以后擴(kuò)展節(jié)點(diǎn)的明細(xì)表，所有節(jié)點(diǎn)按費(fèi)用f（n）遞增順序排列，CLOSED是管理已擴(kuò)展節(jié)點(diǎn)的明細(xì)表通常A*(或A)等搜索算法，從節(jié)點(diǎn)n擴(kuò)展的所有節(jié)點(diǎn)n’中，把必要的節(jié)點(diǎn)同費(fèi)用f(n’)都標(biāo)注OPEN上(參看算法的第⑤步)，這個(gè)操作稱為“擴(kuò)展節(jié)點(diǎn)n”算法A*(A)的程序流程說明：①?????把起始節(jié)點(diǎn)ns代入OPEN②?????如果OPEN是空表，由于路徑不存在，所以算法終止③????? 從OPEN取出先頭(費(fèi)用f最小)的節(jié)點(diǎn)n，并把它移到CLOSED④?????如果節(jié)點(diǎn)n是目標(biāo)節(jié)點(diǎn)ng，則順次返回到來自的節(jié)點(diǎn)上(程序上是追尋(返回)指針)然后，若是到達(dá)起始節(jié)點(diǎn)ns，則終止算法，得到一個(gè)路徑。

⑤?????如果不是這樣，擴(kuò)展節(jié)點(diǎn)n，把指針從其子孫節(jié)點(diǎn)n’返回到節(jié)點(diǎn)n(記住從哪來的)然后，對所有的子孫節(jié)點(diǎn)n’做以下工作:?????????節(jié)點(diǎn)n’如果不在OPEN或CLOSED表中，則它就是新的搜索節(jié)點(diǎn)因此，首先計(jì)算估計(jì)值h(n’)(從節(jié)點(diǎn)n’到節(jié)點(diǎn)ng的最短距離的估計(jì)值).其次,計(jì)算評價(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’存在于OPEN或CLOSED表中，則它就是已被搜索的節(jié)點(diǎn)于是，把指針換到帶來最小值g(n’)的路徑上(變更來自的地方)然后，在這個(gè)指針發(fā)生替換時(shí)，若節(jié)點(diǎn)n’存在于CLOSED中，則把它返回到OPEN后，再計(jì)算值f(n’)=g(n’)+h(n’)⑥ 返回到②?算法A*(A)的程序流程???估估計(jì)計(jì)值值h比比真真值值h*小小或或相相等等時(shí)時(shí)，上述的算法變變?yōu)闉锳*，可選出從起始節(jié)點(diǎn)ns到目標(biāo)節(jié)點(diǎn)ng的最佳路徑最佳路徑(總計(jì)費(fèi)用最小的路徑總計(jì)費(fèi)用最小的路徑)???若估計(jì)值h比真值大，?h*算法則變?yōu)锳，可選出從起始節(jié)點(diǎn)ns到目標(biāo)節(jié)點(diǎn)ng的滿足要求的路徑(總計(jì)費(fèi)用不是最小的路徑)。

???因此，機(jī)器人的路徑規(guī)劃多用從當(dāng)前地點(diǎn)(??????,???????,?)到目的地(???????,????????)的平方范數(shù)定義估計(jì)值這個(gè)估計(jì)值h常常比h*小，成為算法A*，用它可選擇最佳路徑圖7-20的搜索圖G存在估計(jì)值h(在節(jié)點(diǎn)上用括號給出)比真值h*大的節(jié)點(diǎn)例如，節(jié)點(diǎn)A和H的估計(jì)值h是8和4，但到達(dá)目的地的最小真值是7和2由于這個(gè)費(fèi)用評價(jià)過大，存在于最短路徑上的節(jié)點(diǎn)H等可以忽略，算法錯(cuò)過了費(fèi)用8的最佳路徑，最終得到費(fèi)用9的滿足要求的路徑?EDFGHIBCAS(7)32(5)(5)(5)(3)(8)(1)(4)(3)221332322441圖7-20 ?搜索圖G(有的地方估計(jì)值比真值大)EDFGHIBCAS(7)32(5)(5)(5)(3)(8)(1)(4)(3)221332322441圖7-20 ?搜索圖G(有的地方估計(jì)值比真值大)B（8）I.起始節(jié)點(diǎn)S被代入OPEN[圖7-21(a)]，子節(jié)點(diǎn)A和B被代人OPEN[圖7-21(b)]起始節(jié)點(diǎn)S擴(kuò)展后移到CLOSED，II.由于節(jié)點(diǎn)A、B的評價(jià)值分別為10、8，所以選中擴(kuò)展節(jié)點(diǎn)B?B的子節(jié)點(diǎn)D、E、F，評價(jià)值分別為9、8、10，全都代人OPEN，擴(kuò)展后節(jié)點(diǎn)B被移到CLOSED[圖7-21(c)]。

III.節(jié)點(diǎn)E評價(jià)值最小，選中擴(kuò)展節(jié)點(diǎn)EE的子節(jié)點(diǎn)H同評價(jià)值10都代入OPEN，擴(kuò)展后節(jié)點(diǎn)E被移到CLOSEDIV.OPEN中當(dāng)前評價(jià)值最小的子節(jié)點(diǎn)是D，所以選中節(jié)點(diǎn)D?D的子節(jié)點(diǎn)H被再次搜索被再次搜索?，節(jié)點(diǎn)D被移到CLOSED注意注意到節(jié)點(diǎn)到節(jié)點(diǎn)H H的值的值g g，，由于過去的費(fèi)用由于過去的費(fèi)用6(6(經(jīng)由節(jié)點(diǎn)經(jīng)由節(jié)點(diǎn)E E、、B B返回到節(jié)返回到節(jié)點(diǎn)點(diǎn)S)S)比新的費(fèi)用比新的費(fèi)用7(7(經(jīng)由節(jié)點(diǎn)經(jīng)由節(jié)點(diǎn)D D、、B B返回到返回到S)S)小，所以不更換小，所以不更換指針指針[ [圖圖7-21(7-21(d)]d)]指針仍在指針仍在E E由于當(dāng)前OPEN上存在評價(jià)值f都為10的三個(gè)節(jié)點(diǎn)A、H、F，此時(shí)須對這三個(gè)節(jié)點(diǎn)A、H、F都分別向下擴(kuò)展V.用中斷連接節(jié)點(diǎn)A，擴(kuò)展節(jié)點(diǎn)C同評價(jià)值8都代人OPEN，節(jié)點(diǎn)A被移到CLOSED然后，?C的兩個(gè)擴(kuò)展節(jié)點(diǎn)I、H中，選中值f最小的節(jié)點(diǎn)I?（實(shí)際上，ACH路徑在先已經(jīng)被否定），節(jié)點(diǎn)I同評價(jià)值10都代人OPEN，節(jié)點(diǎn)C同評價(jià)值8都被移到CLOSED節(jié)點(diǎn)節(jié)點(diǎn)I的擴(kuò)展節(jié)點(diǎn)即為目標(biāo)，的擴(kuò)展節(jié)點(diǎn)即為目標(biāo)， OPEN保持VI.節(jié)點(diǎn)節(jié)點(diǎn)H的擴(kuò)展節(jié)點(diǎn)即為目標(biāo)，的擴(kuò)展節(jié)點(diǎn)即為目標(biāo)，OPEN保持VII.節(jié)點(diǎn)節(jié)點(diǎn)F的擴(kuò)展節(jié)點(diǎn)即為目標(biāo)，的擴(kuò)展節(jié)點(diǎn)即為目標(biāo)，OPEN保持VIII.當(dāng)前當(dāng)前OPEN上三個(gè)節(jié)點(diǎn)上三個(gè)節(jié)點(diǎn)I 、、H、、F的評價(jià)值都為的評價(jià)值都為10,其后的其后的擴(kuò)展節(jié)點(diǎn)都是目標(biāo)擴(kuò)展節(jié)點(diǎn)都是目標(biāo)G。

計(jì)算分別經(jīng)三個(gè)節(jié)點(diǎn)F、H、I到目標(biāo)G的評價(jià)值,經(jīng)節(jié)點(diǎn)F到目標(biāo)G的評價(jià)值最小所以用所以用中斷連接擴(kuò)展節(jié)點(diǎn)中斷連接擴(kuò)展節(jié)點(diǎn)F，，節(jié)點(diǎn)節(jié)點(diǎn)G連同評價(jià)值連同評價(jià)值9都代人都代人OPEN，，節(jié)點(diǎn)節(jié)點(diǎn)F移到移到CLOSED[圖圖7-21(e)]在圖7-22的搜索圖G上，所有節(jié)點(diǎn)的估計(jì)值h(在節(jié)點(diǎn)上用括號給出)常常比真值h*小或相等?I.起始節(jié)點(diǎn)S被代入OPEN，子節(jié)點(diǎn)A、B連同評價(jià)值f6、8被代人OPEN，起始節(jié)點(diǎn)S擴(kuò)展后移到CLOSEDII.由于節(jié)點(diǎn)A、B的評價(jià)值f分別為6、8，所以節(jié)點(diǎn)A擴(kuò)展子節(jié)點(diǎn)C、D后移到CLOSED，節(jié)點(diǎn)B、C、D連同各自的評價(jià)值8、8、9都代入OPENIII.用中斷連接擴(kuò)展節(jié)點(diǎn)B，節(jié)點(diǎn)B擴(kuò)展子節(jié)點(diǎn)E、F子節(jié)點(diǎn)E、F連同評價(jià)值8、9都代入OPEN，節(jié)點(diǎn)B擴(kuò)展后代入CLOSED再次搜索節(jié)點(diǎn)D這時(shí)，如果注意到節(jié)點(diǎn)D的值g，由于新的費(fèi)用值4(經(jīng)由節(jié)點(diǎn)B返回到節(jié)點(diǎn)S)比過去的費(fèi)用5(經(jīng)由節(jié)點(diǎn)A返回到節(jié)點(diǎn)S)小，所所以以要要更更換換指指針針，，重新計(jì)算的評價(jià)值f變?yōu)?[圖7-23(a)]IV.仍然用中斷連接擴(kuò)展節(jié)點(diǎn)C，節(jié)點(diǎn)C擴(kuò)展子節(jié)點(diǎn)I、H?子節(jié)點(diǎn)I、H連同評價(jià)值10?、9都代入OPEN，節(jié)點(diǎn)C移到CLOSED?[圖7-23(b)]?，V.當(dāng)當(dāng)前前OPEN上上五五個(gè)個(gè)節(jié)節(jié)點(diǎn)點(diǎn)I 、、H、、 D、 E 、、F。

所以選中評價(jià)值f最小的擴(kuò)展節(jié)點(diǎn)E然后，把節(jié)點(diǎn)E代入CLOSED，再次搜索節(jié)點(diǎn)HVI.這時(shí)，注意到節(jié)點(diǎn)H的值g，比起過去的費(fèi)用7(經(jīng)由節(jié)點(diǎn)C，A返回節(jié)點(diǎn)S)來新的費(fèi)用6(經(jīng)由節(jié)點(diǎn)E、B返回到節(jié)點(diǎn)S)要小，所以更換指針，重新計(jì)算H的評價(jià)值f為8[圖7-23(c)]VII.當(dāng)當(dāng)前前OPEN上上擴(kuò)展值f最小的節(jié)點(diǎn)H，其其后后的的擴(kuò)擴(kuò)展展節(jié)節(jié)點(diǎn)點(diǎn)是是目目標(biāo)標(biāo)G，節(jié)點(diǎn)G以評價(jià)值8代人OPEN，節(jié)點(diǎn)H代入CLOSEDVIII.最后，節(jié)點(diǎn)G如果選擇作為值f最小的節(jié)點(diǎn)，則把指針返回到節(jié)點(diǎn)H、E、B、S，最終得到費(fèi)用8的最短路徑這里，由于節(jié)點(diǎn)H的估計(jì)值h與真值h*相比過小，所以這個(gè)最佳路徑上的節(jié)點(diǎn)必須調(diào)整4．AGV的路徑規(guī)劃實(shí)例Dijkstra最短路徑確定法圖7-24中的節(jié)點(diǎn)1～5是AGV運(yùn)行路線上的岔口，6～18是貨物裝裝卸卸點(diǎn)點(diǎn)，6是系統(tǒng)的入入口口，9、15、16是系統(tǒng)的出出口口，19是AGV停車處在圖7-24(b)中，將AGV可能的運(yùn)行方向用箭頭進(jìn)行了表示????(1)?因?yàn)楣?jié)點(diǎn)1～5是找出6～18貨物裝卸點(diǎn)間最短距離的關(guān)鍵點(diǎn)，故先只考慮系統(tǒng)中的各岔口即節(jié)點(diǎn)先只考慮系統(tǒng)中的各岔口即節(jié)點(diǎn)l～～5間的最短路徑。

間的最短路徑為此，將相應(yīng)箭頭所表示的距離填人下面的距離矩陣因節(jié)點(diǎn)1、?3之間無直接連接的箭頭，但兩者之間可通過16、18連在一起，所以C1,3=C1,16+C16,18+Cl8,3=84C3,4=∞表示所連兩點(diǎn)間無直接表示所連兩點(diǎn)間無直接聯(lián)系，之間的聯(lián)系要通過岔口節(jié)點(diǎn)聯(lián)系，之間的聯(lián)系要通過岔口節(jié)點(diǎn)由此得到系統(tǒng)的距離矩陣(表7-2)表7-2 距離矩陣(2)搜索過程I.最短路徑法首先要求找到搜索的起始點(diǎn)i，起始點(diǎn)i必須是通過一個(gè)單箭頭就能和其余節(jié)點(diǎn)相連最多的節(jié)點(diǎn)很顯然，圖7-24(b)中的節(jié)點(diǎn)1符合這個(gè)要求，將此節(jié)點(diǎn)作為第一層II.在找出由該i點(diǎn)出發(fā)的最短距離Ci，k后，令令di，，k=Ci，，k再以再以k節(jié)節(jié)點(diǎn)作為第點(diǎn)作為第2次搜索的起點(diǎn)次搜索的起點(diǎn)III.根據(jù)距離矩陣中與k節(jié)點(diǎn)對應(yīng)的行，計(jì)算由起始點(diǎn)出發(fā)，經(jīng)此k點(diǎn)到其余節(jié)點(diǎn)的最短距離，若到節(jié)點(diǎn)j的距離最短，則計(jì)算di，k+Ck，j?IV.若若di，，k+Ck，，j>Ci，，j 再取再取i j路徑的路徑的j點(diǎn)作為第點(diǎn)作為第3次搜索的起點(diǎn)次搜索的起點(diǎn)??????????重復(fù)上面搜索過程（將j替換替換k））V.若若di，，k+Ck，，j

次搜索的起點(diǎn)如此往返進(jìn)行，直到所有節(jié)點(diǎn)均被選上為止最短路徑法的整個(gè)搜索過程見表7-3，最短路徑計(jì)算結(jié)果見圖7-25，細(xì)節(jié)見表7-4?表7-3 最短路徑法的搜索步驟表7-4 最短路徑一覽表?7.3.3 基于傳感器的路徑規(guī)劃基于傳感器的路徑規(guī)劃(1)基于傳感器的路徑規(guī)劃的指導(dǎo)思想 :離障礙物一定距離時(shí)，實(shí)施變向避障,同時(shí)單調(diào)減少單調(diào)減少到達(dá)目的地的距離，從而保證AGV到達(dá)目的地I.首先AGV向目的地直進(jìn)，若是AGV受到障礙物阻礙，記錄碰撞點(diǎn)Hi?,同時(shí)AGV順時(shí)針或反時(shí)針轉(zhuǎn)過障礙物II.如果目的地的方向有空位(脫離點(diǎn))，記錄該脫離點(diǎn)Li,若是脫離點(diǎn)Li比碰撞點(diǎn)Hi更接近目的地，AGV就離開障礙物向目的地直進(jìn)(圖7-26)III.若是脫離點(diǎn)Li比碰撞點(diǎn)Hi更遠(yuǎn)離目的地，AGV就返回碰撞點(diǎn)Hi,反向搜索搜索比碰撞點(diǎn)Hi更接近目的地的脫離點(diǎn)IV.按照這個(gè)程序，脫離點(diǎn)Li和碰撞點(diǎn)Hi單調(diào)接近目的地G GV.V.AGVAGV可看成點(diǎn)機(jī)器人點(diǎn)機(jī)器人可能與障礙物碰撞的領(lǐng)域Ri單調(diào)減少(領(lǐng)域R1→R2→R3→R4)由此，AGV最終到達(dá)目的地G算法Class2的程序：①??初始設(shè)定L0=S=R，i=0。

②點(diǎn)機(jī)器人R向目的地直進(jìn)?如果點(diǎn)機(jī)器人到達(dá)目的地，由于得到了解，算法終止；?如果向量RG被障礙物妨礙，取i=i+1，把當(dāng)前地點(diǎn)作為碰撞點(diǎn)Hi，執(zhí)行③③點(diǎn)機(jī)器人R順時(shí)針或反時(shí)針方向繞過障礙物進(jìn)行追尋?·如果點(diǎn)機(jī)器人到達(dá)目的地G，由于得到了解，算法終止；?·如果歐幾里得距離|RG|比|HiG|小，并且向量RG不受障礙物妨礙，把當(dāng)前地點(diǎn)作為脫離點(diǎn)Li,,回到②；?·若點(diǎn)機(jī)器人R返回到碰撞點(diǎn)Hi，由于不存在解，所以算法終止。