一種運(yùn)輸自動導(dǎo)引車路徑規(guī)劃研究

吳文軍1　張　巖2　吳為民3　龔松柏3　張榮輝3

（1新疆農(nóng)業(yè)大學(xué) 機(jī)械交通學(xué)院,，烏魯木齊,，830052；2中國科學(xué)院新疆理化技術(shù)研究所,，烏魯木齊,，830011；3新疆物聯(lián)網(wǎng)感知與控制實(shí)驗(yàn)室,，烏魯木齊,，830011）

摘 要

關(guān)鍵詞：AGV，路徑規(guī)劃,，環(huán)境地圖建模算法,，路徑搜索算法

0　引言

自動導(dǎo)引車（Automatic Guided Vehicle，簡稱AGV）是一種利用電磁或者光學(xué)等自動導(dǎo)航設(shè)備,，能夠沿著規(guī)定的路徑行駛,，具有安全保護(hù)的無人駕駛的物流運(yùn)輸設(shè)備。而AGV在運(yùn)行過程中主要完成路徑規(guī)劃,、定位,、導(dǎo)航、避障等任務(wù),，所以,，路徑規(guī)劃是AGV導(dǎo)航過程中基本環(huán)節(jié)之一。路徑規(guī)劃主要研究在具有障礙物的環(huán)境條件下,，AGV如何尋找到目標(biāo)地,，也就是選擇合適合理的路徑。本文以一種實(shí)用型火工品運(yùn)輸自動導(dǎo)引車為研究對象,，主要闡述其路徑規(guī)劃研究,。

1　路徑規(guī)劃分類

路徑規(guī)劃就是按照某一性能指標(biāo)搜索一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)或者近似最優(yōu)的無碰撞路徑,；路徑規(guī)劃按照不同的分類方法可以有不同分類。

1.1　按照AGV對環(huán)境信息獲取的程度不同分類

按照AGV對環(huán)境信息獲取的程度不同分類,，路徑規(guī)劃可以分為兩類：全局路徑規(guī)劃和局部路徑規(guī)劃,。全局路徑規(guī)劃也稱為靜態(tài)路徑規(guī)劃，就是指環(huán)境信息完全知道的路徑規(guī)劃,，而局部路徑規(guī)劃也稱為動態(tài)路徑規(guī)劃,，是指環(huán)境信息完全未知或者部分未知的路徑規(guī)劃［1］。

1.1.1　局部路徑規(guī)劃

局部路徑規(guī)劃適應(yīng)于動態(tài)環(huán)境（未知環(huán)境或者部分未知的環(huán)境）,，其是通過AGV上安裝的傳感器在線地（實(shí)時(shí)地）對AGV的工作環(huán)境進(jìn)行探測,，獲取障礙物的位置、形狀,、尺寸等信息來完成路徑規(guī)劃,，即路徑是在線規(guī)劃（隨著AGV行駛，實(shí)時(shí)地探測規(guī)劃路徑）,。動態(tài)環(huán)境路徑規(guī)劃需要平衡時(shí)間性和安全性,，其主要內(nèi)容包括目標(biāo)吸引、動態(tài)安全性,、時(shí)間約束三部分,。

1.1.2　全局路徑規(guī)劃

全局路徑規(guī)劃適應(yīng)于靜態(tài)環(huán)境（已知環(huán)境），其路徑是離線規(guī)劃（在AGV行駛之前的規(guī)劃）,。但是靜態(tài)環(huán)境AGV路徑規(guī)劃首先要解決的是路徑合理的條件問題（合理路徑就是指能夠使AGV系統(tǒng)實(shí)現(xiàn)控制的路徑）,。路徑的平滑程度決定路徑是否合理，路徑越平緩,，AGV系統(tǒng)越易于實(shí)現(xiàn)控制,。靜態(tài)環(huán)境下的路徑一般分為四類：

1）路徑不連續(xù)，也就是平滑程度低,，主要表現(xiàn)為具有多個(gè)突變點(diǎn),，此時(shí)AGV系統(tǒng)不易被控制，曲線不連續(xù),，無法對其追蹤,。

