唐 俊，楊友波，張 目，雷印杰

（四川大學(xué)電子信息學(xué)院，成都 610064）

0 引言

避障導(dǎo)航算法是移動機(jī)器人自主智能中一個基礎(chǔ)且重要的算法，其作用是引導(dǎo)機(jī)器人在空間中從起始點無碰撞地移動到目標(biāo)點。避障導(dǎo)航算法通?？煞譃閮煞N：動態(tài)環(huán)境導(dǎo)航避障和靜態(tài)環(huán)境導(dǎo)航避障算法，前者空間中存在可移動的障礙物，后者僅存在不可移動的障礙物。通常，移動機(jī)器人工作在餐廳、機(jī)場、街道等場景中，這些場景中存在著大量移動且密集的人群，移動機(jī)器人往往需要穿過密集的人群到達(dá)目的地，同時避免發(fā)生碰撞。相較于只有靜態(tài)障礙物的環(huán)境，這些環(huán)境中的障礙物狀態(tài)不斷變化且難以預(yù)測，導(dǎo)航與避障變得困難。因此，如何在這些未知密集的動態(tài)環(huán)境中自主導(dǎo)航和避障，依然是移動機(jī)器人自主智能中具有挑戰(zhàn)性的問題，具有重要的研究意義［1?2］。

目前，移動機(jī)器人導(dǎo)航算法主要分為兩種：基于規(guī)則的算法［3?5］和基于學(xué)習(xí)［6?7］的算法。基于規(guī)則的算法通過設(shè)計一系列規(guī)則，并根據(jù)這些規(guī)則運動。經(jīng)典的基于規(guī)則的導(dǎo)航算法如ORCA［3］、人工勢場算法［4］、A?Star［5］算法等。這些算法在靜態(tài)場景中可以很好地完成任務(wù)。然而，當(dāng)環(huán)境變?yōu)閯討B(tài)時，這些基于規(guī)則的算法往往產(chǎn)生不自然的運動路徑，甚至導(dǎo)致導(dǎo)航失敗?；趯W(xué)習(xí)的算法主要為強(qiáng)化學(xué)習(xí)算法，如CADRL［6］、LSTM?RL［7］等，這些算法包括訓(xùn)練和推理兩個階段。在訓(xùn)練階段，算法不斷與環(huán)境交互以獲得獎勵或者懲罰，從而不斷改進(jìn)策略以學(xué)習(xí)到在動態(tài)環(huán)境中導(dǎo)航的模型。在推理階段，算法直接通過訓(xùn)練階段獲得的模型進(jìn)行決策。雖然基于學(xué)習(xí)的算法在動態(tài)環(huán)境中取得了一些成果，然而隨著場景中動態(tài)障礙物的數(shù)量增加，這些算法均出現(xiàn)了不同程度的性能下降，如：導(dǎo)航成功率下降和導(dǎo)航時間過長等。為了解決以上問題，本文提出了一種基于深度強(qiáng)化學(xué)習(xí)的導(dǎo)航避障算法，僅需八個距離傳感器和機(jī)器人的運動狀態(tài)便可引導(dǎo)機(jī)器人在未知的密集動態(tài)環(huán)境中導(dǎo)航和避障。該算法主要包括一個用于提取融合傳感器特征并進(jìn)行Q 值估計的神經(jīng)網(wǎng)絡(luò)RA?DQN，以及一個受人工勢場啟發(fā)而設(shè)計的勢能獎勵函數(shù)PEFR。仿真實驗結(jié)果表明，當(dāng)環(huán)境中障礙物數(shù)量超過40 個時，本文提出的算法可以保持60%的成功率，而參與對比的其他算法成功率低于50%，本文算法可以有效提高在密集環(huán)境中導(dǎo)航避障的性能。

1 算法框架

本文提出的算法框架如圖1所示，其主要包括兩個部分：基于殘差卷積網(wǎng)絡(luò)和注意力機(jī)制［8］的深度Q 網(wǎng)絡(luò)（residual attention Q?network,RA?DQN），基于人工勢能場的獎勵函數(shù)（poten?tial energy field reward, PEFR）。RA?DQN 由帶注意力機(jī)制的殘差卷積網(wǎng)絡(luò)和深度Q 網(wǎng)絡(luò)［9］組成，其主要作用是提取來自傳感器的狀態(tài)信息，并獲得當(dāng)前狀態(tài)下每個可選動作的Q 值，該值表征了當(dāng)前狀態(tài)下選擇某一動作的收益期望。PEFR 通過特殊設(shè)計的勢能場函數(shù)給予智能體（agent）獎勵信號，即：當(dāng)智能體發(fā)生碰撞時給予懲罰；當(dāng)智能體靠近目標(biāo)點時給予獎勵，從而有效引導(dǎo)智能體學(xué)習(xí)在動態(tài)環(huán)境中的導(dǎo)航策略。

圖1 導(dǎo)航避障算法框架

