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

曾祥蘋

(廣州南洋理工職業(yè)學(xué)院，廣州 510925)

1 AGV發(fā)展歷程

AGV全稱為自動導(dǎo)引小車，指的是能夠按照設(shè)置好的導(dǎo)引路徑，安裝有光學(xué)或電磁扥自動導(dǎo)引裝置的小車編程和選擇停車功能的裝置，它具有多樣化的移載方式，安裝有安全保護(hù)裝置，能夠?qū)崿F(xiàn)多種操作任務(wù)[1]。AGVs指的是自動導(dǎo)引車系統(tǒng)，主要構(gòu)成系統(tǒng)為數(shù)據(jù)傳遞子系統(tǒng)、管理計算機(jī)系統(tǒng)、若干自動導(dǎo)引小車及地面子系統(tǒng)等，可以實現(xiàn)AGV分派移載的指定任務(wù)，起到實時監(jiān)測效果。

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

2 AGV技術(shù)的組成和分類

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

3 基于路徑時間窗算法的AGVS路徑規(guī)劃

3.1 時間窗算法概述

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

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

每個任務(wù)、起點/終點位置、分配任務(wù)都和時間變化無關(guān)，小車路徑如果沒有發(fā)生沖突，也不隨之產(chǎn)生關(guān)系。但是如果在任務(wù)執(zhí)行中，沖突只有通過路徑改變才能解決，則可以將路徑改為動態(tài)化的。每個小車在第一次任務(wù)分配中會有一個相對應(yīng)的優(yōu)先級，如果任務(wù)執(zhí)行時間延長，則對應(yīng)的優(yōu)先級也會逐步變高。

當(dāng)AGV小車在沿著有序路徑上執(zhí)行任務(wù)時，在駛?cè)牒婉{駛出的時間段內(nèi)，小車一直會在該路徑上行駛，不準(zhǔn)行駛第二輛小車。駛?cè)霑r間和駛出時間段則被稱為是路徑時間窗。被小車所占用的時間屬于保留時間窗，路徑上沒有小車占用，則被稱為自由時間窗。自由時間窗意味著可以分配任務(wù)給這個小車到這個路徑上，且不會產(chǎn)生小車碰撞的沖突。假設(shè)小車路徑被分配為n，則需要觀測小車行駛速度和轉(zhuǎn)彎速度，計算出小車駛?cè)牒婉偝鏊ㄙM的時間窗。

3.2 時間窗計算方法

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

3.3 沖突解決方法

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

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

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

4 結(jié)語

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