自動(dòng)導(dǎo)引車路徑規(guī)劃

1、2021-11-251自動(dòng)導(dǎo)引車路徑規(guī)劃自動(dòng)導(dǎo)引車路徑規(guī)劃作者： 崔晨群班級(jí)： 工物121學(xué)號(hào)：2012102220132021-11-252一、自動(dòng)導(dǎo)引車一、自動(dòng)導(dǎo)引車(Automated Guided Vehicle，簡稱，簡稱 AGV）路徑規(guī)劃問題的提出）路徑規(guī)劃問題的提出 AGV的效率對(duì)倉儲(chǔ)系統(tǒng)的運(yùn)作效率有重要的影響，而AGV系統(tǒng)的效率很大程度上取決于對(duì)路徑的導(dǎo)引，即AGV運(yùn)送路徑的優(yōu)劣嚴(yán)重影響AGV的效率，間接制約著倉儲(chǔ)系統(tǒng)的自動(dòng)化程度及企業(yè)的生產(chǎn)效率。 對(duì)于單AGV而言，路徑規(guī)劃相對(duì)比較簡單，即從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的最短路徑。 對(duì)于多AGV自動(dòng)化倉儲(chǔ)系統(tǒng)路徑規(guī)劃，要考慮到避免系統(tǒng)的沖突

2、、碰撞，這就不得不涉及到路徑規(guī)劃。 因此研究自動(dòng)化倉儲(chǔ)系統(tǒng)AGV路徑規(guī)劃問題就變得十分必要。 2021-11-253二、固定路徑導(dǎo)引二、固定路徑導(dǎo)引AGV路徑規(guī)劃路徑規(guī)劃1.單AGV路徑規(guī)劃1）局部路徑規(guī)劃 局部路徑規(guī)劃要解決的是根據(jù)具體環(huán)境模型找出一條連接兩個(gè)不同目 標(biāo)點(diǎn)最佳路徑。利用Floyd算法能較好地解決AGV局部路徑規(guī)劃。2）全局路徑規(guī)劃 全局路徑規(guī)劃負(fù)責(zé)根據(jù)局部路徑規(guī)劃的結(jié)果，為當(dāng)前任務(wù)中所需運(yùn)送 的所有物品安排一個(gè)最優(yōu)運(yùn)送次序，即一條最佳的全局路徑。AGV的全 局路徑規(guī)劃可以轉(zhuǎn)化為TSP問題，然后用模擬退火算法（SA算法）通過 模擬固體退火過程，采用Metropolis接受準(zhǔn)則，

3、可以在多項(xiàng)式時(shí)間取得 問題的近似解。2021-11-254二、固定路徑導(dǎo)引二、固定路徑導(dǎo)引AGV路徑規(guī)劃路徑規(guī)劃2.多AGV路徑規(guī)劃 單臺(tái)AGV不能從整體上提高自動(dòng)化倉儲(chǔ)效率的要求，因此多AGV路徑 規(guī)劃問題成為研究的熱點(diǎn)。多AGV的應(yīng)用首先要解決的是避碰問題， 即在完成任務(wù)的前提下，避免與其他正在工作的AGV發(fā)生碰撞問題。 1）而引起碰撞的主要原因有： （1）線路交叉； （2）多個(gè)AGV的線路沖突； （3）AGV本身出現(xiàn)故障；（4）運(yùn)輸線路超負(fù)荷運(yùn)行。 2）多AGV的碰撞類型有如圖四種，根據(jù)碰撞類型提出兩種主要解決方案： （1）延時(shí)等待：主要解決b、c碰撞類型。 （2）局部調(diào)整路徑：主要解決

4、第一類碰撞類型。2021-11-255二、固定路徑導(dǎo)引二、固定路徑導(dǎo)引AGV路徑規(guī)劃路徑規(guī)劃3）多AGV路徑規(guī)劃所用方法： 基于CPN的AGV控制系統(tǒng)建模與求解方法： ：AGV等待任務(wù) :AGV向目標(biāo)工位移動(dòng) : AGV處于沖突檢測中 ：AGV處于沖突中 :AGV處于執(zhí)行解決沖突方案的狀態(tài) ：新任務(wù) ：檢測沖突 ：無沖突 ：發(fā)現(xiàn)沖突 ：解決沖突 ：執(zhí)行解決方案 ：任務(wù)結(jié)束 CPN較好的描述了AGVS系統(tǒng)地運(yùn)行情況，為解決多AGV路徑規(guī)劃問題提供很好的分析工具和理論指導(dǎo)，有效地解決了多AGV小車路徑規(guī)劃問題。1P2P3P4P5P1t2t3t4t5t6t7t2021-11-256三、自由路徑導(dǎo)引三

5、、自由路徑導(dǎo)引AGV路徑規(guī)劃路徑規(guī)劃 在固定路徑環(huán)境中，AGV只能完成一些簡單的任務(wù)。隨著作業(yè)任務(wù)的復(fù)雜化，要求AGV能實(shí)現(xiàn)自由路徑行走方式。下面將應(yīng)用一種新的方法模擬退火-人工勢場法，并介紹基于該方法的路徑規(guī)劃系統(tǒng)的設(shè)計(jì)。 人工勢場法的基本思想是構(gòu)造目標(biāo)位姿引力場和周圍障礙物斥力場共同作用的人工勢場，搜索勢函數(shù)的下降方向來尋找無碰路徑。人工勢場法最主要的弊端是在到達(dá)目標(biāo)位置前陷入局部最小點(diǎn)而無法達(dá)到目標(biāo)位置。通過將模擬退火算法和人工勢場法結(jié)合，利用模擬退火算法求解全局極小點(diǎn)。模擬退火-人公勢場法的流程如右圖2021-11-257三、自由路徑導(dǎo)引三、自由路徑導(dǎo)引AGV路徑規(guī)劃路徑規(guī)劃 用Vis

6、ual C+6.0為工具開發(fā)了基于SA-APE的AGV路徑規(guī)劃原型系統(tǒng)，該系統(tǒng)實(shí)現(xiàn)了單AGV無碰撞路徑的自動(dòng)生成，下圖為復(fù)雜環(huán)境下，算法生成無碰撞路徑的仿真實(shí)例。2021-11-258四、四、AGV路徑規(guī)劃實(shí)例路徑規(guī)劃實(shí)例Dijkstra最短路徑確定法。下圖中的節(jié)點(diǎn)15是AGV運(yùn)行路線上的岔口，618是貨物裝卸點(diǎn)裝卸點(diǎn)，6是系統(tǒng)的入口入口，9、15、16是系統(tǒng)的出口出口，19是AGV停車處。在圖(b)中，將AGV可能的運(yùn)行方向用箭頭進(jìn)行了表示。2021-11-259四、四、AGV路徑規(guī)劃實(shí)例路徑規(guī)劃實(shí)例 (1) 因?yàn)楣?jié)點(diǎn)15是找出618貨物裝卸點(diǎn)間最短距離的關(guān)鍵點(diǎn)，故先只考慮系統(tǒng)中的先只考慮系