2）路徑連續(xù)，但是切線方向不連續(xù),，也就是切線方向發(fā)生突變,。

3）路徑連續(xù)并且切線方向連續(xù)，較為合理的路徑規(guī)劃,，常常被采用,。

4）集以上三種曲線優(yōu)點(diǎn)于一身，但是這種路徑在現(xiàn)實(shí)實(shí)踐中由于復(fù)雜,、不易實(shí)現(xiàn),，所以很難被采用,。

所以，一般我們認(rèn)為路徑連續(xù)并且切線方向連續(xù)的路徑是較為合理的路徑規(guī)劃,，即合理路徑,，一般情況下常常被采用。

1.2　按照AGV車輛的數(shù)量分類

按照車輛的數(shù)量分類,，路徑規(guī)劃可以分為兩類：單車路徑規(guī)劃和多車路徑規(guī)劃,。其中單車路徑規(guī)劃是多車路徑規(guī)劃的基礎(chǔ)，從單車路徑規(guī)劃到多車路徑規(guī)劃,，一般需要解決幾個(gè)問題：多車協(xié)調(diào)調(diào)度問題，多車碰撞沖突問題,，通信問題等,，解決這類問題一般給予每輛單車優(yōu)先級來解決。

本文主要研究的是單車全局靜態(tài)的路徑規(guī)劃問題,，主要針對設(shè)計(jì)制造實(shí)用型火工品運(yùn)輸自動導(dǎo)引車的路徑規(guī)劃問題,。

2　路徑規(guī)劃步驟及方法

單AGV的全局路徑規(guī)劃問題，分為兩個(gè)子問題,，即是環(huán)境地圖建模和路徑搜索算法,。

2.1　環(huán)境地圖建模

目前，常用的環(huán)境地圖建模方法有：可視圖法,、拓?fù)浞?、柵格?span>［2］以及圖論法。

2.1.1　可視圖法

在可視圖法中,，把AGV看作一個(gè)點(diǎn),，障礙物看作一個(gè)個(gè)多邊形。初始節(jié)點(diǎn),、目標(biāo)節(jié)點(diǎn),、多邊形障礙物的各個(gè)頂點(diǎn)看作節(jié)點(diǎn)進(jìn)行組合連線，并且保證這些直線與多邊形障礙物均不相交,，最終形成的一張地圖稱為可視圖,。利用可視圖法形成的地圖，在圖中存在一些不必要的連線,，為了刪除這些多余的線條,，縮短搜索時(shí)間，我們對可視圖法進(jìn)行改進(jìn),，形成改進(jìn)的可視圖法,。改進(jìn)的可視圖法有切線圖法和Voronoi圖法。以切線圖法為例,，切線圖法就是使用多邊形障礙物的切線表示路徑弧段,，如圖1所示,。

圖1　切線圖

圖2　（a） 四叉樹表示柵格圖

柵格法制圖以網(wǎng)格單元為單元記錄環(huán)境障礙物信息,，有障礙物的地方網(wǎng)格值較高,，我們把有障礙物的網(wǎng)格單元稱為障礙柵格，其他稱為自由柵格,。同時(shí),，我們一般把每個(gè)網(wǎng)格單元看作一個(gè)點(diǎn)，所以一般以AGV機(jī)器人的自身尺寸為準(zhǔn)來分割網(wǎng)格單元的大小,，如圖2（b）所示,。

圖2　（b） 障礙柵格和自由柵格圖

2.1.3　拓?fù)浞?/p>

拓?fù)浞ㄒ卜Q為拓?fù)涞貓D法,，就是把室內(nèi)環(huán)境表示為帶結(jié)點(diǎn)和相關(guān)連接線的拓?fù)浣Y(jié)構(gòu)圖,，其中結(jié)點(diǎn)表示環(huán)境中的重要位置點(diǎn)（拐角、門,、電梯,、樓梯等），邊表示結(jié)點(diǎn)間的連接關(guān)系,，如走廊等,，拓?fù)潢P(guān)系如圖3所示。

