黃志鋒 劉媛華 任志豪 張文敏 張孝文

收稿日期：2023-06-12；修回日期：2023-08-07? 基金項目：國家自然科學(xué)基金資助項目（72071130）

作者簡介：黃志鋒（1998—），男，福建惠安人，碩士研究生，CCF會員，主要研究方向為路徑規(guī)劃、算法優(yōu)化；劉媛華（1974—），女（通信作者），山東萊陽人，副教授，碩導(dǎo)，博士，主要研究方向為路徑規(guī)劃（liuyuanhua@usst.edu.cn）；任志豪（1997—），男，四川綿陽人，碩士研究生，主要研究方向為路徑規(guī)劃；張文敏（1998—），男，安徽安慶人，碩士研究生，主要研究方向為路徑規(guī)劃；張孝文（1998—），男，河南洛陽人，碩士研究生，主要研究方向為算法優(yōu)化、博弈．

摘? 要：針對動態(tài)環(huán)境的移動機器人路徑規(guī)劃問題，提出了一種改進哈里斯鷹算法（IHHO）與改進動態(tài)窗口算法（IDWA）的融合算法（IHHO-IDWA）。首先，針對哈里斯鷹算法后期搜索性能不足等問題，提出了融合自適應(yīng)混沌和核心種群動態(tài)劃分策略、融合黃金正弦策略以及動態(tài)云最優(yōu)解擾動策略來提高算法的性能。其次，針對動態(tài)窗口算法存在規(guī)劃的路徑長和易陷入死鎖等問題，提出了三個改進策略：增加子函數(shù)，保證算法能夠規(guī)劃出更短的路徑；提出自適應(yīng)權(quán)重策略，平衡算法局部避障能力和全局搜索性能；設(shè)定初始航向角，避免路徑冗余。最后，通過測試函數(shù)、CEC2014函數(shù)的數(shù)值實驗和靜態(tài)、動態(tài)路徑規(guī)劃實驗，驗證了IHHO和IDWA性能有明顯提升；通過50×50大型動態(tài)地圖驗證了融合算法較對照組算法規(guī)劃的路徑縮短了11.51%，證明了該方法的優(yōu)越性。

關(guān)鍵詞：動態(tài)窗口算法；哈里斯鷹算法；自適應(yīng)；路徑規(guī)劃；測試函數(shù)

中圖分類號：TP301.6；TP391.9??? 文獻標志碼：A

文章編號：1001-3695（2024）02-020-0450-09

doi：10.19734/j.issn.1001-3695.2023.06.0256

Research on mobile robot dynamic path planning based on improved

Harris hawk algorithm and improved dynamic window algorithm

Huang Zhifeng，Liu Yuanhua，Ren Zhihao，Zhang Wenmin，Zhang Xiaowen

（Business School，University of Shanghai for Science & Technology，Shanghai 200093，China）

Abstract：Aiming at the path planning problem of mobile robot in dynamic environment，this paper proposed a fusion algorithm（IHHO-IDWA） of improved Harris hawk algorithm（IHHO） and improved dynamic window algorithm（IDWA）.First of all，this paper proposed a fusion adaptive chaos and core population dynamic division strategy，a fusion golden sine strategy and a dynamic cloud optimal disturbance resolution strategy to improve the performance of and solve the lack of search performance in the late stage of the Harris eagle algorithm.In addition，in view of the problems that the dynamic window algorithm had a long planned path and easied to fall into deadlock，this paper proposed three improvement strategies to solve them.Firstly，it added sub-functions to ensure that the algorithm could plan a shorter path.Secondly，it proposed an adaptive weight strategy to balance the local obstacle avoidance ability and global search performance of the algorithm.Thirdly，it set the initial heading angle to avoid path redundancy.Finally，through numerical experiments of test functions，CEC2014 functions，and static and dynamic path planning experiments，it is verified that the performance of IHHO and IDWA in this paper has been significantly improved；through the 50×50 large-scale dynamic map，it is verified that the path planned by the fusion algorithm is shorter than that planned by the control group algorithm 11.51%，proving the superiority of the IHHO-IDWA.

Key words：dynamic window algorithm；Harris hawk algorithm；self-adaptation；path planning；test function

0? 引言

目前路徑規(guī)劃算法可以分為經(jīng)典算法和智能優(yōu)化算法。經(jīng)典算法如A*算法［1］和RRT算法［2］等；智能優(yōu)化算法包括粒子群算法［3］、獅群算法［4，5］、鯨魚優(yōu)化算法［6］和哈里斯鷹優(yōu)化算法［7］等。經(jīng)典算法需要提前載入環(huán)境信息，在復(fù)雜地圖中計算量大，而智能優(yōu)化算法在已知環(huán)境中具有更好的全局性，在未知環(huán)境中能夠通過測量自身位置與環(huán)境的相對信息快速進行路徑規(guī)劃，在復(fù)雜環(huán)境和未知環(huán)境中的路徑規(guī)劃求解上具有優(yōu)勢［8］。哈里斯鷹算法具有參數(shù)少、尋優(yōu)速度快等優(yōu)點，因此，本文選取哈里斯鷹優(yōu)化算法進行路徑規(guī)劃研究。

近年來，智能優(yōu)化算法的路徑規(guī)劃研究成果頗豐。黃志鋒等人［9］提出了一種雙種群改進獅群算法用于路徑規(guī)劃中，首先在獅群算法基礎(chǔ)上引入調(diào)節(jié)因子和sin混沌提高算法的性能；其次加入方向約束性函數(shù)來加快算法向終點靠近，并使用雙種群結(jié)構(gòu)提高算法的搜索速度，通過仿真實驗驗證了改進算法的有效性。劉志強等人［10］針對傳統(tǒng)灰狼算法應(yīng)用在路徑規(guī)劃中收斂效率低的缺陷，首先使用Tent混沌種群初始化，提高解的質(zhì)量；其次通過改進控制參數(shù)H以平衡算法的全局和局部搜索能力；最后在多張地圖中驗證了改進算法的性能得到了提升。張恒等人［11］提出了一種雙層蟻群的路徑規(guī)劃算法，將蟻群分為引導(dǎo)蟻群和普通蟻群，引導(dǎo)蟻群專門應(yīng)對死鎖問題，能夠幫助蟻群快速跳出死鎖路徑。Xu等人［12］提出了一種基于四次Bezier曲線和改進粒子群算法融合的路徑規(guī)劃方法。首先提出了一種加權(quán)自適應(yīng)延遲速度的粒子群算法，提高粒子群的搜索性能；接著，使用四次Bezier曲線對路徑進行平滑處理。該方法提高了路徑的平滑度和安全性。

