AGVS路徑規(guī)劃的可行性問題研究

祝俊皓

摘 要：AGV作為計(jì)算機(jī)集成制造系統(tǒng)內(nèi)物流運(yùn)輸?shù)闹饕ぞ撸蚱渥陨碓谌嵝浴⒖刂萍傻确矫娴膬?yōu)勢，使其應(yīng)用范圍逐步得以拓寬。在一般情況下來說，AGV都是由在線的柔性微機(jī)所控制的，并借助自身內(nèi)部的電池驅(qū)動和埋設(shè)在地板槽內(nèi)部大感應(yīng)導(dǎo)線所組成的導(dǎo)引回路系統(tǒng)，做到以任意的編程速度進(jìn)行運(yùn)動。由此不難看出，AGV的效率將會直接影響到整個計(jì)算機(jī)集成制造物流系統(tǒng)的效率，但目前有關(guān)AGV路徑規(guī)劃可行性研究較少，而本文正是針對這一點(diǎn)展開了研究。

關(guān)鍵詞：AGV路徑 規(guī)劃可行性 研究

Research on the Feasibility of AGVS Path Planning

Zhu Junhao

Abstract：AGV， as the main tool of logistics transportation within the computer integrated manufacturing system， has gradually expanded its application scope due to its own advantages in flexibility and control integration. In general， the AGV is controlled by an online flexible microcomputer， and is driven by its own internal battery and a guidance loop system composed of large induction wires buried in the floor slot， so that it can be programmed at any speed movement. It is not difficult to see from this that the efficiency of AGV will directly affect the efficiency of the entire computer integrated manufacturing logistics system， but there are few feasibility studies on AGV path planning at present， and this article is aimed at this point.

Key words：AGV path， planning feasibility， research

1 研究中基本概念分析

1.1 空間窗概念

時(shí)間窗的概念，簡單來說，就是構(gòu)成某個特定動作的時(shí)間集合，而在這個過程中，還涉及到了保留時(shí)間窗的概念，其實(shí)就是停在某一個緩沖區(qū)內(nèi)部的時(shí)間間隔。而AGV從一個緩沖區(qū)嚴(yán)格遵循指定路徑達(dá)到另一個緩沖區(qū)的這一段持續(xù)時(shí)間集合就是自由時(shí)間窗。空間的可行性就是指兩個結(jié)點(diǎn)之內(nèi)存在的實(shí)際物理通路，而所謂的時(shí)間可行性就是在下一個即將開始的時(shí)間窗內(nèi)，AGV能夠做到按時(shí)進(jìn)入并離開，借助對空間和時(shí)間的可行性做出全面的檢查，便可及時(shí)發(fā)現(xiàn)AGV內(nèi)潛藏的碰撞。

1.2 柔性可行性概念

這里提到的柔性可行性概念，實(shí)際上就是AGVS在處于突發(fā)情況的時(shí)候，對于某一輛AGV做出突發(fā)情況路徑規(guī)劃再調(diào)度的一種重新執(zhí)行能力。

2 判斷AGVS突發(fā)柔性可行的方式及實(shí)例分析

2.1 判斷AGVS突發(fā)柔性可行性的具體依據(jù)

假設(shè)存在n個的AGV活動集合E={1，2，……n}，其中每一個活動集合的每一個活動都會被要求通過完全相同的下一段通道，并且該段活動通道的開始及結(jié)束時(shí)刻都被每一個活動所使用了，分別用s[i]以及f[i]來表示開始和結(jié)束時(shí)刻，并且開始時(shí)刻的數(shù)值是要小于結(jié)束時(shí)刻的。，在上位機(jī)選擇了活動i的情況下，那么AGV#i則是會在[si，fi）時(shí)間段內(nèi)占據(jù)并使用這段通道，在[si，fi）以及[sj，fj）完全不相交的情況下，也就意味著AGV#i能夠?qū)崿F(xiàn)在通過通道的目標(biāo)。隨后針對AGV#i原定計(jì)劃中想要占用每一段通道做出相應(yīng)的判斷工作，在全部判斷完全通過的前提下，也就意味著AGV#i的原定計(jì)劃是非常成功的，一旦出現(xiàn)了有一段通道無法通過的問題，則上位機(jī)就需要重新規(guī)劃一下路徑。

2.2 判斷的具體方法

在選定判斷方法的時(shí)候需要定義如下的結(jié)構(gòu)體：第一，代表通道數(shù)目的#define PathNum 10。第二，代表著車輛數(shù)值的#define AGVNum 5。第三，代筆啊AGV編號的int agvnumber。第四，代表著AGV占用通道開始時(shí)刻的int starttime以及代表AGV占用通道的結(jié)束時(shí)刻int finishtime。第五，代表AGV是否能夠占據(jù)該通道的int tag。此后，需要構(gòu)建如下的二維數(shù)組

typedef struct{

int agvnumber

int starttime

int finishtime

}timeinterval

timeinterval T[PathNum][AGVNum]

對于那些承擔(dān)著突發(fā)性運(yùn)輸任務(wù)的AGV#t而言，需要將之占據(jù)每一段通道的開始以及結(jié)束時(shí)刻轉(zhuǎn)變?yōu)檎麛?shù)單位之后傳達(dá)到上位機(jī)中，而上位機(jī)在接收到這些數(shù)據(jù)之后，則會嚴(yán)格按照的數(shù)據(jù)時(shí)間的順序?qū)GV即將要占據(jù)的i通道的開始以及結(jié)束時(shí)刻數(shù)據(jù)存放到結(jié)構(gòu)體數(shù)組對應(yīng)第i行中T[i][t].starttime、T[i][t].finishtime，在此之后，則是需要數(shù)組內(nèi)的第i行元素以T[i][t].finishtime作為基礎(chǔ)做到非減序的數(shù)據(jù)排列。接下來，就是針對這些承擔(dān)著突發(fā)運(yùn)輸任務(wù)的AGV#t設(shè)定的行進(jìn)路線執(zhí)行相應(yīng)的可行性判斷，如若判斷出無法行進(jìn)，則是在全新規(guī)劃路徑之后進(jìn)行二次判斷，一直到任務(wù)完成為止。