如果不論在可視圖法還是改進(jìn)的可視圖法中,，AGV都要經(jīng)過多邊形障礙物的頂點(diǎn),，那么AGV就不可避免的容易與障礙物的頂點(diǎn)處發(fā)生碰撞。

2.1.2　柵格法

柵格法在地圖中應(yīng)用非常廣泛,，如地理信息中的GIS地圖等,，都是利用柵格法制作而成的。柵格地圖法就是將工作環(huán)境分割成一系列具有二值信息的網(wǎng)格單元,。柵格地圖使用2k（k＞1且k屬于整數(shù)）的樹表示存儲,，一般使用四叉樹、八叉樹和十六叉樹,，其中四叉樹使用最為頻繁,。

四叉樹的基本思想就是將柵格地圖等分為四部分，逐塊檢查其網(wǎng)格屬性值,，如果某個(gè)子區(qū)的所有網(wǎng)格值相等,，則該子區(qū)不再分割，否則繼續(xù)把該子區(qū)四分,，直到每個(gè)子快都具有相同的值或者子區(qū)不能再分割,，如圖2（a）所示。

圖3　拓?fù)潢P(guān)系圖

拓?fù)涞貓D法只包含拓?fù)潢P(guān)系信息，但卻沒有節(jié)點(diǎn)之間的權(quán)值信息,，為此,，我們得到改進(jìn)的拓?fù)涞貓D法——混合拓?fù)浜统叨鹊貓D法。

混合拓?fù)浜统叨鹊貓D法不僅包含拓?fù)潢P(guān)系信息,，而且包含節(jié)點(diǎn)之間的權(quán)值信息,，對此能夠更好的表示環(huán)境模型，進(jìn)而制作高效率,、高精度的地圖,。

2.1.4　圖論法

2.1.4.1　圖的定義

歐拉1736年提出圖論的理論，至此,，圖論逐漸發(fā)展成為一個(gè)數(shù)學(xué)的分支學(xué)科,。圖論是以圖作為研究對象，在圖論中,，圖是由若干給定的節(jié)點(diǎn)及節(jié)點(diǎn)之間的連線（連線通常被稱為兩節(jié)點(diǎn)的邊）構(gòu)成,，用以描述事物之間的某種關(guān)系，其中節(jié)點(diǎn)表示各種事物,，連線表示事物之間的關(guān)系,。圖的表示形式：

式中：V表示節(jié)點(diǎn)集合,，E表示節(jié)點(diǎn)連線的集合,，其中E中的每條連線都是V中兩個(gè)節(jié)點(diǎn)的邊［3］。

2.1.4.2　圖的分類

1）按照圖的邊有無方向性分：有向圖和無向圖,，其中無向圖也可稱為雙向有向圖,。對于有向圖而言，節(jié)點(diǎn)的度等于節(jié)點(diǎn)出度減去節(jié)點(diǎn)入度,，節(jié)點(diǎn)出度也就是與此節(jié)點(diǎn)相連的所有出邊的權(quán)值之和,，節(jié)點(diǎn)入度就是與此節(jié)點(diǎn)相連的所有入邊的權(quán)值之和；而對于無向圖而言,，節(jié)點(diǎn)的度等于與此節(jié)點(diǎn)相連的所有邊的權(quán)值之和,。

2）按照圖的邊有無權(quán)值分：有權(quán)圖和無權(quán)圖，其中無權(quán)圖也可稱為權(quán)值均等有權(quán)圖,。

2.1.4.3　圖的常用表示方法

一般圖有兩種常用表示方法：鄰接矩陣和鄰接表［3］,。

1）鄰接矩陣

設(shè)

其中：

則V中有m個(gè)節(jié)點(diǎn)，E中有n個(gè)邊,。

權(quán)值定義：

即在圖G中,，節(jié)點(diǎn)集合V中兩節(jié)點(diǎn)Vi和Vj的連線權(quán)值為，兩節(jié)點(diǎn) Vi和Vj不都在節(jié)點(diǎn)集合V中,，則其連線權(quán)值設(shè)定為,。圖3拓?fù)潢P(guān)系示意圖用鄰接矩陣表示如下：

