基于路段時間窗考慮備選路徑的AGV路徑規劃研究

曾祥蘋

(廣州南洋理工職業學院，廣州 510925)

1 AGV發展歷程

AGV全稱為自動導引小車，指的是能夠按照設置好的導引路徑，安裝有光學或電磁扥自動導引裝置的小車編程和選擇停車功能的裝置，它具有多樣化的移載方式，安裝有安全保護裝置，能夠實現多種操作任務[1]。AGVs指的是自動導引車系統，主要構成系統為數據傳遞子系統、管理計算機系統、若干自動導引小車及地面子系統等，可以實現AGV分派移載的指定任務，起到實時監測效果。

AGV技術從叉車技術延伸發展而來，還有一種AGV技術是來源于機器人研發技術。兩類AGV技術主要的研發目的是完成對貨物路徑的自動搬運。從導航技術發展來看，包括電磁導航、光學導航、激光導航及無路徑視覺導航等。從控制系統發展來看，主要是從速度閉環控制系統發展到現在的位置閉環控制系統。從控制系統構成體系來看，主要是從專用封閉結構發展到目前的開放式結構[2]。從驅動技術來看，則是從直流電機驅動發展到直流無刷電機驅動，再到交流伺服電機驅動。從能源發展經歷來看，主要是從鉛酸電池發展到可以快速充電的鎳鉻電池能源，已經逐漸放棄需要充電的感應式供電方式[3]。從發展經歷來看，相比于傳統運輸工具，AGV應用范圍更廣、更可靠、更智能，還具有監控系統。

2 AGV技術的組成和分類

AGV主要由轉向系統、驅動系統、能源儲存裝置、車體、控制系統、通信系統、導引系統、安全系統構成。AGV自動導引車分為有軌道型自動導引車、無軌道型自動導引車。根據用途分類，可分為自動叉車、裝配性自動導引車、搬運型自動導引車以及自動拖車等。根據行駛方式分類，可分為履帶式和輪式兩種類型的自動導引車。根據驅動方式可分為差速驅動、單輪驅動、全向輪驅動。根據導引方式分類，可分為激光導引、電磁導引、慣性導引、視覺導引、GPS導引以及聲波導引等。根據搬運機構來分，則可以分為側叉式、牽引式、后叉式。根據是否有導引路徑來分類，包括自有路徑自動導引車和固定路徑的自動導引車。根據自動化水平分類，可分為AGV全自動化導引車和AGV-AGC簡易自動導引車[4]。

3 基于路徑時間窗算法的AGVS路徑規劃

3.1 時間窗算法概述

系統交通狀況的檢測是最早應用時間窗算法的，AGV在雙向和有向圖中搜索無沖突最優路徑，而時間窗算法能夠有效預測和預防小車失去控制而引發沖突。

假設目前系統中有n臺數量的小車，R={r1，r2，r3…rn}，AGVs分配了m臺數量的小車去執行任務，M={m1，m2，m3…mn}，對于每一個任務，都有相應的路徑來相對應。每條路徑都是從的Oi-Di(起始位置到終點位置)之間的弧段路徑。諸多路徑的集合也可以被稱為有序弧段集合，即Oi={ej，ek…eq}，其中ei…eq都屬于自然數，也就是環境中集合的路段，而每個任務都有相應的優先級Pi。

每個任務、起點/終點位置、分配任務都和時間變化無關，小車路徑如果沒有發生沖突，也不隨之產生關系。但是如果在任務執行中，沖突只有通過路徑改變才能解決，則可以將路徑改為動態化的。每個小車在第一次任務分配中會有一個相對應的優先級，如果任務執行時間延長，則對應的優先級也會逐步變高。

當AGV小車在沿著有序路徑上執行任務時，在駛入和駕駛出的時間段內，小車一直會在該路徑上行駛，不準行駛第二輛小車。駛入時間和駛出時間段則被稱為是路徑時間窗。被小車所占用的時間屬于保留時間窗，路徑上沒有小車占用，則被稱為自由時間窗。自由時間窗意味著可以分配任務給這個小車到這個路徑上，且不會產生小車碰撞的沖突。假設小車路徑被分配為n，則需要觀測小車行駛速度和轉彎速度，計算出小車駛入和駛出所要花費的時間窗。

3.2 時間窗計算方法

任務需要按照其對應的優先級來進行排序，根據優先級的調度來設置任務的調度。最高優先級需要選擇一個尚未被分配任務的小車，用Dijkstra的時間窗算法對其完成該任務所用的最短路徑進行計算，計算出駛入時間和駛出時間，并對各個階段上存在的時間窗向量表進行初始化。其次是次優級的任務，要先檢查控線小車數量，如果暫時沒有，則需要進入暫時的等待狀態，然后再進行路徑規劃。同樣用Dijkstra的時間窗算法來對小車駛入時間和駛出時間及性能計算，對各個路段上的時間窗向量表進行初始化。要檢查每個時間窗中是否會發生沖突。如果不發生沖突，則路徑規劃工作完成。如果有沖突發生的可能性，則需要將第一個沖突的時間窗做一個不可用的標記，然后再進行最短路徑的規劃計算，直到不會發生沖突[5]。如果不能計算出最短路徑，則需要對該任務的調度進行暫停，繼續其他任務的執行。最后是對最次優級的任務進行分配小車和規劃路徑的計算。如果在路徑規劃以后也對時間窗向量表進行了更新，同樣需要檢查是否會發生沖突。通過這樣循環往復的計算，就可以設置出多個任務并行但是無沖突發生的最短AGV自動小車路徑。

3.3 沖突解決方法

等待策略。對于路徑沖突的解決，等待策略的應用是比較有效的。比如：在路口發生沖突，根據人物優先級決定讓哪輛車先停下來讓路，具體的計算則是對來兩輛小車，如i和j之間的距離dij的計算。計算公式為，d比設定值小的話，則需要判斷交叉路口兩輛車之間的距離。如果其中一輛小車與路口之間的距離大于另一輛小車，則需要暫停先讓距離近的小車通過。如果兩輛車與交叉路口之間的距離是相等或者差距很小的時候，則需要按照任務優先級來決定哪輛車先過，哪輛車后過。而后過的那輛車在沒有小車發生沖突的時候，則可以繼續運行[6]。

另一種沖突是趕超沖突，后車需要暫時的等待。如果發生了相向沖突，即兩輛車都要面對同一段公共交叉路段，也可以用等待策略，如果是多個公共交叉路段，則不能用等待策略來解決。

重新規劃路徑策略。這個策略比較適用于當兩輛小車都處于對方下一段路徑的沖突情況的解決。可以先標記沖突路段不可用，然后再重新根據路徑搜索算法探尋到其他可用的路徑，對時間窗向量表進行初始化，循環往復，直到可用路徑規劃成功為止。

4 結語

時間窗算法比較容易操作，檢查沖突也更為準確，對于環境變化有較快的反應能力，但是一旦小車數量增多，就會造成系統運算增加，路徑優化工作也將會變得遲鈍或者失效。