本文算法使用了兩個RA?DQN 網(wǎng)絡(luò)。在探索階段，使用其中一個RA?DQN 與環(huán)境不斷交互從而獲得經(jīng)驗，并將這些經(jīng)驗儲存在經(jīng)驗池（replay buffer, RB）中供訓(xùn)練時使用。在訓(xùn)練階段，使用兩個RA?DQN 的TD?error 作為損失函數(shù)訓(xùn)練，并按照一定頻率更新與環(huán)境交互的網(wǎng)絡(luò)。本文的RB 采用優(yōu)先級經(jīng)驗回放池［10］，可以有效提高探索樣本的利用效率。

2 方法及細(xì)節(jié)

2.1 任務(wù)建模和強(qiáng)化學(xué)習(xí)算法

記r是機(jī)器人半徑，其周圍等距分布有8 個同構(gòu)的距離傳感器，每個傳感器間隔45 度。機(jī)器人導(dǎo)航和避障任務(wù)通常被建模為馬爾科夫決策過程。每個智能體的狀態(tài)通常被分為可觀測狀態(tài)和不可觀測狀態(tài)，可觀測狀態(tài)包括位置坐標(biāo)(x,y)、速度(vx,vy)、智能體半徑r；不可觀測狀態(tài)包括目的地坐標(biāo)(gx,gy)、偏好速度（v偏好）等。機(jī)器人可以獲取的狀態(tài)信息包括自己所有的狀態(tài)（可觀測和不可觀測狀態(tài)）以及來自傳感器的狀態(tài)(S傳感器)。因此，本文算法的狀態(tài)st的表達(dá)式為

在強(qiáng)化學(xué)習(xí)中，使用狀態(tài)?動作函數(shù)來表征當(dāng)前時刻動作的價值，也稱作Q 函數(shù)，獲得Q函數(shù)后便可根據(jù)Q 函數(shù)選擇當(dāng)前的動作，一般而言選擇Q值最大的動作即為最佳動作。Q函數(shù)的表達(dá)式為

其中：Ras為即時獎勵；s和s'分別為當(dāng)前狀態(tài)和下一時刻狀態(tài)；a是當(dāng)前執(zhí)行的動作；Pass'為當(dāng)前狀態(tài)到下一狀態(tài)的轉(zhuǎn)移概率；γ是折扣因子。本算法中Q 函數(shù)使用神經(jīng)網(wǎng)絡(luò)進(jìn)行值近似，并采用強(qiáng)化學(xué)習(xí)時間差分迭代的方式獲得最優(yōu)Q函數(shù)，即學(xué)習(xí)導(dǎo)航和避障的策略。

2.2 RA?DQN的結(jié)構(gòu)

本文的RA?DQN 網(wǎng)絡(luò)的主要作用是估計當(dāng)前狀態(tài)下每個動作的Q 值，即當(dāng)前狀態(tài)下每個動作的價值。RA?DQN的結(jié)構(gòu)如圖2所示。

圖2 RA?DQN網(wǎng)絡(luò)結(jié)構(gòu)

RA?DQN 主要由兩個部分構(gòu)成：基于殘差卷積和注意力機(jī)制的狀態(tài)特征提取網(wǎng)絡(luò)RAF 和基于多層感知機(jī)MLP 的Q 值估計網(wǎng)絡(luò)。RAF 的主要作用是利用殘差卷積提取狀態(tài)特征并利用注意力機(jī)制捕捉特征間的依賴關(guān)系，將這些特征加權(quán)融合。RAF 主要由多個注意力殘差塊ARB 組成。ARB 本質(zhì)上是一個帶通道注意力的殘差卷積塊，其將輸入的特征首先輸入一個卷積層，而后通過池化層生成通道注意力，最后將注意力值與卷積層提取的特征相乘以殘差到的形式輸出。Q值估計網(wǎng)絡(luò)也稱Q網(wǎng)絡(luò)，其作用是通過輸入RAF 提取得到的狀態(tài)特征輸出每個Q值。

2.3 勢能場獎勵函數(shù)（PEFR）的設(shè)計

PEFR 的基本思想是當(dāng)智能體靠近障礙物或發(fā)生碰撞時給予懲罰，當(dāng)智能體遠(yuǎn)離障礙物或靠近目標(biāo)點時給予獎勵，因此本文將期望智能體靠近的區(qū)域設(shè)置為低勢能區(qū)域，并在將當(dāng)前時刻t與上一時刻t?1的勢能函數(shù)差值作為獎勵。綜合以上思想，在t時刻，獎勵Rt的數(shù)學(xué)表達(dá)式如下：

其中：r碰撞< 0 是發(fā)生碰撞時的懲罰值；r到達(dá)> 0是到達(dá)目標(biāo)點時的獎勵值；Et和Et?1分別是t、t?1 時刻的勢能場函數(shù)值。勢能場函數(shù)E的表達(dá)式為

其主要包括兩個部分：引力場函數(shù)和斥力場函數(shù)，引力場函數(shù)At的表達(dá)式為

斥力場函數(shù)是智能體與所有動態(tài)障礙物的斥力的總和，智能體與第i個障礙物之間斥力的表達(dá)式為

2.4 算法訓(xùn)練過程