總結(jié)現(xiàn)有的文獻發(fā)現(xiàn)，目前路徑規(guī)劃的研究側(cè)重于靜態(tài)環(huán)境的情況較多，有關(guān)動態(tài)環(huán)境的路徑規(guī)劃研究比例相對偏少。然而在實際生產(chǎn)、生活中，通常存在動態(tài)障礙物，這時使用靜態(tài)環(huán)境的路徑規(guī)劃算法可能就存在問題。因此，研究動態(tài)環(huán)境中的路徑規(guī)劃不僅具有理論意義，還具有現(xiàn)實意義。

Molinos等人［13］將動態(tài)窗口算法（dynamic window algorithm，DWA）融合動態(tài)障礙樹法來提高算法的性能，并結(jié)合了預(yù)測曲率速度法和動態(tài)曲率速度法提高路徑的安全性。Liu等人［14］利用跳點搜索算法對動態(tài)窗口算法進行改進，將跳點搜索改進為新的子函數(shù)，并整合全局信息平滑最優(yōu)路徑。Chang等人［15］提出一種基于Q-learning的改進DWA，首先通過增加兩個子函數(shù)提高全局導(dǎo)航性能；其次，采用Q-learning算法學(xué)習(xí)機器人路徑規(guī)劃，以適應(yīng)未知環(huán)境。李薪穎等人［16］提出了一種多目標粒子群的動態(tài)窗口算法，利用多目標粒子群算法優(yōu)化DWA參數(shù)，使路徑能夠兼顧安全和運行速度。蒲興成等人［17］針對動態(tài)避障問題提出了結(jié)合DWA的改進細菌算法。首先利用細菌算法獲得初始路徑，再基于初始路徑，機器人利用DWA進行動態(tài)避障，最后通過實驗證明改進算法在性能上有明顯提升。魏立新等人［18］提出了基于改進蟻群結(jié)合DWA的動態(tài)路徑規(guī)劃算法，首先增加了蟻群搜索接力的方式解決了死鎖問題，在蟻群算法路徑規(guī)劃完成以后，運用DWA進行局部避障。劉鈺銘等人［19］提出了一種結(jié)合A*算法和動態(tài)窗口的路徑規(guī)劃融合算法，提出自動調(diào)整航向角策略，增強算法遇到動態(tài)障礙物時的及時避障能力，并針對局部路徑規(guī)劃問題設(shè)計了路徑偏離評價指標和能耗評價指標。

綜上所述，目前關(guān)于動態(tài)環(huán)境的路徑規(guī)劃研究采用的方法多是智能算法融合DWA，雖然上述改進使算法性能有了一定提升，但仍存在改進的空間，例如算法的性能十分依賴參數(shù)的設(shè)定、在復(fù)雜的環(huán)境中無法完成路徑規(guī)劃以及路徑規(guī)劃所需時間較長等問題。本文對動態(tài)窗口法進行改進，提出三個改進策略來提升算法性能，并融合改進哈里斯鷹算法，利用其較好的全局性優(yōu)點先進行靜態(tài)全局路徑規(guī)劃，再進行局部避障，使算法能夠應(yīng)用在動態(tài)環(huán)境當(dāng)中。

1? 改進哈里斯鷹優(yōu)化算法

1.1? 基礎(chǔ)哈里斯鷹優(yōu)化算法

逃離能量值決定算法執(zhí)行哪種行為，當(dāng)逃離能量|E|≥1時執(zhí)行探索行為，逃離能量變化如下：

E=2E0（1-tT）（1）

其中：E0是（-1，1）的隨機初始值；t為當(dāng)前迭代次數(shù)；T為最大迭代次數(shù)。

1.1.1? 探索行為

當(dāng)逃離能量|E|≥1時進行隨機探索，其更新公式為

X（t+1）=Xk（t）-r1|Xk（t）-2r2X（t）|

（Xk（t）-Xm（t））-r3（lb-r4（ub-lb）） （2）

Xm（t）=1N∑Ni=1Xi（t）（3）

其中：Xk為哈里斯鷹種群中的隨機個體；Xr為哈里斯鷹最佳值個體位置；Xm為種群平均位置；N為種群規(guī)模；r1～r4 是四個獨立服從正態(tài)分布［0，1］的隨機數(shù)；lb和ub為所求問題上下界。

1.1.2? 開發(fā)行為

當(dāng)逃離能量|E|<1時進入局部搜索的開發(fā)階段，這時會根據(jù)能量值選擇四種不同策略進行更新位置。

a）當(dāng)|E|≥0.5且r≥0.5時，進行軟包圍，其更新公式為

X（t+1）=ΔX（t）-E|JX（t）-X（t）|（4）

ΔX（t）=Xr-X（t）（5）

其中：J∈［0，2］的隨機數(shù)，表示算法的步長；ΔX（t）表示最佳位置與當(dāng)前位置之間的距離。

b）當(dāng)|E|≥0.5且r<0.5時，算法進行硬包圍，其位置更新公式為

X（t+1）=Xr（t）-E|ΔX（t）|（6）

c）當(dāng)逃離能量值|E|<0.5且r≥0.5時，野兔能量不足，哈里斯鷹采取更為智能的軟包圍，具體方式為

Y=Xr（t）-E|JXr（t）-X（t）|（7）

Z=Y+S×LF（D）（8）