7、統(tǒng)中的各岔口即節(jié)點(diǎn)各岔口即節(jié)點(diǎn)l5間的最短路徑。間的最短路徑。為此，將相應(yīng)箭頭所表示的距離填人下面的距離矩陣。因節(jié)點(diǎn)1、 3之間無直接連接的箭頭，但兩者之間可通過16、18連在一起，所以C1,3=C1,16+C16,18+Cl8,3=84。C3,4=表示所連兩點(diǎn)間無直接聯(lián)系，之間的聯(lián)系要通過岔口表示所連兩點(diǎn)間無直接聯(lián)系，之間的聯(lián)系要通過岔口節(jié)點(diǎn)。節(jié)點(diǎn)。由此得到系統(tǒng)的距離矩陣(表7-2)。 距離矩陣 2021-11-2510(2)搜索過程搜索過程I.最短路徑法首先要求找到搜索的起始點(diǎn)最短路徑法首先要求找到搜索的起始點(diǎn)i，起始點(diǎn)起始點(diǎn)i必須是通過一個(gè)單必須是通過一個(gè)單箭頭就能和其余節(jié)點(diǎn)相連最多的節(jié)

8、點(diǎn)。很顯然，圖箭頭就能和其余節(jié)點(diǎn)相連最多的節(jié)點(diǎn)。很顯然，圖7-24(b)中的節(jié)點(diǎn)中的節(jié)點(diǎn)1符符合這個(gè)要求，將此節(jié)點(diǎn)作為第一層。合這個(gè)要求，將此節(jié)點(diǎn)作為第一層。II.在找出由該在找出由該i點(diǎn)出發(fā)的最短距離點(diǎn)出發(fā)的最短距離Ci，k后，后，令di，k=Ci，k再以k節(jié)點(diǎn)作為第2次搜索的起點(diǎn)。III.根據(jù)距離矩陣中與根據(jù)距離矩陣中與k節(jié)點(diǎn)對(duì)應(yīng)的行，計(jì)算由起始點(diǎn)出發(fā)，經(jīng)此節(jié)點(diǎn)對(duì)應(yīng)的行，計(jì)算由起始點(diǎn)出發(fā)，經(jīng)此k點(diǎn)到點(diǎn)到其余節(jié)點(diǎn)的最短距離，若到節(jié)點(diǎn)其余節(jié)點(diǎn)的最短距離，若到節(jié)點(diǎn)j的距離最短，則計(jì)算的距離最短，則計(jì)算di，k+Ck，j IV.若di，k+Ck，jCi，j 再取i j路徑的j點(diǎn)作為第3次搜索的起點(diǎn)。 重復(fù)上面搜索過程（將重復(fù)上面搜索過程（將j替換k）V.若