基于遺傳算法的平面車庫車輛路徑規(guī)劃

摘要:隨著物流系統(tǒng)自動化、智能化水平的提高，AGV在物流系統(tǒng)的應(yīng)用越來越普遍。AGV的導(dǎo)航是AGV的核心技術(shù)，而路徑規(guī)劃是AGV導(dǎo)航的重要環(huán)節(jié)之一。本文應(yīng)用遺傳算法求解單個AGV的路徑規(guī)劃問題，最后給出該算法實現(xiàn)的路徑規(guī)劃仿真和實驗結(jié)果，實驗結(jié)果證實了該方法的有效性。

關(guān)鍵詞:遺傳算法路徑規(guī)劃AGV

中圖分類號:TP3文獻(xiàn)標(biāo)識碼:A文章編號:1672-3791(2011)02(b)-0030-02

自動導(dǎo)航車(Automated Guided Vehicles，AGV)又名無人搬運車，出現(xiàn)于20世紀(jì)50年代，是一種自動化的無人駕駛的智能化搬運設(shè)備，屬于移動式機(jī)器人系統(tǒng)，能夠沿預(yù)先設(shè)定的路徑行駛，是現(xiàn)代工業(yè)自動化物流系統(tǒng)如計算機(jī)集成制造系統(tǒng)(CIMS)中的關(guān)鍵設(shè)備之一[1]。它具有靈活性、智能性、對惡劣環(huán)境的強(qiáng)適應(yīng)性等特點，可以實現(xiàn)運輸?shù)淖詣踊⒅悄芑⑷嵝曰ｋS著物流系統(tǒng)自動化、智能化水平的提高，AGV在物流系統(tǒng)的應(yīng)用越來越普遍[2]。

AGV的導(dǎo)航控制是AGV的核心技術(shù)，而路徑規(guī)劃是AGV導(dǎo)航的重要環(huán)節(jié)之一。AGV的路徑規(guī)劃是按照某一性能指標(biāo)搜索一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或近似最優(yōu)的無碰路徑[3]。根據(jù)對環(huán)境信息知道程度的不同，可分為環(huán)境信息完全知道的全局路徑規(guī)劃和環(huán)境信息完全未知或部分未知的局部路徑規(guī)劃及混合路徑規(guī)劃[4]。

傳統(tǒng)的解決路徑規(guī)劃問題的方法有可視圖法、自由空間法、人工勢場法等[5，6]。隨著智能方法的發(fā)展，許多研究者把目光放在了基于智能方法的路徑規(guī)劃研究上。遺傳算法是智能方法的一種，它具其不要求適應(yīng)度函數(shù)是可導(dǎo)或連續(xù)的、并行性、對問題的依賴程度小、在解空間進(jìn)行高效啟發(fā)式搜索等優(yōu)點。本文以路徑長短作為評判路徑好壞的指標(biāo)，利用遺傳算法對靜態(tài)已知環(huán)境下的全局路徑規(guī)劃進(jìn)行研究。

1問題描述

在物流系統(tǒng)中應(yīng)用AGV完成搬運任務(wù)，任務(wù)中規(guī)定了AGV的起始點S，和目標(biāo)點E，要求提前規(guī)劃一條可行的無碰撞的路徑，且該條路徑的總長度盡量短。該路徑由起點、終點以及4個中間點Ai(0

本文就是在已知當(dāng)前的物流系統(tǒng)布局情況和AGV小車的起始點和目標(biāo)點坐標(biāo)的條件下，求解中間點的坐標(biāo)，使得路徑盡量最短。

假設(shè)物流系統(tǒng)為一個平面?zhèn)}庫，它的形狀為長為18，寬為18的矩形，倉庫的當(dāng)前布局中，存在三個矩形障礙物，需要移動的物體起始位置為(0，0)，終止位置為(16，16)。

本文以路徑長短作為評判路徑好壞的指標(biāo)，故性能指標(biāo)函數(shù)為:

L=

(1)

基本的約束條件為:

(2)

2環(huán)境建模

路徑規(guī)劃分為兩個步驟，第一步是環(huán)境建模，第二步是求解路徑。環(huán)境建模是求解路徑的基礎(chǔ)，合理的環(huán)境表示有利于建立規(guī)劃方法和選擇合適的搜索算法，最終實現(xiàn)較少的時間和內(nèi)存開銷而規(guī)劃出較為滿意的路徑。在當(dāng)前的研究中，環(huán)境建模的方法有很多種，如頂點法、柵格法、廣義錐法、鏈路可視圖法。

本文考慮二維空間，采用的是直角坐標(biāo)系對物流系統(tǒng)當(dāng)前布局進(jìn)行建模，以平面?zhèn)}庫的一個頂點為起始點，用(x，y)坐標(biāo)對AGV在平面?zhèn)}庫中的位置進(jìn)行定位，同時把要移動的AGV等同與一個質(zhì)點。

3基于遺傳算法的AGV路徑規(guī)劃

3.1 算法流程

遺傳算法是一種基于自然選擇和基因遺傳學(xué)原理的優(yōu)化搜索方法，使得我們可以在計算機(jī)上模擬生物的進(jìn)化過程和基因的操作。它一般包括初始種群的產(chǎn)生，交叉，變異等過程。本文的算法流程如圖1所示。

