唐巧玲 彭全 張燎

摘??要：隨著我國(guó)工業(yè)技術(shù)的高速發(fā)展，多自動(dòng)運(yùn)輸車（Automated?Guided?Vehicle，AGV）在自主性和節(jié)約成本方面受到越來越多的重視?；诙郃GV在復(fù)雜多變的車間環(huán)境中的路徑規(guī)劃問題，提出了改進(jìn)的A*算法（A-star?Algorithm）和DWA算法（Dynamic?Window?Approach）融合的智能優(yōu)化算法。首先，利用A*算法規(guī)劃出從起點(diǎn)到終點(diǎn)的全局路徑，然后針對(duì)A*算法多冗余的缺點(diǎn)，提出了一種提取關(guān)鍵點(diǎn)的方法，剔除掉全局路徑中的冗余節(jié)點(diǎn)和多余拐點(diǎn)，保證了對(duì)全局路徑的改進(jìn)。其次，通過對(duì)全局路徑的分段，設(shè)置一系列的局部目標(biāo)點(diǎn)，利用DWA動(dòng)態(tài)窗口法對(duì)新增和移動(dòng)的障礙物進(jìn)行動(dòng)態(tài)避障的同時(shí)不斷地到達(dá)局部目標(biāo)點(diǎn)，得到了多AGV從起點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑，最終實(shí)現(xiàn)了對(duì)多AGV關(guān)于路徑長(zhǎng)度和安全性方面的改進(jìn)。

關(guān)鍵詞：A*算法??DWA算法??算法融合??路徑規(guī)劃

中圖分類號(hào)：?TP18

Research?on?the?Intelligent?Optimization?of?the??Pathway?of?Multiple?AGVs?in?the?Inter-Vehicle?Environment

TANG?Qiaoling??PENG?Quan??ZHANG?Liao

Neijiang?Normal?University，?Neijian，?Sichuan?Province，?641100?China

Abstract：?With?the?rapid?development?of?industrial?technology?in?China，?the?automated?guided?vehicle?（AGV）?is?receiving?increasing?attention?in?terms?of?autonomy?and?cost?saving.?This?article?proposes?an?intelligent?optimization?algorithm?that?integrates?the?improved?A*?algorithm?（A-star?algorithm）?and?DWA?（dynamic?window?approach）?for?the?path?planning?problem?of?multiple?AGVs?in?the?complex?and?variable?inter-vehicle?environment.?Firstly，?this?article?uses?the?A*?algorithm?to?plan?the?global?path?from?the?starting?point?to?the?endpoint，?and?then，?for?the?shortcoming?of?the?multiple?redundancy?of?the?A*?algorithm，?proposes?a?method?for?extracting?key?points?to?eliminate?the?redundant?nodes?and?inflection?points?of?the?global?path，?which?ensures?the?improvement?of?the?global?path.?Secondly，?by?segmenting?the?global?path，?it?sets?a?series?of?local?target?points，?and?uses?the?DWA?to?dynamically?avoid?newly-added?and?moving?obstacles?while?continuously?reaching?the?local?target?points，?so?as?to?obtain?the?optimal?path?for?multiple?AGVs?from?the?starting?point?to?the?target?point，?and?ultimately?achieve?the?improvement?of?the?path?length?and?safety?of?multiple?AGVs.

Key?Words：?A-star?algorithm;?Dynamic?window?approach;?Algorithm?fusion;?Path?planning

AGV（Automated?Guided?Vehicle）作為自動(dòng)運(yùn)輸小車，擁有自動(dòng)尋址系統(tǒng)，使其能通過進(jìn)行非接觸提前路線規(guī)劃。按照預(yù)先規(guī)劃好的路徑獨(dú)自運(yùn)動(dòng)或牽引貨物從起始點(diǎn)一直行駛到目標(biāo)地點(diǎn)，完成貨物的自動(dòng)運(yùn)輸服務(wù)。本文提出了一種基于改進(jìn)的A*算法和DWA算法的融合算法，通過對(duì)A*算法的優(yōu)化和改進(jìn)，彌補(bǔ)了A*算法平滑性不高的缺陷，再融合了DWA算法，實(shí)現(xiàn)了車間環(huán)境中多AGV對(duì)新增和移動(dòng)的障礙物動(dòng)態(tài)避障路徑規(guī)劃。

1??多AGV路徑規(guī)劃融合算法

在車間環(huán)境中，多AGV最優(yōu)路徑規(guī)劃問題，就是在其工作環(huán)境中對(duì)周圍環(huán)境模型進(jìn)行搜索，依據(jù)某種測(cè)評(píng)找到一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑，并且此路徑能動(dòng)態(tài)避開環(huán)境中的障礙物[1-2]。但常用的路徑規(guī)劃算法只考慮單個(gè)小車對(duì)于障礙物的避碰，沒有考慮車輛之間的碰撞，都是靜態(tài)規(guī)劃，不能根據(jù)實(shí)時(shí)情況進(jìn)行路徑動(dòng)態(tài)變化，此外現(xiàn)有的路徑規(guī)劃方法只適應(yīng)于AGV可以在各個(gè)方向自由行走的情況，不適用于復(fù)雜的車間環(huán)境。

