国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

蟻群融合動態(tài)窗口法的分布式多機器人運動規(guī)劃研究

2024-02-26 01:41楊立煒李俊麗
關(guān)鍵詞:移動機器人障礙物機器人

王 倩,楊立煒,李俊麗,楊 振

(昆明理工大學 信息工程與自動化學院, 昆明 650504)

0 引 言

分布式多移動機器人系統(tǒng)可完成更復雜的任務,成為了目前的前沿研究熱點[1]。運動規(guī)劃作為其中的關(guān)鍵性技術(shù),在具有先驗信息的靜態(tài)環(huán)境下為機器人規(guī)劃安全行駛路徑,在充滿未知復雜的動態(tài)環(huán)境下機器人遵循全局路徑的引導進行局部避障運動。

幾十年來,眾多專家學者提出了大量的路徑規(guī)劃算法,如A*算法[2]、蟻群算法、粒子群算法[3]、遺傳算法[4]等,這些優(yōu)化算法被廣泛應用于車間調(diào)度[5]、多目標優(yōu)化[6]、機器人路徑規(guī)劃[7]等方面。蟻群算法[8]具有正反饋、較好的適應性以及優(yōu)化能力強等優(yōu)點,但也存在前期搜索盲目性、搜索效率低、易陷入局部最優(yōu)等問題。文獻[9]受A*算法啟發(fā),采用該算法作為蟻群的啟發(fā)信息以提高搜索效率,并加入彎曲抑制算子提高了路徑平滑度。文獻[10]引入最優(yōu)最差螞蟻系統(tǒng),對全局信息素進行差別更新,加快了算法的收斂速度。文獻[11]在轉(zhuǎn)移概率中加入避障因子提高螞蟻算法搜索能力,大大減少了復雜環(huán)境下螞蟻個體的致死數(shù)量。上述改進都側(cè)重于實現(xiàn)全局路徑的最優(yōu),缺乏考慮局部未知環(huán)境下機器人的實時運動。動態(tài)窗口法(dynamic window algorithm,DWA)是一種實時避障算法,文獻[12]提出了一種基于Q學習的改進DWA,修正了原有評價函數(shù)的不合理機制,擴展了兩個新評價函數(shù),使得機器人在復雜環(huán)境下?lián)碛休^好的導航運動效果。由于航向和速度評價函數(shù)之間的矛盾可能會導致機器人頻繁換向、避障不及時等問題,文獻[13]為此在DWA的路徑評價函數(shù)中引入方向變化評價因子,抑制某些特定因素對評價函數(shù)的過度影響,減少機器人不必要的轉(zhuǎn)向。

以上算法[9-13]在不同程度上解決了單移動機器人而未考慮多個機器人場景下的路徑規(guī)劃問題。文獻[14]針對多移動機器人,以神經(jīng)網(wǎng)絡和滾動窗口法為基礎(chǔ),提出了一種未知環(huán)境下的混合路徑規(guī)劃算法,引入了動量梯度下降法與路徑點檢測機制,加快了算法的搜索效率。文獻[15]采用分層路徑規(guī)劃來解決多移動機器人的運動問題,使用貝茲曲線融合遺傳算法規(guī)劃出單機器人的最優(yōu)路徑,區(qū)分多機器人的沖突類型,確定其碰撞區(qū)域從而選擇合適的策略消除沖突。文獻[16]受到多目標粒子群優(yōu)化的啟發(fā),提出了一種多機器人路徑規(guī)劃新方法,其以路徑短、安全性高和平滑性優(yōu)為目標,尋找從起點到終點的最優(yōu)路徑,引入概率窗口的理念,結(jié)合機器人傳感器獲得的實時信息和先驗信息,選擇適應度更高的路徑。

