馮恒莉
(1.江蘇聯(lián)合職業(yè)技術(shù)學(xué)院蘇州工業(yè)園區(qū)分院,江蘇 蘇州 215000;2.蘇州工業(yè)園區(qū)工業(yè)技術(shù)學(xué)校,江蘇 蘇州 215000)
在路徑規(guī)劃領(lǐng)域中,傳統(tǒng)方法和強化學(xué)習各有優(yōu)缺點。因此,該文將傳統(tǒng)學(xué)習中的人工勢能場算法與強化學(xué)習中的DQN算法相結(jié)合,構(gòu)建了一種APF-DQN算法,該算法可以在減少迭代次數(shù)的同時不影響最終效果。基于APF算法和DQN算法,該文構(gòu)建了APF-DQN算法,最終的試驗結(jié)果表明,該算法在路徑規(guī)劃領(lǐng)域具有良好的效果。傳統(tǒng)的APF算法存在一些局限,該文對這些局限進行分析和改進。將DQN算法與APF算法相結(jié)合,APF-DQN算法克服了傳統(tǒng)APF算法的一些缺點,可以提高在路徑規(guī)劃任務(wù)中的性能。
隨著人工智能和機器人等技術(shù)迅速發(fā)展,路徑規(guī)劃廣泛應(yīng)用于各個領(lǐng)域,例如服務(wù)機器人、船舶以及無人機等領(lǐng)域[1-3]。針對路徑規(guī)劃的研究可以分為3種方法,即傳統(tǒng)方法、深度學(xué)習方法和強化學(xué)習方法。
在傳統(tǒng)的路徑規(guī)劃方法中,研究人員將路徑規(guī)劃分為3個步驟,即構(gòu)建環(huán)境模型、搜索路徑和路徑處理。這3個步驟在不同的算法中有不同的處理方式,由于任務(wù)的關(guān)注點不同,因此傳統(tǒng)方法中存在多種不同的算法。例如Dijkstra算法使用廣度優(yōu)先和貪婪搜索策略搜索完整的圖路徑,A*算法在Dijkstra算法的基礎(chǔ)上增加了啟發(fā)式函數(shù)和估計函數(shù)來限制搜索,以獲得更好的結(jié)果。除了這些算法,還有一些仿生算法被應(yīng)用于路徑規(guī)劃,例如蟻群算法通過模擬螞蟻在尋找食物過程中傳遞給彼此的信息素來進行路徑規(guī)劃;遺傳算法通過模擬自然繁殖過程中的遺傳和變異來規(guī)劃更好的路徑;粒子群算法通過模擬鳥類覓食過程中信息的相互作用來規(guī)劃路徑。此外,當?shù)貓D信息不足時,一些研究人員更注重研究規(guī)劃路徑的方法,因此衍生了一系列局部路徑規(guī)劃算法,例如人工勢場算法,它將物理學(xué)中的“場”概念引入路徑規(guī)劃領(lǐng)域中,假設(shè)智能體在一個力場中運動,障礙物產(chǎn)生斥力,目標產(chǎn)生引力,在斥力和引力的綜合作用下找到最優(yōu)路徑。
傳統(tǒng)路徑規(guī)劃方法存在先驗知識過多、在復(fù)雜環(huán)境中規(guī)劃效率和結(jié)果下降的問題[4-5]。因此,深度學(xué)習逐漸應(yīng)用于路徑規(guī)劃中。例如Wu K Y等[6]提出了一種基于DNN網(wǎng)絡(luò)的混沌環(huán)境實時路徑規(guī)劃算法;Huang F R等[7]將深度學(xué)習引入旅行路線規(guī)劃問題中。除此之外,深度學(xué)習還被引入基于無人機網(wǎng)絡(luò)的多目標路徑優(yōu)化和城市中的車輛網(wǎng)絡(luò)進行細粒度路徑規(guī)劃。
雖然深度學(xué)習在路徑規(guī)劃方面頗有成效,但是與強化學(xué)習相比,它在規(guī)劃效果上仍存在一些不足,其根本原因是2種學(xué)習方法不同。深度學(xué)習是基于樣本的靜態(tài)學(xué)習,而強化學(xué)習是與環(huán)境交互的交互學(xué)習。在強化學(xué)習的訓(xùn)練過程中,智能體會探索各種策略,以達到更好的效果。標準的強化學(xué)習框架通常由3個模塊組成,即輸入模塊、強化模塊和策略模塊。輸入模塊讀取外部輸入;強化模塊確定代理要實現(xiàn)的目標,一般是使其獲得最大的最終獎勵;策略模塊根據(jù)當前狀態(tài)和強化目標選擇代理要采取的行動。
人工勢場算法(APF)是一種標準的路徑規(guī)劃算法,其基本思想是將路徑規(guī)劃中的環(huán)境模型與混合引力場和斥力場的人工勢能場算法進行比較,在人工勢能場中,目標點對機器人具有吸引效應(yīng),周圍的障礙物對機器人具有排斥效應(yīng),機器人在二者的共同影響下進行路徑規(guī)劃。概率路網(wǎng)算法通過在相容空間中采樣來對采樣點進行碰撞檢測,并測試相鄰采樣點是否可以連接(表示路徑圖的連通性)。模擬退火算法基于路徑規(guī)劃過程中連續(xù)變化的概率最終趨于0的原則,算法在當前解附近隨機尋找可能的全局最優(yōu)解,以實現(xiàn)全局優(yōu)化的目的。
如圖1所示,APF算法涉及斥力和引力,該文介紹的APF算法中涉及的引力場函數(shù)如公式(1)所示。
式中:ξ為引力增益;d(q,qgoai)為目標點間的歐氏距離。
根據(jù)公式(1)可以推導(dǎo)引力力的公式,如公式(2)所示。
式中:Uatt為引力勢場函數(shù);qgoal為目標點位置;q為當前點位置。
該文涉及的APF算法中的斥力場函數(shù)如公式(3)所示。
式中:η為斥力增益;D(q)為當前點q與最近障礙物點間的歐氏距離;Q*為障礙物受到斥力影響的距離閾值。可以根據(jù)公式(3)推導(dǎo)斥力的公式,如公式(4)所示。
最終,結(jié)合公式(1)~公式(4)可以得到人工勢場的最終表達式,如公式(5)、公式(6)所示。
式中:U(q)為最終人工勢場函數(shù);Uatt(q)為引力勢場函數(shù);F(q)為合力。
由公式(1)~公式(6)可知,人工勢場算法存在2個問題:1) 由于引力過小,因此難以捕捉目標。2) 當引力和斥力的合力為0時,容易陷入局部最優(yōu)解。為了解決這些問題,該文設(shè)置相關(guān)區(qū)域和無關(guān)區(qū)域,以減少無關(guān)區(qū)域中斥力的影響。
原始的人工勢場算法通過全局考慮所有障礙物和目標來計算斥力和引力。然而,這并不合理,因為一定距離之外的障礙物不會對智能體的路徑規(guī)劃產(chǎn)生影響,所以該文圍繞智能體設(shè)置了一個相關(guān)區(qū)域,在相關(guān)區(qū)域半徑R內(nèi)僅考慮障礙物產(chǎn)生的斥力。經(jīng)過對比可知,不考慮相關(guān)區(qū)域外障礙物產(chǎn)生的斥力,可以降低出現(xiàn)斥力和引力合力合理為0的情況的概率。相關(guān)區(qū)域的示意圖如圖2、圖3所示。
圖3 改進的人工勢能場算法的效果
深度學(xué)習算法與強化學(xué)習算法在路徑規(guī)劃任務(wù)中有不同的優(yōu)勢,將深度學(xué)習與強化學(xué)習結(jié)合,執(zhí)行路徑規(guī)劃任務(wù)也取得了顯著的成果。DQN算法是典型的深度強化學(xué)習算法,其優(yōu)點是可以處理高維度的狀態(tài)空間,而且可以在沒有干預(yù)的情況下自主學(xué)習,從而實現(xiàn)自適應(yīng)不同地圖和場景。DQN算法可以利用深度學(xué)習的感知能力與強化學(xué)習的決策能力,實現(xiàn)端到端學(xué)習。即使在復(fù)雜的動態(tài)環(huán)境下,DQN算法也能通過調(diào)整神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)和參數(shù)來提高路徑規(guī)劃的準確性,在網(wǎng)絡(luò)收斂速度較快的前提下,具有良好的路徑規(guī)劃能力。因此,該文對改進人工勢場算法和DQN算法進行融合。
DQN算法的核心概念是用一個神經(jīng)網(wǎng)絡(luò)q(s,a:ω)來代替Q表,其具體的原理如公式(7)所示。
式中:Q*(s,a)為價值函數(shù)近似。
在公式(7)中,f值可以是任意類型的函數(shù),而s表示輸入的狀態(tài)。
DQN算法中的損失函數(shù)如公式(8)所示。
式中:E為期望值;r為實際觀察得到的值;γ為回報的折扣率;Q(st+1,at+1,ω-)為目標網(wǎng)絡(luò);Q(st,at,ω)為評估網(wǎng)絡(luò)。
DQN網(wǎng)絡(luò)的結(jié)構(gòu)如圖4所示。原始的DQN算法在路徑規(guī)劃領(lǐng)域需要大量的迭代次數(shù),其原因是它沒有先驗知識?;贒QN算法的APF-DQN算法將APF算法作為先驗知識添加到DQN算法中,最終減少了迭代次數(shù)。
圖4 DQN網(wǎng)絡(luò)結(jié)構(gòu)圖
為了驗證該文提出的方法的有效性,對APF-DQN算法進行試驗和分析,APF與DQN融合后可以減少迭代次數(shù)、提高算法效率。通過大量試驗驗證,該文提出的方法能夠縮短50%的迭代時間。APF-DQN算法的實施效果如圖5所示,在復(fù)雜場景中,該算法仍然具有較高的性能。
圖5 APF-DQN算法實施效果圖
為了驗證APF-DQN算法的先進性,在相同的柵格地圖上對APF-DQN算法和其他先進的算法進行多次對比試驗。由于單次路徑規(guī)劃可能存在一定的隨機性,因此該文選擇10個點進行路徑規(guī)劃,分別求取10個點的試驗結(jié)果的平均值,并將其作為最終的試驗結(jié)果。具體的試驗結(jié)果見表1,將該文提出的APF-DQN算法與D*、A*、GA以及APF等先進算法進行對比。
表1 路徑規(guī)劃算法對比試驗結(jié)果
由表1可知,APF-DQN路徑規(guī)劃長度最短,與其他常見的先進路徑規(guī)劃算法相比,APF-DQN具有更好的結(jié)果,在復(fù)雜路徑規(guī)劃場景中具有較高的性能。
該文提出了一種基于DQN算法的APF-DQN算法。與DQN算法相比,該文提出的算法可以更快地迭代最終結(jié)果,其規(guī)劃效果比其他標準算法更好。但是,當前的APFDQN算法仍然有需要改進的地方,在復(fù)雜環(huán)境中,APFDQN算法很難獲得最優(yōu)解,因此如何在復(fù)雜環(huán)境中仍然具有良好效果是一個亟待解決的問題;與其他標準傳統(tǒng)算法相比,APF-DQN算法的運行速度仍然太慢,提高APFDQN算法的速度也是未來的重要研究方向之一。