LF（D）=uσ100×|v|1β，σ=（Γ（1+β）×sin（πβ2）Γ（1+β2）×β×2（β-12））1/β（9）

X（t+1）=Yif F（Y）

其中：D是所求問題維度；S是D維上的隨機向量；LF（D）是萊維飛行公式；u、v是（0，1）上的隨機數(shù)；β值為1.5。

d）當(dāng)|E|<0.5且r<0.5時，采取漸近的軟包圍，逐步縮短與野兔之間的距離，具體方式為

Y=Xr（t）-E|JXr（t）-Xm（t）|（11）

Z=Y+S×LF（D）（12）

1.2? 改進哈里斯鷹優(yōu)化算法

1.2.1? 基于自適應(yīng)混沌和核心種群動態(tài)劃分策略

哈里斯鷹優(yōu)化算法在前期和后期運算中的探索行為和開發(fā)行為并不是先后發(fā)生，也不是等概率發(fā)生。根據(jù)式（1），當(dāng)t=1時也就是第一次迭代，探索概率約為50%；在t=T/2時，E=E0，探索概率為0%，且之后算法也不會再有探索行為。因此，在t

因此，本文提出一種自適應(yīng)混沌和核心種群動態(tài)劃分策略。將混沌種群的選取和智能優(yōu)化算法的收斂優(yōu)化策略相融合，可以使算法在全局探索和局部搜索之間取得平衡，提高算法的搜索性能和多樣性，在哈里斯鷹算法每次行為完成以后且迭代次數(shù)超過T/2時進行該操作，這樣能彌補哈里斯鷹算法在后期缺乏探索行為的缺點，能夠?qū)⒉糠址N群釋放出去，在遠離最優(yōu)值的位置進行全局隨機探索，同時保證在最優(yōu)值附近充分搜索。

設(shè)置一種自適應(yīng)準線baseline作為劃分閾值，之后每次迭代結(jié)束后都會將種群重新劃分為兩種，第一種是以混沌規(guī)則在解空間進行全局探索；第二種是遵循智能優(yōu)化算法收斂規(guī)則在領(lǐng)先混沌種群Xr的局部范圍內(nèi)進行逼近搜索，具體流程如下：

a）計算baseline=1T∑Ti=1fit，T為總迭代次數(shù)；

b）若當(dāng)前解X對應(yīng)的fit

c）若當(dāng)前解X對應(yīng)的fit≥baseline，則將X劃分為混沌離散種群，稱為chaos_swarm；

d）設(shè)t為當(dāng)前迭代次數(shù)，tmax為最大迭代次數(shù)，計算參數(shù)order=size（chaos_swarm）·（t/tmax）2，size（）為種群規(guī)模，稱order為劃分變量；將混沌離散種群從第一個到第order個劃分出到核心種群core_swarm中，因為混沌本身具有隨機性，所以無須增加隨機選取的過程。

如此完成一次劃分，baseline會隨著迭代次數(shù)的變化自適應(yīng)收斂于fit；此外，混沌種群并不會永遠處于混沌當(dāng)中，在領(lǐng)域周圍進行搜索，而是隨著迭代次數(shù)的增加而減少，會逐漸回歸到核心種群，最后只剩極少數(shù)還遠離核心種群進行隨機搜索，且在該過程中游離的混沌種群也會隨基線作微小的振蕩，反復(fù)釋放少量的群粒，在混沌操作以后重新進行領(lǐng)域逼近搜索。

Tent混沌種群初始化操作如下：

xk+1=xk/φ0

當(dāng)φ∈（0，1）且x∈［0，1］時，式（13）處于混沌狀態(tài)。完成混沌種群初始化構(gòu)造以后，將所有的群粒以矩陣運算方式輸入求解最優(yōu)適應(yīng)度fit*及其對應(yīng)的Xr，該個體稱為領(lǐng)先混沌群粒。該劃分策略相較于其他文獻使用的混沌種群初始化能夠保證算法在搜索過程中的多樣性。

1.2.2? 融合黃金正弦策略

根據(jù)式（7）～（10），哈里斯鷹算法采用了一種貪婪策略，如果該策略在軟包圍沖刺階段有效，即找到更優(yōu)解，則更新位置；若該策略失敗，沒有更優(yōu)解，則采取式（8）策略，進行萊維飛行擾動；若萊維飛行隨機游走失敗，沒有找到更優(yōu)解，則退回原解。為了測試萊維飛行游走的效率，采用標準測試函數(shù)進行測試，發(fā)現(xiàn)加入萊維飛行游走以后，算法收斂精度并沒有明顯提高；此外，根據(jù)文獻［20］，軟包圍策略失敗后，萊維飛行的有效率僅為0.03%。因此，本文融合黃金正弦策略替換萊維飛行游走，提高算法性能。

黃金正弦策略［21］于2017年提出，能夠快速遍歷最優(yōu)解附近單位圓的所有領(lǐng)域，比萊維隨機游走有更強的遍歷性。在搜索過程中引入黃金分割系數(shù)，確保掃描范圍控制在最優(yōu)解的周圍領(lǐng)域，加快算法收斂速度。因此，式（8）和（12）的更新公式變更為

Z=Y+S×R2 sin R1×|x1Xr-x2X（t）|（14）

其中：R1為0～2π的隨機數(shù)，R2為0～π的隨機數(shù)，這兩個參數(shù)決定了算法在下次迭代時的搜索方向和移動距離；x1和x2為黃金分割系數(shù)。

x1=-π+（1-δ）2π（15）

x2=-π+δ·2π（16）

δ=0.5（5-1）（17）

1.2.3? 融合正態(tài)云最優(yōu)解擾動

為了增強算法后期跳出局部最優(yōu)解的能力，本文融合了一種自適應(yīng)正態(tài)云最優(yōu)解擾動策略［22］，越到算法后期，擾動影響越大。正態(tài)云模型由云滴論域空間期望Ex、云團不確定性程度熵En和熵不確定性程度超熵He三個參數(shù)進行描述。正態(tài)云是服從正態(tài)分布云滴的一種算法，每一次運行都會生產(chǎn)一個云滴，直到生成期望數(shù)量的云滴，其生成過程如下：