本算法包含兩個RA?DQN網(wǎng)絡(luò)：目標(biāo)網(wǎng)絡(luò)和評估網(wǎng)絡(luò)。在探索階段，目標(biāo)網(wǎng)絡(luò)根據(jù)當(dāng)前環(huán)境狀態(tài)st得到每個動作的Q值，并依據(jù)e?greedy 策略選擇動作at從而獲得下一時刻的狀態(tài)st+1以及獎勵rt，并將它們存入經(jīng)驗池（replay buffer，RB）中。其中e?greedy的過程如下：

在訓(xùn)練階段，從RB 中隨機(jī)采樣nbatch條經(jīng)驗，計算評估網(wǎng)絡(luò)與目標(biāo)網(wǎng)絡(luò)的TD?error，從而訓(xùn)練目標(biāo)網(wǎng)絡(luò)，每隔k輪探索，目標(biāo)網(wǎng)絡(luò)將會更新評估網(wǎng)絡(luò)。其中，TD?error的表達(dá)式如下：

3 仿真實驗和運行效果

3.1 實驗設(shè)置

本文使用Python 實現(xiàn)了所提算法，使用Py?Torch來實現(xiàn)RA?DQN。選擇了當(dāng)前廣泛使用的動態(tài)環(huán)境導(dǎo)航避障算法， ORCA、 CADRL、LSTM?RL與我們的算法進(jìn)行對比。仿真環(huán)境長10米、寬10 米，有n個障礙。所有算法在n=10、20、30 和40 的情況下運行了100 次，并記錄成功率、導(dǎo)航時間等指標(biāo)。障礙物的起始位置是隨機(jī)確定的，并均勻地分散在場景中，并且障礙物的目標(biāo)也是隨機(jī)和均勻地分散在整個場景中。強(qiáng)化學(xué)習(xí)算法的參數(shù)包括：0.01 的學(xué)習(xí)率，0.95 的折扣因子，探索率e按照線性衰減策略從0.5 下降到0.1。經(jīng)驗回放池的大小為20000。批訓(xùn)練的大小為64，并隨著訓(xùn)練的進(jìn)行逐步提升至256。訓(xùn)練使用了一張GTX2080Ti GPU。

3.2 實驗結(jié)果及分析

每個算法在每個測試環(huán)境中均測試了100次，并對每個算法使用相同的隨機(jī)種子。對于每個仿真環(huán)境，我們通過統(tǒng)計成功率、平均到達(dá)時間、平均到達(dá)距離以及平均獎勵來評估算法的性能，顯示了不同障礙物數(shù)量情況下，不同算法指標(biāo)的變化情況，結(jié)果如圖3所示。

圖3 成功率和平均時間對比

當(dāng)障礙物數(shù)量增加到40 個時，環(huán)境變得十分稠密，高度動態(tài)且擁擠，此時除本文算法，其余算法成功率均低于50%，ORCA、CADRL、LSTM?RL 均難以完成導(dǎo)航任務(wù)。本文算法仍能保持69%的成功率，優(yōu)于參與測試的所有算法。RA?DQN 可以有效緩解障礙物數(shù)量上升時帶來的性能下降，并能保持穩(wěn)定的運行效率。

圖4 展示了算法在具有20 個動態(tài)障礙物的隨機(jī)環(huán)境中的軌跡特征。相比基于強(qiáng)化學(xué)習(xí)的算法，基于規(guī)則的ORCA 僅有少數(shù)情況下產(chǎn)生了直接通向目標(biāo)的路徑，且成功率較低。本文算法、CADRL 以及LSTM?RL 算法均使用圓形運動以避免碰撞。然而與本文算法相比，CADRL算法軌跡波動程度更大。本文算法軌跡更加集中，穩(wěn)定程度更高。LSTM?RL 算法則產(chǎn)生了大量低效的迂回、且不自然的軌跡。相較參與測試的其他算法，本文算法可以完成可靠且穩(wěn)定的碰撞規(guī)避，且導(dǎo)航過程中動作變更較少，更加高效。

圖4 特征軌跡對比

4 結(jié)語

本文提出了一種基于深度強(qiáng)化學(xué)習(xí)的密集動態(tài)環(huán)境導(dǎo)航算法，該算法使用基于殘差卷積和注意力機(jī)制的深度Q 網(wǎng)絡(luò)RA?DQN 以獲得當(dāng)前最佳動作，并設(shè)計了一個基于勢能函數(shù)的獎勵函數(shù)PEFR 引導(dǎo)算法學(xué)習(xí)有效的導(dǎo)航策略。實驗結(jié)果表明，本文提出的算法可以在高度動態(tài)的環(huán)境中完成導(dǎo)航和避障任務(wù)，同時與CADRL、LSTM?RL 算法相比具有優(yōu)勢。本文提出的算法，結(jié)構(gòu)簡單且易于使用，只需要8個距離傳感器的數(shù)據(jù)以及少量自身的位置信息便可完成導(dǎo)航避障任務(wù)。未來，我們會將算法整合到導(dǎo)航框架中，通過長距離的路徑規(guī)劃和本算法結(jié)合從而完成更長距離的導(dǎo)航避障任務(wù)。