針對多移動機器人在運動過程中的避障和安全性協(xié)調(diào)問題,本文引入A*算法、轉(zhuǎn)彎代價和轉(zhuǎn)彎抑制因子改進啟發(fā)式函數(shù)以增加路徑平滑度;引入路徑綜合信息素更新概念,結(jié)合路徑特性對信息素揮發(fā)系數(shù)進行調(diào)整提高全局路徑綜合性能以避免局部最優(yōu);考慮到機器人的運動特性,利用冗余點刪除策略進行后期優(yōu)化;基于DWA進行局部路徑規(guī)劃,提出機器人自適應導航方法提高全局路徑的追蹤精度。最后,本文將融合蟻群與DWA的單機器人運動導航策略運用于分布式多機器人系統(tǒng),通過優(yōu)先級策略協(xié)調(diào)多機器人系統(tǒng)存在的各種沖突。

1 蟻群算法

1.1 傳統(tǒng)蟻群算法原理

蟻群算法是一種經(jīng)典的啟發(fā)式算法。人工螞蟻依據(jù)路徑信息從八鄰域范圍內(nèi)選擇合適的節(jié)點,迭代出一條最優(yōu)的可行路徑。在t次迭代中,螞蟻k由節(jié)點i向節(jié)點j轉(zhuǎn)移的概率為

(1)

(2)

當所有螞蟻完成一次迭代以后,路徑上的信息素根據(jù)(3)—(4)式進行更新。

τij(t+1)=(1-ρ)τij(t)+Δτij(t,t+1)

(3)

(4)

(3)—(4)式中:ρ是信息素揮發(fā)系數(shù);Δτij(t,t+1)是螞蟻尋路中的信息素增量;Q是初始信息素強度;L表示螞蟻通過當前迭代的總路徑長度。

1.2 改進蟻群算法

1.2.1 優(yōu)化啟發(fā)函數(shù)

傳統(tǒng)啟發(fā)式函數(shù)只考慮了當前節(jié)點到下一節(jié)點之間的歐氏距離,使得螞蟻在搜索節(jié)點時更傾向于選擇與當前節(jié)點距離較近的節(jié)點,路徑的最優(yōu)性得不到保證。為了提高蟻群搜索過程的啟發(fā)效果和算法的收斂速度,本文在啟發(fā)函數(shù)中引入A*算法思想,可表示為

f(n)=h(n)+g(n)

(5)

(6)

(7)

(5)—(7)式中:f(n)、g(n)和h(n)為代價函數(shù);(xs,ys)為起始點;(xn,yn)為當前節(jié)點;(xg,yg)為目標點。本文將A*算法的實際代價函數(shù)g(n)和估計代價函數(shù)h(n)作為蟻群搜索路徑的啟發(fā)式信息,并添加轉(zhuǎn)彎代價因子和轉(zhuǎn)角抑制因子,以減少路徑累積轉(zhuǎn)向角度和轉(zhuǎn)彎次數(shù)。改進的啟發(fā)式函數(shù)可表示為

(8)

(9)

(10)

(8)—(10)式中,A、B、C為大于1的常數(shù);Cbend為轉(zhuǎn)彎代價;Rthita表示上一節(jié)點n-1、當前節(jié)點n和待選節(jié)點n+1之間的角度(弧度);Eturn為轉(zhuǎn)角抑制因子,用于強化螞蟻在路徑搜索過程中沿著相同方向運動的趨勢,以此減少冗余轉(zhuǎn)折點的生成;t(J)表示螞蟻從當前柵格向待選柵格的轉(zhuǎn)向標號;t(J-1)表示螞蟻從上一柵格到當前柵格的轉(zhuǎn)向標號。

1.2.2 改進信息素更新規(guī)則

將螞蟻的搜索行為集中到最優(yōu)解的附近可以提高解的質(zhì)量和收斂速度,但會導致算法“早熟”。為了充分利用當前最優(yōu)解,本文每次迭代只對最優(yōu)螞蟻路徑進行信息素更新。此外,本文綜合考慮了路徑的長度、轉(zhuǎn)彎次數(shù)和轉(zhuǎn)彎角度,改進信息素更新規(guī)則并將綜合評分最高的最優(yōu)解進行定義,表示為

(11)

(12)

(13)