X［x1，x2，…，xnd］=Gnc（Ex，En，He，Nd）（18）

其中：Nd表示生成的云滴數(shù)量。正態(tài)云分布圖如圖1所示。

Gbest=Xr·［λGnc（Ex，En，He，Nd）］（19）

λ=t2/T2（20）

其中：Gbest表示正態(tài)云擾動后的解；t表示當(dāng)前迭代次數(shù)；T表示總迭代次數(shù)；λ隨著迭代次數(shù)增大而增大，到算法后期，最優(yōu)解受正態(tài)云擾動影響也越大。

2? 改進動態(tài)窗口算法

2.1? 基礎(chǔ)動態(tài)窗口算法

動態(tài)窗口法（DWA）是一種用于局部避障的路徑規(guī)劃方法，在DWA中，機器人的速度約束條件如下：

0≤vt≤vmax

vt-amaxΔt≤vt+1≤vt+amaxΔt-ωmax≤ωt≤ωmax

ωt-αmaxΔt≤ωt+1≤ωt+αmaxΔt（21）

其中：vt和ωt分別表示機器人在t時刻的線速度和角速度；vmax和ωmax表示最大速度和最大角速度，vt+1和ωt+1分別為機器人在t+1時刻的線速度和角速度；amax和αmax分別表示最大線加速度和最大角加速度；Δt為時間步長。

可行速度集是通過對運動學(xué)模型相適配的速度空間進行采樣得到的，并且生成預(yù)測軌跡，這些軌跡由評估函數(shù)進行評分以找到最佳軌跡和對應(yīng)的速度集合。評估函數(shù)如式（22）所示，包括三個評估子函數(shù)及其權(quán)重w1、w2和w3，σ表示歸一化過程。

J（v，ω）=σ［w1·heading（v，ω）+w2·obdist（v，ω）+

w3·velocity（v，ω）］（22）

heading函數(shù)計算機器人在預(yù)測軌跡末端的方位角與機器人位置相對于目標方位角之間的角度差，角度差越大，函數(shù)值越小；obdist函數(shù)計算從預(yù)測軌跡的每個點到障礙物的最小距離，該函數(shù)用于評估軌跡遠離障礙物的程度，函數(shù)值越大則距離越大，若軌跡的最小距離小于安全距離，則該軌跡將直接放棄并從采樣空間中移除；velocity是評價機器人線速度和角速度的函數(shù)，線速度越高，角速度越小，得分越高。

若要求算法的全局搜索能力較強時，則權(quán)重w1設(shè)置較大一些；若要求機器人有較好的避障能力，則權(quán)重w2設(shè)置較大一些；若要求機器人行走路徑更平滑，則權(quán)重w3設(shè)置大一些。

基礎(chǔ)動態(tài)窗口算法在路徑規(guī)劃方面的應(yīng)用仍存在一些局限性：a）動態(tài)窗口進行動態(tài)避障后規(guī)劃的路徑與智能優(yōu)化算法規(guī)劃的路徑有一定差距，這也會增加路徑長度；b）動態(tài)窗口法與智能優(yōu)化算法不同，沒有設(shè)定一個初始的搜索方向，這也會增加路徑長度；c）子函數(shù)權(quán)重是固定值，在靠近障礙物時w2應(yīng)該設(shè)定較大進行避障，但這會削弱算法全局搜索性能，若w2設(shè)定過小就會撞上障礙物，且在復(fù)雜環(huán)境中基礎(chǔ)動態(tài)窗口出現(xiàn)無法規(guī)劃出路徑的情況。因此，本文提出三個策略以解決動態(tài)窗口算法存在的缺陷。

2.2? 改進動態(tài)窗口算法

2.2.1? 策略1：增加子函數(shù)pathdist（v，ω）

融合算法的原理是，在全局信息已知的條件下，先通過智能優(yōu)化算法計算出靜態(tài)環(huán)境下的最短路徑，記作minpath。機器人開始沿著該路徑行走，同時對周圍環(huán)境進行掃描，當(dāng)遇到動態(tài)障礙物時進行避障，改變當(dāng)前路徑。此時，基礎(chǔ)動態(tài)窗口規(guī)劃的路徑有可能會遠離最短路徑，為了保證規(guī)劃出的路徑最短，本文增加子函數(shù)pathdist（v，ω），其權(quán)重系數(shù)為w4。子函數(shù)的作用就是使算法選擇最靠近智能優(yōu)化算法規(guī)劃出的路徑，改進后的動態(tài)窗口算法評估函數(shù)為

J（v，ω）=σ［w1·heading（v，ω）+w2·obdist（v，ω）+

w3·velocity（v，ω）+w4·pathdist（v，ω）］（23）

dp1=（x1-xp1）2+（y1-yp1）2（24）

ψ=dp1+dp2+dp3+dp4+dp55（25）

pathdist=1ψ（26）

式（24）表示預(yù)測軌跡的起點到minpath的最短距離；dp1…dp5分別表示預(yù)測軌跡上均等分的五個點到路徑minpath的最短距離；（x1，y1）表示預(yù)測軌跡上第一個點的坐標；（xp1，yp1）為預(yù)測軌跡上第1個點到路徑minpath最短距離上的點；ψ表示衍射線5個點到minpath最短距離的加權(quán)平均距離，ψ越小，表示該預(yù)測軌跡與minpath最接近，pathdist的值就越大，評分就越高。算法會優(yōu)先選擇評分高的路徑，這樣能使動態(tài)窗口算法規(guī)劃出的路徑最接近智能優(yōu)化算法規(guī)劃出的minpath。

2.2.2? 策略2：自適應(yīng)權(quán)重策略