通過鄰接矩陣，我們可以發(fā)現(xiàn)幾點(diǎn)：對角線都是無窮大；矩陣是對稱矩陣,；圖總共需要m2個(gè)空間,。

2）鄰接表

鄰接表只考慮非零元素，在對圖的信息存儲方面,，它節(jié)約了大量零元素所占的存儲空間,，并且對有向圖和無向圖都可以節(jié)約空間，不像鄰接矩陣只有無向圖才可以節(jié)約空間,。

鄰接表是指圖的順序存儲及鏈?zhǔn)酱鎯ο嘟Y(jié)合的一種存儲方法,。鄰接表的節(jié)點(diǎn)結(jié)構(gòu)表如表1所示：

表1　鄰接表節(jié)點(diǎn)結(jié)構(gòu)表

鄰接表一般有表頭結(jié)點(diǎn)和邊表結(jié)點(diǎn)兩部分組成。表頭結(jié)點(diǎn)利用順序表存儲,，有時(shí)也利用一維數(shù)組存儲,；邊表結(jié)點(diǎn)利用鏈接表存儲。圖3拓?fù)潢P(guān)系示意圖用鄰接表表示,，如表2所示：

表2　鄰接表存儲方式

從表頭結(jié)點(diǎn)中每個(gè)結(jié)點(diǎn)出發(fā),，鏈?zhǔn)竭B線其相連的節(jié)點(diǎn)，例如節(jié)點(diǎn)v1-v2和v1-v3相連,，利用鏈?zhǔn)酱鎯関1-v2-v3,。以此類推，可遍歷表頭結(jié)點(diǎn)中所有節(jié)點(diǎn),。

2.1.4.4　圖的性質(zhì)

1）無向圖的鄰接矩陣對稱且對角線均為無窮大,，而有向圖的鄰接矩陣只是對角線無窮大，而矩陣不一定對稱,。

2）對于無向圖而言,，節(jié)點(diǎn)i的度為鄰接矩陣第i列所有元素之和；對于有向圖而言,，節(jié)點(diǎn)i的度為出度減去入度,，而節(jié)點(diǎn)i的出度為鄰接矩陣第i行所有元素之和，而節(jié)點(diǎn)i的入度為鄰接矩陣第i列所有元素之和,。

3）鄰接矩陣表示的圖需要m2個(gè)空間,，而對于無向圖而言，由于其是對稱矩陣并且對角線均為無窮大,，其只需要個(gè)空間,。所以對于鄰接矩陣來說，一般情況下無窮大比較多,，浪費(fèi)大量空間,。

2.2　路徑搜索算法

在環(huán)境地圖中，搜索一條路徑,，即是搜索一個(gè)節(jié)點(diǎn)序列,。在AGV運(yùn)行過程中，由于我們要求運(yùn)行效率盡可能高效，則是一條路徑,，但不一定是最優(yōu)路徑,，所以我們需要選擇一種路徑搜索策略，搜索出最優(yōu)路徑,。

最優(yōu)路徑搜索指標(biāo)目前主要包括最短時(shí)間,、最短路徑等。由于AGV運(yùn)行速度恒定,，所以本課題選擇最短路徑作為最優(yōu)路徑搜索指標(biāo),。設(shè)公式如下：

式中：是路徑邊的權(quán)值（一般以邊的長度作為權(quán)值）之和。

是路徑中每個(gè)邊的權(quán)值,。

路徑規(guī)劃問題轉(zhuǎn)化為已知初始節(jié)點(diǎn)和終止節(jié)點(diǎn),，求一條路徑使最小問題。

2.2.1　深度優(yōu)先搜索