(11)—(13)式中:F為當前綜合評價下的路徑指標;Q1為大于1 的常數(shù);L為最優(yōu)路徑長度;T表示最優(yōu)路徑的轉(zhuǎn)彎數(shù);C表示最優(yōu)路徑的轉(zhuǎn)彎角度總和(弧度);K1、K2、K3為權(quán)重系數(shù)。

1.2.3 冗余點刪除策略

經(jīng)過上述改進所得到的最優(yōu)路徑上依舊存在少量的冗余拐點。為此,本文進一步優(yōu)化路徑。

步驟1消除同一直線上的冗余點,具體刪除策略如圖1所示。原始路徑包含節(jié)點P1→P2→P3→P4→P5,消除同一直線上的冗余點,直到生成僅包含起點、終點和轉(zhuǎn)折點P1→P2→P3→P4的路徑Mid_Route。

圖1 步驟1冗余點刪除策略Fig.1 Redundancy point deletion strategy step 1

步驟2消除整條路徑上的冗余點,具體刪除策略如圖2所示。優(yōu)先連接起點P1與終點P4,線段[P1,P4]的直線距離dis[P1,P4]滿足dis[P1,P4]

圖2 步驟2冗余點刪除策略Fig.2 Redundancy point deletion strategy step 2

2 動態(tài)窗口法

DWA通過對多組速度進行采樣分析來預測機器人在一段時間內(nèi)的運動軌跡,然后根據(jù)評價函數(shù)選出最優(yōu)速度組驅(qū)動機器人運動。

2.1 動態(tài)窗口法原理

2.1.1 機器人運動模型

DWA對窗口內(nèi)機器人的線速度與角速度進行采樣,假設(shè)機器人的軌跡可以分解成多個時間片,則在每個時間片Δt內(nèi),機器人的運動學模型可表示為

(14)

(14)式中:x(t)、y(t)、θ(t)分別表示機器人在t時刻x、y方向上的位置和運動方向角;v(t)和ω(t)分別表示線速度和角速度。

2.1.2 機器人速度約束

在移動機器人速度組空間中,DWA將機器人的避障描述為具有約束的優(yōu)化問題,包括對微分機器人的不完全運動約束,對機器人結(jié)構(gòu)的動力學約束和環(huán)境約束。

1)機器人受自身條件制約的最大最小速度約束。機器人速度約束范圍可表示為

Vs={(v,ω)|v∈[vmin,vmax],ω∈[ωmin,ωmax]}

(15)

2)電機加減速約束。機器人受電機影響,存在加減速度約束。在動態(tài)窗口顯示內(nèi),受到加減速影響的最大和最小速度范圍為

(16)

3)制動距離約束。整個機器人軌跡可以細分為若干個直線或圓弧運動,為保證機器人的安全,在最大減速條件下機器人應在撞到障礙物之前減速至0。機器人速度必須滿足的條件為

(17)

(17)式中,dist(v,ω)表示此速度下該軌跡與障礙物之間的最短距離。速度只有滿足(17)式的條件,才能保證機器人運動的安全。

上述約束將機器人限制在一定的速度范圍內(nèi),可將其表示為速度集

Vr=Vs∩Vd∩Va

(18)

2.1.3 評價函數(shù)

經(jīng)過速度組(v,ω)采樣后,DWA會生成若干條預測軌跡,然后根據(jù)評價函數(shù)進行軌跡評分,篩選出得分最佳的軌跡,機器人在此速度組的驅(qū)動下實現(xiàn)(14)式所示的運動。評價函數(shù)可以表示為

G(v,ω)=σ(a·heading(v,ω)+b·dist(v,ω)+c·velocity(v,ω))

(19)

(19)式中:σ表示歸一化操作;G(v,ω)為模擬軌跡評價值,使其值最大的(v,ω)即為最優(yōu)速度;heading(v,ω)為機器人導航函數(shù),機器人運動方向與目標方向偏航越小,其值越大;dist(v,ω)為機器人與障礙物的最近距離,其值越大,發(fā)生碰撞的危險就越小;velocity(v,ω)用于評估機器人運動性能,速度越大,得分越高;a、b、c為對應評價函數(shù)的權(quán)重因子。