在遠離障礙物時，算法需要較強的局部搜索能力，靠近障礙物時需要較強的局部避障能力，但基礎(chǔ)動態(tài)窗口算法中各權(quán)重系數(shù)是固定的；此外在實驗中發(fā)現(xiàn)，如果動態(tài)障礙物的速度過快，就會使動態(tài)窗口算法避障不及時，碰上障礙物。因此本文提出自適應(yīng)權(quán)重，當(dāng)機器人靠近至障礙物一定距離后，自適應(yīng)控制權(quán)重w2增加，使算法具有更強的避障能力。具體思路如下：

首先計算機器人在當(dāng)前時刻的空間位置和障礙物之間的最短距離：

dro=（xr-xo）2+（yr-yo）2（27）

dall=（xs-xe）2+（ys-ye）2（28）

其中：dro表示機器人與障礙物之間的距離；（xr，yr）表示機器人當(dāng)前坐標位置；（xo，yo）表示動態(tài)障礙物的坐標位置；dall表示起點到終點的距離；（xs，ys）表示起點坐標位置；（xe，ye）表示終點坐標位置。

w2=（vt+ωt）×dalldro（29）

其中：vt和ωt分別表示機器人在t時刻的線速度和角速度。由此可知，w2權(quán)重大小與速度和角速度成正比，與距離dro成反比，當(dāng)機器人速度越快、越靠近障礙物時，w2權(quán)重越大，避障能力越強。

2.2.3? 策略3：設(shè)定動態(tài)航向角

動態(tài)窗口算法的初始方向和初始航向角的設(shè)定是隨機的，當(dāng)與目標柵格角度偏差過大時，會出現(xiàn)初期繞行甚至陷入死鎖無法規(guī)劃出完整路徑的現(xiàn)象。因此，本文提出以起點與第一個子目標點的連線和水平方向的夾角來動態(tài)規(guī)定初始方向，防止機器人繞行。

為了避免子目標點選擇不正確導(dǎo)致角度偏差帶來的影響，對起點周圍的節(jié)點進行篩選處理，根據(jù)周圍節(jié)點到目標點距離設(shè)置距離估值評分函數(shù)。具體操作如下：設(shè)（xs，ys）為當(dāng)前點，（xjn，yjn）為下一可行節(jié)點（沒有障礙物即可算作可行節(jié)點），（xgoal，ygoal）為目標節(jié)點。假設(shè)當(dāng)前點周圍不存在障礙物，均為可行區(qū)域，則n=1，2，3，…，8。分別計算可行節(jié)點距離估值評分函數(shù)的值：

h（dn）=d-min d（max d-min d）+ep（30）

其中：d=dsjn+djng，dsjn表示當(dāng)前節(jié)點到下一可行節(jié)點n的距離，djng表示下一可行節(jié)點n到目標節(jié)點的距離； min d表示可行節(jié)點到目標節(jié)點和當(dāng)前節(jié)點距離之和最短的距離；max d表示可行節(jié)點到目標節(jié)點和當(dāng)前節(jié)點距離之和最長的距離；ep表示很小的數(shù)，避免分母為0。當(dāng)下一可行節(jié)點離目標點越近，該函數(shù)值就越大，下一節(jié)點離終點越近；該函數(shù)值越小，下一節(jié)點離終點越遠。最后對可行節(jié)點進行排序，選擇函數(shù)值最大的節(jié)點做為第一個子目標點。

（xs，ys）為起點坐標，假設(shè)（x1，y1）為第一個子目標點，則初始航向角規(guī)定為

φ=arcsin c（31）

c=y1-ysdr1（32）

dr1=（x1-xs）2+（y1-ys）2（33）

其中：c是初始航向角的正弦值；dr1表示機器人到第一個子目標點的距離。

圖2（a）（b）是航向角對算法的影響示意圖。圖2（a）是未改進初始航向角的動態(tài)窗口算法，其一開始就繞行，而改進后的算法直接向下一個目標點行走，避免了路徑冗余。

2.3? 融合算法流程

改進動態(tài)窗口算法結(jié)合改進哈里斯鷹優(yōu)化算法的融合算法，以下簡稱IHHO-IDWA，其具體流程如圖3所示。

3? 實驗結(jié)果及分析

實驗環(huán)境：操作系統(tǒng)Windows 11（64bit），處理器AMD Ryzen 7 5800H with Radeon Graphics.3.20 GHz，運行內(nèi)存16 GB，仿真平臺MATLAB 2021a。

為了驗證改進哈里斯鷹算法和改進動態(tài)窗口算法的性能，設(shè)置了以下四組實驗：

a）數(shù)值實驗。設(shè)置國際通用測試函數(shù)和CEC2014函數(shù)驗證IHHO算法的性能。對照組算法為傳統(tǒng)算法GA、PSO，新型智能優(yōu)化算法GWO、HHO，改進智能優(yōu)化算法DCSOA-S［23］（融合螺旋策略的離散混沌群粒振蕩搜索算法）和GHHO［24］（融合能量周期性遞減與牛頓局部增強的改進HHO算法）。

b）路徑規(guī)劃實驗。設(shè)置兩張不同大小的地圖，驗證IHHO算法在路徑規(guī)劃中具有較好的性能。

c）動態(tài)窗口路徑規(guī)劃實驗。驗證IDWA比基礎(chǔ)DWA具有更好的性能。

d）融合算法實驗。驗證IHHO-IDWA的性能。對照組算法為PSO-DWA、HHO-DWA和DLSO-DWA。

參數(shù)設(shè)置：其中GA交叉概率Pc=0.8，變異概率Pm=0.1；PSO學(xué)習(xí)因子c1=2，c2=2，慣性權(quán)重ω=0.8；GWO系數(shù)A=2；DLSO哈里斯磨β=0.3。

為保證實驗公平性，每次實驗重復(fù)10次，每次算法運行10輪，統(tǒng)計其平均值和標準差。

3.1? 數(shù)值實驗

為驗證本文所提改進哈里斯鷹算法（IHHO）的性能，選擇了9個國際標準測試函數(shù)進行驗證，如表1所示。其中f1～f3是多維單峰函數(shù)，用于檢測算法局部搜索性能；f4～f6是多峰函數(shù)，用于檢驗算法全局尋優(yōu)能力；f7～f9為固維函數(shù)，檢驗算法平衡全局和局部搜索的能力。本次實驗統(tǒng)一設(shè)置維度D=30、種群規(guī)模N=30、T=500，各算法一致。