本文提出的改進(jìn)的A*算法和DWA融合算法，充分利用了兩種算法的優(yōu)勢(shì)，實(shí)現(xiàn)了路徑平滑度和安全性的改進(jìn)[3]。首先利用改進(jìn)的A*算法規(guī)劃全局靜態(tài)路徑，然后在全局路徑中設(shè)置多個(gè)局部目標(biāo)點(diǎn)，再利用DWA算法進(jìn)行局部動(dòng)態(tài)路徑規(guī)劃，使其在最優(yōu)全局路徑的基礎(chǔ)上可以實(shí)現(xiàn)動(dòng)態(tài)地避讓小車和障礙物。

1.1??改進(jìn)A*全局靜態(tài)路徑規(guī)劃

在車間環(huán)境中，對(duì)于傳統(tǒng)A*算法所規(guī)劃路徑存在較多冗余節(jié)點(diǎn)的缺點(diǎn)，提出了一種關(guān)鍵節(jié)點(diǎn)提取法，保留路徑必經(jīng)的關(guān)鍵折點(diǎn)，使改進(jìn)后的路徑長(zhǎng)度更短、折點(diǎn)更少[4]。具體步驟如下。

（1）用面積法提取轉(zhuǎn)折點(diǎn)，依次計(jì)算路徑中相鄰三點(diǎn)（p-1、p、p+1）圍成的面積，如果面積不為0，則p為轉(zhuǎn)折點(diǎn)，否則p不是轉(zhuǎn)折點(diǎn)。p的初始點(diǎn)為距起點(diǎn)最近的路徑節(jié)點(diǎn)，直到p為距目標(biāo)點(diǎn)最近的路徑節(jié)點(diǎn)，轉(zhuǎn)折點(diǎn)提取結(jié)束，將起點(diǎn)和目標(biāo)點(diǎn)也視為轉(zhuǎn)折點(diǎn)。

（2）進(jìn)行關(guān)鍵點(diǎn)篩選，在相鄰轉(zhuǎn)折點(diǎn)（q-1、q、q+1）中，連接不相鄰的兩點(diǎn)（q-1、q+1），如果連線經(jīng)過障礙物區(qū)域，則轉(zhuǎn)折點(diǎn)q為關(guān)鍵點(diǎn)，否則為冗余點(diǎn)。q初始點(diǎn)為距起點(diǎn)最近的轉(zhuǎn)折點(diǎn)，直到q為距目標(biāo)點(diǎn)最近的轉(zhuǎn)折點(diǎn)時(shí)，關(guān)鍵點(diǎn)篩選結(jié)束。

1.2??DWA局部動(dòng)態(tài)路徑規(guī)劃

DWA算法是通過運(yùn)動(dòng)模型和采樣的運(yùn)動(dòng)信息推算出小車可能的多種運(yùn)動(dòng)軌跡，然后通過評(píng)價(jià)函數(shù)選取最優(yōu)的規(guī)劃路徑。本文將改進(jìn)的A*算法中提取的關(guān)鍵點(diǎn)設(shè)置為局部路徑的局部目標(biāo)點(diǎn)，使其一一到達(dá)并最終抵達(dá)終點(diǎn)，從而得到一條改進(jìn)的路徑。當(dāng)多輛AGV將會(huì)碰撞時(shí)，DWA算法會(huì)依次設(shè)定AGV的優(yōu)先級(jí)，讓優(yōu)先級(jí)高的AGV先通行。為使DWA算法所規(guī)劃的局部路徑更接近全局路徑，在預(yù)測(cè)軌跡評(píng)價(jià)函數(shù)中加入A*算法的代價(jià)值函數(shù)為全局路徑評(píng)價(jià)子函數(shù)[5]，則融合算法的評(píng)價(jià)函數(shù)為：

（1）

式（1）中，heading（v，w）是方位角評(píng)價(jià)函數(shù)，指小車航向與目標(biāo)之間的角度差；dist（v，w）是小車與最近障礙物之間的距離；velocity（v，w）是軌跡對(duì)應(yīng)的速度大小。P為t時(shí)刻通過v和w預(yù)測(cè)的移動(dòng)機(jī)器人位置坐標(biāo)；g（P）表示預(yù)測(cè)位置到起點(diǎn)的距離；h（P）表示預(yù)測(cè)位置到局部目標(biāo)點(diǎn)的距離；為全局路徑評(píng)價(jià)函數(shù)子函數(shù)權(quán)重（取值小于α和γ，大于β）。H（v，w）值越小，得分越高。

2??算法測(cè)試結(jié)果及分析

本文采用MATLAB平臺(tái)，使用改進(jìn)的A*算法和DWA算法的融合算法對(duì)存在靜態(tài)以及動(dòng)態(tài)障礙物的車間環(huán)境進(jìn)行多AGV路徑規(guī)劃仿真，實(shí)現(xiàn)了智能車間環(huán)境中多AGV動(dòng)態(tài)避障路徑規(guī)劃。