2.2 自適應追蹤局部目標點

目前很多文獻[17-20]基于全局路徑規(guī)劃算法融合DWA進行研究,將全局路徑的拐點作為機器人運動的局部目標點。然而在具有未知障礙物的環(huán)境中,該方式存在不合理性。例如,在一段沒有轉(zhuǎn)折點的路徑上往往存在大量未知靜態(tài)障礙物,機器人存在的避障困難以及對路徑跟蹤精度的不夠會導致其丟失導航方向。因此,本文提出了自適應追蹤局部目標點的方法,表示為

Old_path(i-1),nds]

(20)

local_target(t+1)=

(21)

(20)—(21)式中:Remake函數(shù)是本文設(shè)計的路徑生成函數(shù);local_target(t+1)表示機器人在t+1時刻的導航信息點;d1表示機器人與當前導航點的距離;d2表示預測的最優(yōu)模擬軌跡末端到當前導航點的距離;d3表示導航點到障礙物的最近距離(該項的作用是為了防止導航點生成在未知障礙物區(qū)域內(nèi),機器人不可達);l1,l2,l3是距離相關(guān)的參數(shù)。Remake函數(shù)按照一個期望節(jié)點間距nds從全局路徑中重新生成包含大量節(jié)點的導航路徑,操作流程如下:首先,基于蟻群算法得到全局路徑Old_path;其次,將相鄰節(jié)點Old_path(i)和Old_path(i-1)連接生成線段方程;然后,求解該線段上滿足期望的節(jié)點間距nds的節(jié)點序列,保存在New_path中;最后,依次遍歷完所有線段得到完整的機器人導航路徑New_path。當機器人運動過程中滿足3個條件(d1

改進局部目標點選取規(guī)則如圖3所示。原始路徑包含3個路徑節(jié)點Old_path(i-1,i,i+1),通過(20)式生成具有大量節(jié)點信息的新路徑,且每兩個節(jié)點之間的距離為nds;由于未知障礙物(圖3中紅色障礙物)會影響機器人對局部目標點的選取,本文在(21)式中設(shè)置幾個不同的距離保證機器人在具有未知障礙物環(huán)境下導航的正確性。當滿足機器人與局部目標點的距離小于1.7 m,或者模擬軌跡末端到局部目標點的距離小于1.5 m,或者局部目標點到最近障礙物的距離小于0.7 m這3個條件之一時,可認定該點可取為局部目標點(也即機器人運動導航點),否則設(shè)置終點為局部目標點。

圖3 局部目標點選取規(guī)則Fig.3 Schematic diagram of the our local target point tracking method

3 多機器人的優(yōu)先級協(xié)調(diào)策略

多移動機器人的路徑規(guī)劃問題實則是由單移動機器人擴展出來的。DWA動態(tài)避障策略主要適用于靜態(tài)環(huán)境或局部小規(guī)模動態(tài)環(huán)境,對于解決多個機器人之間的運動沖突效果不佳,本文基于IACO-IDWA策略構(gòu)建了分布式多移動機器人系統(tǒng)。

優(yōu)先級策略作為當前協(xié)調(diào)避碰的主流技術(shù)之一,旨在通過不同的任務指標預先為每個移動機器人設(shè)定相應的優(yōu)先級別,當存在運動沖突時優(yōu)先級低的機器人為優(yōu)先級高的機器人讓行。為此,本文引入了優(yōu)先級機制,以此降低多機器人在求解路徑?jīng)_突問題時的難度,下述以優(yōu)先級較高的AGV1和優(yōu)先級較低的AGV2進行闡述。

1)如果兩個機器人的實際距離d12小于期望避障距離d,則存在潛在碰撞風險。

2)以優(yōu)先級較低的機器人AGV2為中心建立局部坐標軸用于計算兩機器人的連線與x軸正方向構(gòu)成的夾角α,以及AGV1的運動方向角β。