從表2的實驗結(jié)果可以看出，IHHO算法在f1～f3多峰函數(shù)的尋優(yōu)中較基礎(chǔ)的HHO和GHHO有明顯的提升，且IHHO都找到了最優(yōu)值，證明黃金正弦策略能夠幫助IHHO有更好的局部搜索能力；對于f4～f6多峰函數(shù)，IHHO較傳統(tǒng)算法GA、PSO和DCSOA-S，搜索的均值和標準差更小，證明IHHO有更好的穩(wěn)定性和全局搜索性能；對于固維函數(shù)f7～f9的搜索表現(xiàn)，IHHO算法和DCSOA-S算法性能相差不大，但相較于HHO和GHHO的平均值和標準差更小，搜索精度更高，且都搜索到了最優(yōu)值，證明了自適應(yīng)混沌和核心種群劃分策略，提高了算法平衡全局和局部搜索的能力?？傮w而言，改進IHHO算法性能最優(yōu)，算法在穩(wěn)定性、局部搜索能力以及全局搜索能力均有提升，說明融合三個改進策略能夠明顯提升算法性能。圖4為部分測試函數(shù)收斂曲線。

接下來選取了6個CEC2014測試函數(shù)，該函數(shù)更為復(fù)雜，分別有單峰函數(shù)（UN）、多峰函數(shù)（MN）、混合型函數(shù)（HF），如表3所示。表4為實驗結(jié)果，圖5為部分CEC2014函數(shù)的收斂曲線。

從表4可知，IHHO在更復(fù)雜的單峰、多峰和混合型函數(shù)尋優(yōu)中，IHHO的尋優(yōu)平均值和標準差比HHO算法提高了1～2個量級，提升明顯，證明了IHHO算法具有更好的穩(wěn)定性和尋優(yōu)能力。IHHO算法在對照組算法中性能最優(yōu)。

3.2? 基于改進哈里斯鷹的移動機器人路徑規(guī)劃

本節(jié)通過路徑規(guī)劃實驗來驗證本文算法的性能。實驗中種群規(guī)模N=30，迭代次數(shù)T=50。

為了對比改進前后的效果，定義優(yōu)化率為

η=μm-μ0μ0=Δμμ0（34）

其中：μm表示改進后算法規(guī)劃路徑的長度和算法運行時間；μ0表示改進前算法的路徑長度和算法運行時間。該等式能夠直接反映算法的優(yōu)化程度。

3.2.1? 40×40靜態(tài)地圖實驗

首先設(shè)置一張40×40的中型地圖，障礙物占比約為23%，驗證改進算法的性能，結(jié)果如表5和圖6所示。

從表5和圖6實驗結(jié)果可知，IHHO算法在40×40地圖表現(xiàn)中性能最優(yōu)，搜索到的最短路徑為62.769 6，較其他算法縮短了8.20%，運行時間也最短，證明了IHHO算法在路徑規(guī)劃中具有較好的搜索性能。圖6中，（a）為算法迭代曲線，（b）～（g）為各算法規(guī)劃出的路徑。

3.2.2? 50×50靜態(tài)地圖實驗

設(shè)置一張50×50，障礙物占比約為25%的大型地圖來驗證改進算法的性能。圖7為各算法的規(guī)劃結(jié)果。

從表6的實驗結(jié)果可知，在50×50地圖實驗中，IHHO規(guī)劃出的路徑最短，為78.669 0 m，相比其他算法縮短了12.66%，平均路徑縮短了13.84%，算法運行時間也最短，IHHO算法在路徑規(guī)劃中表現(xiàn)優(yōu)異，性能提升明顯。此外，從圖7可以看出，IHHO規(guī)劃出的路線最平滑，沒有路徑冗余。

3.3? 基于改進動態(tài)窗口的移動機器人路徑規(guī)劃

為驗證本文改進的動態(tài)窗口算法在移動機器人路徑規(guī)劃中的性能，將改進后的動態(tài)窗口算法（IDWA）與基礎(chǔ)動態(tài)窗口法（DWA）進行比較，分別在靜態(tài)和動態(tài)環(huán)境進行測試。

3.3.1? 改進動態(tài)窗口法在靜態(tài)地圖中的性能分析

首先在50×50的靜態(tài)地圖中進行實驗，設(shè)置起點坐標為（50，0），終點坐標為（0，50），實驗結(jié)果如圖8所示。

從圖8可以看出，在靜態(tài)地圖中，DWA沒有規(guī)劃出路徑，陷入了死鎖，在坐標（10，30）的位置時開始繞圈，無法到達終點；而IDWA能夠很好地完成路徑規(guī)劃，說明自適應(yīng)權(quán)重能夠更好地平衡IDWA的搜索性能和避障性能。

3.3.2? 改進動態(tài)窗口法在動態(tài)地圖中的性能分析

在50×50的動態(tài)地圖當(dāng)中進行實驗，設(shè)置三個動態(tài)障礙物不間斷移動，黑色圈代表動態(tài)障礙物。起點為（49，1），終點為（1，49），實驗結(jié)果如圖9所示。

圖9（a）（b）分別是DWA和IDWA正在進行避障的過程，（c）（d）分別是DWA和IDWA規(guī)劃出的最終路線圖?？梢钥吹剑珼WA規(guī)劃出的路徑一開始是向上行走，而IDWA規(guī)劃出的路徑一開始就是向終點行走，能縮短路程，且IDWA規(guī)劃的路徑能更少地繞彎，整體上規(guī)劃的路徑更優(yōu)。

在靜態(tài)地圖中，DWA陷入死鎖，沒有規(guī)劃出路徑，而IDWA完成了路徑規(guī)劃。如表7所示，在動態(tài)地圖中，IDWA規(guī)劃出的路徑相比DWA縮短了21.29%，時間上減少了26.46%。因此，IDWA的性能得到了明顯的提升。