2.1??改進(jìn)的A*全局路徑規(guī)劃

本文采用柵格化的環(huán)境模型，模擬了3輛AGV的起點(diǎn)和終點(diǎn)以及動(dòng)態(tài)的障礙物的起點(diǎn)和終點(diǎn)。設(shè)AGV1的起點(diǎn)是（19，26），終點(diǎn)是（9，23）；AGV2的起點(diǎn)是（5，8），終點(diǎn)是（11，16）；AGV3的起點(diǎn)是（17，17），終點(diǎn)是（12，27）。然后根據(jù)改進(jìn)的A*算法進(jìn)行全局路徑規(guī)劃，可以得到3條路徑，改進(jìn)的A*算法路徑規(guī)劃結(jié)果如圖2所示。

根據(jù)改進(jìn)的A*全局路徑規(guī)劃圖可知，AGV1和AGV2的路徑發(fā)生了交叉，因此AGV1和AGV2在運(yùn)行過程中可能會(huì)發(fā)生碰撞，此時(shí)就需要運(yùn)用DWA算法進(jìn)行動(dòng)態(tài)避障，使AGV1和AGV2在相遇時(shí)根據(jù)優(yōu)先級(jí)，使最優(yōu)先的AGV先行，次優(yōu)先AGV避讓，以此來達(dá)到多AGV避碰的目的。

2.2??DWA局部路徑優(yōu)化

DWA局部路徑優(yōu)化是將全局路徑分成多個(gè)局部路徑，設(shè)置多個(gè)局部目標(biāo)點(diǎn)，避讓其余AGV和運(yùn)動(dòng)的障礙物，從而到達(dá)各個(gè)局部目標(biāo)點(diǎn)，并最終各自到達(dá)目的地。

根據(jù)本文模擬環(huán)境，AGV1和AGV2在路徑規(guī)劃中相遇，AGV3為了躲避向右的移動(dòng)障礙物，偏向右邊規(guī)劃。然后根據(jù)DWA算法設(shè)置的優(yōu)先級(jí)AGV1大于AGV2，AGV2停下避讓AGV1。如圖3所示，經(jīng)過DWA算法局部規(guī)劃路徑后，分別得到了3條優(yōu)化的路徑[5]。

由圖3所示優(yōu)化后的路徑可知，多AGV的路徑規(guī)劃融合算法可以在動(dòng)態(tài)的車間環(huán)境中避讓小車和障礙物，能夠?qū)崿F(xiàn)多AGV在復(fù)雜的車間環(huán)境下的路徑智能優(yōu)化。

3??結(jié)語(yǔ)

本文針對(duì)智能車間環(huán)境中使用傳統(tǒng)路徑規(guī)劃算法對(duì)多AGV路徑規(guī)劃造成的平滑性和靈活性不足、安全性不高等問題，提出了改進(jìn)的A*算法和DWA算法融合的路徑智能優(yōu)化算法，融合了兩種算法的優(yōu)勢(shì)，并通過MATLAB平臺(tái)，模擬了車間中存在的復(fù)雜環(huán)境，進(jìn)行了多AGV動(dòng)態(tài)避障路徑規(guī)劃的仿真，實(shí)現(xiàn)了多AGV在復(fù)雜車間情況下的無碰路徑規(guī)劃。但在A*算法進(jìn)行全局規(guī)劃時(shí)，有出現(xiàn)重復(fù)點(diǎn)的可能性，因此DWA算法進(jìn)行局部規(guī)劃追蹤時(shí)，會(huì)出現(xiàn)重復(fù)識(shí)別，造成錯(cuò)誤，未來將針對(duì)重復(fù)點(diǎn)問題進(jìn)一步研究。

參考文獻(xiàn)

• 岑云飛.面向智能工廠的多AGV調(diào)度系統(tǒng)開發(fā)[D].西安：西安理工大學(xué)，2023.
• 熊焰，劉金庫(kù).多移動(dòng)機(jī)器人路徑無障礙智能規(guī)劃算法仿真[J].計(jì)算機(jī)仿真，2023，40（4）：434-438.
• 陳嬌，徐菱，陳佳，等.改進(jìn)A*和動(dòng)態(tài)窗口法的移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)集成制造系統(tǒng)，2022，28（6）：1650-1658.
• 于洋，杜學(xué)歷，馮迎賓.融合A*算法和動(dòng)態(tài)窗口法的全局動(dòng)態(tài)路徑規(guī)劃方法[J].沈陽(yáng)理工大學(xué)學(xué)報(bào)，2020，39（5）：1-7.
• 王彬，聶建軍，李海洋，等.優(yōu)化A*與動(dòng)態(tài)窗口法的移動(dòng)機(jī)器人路徑規(guī)劃[J/OL].計(jì)算機(jī)集成制造系統(tǒng)：1-17[2023-12-06].http：//kns.cnki.net/kcms/detail/11.5946.TP.20220305.1932.024.html.