深度優(yōu)先搜索是指從初始節(jié)點(diǎn)V1開始,，選擇其一個(gè)子節(jié)點(diǎn),，如果該節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則路徑搜索結(jié)束,。如果該節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn),，則該子節(jié)點(diǎn)作為節(jié)點(diǎn)搜索新的起點(diǎn)向下一級子節(jié)點(diǎn)擴(kuò)展。重復(fù)上述搜索過程,。當(dāng)?shù)竭_(dá)某個(gè)子節(jié)點(diǎn),，并且該子節(jié)既不是目標(biāo)節(jié)點(diǎn)也不能繼續(xù)向下擴(kuò)展，則考察其兄弟節(jié)點(diǎn),，直到搜索到目標(biāo)節(jié)點(diǎn)為止,。其搜索過程如圖4（a）所示,。

圖4?。╝） 深度優(yōu)先搜索圖

圖4　（b）廣度優(yōu)先搜索圖

深度優(yōu)先搜索是逐步向下搜索,，如果目標(biāo)節(jié)點(diǎn)剛好在此分支,，則搜索很快結(jié)束；但是如果有許多分支,，或者深度優(yōu)先搜索進(jìn)入一個(gè)深度無窮的分支,，則不能找到目標(biāo)節(jié)點(diǎn)或者搜索時(shí)間很長。所以,，深度優(yōu)先搜索的搜索策略不一定有解,。另外，此方法搜索到的解也不一定是最優(yōu)解,。而AGV路徑規(guī)劃問題必須有解并且是最優(yōu)解或者是次優(yōu)解,。所以，AGV路徑規(guī)劃問題一般不使用深度優(yōu)先搜索的搜索策略，一般只在節(jié)點(diǎn)很少并且環(huán)境簡單的場所偶爾使用,。

2.2.2　廣度優(yōu)先搜索

廣度優(yōu)先搜索是指從初始節(jié)點(diǎn)V1開始,，逐層向其子節(jié)點(diǎn)擴(kuò)展查找目標(biāo)節(jié)點(diǎn)，在前一層的節(jié)點(diǎn)沒有全部擴(kuò)展檢查之前,，不對下一層節(jié)點(diǎn)進(jìn)行擴(kuò)展檢查,。搜索過程如圖4（b）所示。

廣度優(yōu)先搜索是一種盲目的搜索方式,，相當(dāng)于枚舉法,，如果目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)，則搜索量大,，效率低,，但是廣度優(yōu)先搜索總能找到最優(yōu)解。所以,，在AGV路徑規(guī)劃中,，能夠搜索到所有路徑和其權(quán)值，通過比較各路徑權(quán)值,，確定搜索得到最優(yōu)路徑或者次優(yōu)路徑,。

2.2.3　Dijkstra算法

Dijkstra算法是最為典型的全局最短路徑算法，用于搜索計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑,。

Dijkstra算法具有如下性質(zhì)：

若是從節(jié)點(diǎn)到的最短路徑,，則必定是從節(jié)點(diǎn)到的最短路徑。

利用Dijkstra算法性質(zhì)得到計(jì)算公式如下：

式中：——節(jié)點(diǎn)到節(jié)點(diǎn)的最短路徑——行列矩陣

由于是到的最短路徑,，則是到的最短路徑,，所以Dijkstra算法是最短路徑遞增，逐次生成最短路徑的算法,。

Dijkstra算法思想是：設(shè)帶權(quán)值有向圖,，圖中節(jié)點(diǎn)集合可分為和兩部分，其中表示已經(jīng)求出從初始節(jié)點(diǎn)到其他節(jié)點(diǎn)最短路徑的節(jié)點(diǎn)集合,。初始時(shí)集合為空集合,，以后每求得一條最短路徑，就將其路徑節(jié)點(diǎn)加入集合中,，直到全部節(jié)點(diǎn)都加入集合中,，搜索算法結(jié)束。而表示其余未求出從初始節(jié)點(diǎn)到其他節(jié)點(diǎn)最短路徑的節(jié)點(diǎn)集合,，初始時(shí)集合為全集合,，以后按最短路徑的遞增次序依次把集合中的節(jié)點(diǎn)加入集合中。在加入過程中,，必須總保持從初始節(jié)點(diǎn)到集合中各節(jié)點(diǎn)的最短路徑長度不大于從初始節(jié)點(diǎn)到集合中任何節(jié)點(diǎn)的最短路徑長度,。此外,，每個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)距離長度，集合中的節(jié)點(diǎn)的距離就是從初始節(jié)點(diǎn)到此節(jié)點(diǎn)的最短距離長度,，集合中的節(jié)點(diǎn)的距離是從初始節(jié)點(diǎn)經(jīng)過集合中的節(jié)點(diǎn)作為中間點(diǎn)再到此節(jié)點(diǎn)的最短路徑長度［3-4］,。

