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

曾祥蘋(píng)

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

1 AGV發(fā)展歷程

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

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

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

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

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

3.1 時(shí)間窗算法概述

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

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

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

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

3.2 時(shí)間窗計(jì)算方法

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

3.3 沖突解決方法

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

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

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

4 結(jié)語(yǔ)

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