3.4? IDWA和IHHO融合算法動態(tài)地圖實驗

本節(jié)將IDWA和IHHO結(jié)合，改進哈里斯鷹算法融合改進動態(tài)窗口算法（IHHO-IDWA）來進一步驗證算法性能，同時設(shè)置對照組算法分別為灰狼算法與動態(tài)窗口（GWO-DWA）、哈里斯鷹算法與動態(tài)窗口（HHO-DWA），雙種群混沌柯西變異的改進獅群算法［9］與動態(tài)窗口（DLSO-DWA）三種算法。

設(shè)置50×50大小的地圖，障礙物占比約為25%，設(shè)置四個動態(tài)障礙物。從表8的實驗結(jié)果來看，IHHO-IDWA性能最優(yōu)。

圖10是IHHO-IDWA路徑規(guī)劃的過程，選取了部分截圖，虛線是IHHO先進行規(guī)劃的最短路徑，紅色路線是啟動IDWA進行實時避障的路線（參見電子版）。圖10中，（a）是機器人碰到的第一個動態(tài)障礙物，進行避障；（b）顯示機器人繞開動態(tài)障礙物之后，沿著IHHO規(guī)劃出的路徑行走；（c）顯示機器人受到障礙物的影響，機器人行走路線與IHHO有所偏離，但之后又馬上回歸到IHHO規(guī)劃的路線；（d）顯示算法規(guī)避動態(tài)障礙物。

3.5? 參數(shù)敏感性分析

實驗中設(shè)置的種群規(guī)模和總迭代次數(shù)可能會影響實驗結(jié)果，在實驗環(huán)境和算法其他參數(shù)不變的情況下，在40×40和50×50地圖進行參數(shù)敏感性實驗。為避免偶然性，重復(fù)十次實驗，取結(jié)果的平均值。圖11為種群敏感性分析。

從圖11的分析結(jié)果得知，在40×40地圖中，種群規(guī)模在N=30時，算法搜索到最優(yōu)值，繼續(xù)增加種群規(guī)模，并不影響算法搜索的結(jié)果。在50×50地圖中，種群規(guī)模在30～40搜索到最優(yōu)值，但是隨著種群規(guī)模的增加，算法運行時間也增加，綜合考慮種群規(guī)模和運行時間，選擇N=30。

圖12是迭代次數(shù)對尋優(yōu)結(jié)果的影響分析?？梢钥吹?，在40×40地圖中，迭代次數(shù)為30時基本收斂，不會繼續(xù)搜索到最優(yōu)值。在50×50地圖中，算法在迭代40次左右時收斂到最優(yōu)值。迭代次數(shù)越多，運算時間越長，因此綜合考慮，T=50。

4? 結(jié)束語

針對動態(tài)環(huán)境下的移動機器人全局路徑規(guī)劃問題，本文提出了一種改進哈里斯鷹算法和改進動態(tài)窗口算法的融合算法。首先，針對哈里斯鷹算法后期搜索性能不足等問題，提出一種自適應(yīng)混沌和核心種群劃分策略，提高算法后期全局搜索性能；其次用黃金正弦替換原有的萊維飛行，提高算法的搜索效率；最后，融合正態(tài)云最優(yōu)解擾動提高算法后期跳出局部最優(yōu)解的能力。針對基礎(chǔ)動態(tài)窗口算法存在規(guī)劃的路徑長和易陷入死鎖等問題，提出了三個改進策略：增加子函數(shù)pathdist（v，ω）保證算法能夠規(guī)劃出更短的路徑；提出自適應(yīng)權(quán)重策略，平衡算法局部避障能力和全局搜索性能；設(shè)定初始航向角避免路徑冗余。最后，本文通過三組實驗分別驗證了改進哈里斯鷹算法、改進動態(tài)窗口算法與融合算法的性能。結(jié)果顯示，本文提出的融合算法路徑最短，路徑平均縮短了11.51%，性能提升顯著。

參考文獻：

［1］Hart P E，Nilsson N J，Raphael B.A formal basis for the heuristic determination of minimum cost paths［J］.IEEE Trans on Systems Science and Cybernetics，1968，4（2）：100-107.

［2］Kuffner J J，LaValle S M.RRT-connect：an efficient approach to single-query path planning［C］//Proc of IEEE International Confe-rence on Robotics and Automation.Piscataway，NJ：IEEE Press，2000：995-1001.

［3］孫睿彤，袁慶霓，衣君輝，等.改進粒子群算法和動態(tài)窗口法的動態(tài)路徑規(guī)劃［J］.小型微型計算機系統(tǒng)，2023，44（8）：1707-1712.（Sun Ruitong，Yuan Qingni，Yi Junhui，et al.Dynamic path planning by combing the improved particle swarm algorithm and dynamic window approach［J］.Journal of Chinese Computer Systems，2023，44（8）：1707-1712.）

［4］黃志鋒，劉媛華，張聰.多策略融合的改進獅群算法及其工程優(yōu)化［J/OL］.小型微型計算機系統(tǒng)（2023-02-09）.https：doi.org/10.20009/j.cnki.21-1106/TP.2021-0600.（Huang Zhifeng，Liu Yuanhua，Zhang Cong.Multi-strategy fusion improved lion swarm algorithm and its engineering optimization［J/OL］.Journal of Chinese Computer Systems（2023-02-09）.https：doi.org/10.20009/j.cnki.21-1106/TP.2021-0600.）

［5］黃志鋒，劉媛華.基于改進獅群算法的城市無人機低空路徑規(guī)劃［J］.信息與控制，2023，52（6）：747-757，772.（Huang Zhifeng，Liu Yuanhua.Urban UAV low altitude path planning based on improved lion swarm algorithm［J］.Information and Control，2023，52（6）：747-757，772.）

［6］Mirjalili S，Lewis A.The whale optimization algorithm［J］.Advances in Engineering Software，2016，95（5）：51-67.