3)判斷|α-β|是否小于90°,如果滿足條件,則碰撞風險可能性極高。AGV1將AGV2視為未知靜態(tài)障礙物,通過DWA進行避障運動。當兩個機器人之間的距離關(guān)系為d12≥d且|α-β|≥90°時,AGV2恢復運動。為保證多機器人運動的安全性,AGV2會在短時間內(nèi)進行驟然減速運動,依據(jù)的規(guī)則為

(22)

本文的優(yōu)先級避障策略在某些情況下會導致低優(yōu)先級的機器人產(chǎn)生額外的等待時間,但機器人的安全性和全局最優(yōu)性在極大程度上得到了保證。

4 仿真實驗分析

4.1 改進蟻群算法實驗分析

為驗證常規(guī)環(huán)境中算法的優(yōu)越性,在30 m×30 m的環(huán)境地圖上將本文算法與文獻[10-11]中的算法進行對比實驗。文獻[11]的路徑是經(jīng)過優(yōu)化的,而文獻[10]的路徑是未經(jīng)優(yōu)化的,測試地圖和數(shù)據(jù)均來自文獻[11]。算法對比分析實驗結(jié)果如表1所示;3種算法的路徑規(guī)劃結(jié)果及算法迭代曲線如圖4所示。為體現(xiàn)本文改進蟻群算法的綜合性能,參考文獻[7]的方法,定義路徑綜合性能為

表1 算法對比分析

圖4 路徑規(guī)劃結(jié)果圖Fig.4 Path planning result diagram

F=xT+yL+zC

(23)

(23)式中:F為路徑綜合指標;T為最優(yōu)路徑轉(zhuǎn)彎次數(shù);L為最優(yōu)路徑長度;C為最優(yōu)路徑與障礙物邊緣發(fā)生碰撞次數(shù);x、y、z表示各個指標的權(quán)重,本文均取為1。

在路徑安全性與平滑性方面,本文算法明顯優(yōu)于文獻[10-11],但在路徑長度方面文獻[10-11]略有優(yōu)勢。由表1可看出,本文算法轉(zhuǎn)彎次數(shù)、與障礙物邊緣碰撞次數(shù)最少;迭代穩(wěn)定次數(shù)為9,與文獻[10]相比下降較多,略高于文獻[11];運行時間明顯優(yōu)于其他兩種算法。從路徑綜合指標來看,本文算法無論是優(yōu)化前還是優(yōu)化后都優(yōu)于對比算法。本文與文獻[11]算法都經(jīng)歷了后期優(yōu)化,但本文的轉(zhuǎn)彎次數(shù)、與障礙物邊緣碰撞次數(shù)都優(yōu)于文獻[11],這樣機器人沿本文路徑運動時更為安全,且運動過程中對姿態(tài)的調(diào)整和避障能力要求更低。

4.2 多移動機器人路徑規(guī)劃實驗

為了驗證本文融合改進算法與優(yōu)先級法在多移動機器人路徑規(guī)劃中解決沖突的能力,本文設(shè)計了具有已知先驗信息的簡單環(huán)境、含有未知靜態(tài)和動態(tài)障礙物的復雜環(huán)境進行驗證;設(shè)計了3個考慮運動學約束的移動機器人,優(yōu)先級為AGV1>AGV2>AGV3。

4.2.1 簡單靜態(tài)環(huán)境

靜態(tài)環(huán)境多移動機器人路徑規(guī)劃如圖5所示。

圖5 靜態(tài)環(huán)境多移動機器人路徑規(guī)劃Fig.5 Multi-robot path planning in static environments

圖5a為本文為每個機器人規(guī)劃出的綜合性能最優(yōu)的全局路徑,其中藍線、紅線、粉線分別為AGV1、AGV2、AGV3這3個機器人的路徑情況;黑色網(wǎng)格是擁有先驗信息的靜態(tài)障礙物。圖5b顯示了機器人在規(guī)劃過程中的實時變化。靜態(tài)環(huán)境多移動機器人參數(shù)變化如圖6所示。圖6a和圖6b分別為機器人的線速度和角速度變化曲線。

4.2.2 復雜動態(tài)環(huán)境