3.2 初始種群的產(chǎn)生

本文采用典型的二進(jìn)制編碼方式，這樣的編碼方式直接簡潔。每個染色體是由4個中間點連接而成的，其所表示的是一條可行或者不可行的路徑。染色體的結(jié)構(gòu)可表示為:(x1，y1)→(x2，y2)→……→(x4，y4)。其中，染色體的長度是固定的，每個中間節(jié)點由兩個坐標(biāo)，每個坐標(biāo)用一個4位二進(jìn)制串表示，則染色體的長度為32。通過隨機(jī)函數(shù)產(chǎn)生初始化種群。

3.3 適應(yīng)度函數(shù)的確定

路徑規(guī)劃，就是要規(guī)劃出一條最短的可行路徑，約束條件是路徑不與障礙物碰撞。對路徑優(yōu)劣程度的評估就作為遺傳算法中染色體的適應(yīng)值。本文考慮簡單的一種情況。只用路徑的長短來判斷路徑的優(yōu)劣程度。所以，求適應(yīng)度函數(shù)就是求線路的長度。另外還需判斷可行路徑和不可行路徑，不可行路徑就是與障礙物的輪廓線有交點的路徑。則適應(yīng)度函數(shù):Fitness=

;

顯然，適應(yīng)度越小越好。

3.4 遺傳算子的確定

選擇算子，采用輪盤賭選擇法，由上可知，適應(yīng)度越小被選擇的概率越大。從種群中選出父體，個體的數(shù)量保持不變。

交叉算子，交叉是以一定的概率，在父染色體中隨機(jī)選擇一個除起始點與目標(biāo)點以外的轉(zhuǎn)向點，這個轉(zhuǎn)向點就作為交叉點，把整個路徑分成了兩個路徑段。然后選擇兩個父代染色體，相互交換交叉點后面的路徑段，這樣就產(chǎn)生了兩個子代染色體。在不同父代中選擇不同的交叉點，可以增加染色體長度的差異性，并且有利于擴(kuò)大解空間的范圍和最優(yōu)解的產(chǎn)生。

變異算子，變異是以一定的概率，除去起始點和目標(biāo)點，在路徑的中間轉(zhuǎn)向點中任意選取一個位置，將該轉(zhuǎn)向點的位置坐標(biāo)作一次非一致性變異，然后把當(dāng)前的轉(zhuǎn)向點移至新產(chǎn)生的轉(zhuǎn)向點上，經(jīng)過變異之后就產(chǎn)生了一條新的路徑。

然后，把新的路徑當(dāng)作新的種群進(jìn)行下一步的遺傳操作，依次循環(huán)往復(fù)。

4仿真和實驗結(jié)果

本文設(shè)計并實現(xiàn)了仿真實驗，實驗的環(huán)境是visual studio2005軟件開發(fā)平臺，用c#語言編寫，為一個窗體程序。如圖2所示，輸入AGV的其實位置坐標(biāo)和終止位置坐標(biāo)，點擊“計算線路”按鈕，系統(tǒng)開始計算，用紅線畫出每次迭代過程中計算得出的可行路徑，并用綠線表示最終計算的最優(yōu)路徑。

初始參數(shù)的設(shè)置為:種群的代數(shù):500，種群大小:500，交叉概率:0.9，變異概率:0.2。起點坐標(biāo)為(0，0)，終點坐標(biāo)為(16，16)運行以上代碼，得出結(jié)果如Fig.3(b)所示。中間點坐標(biāo)中間點的坐標(biāo)(1，2)，(2，5)，(5，7)，(7，6)，最優(yōu)路徑長度為24.69。

5結(jié)語

綜合分析，本文采用遺傳算法解決了物流系統(tǒng)中單個AGV的路徑規(guī)劃問題。隨機(jī)的產(chǎn)生初始種群，在遺傳算法的過程中考慮了選擇算子，交叉算子和變異算子。仿真實驗也證實了該方法的有效性。合理的路徑規(guī)劃不但能夠提高AGV的作業(yè)效率，縮短單個作業(yè)的完成時間，同時也能減少能耗，從而提升整個物流系統(tǒng)的運作效率，減少物流運作成本。

參考文獻(xiàn)

[1] 馬幼捷，張海濤，邵保福，等.電子智能化立體車庫的研究現(xiàn)狀與走向[J].電氣自動化，2008(5):3～6.

[2] 張辰貝西，黃志球.自動導(dǎo)航車發(fā)展綜述[J].中國制造業(yè)信息化，2010(1):53～59.

[3] 范九榮，應(yīng)浩，曾素娣.混合遺傳算法的AGV路徑規(guī)劃的應(yīng)用[J].科技信息，2006(8):266～267.

[4] 王菁華，崔世鋼，羅云林.基于Matlab的智能機(jī)器人路徑規(guī)劃仿真[C].2008系統(tǒng)仿真技術(shù)及應(yīng)用學(xué)術(shù)會議論文集，2008:298～301.

[5]L.Guibas，J.Hershberger.Computing the visibility graph of n line segments in O(n2) time[J].Theoret Comput Sc.，1985，26:13～20.

[6] Y.K.Hwang，N.Ahuja.A Potential field approach to path planning[J].IEEE Trans.Robot Autom，1992，8(1):23～32.