2.3 判斷方法帶有最優(yōu)解的證明

從實(shí)際應(yīng)用上來看，之前設(shè)定的E={1，2，……n}集合就是所給出的通道i的一個活動集合，再加之集合中的活動是以結(jié)束時(shí)刻為基礎(chǔ)的非減序數(shù)據(jù)排列方式，這也就是意味著活動1的完成時(shí)間將會是最早的。隨后在s[i]以及f[i]兩個數(shù)組中將活動i的開始和結(jié)束時(shí)刻分別放入其中，并且后一個數(shù)組中的數(shù)據(jù)元素同樣做到非減序排列。在這種情況下，需要證明的第一個問題就是這個問題本身帶有一個將貪心選擇作為開始點(diǎn)的最優(yōu)化解，換言之，這個最優(yōu)解里需要完全包含活動1的數(shù)據(jù)。假設(shè)AE是給出的活動安排的最優(yōu)解，同時(shí)A中包含的活動執(zhí)行的也是以結(jié)束時(shí)間為基礎(chǔ)的非減序數(shù)據(jù)排列方式，k為A中的第一個活動，在k=1的情形下，則A就是將貪心選擇作為出發(fā)點(diǎn)的最優(yōu)解。即便是在k>1的情形下，假設(shè)B=A-{k}∪{1}，因?yàn)閒[1]始終是小于等于f[k]的，再加之A中的活動帶有相容的特性，則B也是如此。又因?yàn)锳本身是最優(yōu)解，則B也是最優(yōu)解，簡單一些來說，B就是在貪心選擇活動1的情形下的誕生出的最優(yōu)化活動安排。由此不難發(fā)現(xiàn)的一點(diǎn)是，以貪心選擇作為出發(fā)點(diǎn)的最優(yōu)化活動安排方案一直都是存在的。

2.4 實(shí)際應(yīng)用案例分析

圖1展示了D廠內(nèi)部的生產(chǎn)系統(tǒng)內(nèi)部的平面布置拓?fù)鋱D，因?yàn)樵搹S的生產(chǎn)任務(wù)今年有所改變，其中的AGVB#3的路徑順序需要變?yōu)?-2-3-4-5。

上文中提到的可行性判斷方法針對AGV#3的行進(jìn)路線做出相應(yīng)的判斷，在經(jīng)歷判斷、修改、再判斷的多次反復(fù)之后，知道任務(wù)全部完成為止。在具體的行進(jìn)路徑中，AGV#3同樣要向上位機(jī)發(fā)送占有每一段通道的開始和結(jié)束時(shí)刻的整數(shù)數(shù)值，隨后交由上位機(jī)針對每一段通道的實(shí)際占用情形做出相應(yīng)的排列工作。在本次研究中，就以圖中2號通道作為實(shí)例，對具體判斷的實(shí)現(xiàn)進(jìn)行解釋說明，表1中展示了向上位機(jī)發(fā)出占用2號通道AGV任務(wù)。而表2則是展示了經(jīng)由上位機(jī)重新排列之后的非減序排列結(jié)果。

從表2中的數(shù)據(jù)不難發(fā)現(xiàn)，在通道2上的AGV#3行進(jìn)是完全可行的，只要在接下來的AGV#3占據(jù)的其他通道里仍舊使用這一方式逐一進(jìn)行判斷，如若全部通道的判斷結(jié)果都是可行，那么原定的AGV#3行進(jìn)路線則是完全成立的，反之則是需要做出二次的規(guī)劃和判斷，一直到任務(wù)全部完成為止。除此之外，表2中的數(shù)據(jù)還體現(xiàn)出，AGV#3和AGV#5在同一個時(shí)刻會因?yàn)樯a(chǎn)任務(wù)的調(diào)整而針對原本的生產(chǎn)路線進(jìn)行生產(chǎn)，在這個時(shí)間段內(nèi)想要占據(jù)通道2是無法做出有效安排的，解決方案只有等待或者是重新規(guī)劃。通過這一實(shí)例不難發(fā)現(xiàn)，這種判斷方式在取得良好效果的同時(shí)，也能夠保障整個系統(tǒng)最大化柔性。

3 結(jié)語

對于計(jì)算機(jī)集成制造系統(tǒng)而言，想要提高其效率的最為有效的方式就是提高AGVS的效率。本文所提出的AGVS路徑規(guī)劃可行性判斷方式，可以在取得良好效果的同時(shí)，確保整個系統(tǒng)的最大化柔性，在豐富有關(guān)AGVS柔性理論研究的同時(shí)，也可為今后的生產(chǎn)環(huán)節(jié)提供一定的借鑒。

參考文獻(xiàn)：

[1]趙東雄.多自動導(dǎo)引小車系統(tǒng)（AGVS）路徑規(guī)劃研究[D].湖北工業(yè)大學(xué)，2014.

[2]朱傳敏，黃冰冰，楊鵬.基于時(shí)效優(yōu)先的AGVS協(xié)調(diào)路徑規(guī)劃方法[J].制造業(yè)自動化，2013，35（06）： 76-77.

[3]徐翠霞.AGVS路徑規(guī)劃可行性判斷的研究[J].微計(jì)算機(jī)信息，2007（28）：100-102.