以圖3拓?fù)潢P(guān)系示意圖為例，以為初始節(jié)點(diǎn),，利用Dijkstra算法求解的最短路徑及其長度,，搜索步驟如表3所示。

表3　Dijkstra算法執(zhí)行步驟表

即的最短路徑及其長度為

9,，Dijkstra算法是逐層向外擴(kuò)展搜索目標(biāo)節(jié)點(diǎn),，其一定能得到最優(yōu)解，但是由于其搜索節(jié)點(diǎn)多,，所以效率低,；同時(shí)，Dijkstra算法適應(yīng)于非負(fù)權(quán)值的有向圖,，如果是無向圖,，則作雙向有向圖處理。

2.2.4　A*算法

A*算法是一種靜態(tài)網(wǎng)絡(luò)中求解最短路徑最有效的直接搜索算法,。

A*算法搜索原理：

式中：——從初始節(jié)點(diǎn)經(jīng)由節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的估價(jià)函數(shù),，——在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，——從n節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià),。在搜索過程中為了保證找到最短路徑,，關(guān)鍵在于估計(jì)函數(shù)的選取。

1）估計(jì)函數(shù)值節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值,，則節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)較遠(yuǎn),，此時(shí)搜索的節(jié)點(diǎn)數(shù)多，搜索范圍大,，那么效率低,，但是一定能搜索得到最短路徑（最優(yōu)解）。

2）估計(jì)函數(shù)值節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值,。則節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)較近,，此時(shí)搜索的節(jié)點(diǎn)數(shù)少,，搜索范圍小,，那么效率高，但是不能保證搜索得到最短路徑（最優(yōu)解）,。

故而估計(jì)函數(shù)值與實(shí)際值越相近,，最短路徑搜索效果越好。一般平面路網(wǎng)地圖中,，取得兩點(diǎn)的直線距離作為估計(jì)函數(shù)值,。通常我們采用兩個(gè)列表,，即，其中存儲待分析節(jié)點(diǎn),，而存儲已分析節(jié)點(diǎn),。

以圖3拓?fù)潢P(guān)系示意圖為例，以為初始節(jié)點(diǎn),，利用A*算法求解的最短路徑及其長度,，搜索步驟如表4所示。

表4　A*算法搜索步驟表

即的最短路徑及其長度為,。

A*算法與廣度優(yōu)先算法,、深度優(yōu)先算法和Dijkstra算法的聯(lián)系在于：當(dāng)時(shí)， A*算法類似深度優(yōu)先搜索（Depth-First-Search縮寫DFS）,，而當(dāng)時(shí),，A*算法類似廣度優(yōu)先搜索算法（Breadth-First-Search縮寫B(tài)FS）；同時(shí),，時(shí)只需要求出,，即可求出初始節(jié)點(diǎn)到任意節(jié)點(diǎn)的最短路徑，則變?yōu)閱卧醋疃搪窂絾栴},，即Dijkstra算法,。

此外，經(jīng)常應(yīng)用的算法還有Bellman-ford算法,、Floyd-Warshall算法,、Johnson算法、D*算法等,。

本課題的AGV路徑規(guī)劃應(yīng)用于固定線路之間的原料運(yùn)輸,，環(huán)境簡單，節(jié)點(diǎn)少,。所以,，本課題采用Dijkstra搜索算法。

3　試驗(yàn)結(jié)果