從圖5b和圖6可以看出,當AGV2、AGV3檢測到與AGV1的碰撞風險時,分別在第41個運動控制節(jié)點和第50個運動節(jié)點開始減速。AGV2在第47個控制節(jié)點完全停止,AGV3在第51個節(jié)點完全停止。當優(yōu)先級最高的AGV1與其他機器人有發(fā)生碰撞沖突風險時,AGV1把其他機器人的停止節(jié)點視為未知靜態(tài)障礙物,進行避障后繼續(xù)向目標點前進。AGV1離開與AGV2的沖突區(qū)域后,AGV2恢復運動,并將AGV3視為未知靜態(tài)障礙物進行避障,直到AGV2離開沖突范圍后AGV3才恢復運動。本文進行的多機器人運動實驗用時101.7 s,AGV1、AGV2和AGV3的行駛的實際距離分別為12.70 m、12.63 m和11.45 m。

動態(tài)環(huán)境多移動機器人路徑規(guī)劃如圖7所示。圖7a顯示了為每個機器人規(guī)劃出的最優(yōu)路徑,圖7b顯示了機器人在避障過程中的實時變化。動態(tài)環(huán)境多移動機器人參數(shù)變化如圖8所示。圖8中,紅色柵格是未知的靜態(tài)障礙物,黃色柵格是未知的動態(tài)障礙物,黑色虛線是動態(tài)障礙物的運動軌跡。

圖7 動態(tài)環(huán)境多移動機器人路徑規(guī)劃Fig.7 Multi-robot path planning in dynamic environments

圖8 動態(tài)環(huán)境多移動機器人參數(shù)對比Fig.8 Multi-robot parameter comparison in dynamic environments

從圖7b和圖8可以看出,AGV1與AGV3完成了躲避動態(tài)障礙物的動作后,3個機器人相遇。AGV1與AGV3發(fā)生沖突,按照優(yōu)先級的限制,AGV3減速至完全停止。AGV2也與AGV1發(fā)生沖突,AGV2減速至停止,AGV1進行動態(tài)避障后繼續(xù)向目標點前進。AGV1離開沖突范圍后,AGV3恢復運動。隨著AGV1的遠去,AGV2隨即恢復運動并躲避動態(tài)障礙物,最終各機器人成功到達終點。整個多機器人運動實驗用時188.34 s,AGV1、AGV2和AGV3的行駛距離分別為13.16 m、113.89 m和9.165 m。

5 結(jié)束語

針對多移動機器人在運動過程中避障與安全性難以協(xié)調(diào)的問題,本文提出了一種能適應復雜未知環(huán)境的多機器人融合避障算法。在啟發(fā)式函數(shù)中綜合考慮A*算法的啟發(fā)信息、轉(zhuǎn)彎代價因子和轉(zhuǎn)角抑制因子并進行改進,增加路徑的平滑性與安全性;提出了以綜合路徑指標來進行信息素更新的方法,提高了全局路徑綜合性能;通過冗余點優(yōu)化策略進一步減少了全局路徑的長度和轉(zhuǎn)折點數(shù)量,進一步提高路徑質(zhì)量;基于DWA算法提出了自適應導航策略來引導機器人在復雜環(huán)境下的運動;將蟻群融合DWA的避障策略應用在分布式多移動機器人系統(tǒng)中,結(jié)合優(yōu)先級策略解決多機器人之間的運動沖突問題。不同環(huán)境下的多機器人仿真實驗表明,本文算法能夠?qū)崿F(xiàn)多移動機器人在未知環(huán)境中的協(xié)同避障。

猜你喜歡
移動機器人障礙物機器人
移動機器人自主動態(tài)避障方法
高低翻越
SelTrac?CBTC系統(tǒng)中非通信障礙物的設(shè)計和處理
基于Twincat的移動機器人制孔系統(tǒng)
機器人來幫你
認識機器人
機器人來啦
極坐標系下移動機器人的點鎮(zhèn)定
基于引導角的非完整移動機器人軌跡跟蹤控制
土釘墻在近障礙物的地下車行通道工程中的應用