AGVS路徑規劃的可行性問題研究

祝俊皓

摘 要：AGV作為計算機集成制造系統內物流運輸的主要工具，因其自身在柔性、控制集成等方面的優勢，使其應用范圍逐步得以拓寬。在一般情況下來說，AGV都是由在線的柔性微機所控制的，并借助自身內部的電池驅動和埋設在地板槽內部大感應導線所組成的導引回路系統，做到以任意的編程速度進行運動。由此不難看出，AGV的效率將會直接影響到整個計算機集成制造物流系統的效率，但目前有關AGV路徑規劃可行性研究較少，而本文正是針對這一點展開了研究。

關鍵詞：AGV路徑 規劃可行性 研究

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 空間窗概念

時間窗的概念，簡單來說，就是構成某個特定動作的時間集合，而在這個過程中，還涉及到了保留時間窗的概念，其實就是停在某一個緩沖區內部的時間間隔。而AGV從一個緩沖區嚴格遵循指定路徑達到另一個緩沖區的這一段持續時間集合就是自由時間窗。空間的可行性就是指兩個結點之內存在的實際物理通路，而所謂的時間可行性就是在下一個即將開始的時間窗內，AGV能夠做到按時進入并離開，借助對空間和時間的可行性做出全面的檢查，便可及時發現AGV內潛藏的碰撞。

1.2 柔性可行性概念

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

2 判斷AGVS突發柔性可行的方式及實例分析

2.1 判斷AGVS突發柔性可行性的具體依據

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

2.2 判斷的具體方法

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

typedef struct{

int agvnumber

int starttime

int finishtime

}timeinterval

timeinterval T[PathNum][AGVNum]

對于那些承擔著突發性運輸任務的AGV#t而言，需要將之占據每一段通道的開始以及結束時刻轉變為整數單位之后傳達到上位機中，而上位機在接收到這些數據之后，則會嚴格按照的數據時間的順序將AGV即將要占據的i通道的開始以及結束時刻數據存放到結構體數組對應第i行中T[i][t].starttime、T[i][t].finishtime，在此之后，則是需要數組內的第i行元素以T[i][t].finishtime作為基礎做到非減序的數據排列。接下來，就是針對這些承擔著突發運輸任務的AGV#t設定的行進路線執行相應的可行性判斷，如若判斷出無法行進，則是在全新規劃路徑之后進行二次判斷，一直到任務完成為止。

2.3 判斷方法帶有最優解的證明

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

2.4 實際應用案例分析

圖1展示了D廠內部的生產系統內部的平面布置拓撲圖，因為該廠的生產任務今年有所改變，其中的AGVB#3的路徑順序需要變為1-2-3-4-5。

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

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

3 結語

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

參考文獻：

[1]趙東雄.多自動導引小車系統（AGVS）路徑規劃研究[D].湖北工業大學，2014.

[2]朱傳敏，黃冰冰，楊鵬.基于時效優先的AGVS協調路徑規劃方法[J].制造業自動化，2013，35（06）： 76-77.

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