為了驗(yàn)證本課題搜索算法的正確性,，假設(shè)多邊形為障礙物,，邊框?yàn)檫吔纾阎跏脊?jié)點(diǎn)和終止節(jié)點(diǎn),。

3.1　環(huán)境地圖建模

采用拓?fù)浞ǖ墓?jié)點(diǎn)設(shè)置原則,，具體步驟如下：

1）各個(gè)障礙物多邊形外側(cè)頂點(diǎn)對環(huán)境邊界作垂線，取垂線中點(diǎn)為節(jié)點(diǎn),；

2）各個(gè)障礙物多邊形內(nèi)側(cè)頂點(diǎn)就近相互連線,，取連線中點(diǎn)為節(jié)點(diǎn)。

節(jié)點(diǎn)之間就近相互連接,，構(gòu)成環(huán)境地圖,。以上節(jié)點(diǎn)為AGV的路徑規(guī)劃節(jié)點(diǎn),，測量節(jié)點(diǎn)之間距離并儲存，以便路徑規(guī)劃搜索利用［2,，5］,，如圖5所示。

圖5　環(huán)境地圖

表5　節(jié)點(diǎn)之間距離

3.2　采用Dijkstra搜索算法

已知初始節(jié)點(diǎn),、終止節(jié)點(diǎn),、路徑節(jié)點(diǎn)位置及其之間的距離，利用Dijkstra搜索算法,，搜索初始節(jié)點(diǎn)經(jīng)過路徑節(jié)點(diǎn)到達(dá)終止節(jié)點(diǎn)的最優(yōu)路徑,，也就是最短路徑。

假設(shè)開始節(jié)點(diǎn)v1=（2,，2）,，終止節(jié)點(diǎn)vn=（13.5，5）,，利用Dijkstra路徑算法搜索,。

圖6　路徑搜索圖

由試驗(yàn)結(jié)果可知，的最短路徑是：

v1→v2→v3→v4→v5→v18→v19→v20→v17→v16→v1 5→v14→v13→v12→v11→vn,。

分析結(jié)果如表6所示,。

表6　路徑分析表

表6　路徑分析表 （續(xù)）

此試驗(yàn)結(jié)果與分析結(jié)果一致，所以算法正確可用,。通過試驗(yàn)表明,，在上述構(gòu)建的地圖環(huán)境中，通過Dijkstra搜索路徑算法,，雖然路徑搜索時(shí)間長,，效率低，但是能夠搜索得到一條最優(yōu)路徑,。

參考文獻(xiàn)

［1］馬志遠(yuǎn).智能控制下的AGV路徑規(guī)劃研究［J］.河南科技,，2013（19）：98-98.

［2］齊東流，肖本賢.基于智能控制的AGV路徑規(guī)劃研究［D］.合肥：合肥工業(yè)大學(xué)電氣與自動化工程學(xué)院,，2006.

［3］孫奇,，孟濬，顏文俊.AGV系統(tǒng)路徑規(guī)劃技術(shù)研究［D］.杭州：浙江大學(xué)電氣工程學(xué)院,，2012.

［4］賀麗娜,，樓佩煌.AGV系統(tǒng)運(yùn)行路徑優(yōu)化技術(shù)研究［D］.南京：南京航空航天大學(xué)機(jī)電學(xué)院，2011.

［5］李青欣,，蔡延光.混合智能算法在AGV全局路徑規(guī)劃中的應(yīng)用研究［J］.電腦開發(fā)與應(yīng)用,，2011，24（7）：55-56.

本課題是新疆維吾爾自治區(qū)自然科學(xué)基金項(xiàng)目,，項(xiàng)目編號：2014211B44,。

路徑規(guī)劃是AGV導(dǎo)航的基本環(huán)節(jié)之一，其主要研究使在具有障礙物的環(huán)境地圖化,，同時(shí)一般選擇最短路徑作為最優(yōu)路徑的指標(biāo),，并利用算法搜索最優(yōu)路徑。本文以一種實(shí)用型火工品運(yùn)輸自動導(dǎo)引車為研究對象,，主要闡述其路徑規(guī)劃研究,。