［7］Heidari A A，Mirjalili S，F(xiàn)aris H，et al.Harris hawks optimization：algorithm and applications［J］.Future Generation Computer Systems，2019，97（8）：849-872.

［8］陳麒杰，晉玉強，韓露.無人機路徑規(guī)劃算法研究綜述［J］.飛航導(dǎo)彈，2020（5）：54-58.（Chen Qijie，Jin Yuqiang，Han Lu.Review of UAV path planning algorithms［J］.Aerospace Technology，2020（5）：54-58.）

［9］黃志鋒，劉媛華.基于四階貝塞爾曲線和改進獅群優(yōu)化算法求解路徑規(guī)劃問題［J］.信息與控制，2023，52（2）：176-189.（Huang Zhifeng，Liu Yuanhua.Solving path planning problem based on fourth-order Bezier curve and improved lion swarm optimization algorithm［J］.Information and Control，2023，52（2）：176-189.）

［10］劉志強，何麗，袁亮，等.采用改進灰狼算法的移動機器人路徑規(guī)劃［J］.西安交通大學(xué)學(xué)報，2022，56（10）：49-60.（Liu Zhiqiang，He Li，Yuan Liang，et al.Path planning of mobile robot based on TGWO algorithm［J］.Journal of Xian Jiaotong University，2022，56（10）：49-60.）

［11］張恒，何麗，袁亮，等.基于改進雙層蟻群算法的移動機器人路徑規(guī)劃［J］.控制與決策，2022，37（2）：303-313.（Zhang Heng，He Li，Yuan Liang，et al.Mobile robot path planning using improved double-layer ant colony algorithm［J］.Control and Decision，2022，37（2）：303-313.）

［12］Xu Lin，Cao Maoyong，Song Baoye.A new approach to smooth path planning of mobile robot based on quartic Bezier transition curve and improved PSO algorithm［J］.Neurocomputing，2022，473（2）：98-106.

［13］Molinos E J，Llamazares A，Ocaa M.Dynamic window based approaches for avoiding obstacles in moving［J］.Robotics and Autonomous Systems，2019，118（8）：112-130.

［14］Liu Lisang，Yao Jinxin，He Dongwei，et al.Global dynamic path planning fusion algorithm c ombining jump-A* algorithm and dynamic window approach［J］.IEEE Access，2021，9：19632-19638.

［15］Chang Lu，Shan Liang，Jiang Chao，et al.Reinforcement based mobile robot path planning with improved dynamic window approach in unknown environment［J］.Autonomous Robots，2021，45（1）：51-76.

［16］李薪穎，單梁，常路，等.復(fù)雜環(huán)境下基于多目標粒子群的DWA路徑規(guī)劃算法［J］.國防科技大學(xué)學(xué)報，2022，44（4）：52-59.（Li Xinying，Shan Liang，Chang Lu，et al.DWA path planning algorithm based on multi-objective particle swarm optimization in complex environment［J］.Journal of National University of Defense Technology，2022，44（4）：52-59.）

［17］蒲興成，譚令.基于自適應(yīng)動態(tài)窗口改進細菌算法與移動機器人路徑規(guī)劃［J］.智能系統(tǒng)學(xué)報，2023，18（2）：314-324.（Pu Xingcheng，Tan Ling.A mobile robot path planning method based on adaptive DWA and an improved bacteria algorithm［J］.CAAI Trans on Intelligent Systems，2023，18（2）：314-324.）

［18］魏立新，張鈺錕，孫浩，等.基于改進蟻群和DWA算法的機器人動態(tài)路徑規(guī)劃［J］.控制與決策，2022，37（9）：2211-2216.（Wei Lixin，Zhang Yukun，Sun Hao，et al.Robot dynamic path planning based on improved ant colony and DWA algorithm［J］.Control and Decision，2022，37（9）：2211-2216.）

［19］劉鈺銘，黃海松，范青松，等.基于改進A* DWA算法的移動機器人路徑規(guī)劃［J/OL］.計算機集成制造系統(tǒng).（2022-11-28）.https：//kns.cnki.net/kcms/detail/11.5946.TP.20221125.1957.004.html.（Liu Yuming，Huang Haisong，F(xiàn)an Qingsong，et al.Based on improved A*_DWA algorithm for mobile robot path planning［J/OL］.Computer Integrated Manufacturing System.（2022-11-28）.https：//kns.cnki.net/kcms/detail/11.5946.TP.20221125.1957.004.html.）

［20］劉小龍，梁彤纓.基于方形鄰域和隨機數(shù)組的哈里斯鷹優(yōu)化算法［J］.控制與決策，2022，37（10）：2467-2476.（Liu Xiaolong，Liang Tongying.Harris hawk optimization algorithm based on square neighborhood and random array［J］.Control and Decision，2022，37（10）：2467-2476.）

［21］Tanyildizi E，Demir G.Golden sine algorithm：a novel math-inspired algorithm［J］.Advances in Electrical and Computer Engineering，2017，17（2）：71-78.

［22］李德毅，劉常昱.論正態(tài)云模型的普適性［J］.中國工程科學(xué)，2004，6（8）：28-34.（Li Deyi，Liu Changyu.Study on the universality of the normal cloud model［J］.Strategic Study of CAE，2004，6（8）：28-34.）

［23］林之博，劉媛華.融合螺旋策略的離散混沌群粒振蕩搜索算法［J］.計算機應(yīng)用研究，2021，38（10）：3060-3066，3071.（Lin Zhibo，Liu Yuanhua.Dispersed chaotic swarm oscillation algorithm merged with spiral strategy［J］.Application Research of Computers，2021，38（10）：3060-3066，3071.）

［24］趙世杰，高雷阜，于冬梅，等.融合能量周期性遞減與牛頓局部增強的改進HHO算法［J］.控制與決策，2021，36（3）：629-636.（Zhao Shijie，Gao Leifu，Yu Dongmei，et al.An improved HHO algorithm combining periodic energy decrease and Newton local enhancement［J］.Control and Decision，2021，36（3）：629-636.）