無人靶車動態避障研究

魏振亞 魏振亞 崔國梁 寧濤 丁雨康

摘要：無人靶車是軍事訓練中必不可少的一部分。為了測試各類精準打擊武器，需要無人靶車自主移動到目標點。由于測試武器的場地環境比較復雜，所以需要無人靶車躲避移動過程中突如其來的障礙物?；谪澬某跏蓟惴ǖ膭討B避障（Greedy?Initialization?Dynamic?Obstacle?Avoidance?，?GIDOA）算法可以求解無人靶車動態避障路徑規劃問題（Dynamic?Obstacle?Avoidance?Routing?for?Unmanned?Target?Vehicle，?DOARUTV）。該算法在傳統的D*算法（Digital?Smart?Technologies?for?Amateur?Radio）的基礎上進行改進，結合貪心初始化算法，有效地探索了初始解，加快了算法迭代速度。為了驗證該算法的可行性和有效性，使用Python編程語言將GIDOA和迪克斯特拉算法（Dijkstra）、A*算法（A-star?Algorithm）?進行對比。實驗結果表明：GIDOA能夠解決具有動態避障功能的無人靶車問題，相比較Dijkstra算法和A*算法更適合DOARUTV的求解。

關鍵詞：避障?無人靶車?算法研究?動態規劃

中圖分類號：O221;TP242

Research?on?the?Dynamic?Obstacle?Avoidance?of?Unmanned?Target?Vehicles

WEI?Zhenya??CUI?Guoliang??NING?Tao??DING?Yukang

（Anhui?CUSP?Intelligent?Technology?Co.，?Ltd.，??Chuzhou，?Anhui?Province，?239299?China）

Abstract：The?unmanned?target?vehicle?is?an?indispensable?part?in?military?training.?In?order?to?test?various?types?of?precision?strike?weapons，?unmanned?target?vehicles?are?required?to?move?autonomously?to?target?points.?Due?to?the?complex?environment?of?the?sites?for?testing?weapons，?it?is?necessary?for?the?unmanned?target?vehicle?to?avoid?sudden?obstacles?during?moving.The?greedy?initialization?dynamic?obstacle?avoidance?（GIDOA）?algorithm?can?solve?the?dynamic?obstacle?avoidance?routing?for?unmanned?target?vehicles?（DOARUTV）.?The?algorithm?is?improved?on?the?basis?of?the?traditional?D*?（Digital?Smart?Technologies?for?Amateur?Radio）?algorithm?and?is?combined?with?the?greedy?initialization?algorithm，?and?it?effectively?explores?the?initial?solution?and?accelerates?the?iteration?speed?of?the?algorithm.?In?order?to?verify?the?feasibility?and?effectiveness?of?the?algorithm，?GIDOA?is?compared?with?the?Dijkstra?algorithm?and?the?a-star?algorithm?by?using?Python?programming?language.?Experimental?results?show?that?GIDOA?can?solve?the?problem?of?unmanned?target?vehicles?with?the?function?of?dynamic?obstacle?avoidance，?and?that?it?is?more?suitable?for?the?solution?of?DOARUTV?than?the?Dijkstra?algorithm?and?the?A*?algorithm.

Key?Words：?Obstacle?avoidance;?Unmanned?target?vehicle;?Algorithm?research;?Dynamic?planning

各類精導武器在現代戰爭中充當著至關重要的角色。近些年為了測試精導武器的精確打擊性常采用無人靶車充當標靶，這樣既滿足了實戰化的需求，又為訓練提供了強有力的保障。由于測試武器的場地往往選在山區或荒涼地帶，因此無人靶車在前往目標點時不得不考慮避障的問題。

目前國內外學者針對無人靶車的研究主要集中在智能避障算法研究和傳感器避障的研究方面。郭銀景等人[1]分析了人工勢場法的引力和斥力勢場模型，提出了基于人工勢場法的避障算法，解決了復雜環境和目標不可達到的問題。賈慶軒等人[2]提出一種基于A*算法的避障路徑規劃算法，通過大量實驗仿真驗證了該算法的有效性和可行性。遲旭等人[3]提出了一種改進的A*算法與動態窗口法相結合的機器人隨機避障算法，經對比試驗表明改進的A*算法比傳統A*算法尋的路徑更短。李清亮等人[4]考慮了無人艇航跡規劃以及自動避障問題，提出了基于精確罰函數的智能避障算法，最后通過大量仿真表明該算法可以規避航線上所有障礙物。隨著生物啟發式算法研究的不斷深入，李霜琳等人[5]將鴿群優化算法成功運用在機器人避障問題上，仿真結果顯示，所提的算法能提高路徑規劃和避障的性能。裴振兵等人[6]通過建立信息素啟發因子和期望啟發因子的互鎖關系，改進了蟻群算法，最后通過不同的測試案例驗證了該算法的有效性。

此外，在傳感器避障方面廣大學者做出了深入的研究，桑海泉等人[7]提出了一種多傳感器裝置的控制方法，最后通過仿真試驗驗證了這種方法的有效性。蔡卓凡等人[8]采用了超聲波傳感器避障設計，通過多個超聲波傳感器檢測車體和障礙物的距離實現避障功能，最后搭建了仿真平臺驗證了其方法的可靠性。隨著廣大科研工作者在強化學習領域不斷地深入研究，薛均曉等人[9]結合一種預測算法和深度學習的避障算法解決了艦載機動態避障問題。

本文提出了一種無人靶車動態避障路徑規劃問題（Dynamic?Obstacle?Avoidance?Routing?for?Unmanned?Target?Vehicle，?DOARUTV），設計了一種貪心初始化動態避障算法（Greedy?Initialization?Dynamic?Obstacle?Avoidance?，?GIDOA）解決DOARUTV問題。

• DOARUTV問題描述

1.1地圖編碼

本文使用柵格法[10]對DOARUTV問題進行環境建模。柵格法是將無人靶車的移動環境模擬成個具有二進制信息的網絡單元格，每個二進制信息網絡單元格的物理特性由無人靶車所行駛的步長決定。本文假設無人靶車一個步長表示一個單元格。此外，一個單元格內無論是否有障礙物或無人靶車均表示該單元格為1，并填充黑色。自由活動區域的單元格為0，并填充白色。由此使用柵格法對無人靶車行駛空間進行建模和編碼后，更貼近實際無人靶車實際運行環境，具體表述方法如圖1所示。

1.2地圖模型建立

本文假設無人靶車在規格為的柵格中移動，其中柵格是由自由可移動的柵格和障礙物集合組成，那么無人靶車行駛到目標點的可行路徑集合為。本文按照無人靶車的工作場地建立30×50的柵格地圖，即。假設無人靶車從靶車車廠出發即靶車車廠為無人靶車起始單元格，此外設靶車的目標點為。靶車起始位置不與靶車目標點單元格重合（本段提及符號的具體意義如表1所示）。

2.算法設計

本文在D*算法的基礎上提出一種基于貪心初始化的動態避障算法（Greedy?Initialization?Dynamic?Obstacle?Avoidance?，?GIDOA）具體步驟如下。

2.1貪心初始化

步驟1：將無障礙物的路徑存放進列表中。

步驟2：判斷是否已經到達目標點位，若已經到達則算法停止輸出當前最優解。若沒有到達目標點則繼續進行下一步。

步驟3：從出發在中挑選下一個目標點和，比較無人靶車從到的距離和到的距離，如若則將添加至目標路徑中并更新，接著跳轉到步驟2繼續新一輪的迭代。

2.2?D*算法

D*算法是一種啟發式路徑搜索算法，最初是由安東尼?斯坦茨（Anthony?Stentz）?[11]在1994年提出，并將其成功運用于美國火星探測器尋路中。他指出D*算法適用于未知的工作環境和復雜動態的移動環境。以下是D*算法的距離評估公式以及估價函數。

本文采取切比雪夫距離來表示無人靶車移動的距離，其中表示無人靶車行駛距離。具體如下：

D*算法的距離估價公式為

式（2）中?：表示為到當前目標點的實際距離成本，代表n到目標點的最佳距離成本。

D*算法的具體步驟如下所示。

步驟1：將放到中，判斷是否等于空，若則目標點設置錯誤。若則繼續執行算法。

步驟2：將當前子節點放入中，進行估價函數進行估算，若代價小則作為無人靶車下一個目標點。另外將子節點加入。

步驟3：?判斷中的子節點是否為目標節點，若是則輸入最優解，若不是則繼續迭代。

步驟4：擴張子節點放進中，計算。

步驟5：先判斷，再判斷?大小。若則跳轉至步驟6，若則跳轉至步驟1。若不在中則判斷?，若則將從刪除后添加至。

步驟6：更新值，將指針指向下一個。

步驟7：重新計算，計算后算法跳轉至步驟1進行新一輪的迭代。

3.實驗仿真

本文涉及的所有算法均采用Python語言編程，在Win10操作系統下，系統處理區AMD?Ryzen?5?3500U?with?Radeon?Vega?Mobile?Gfx@2.10?GHz（16.00GB?RAM）的機器上運行。測試案例為無人靶車工作場地生成的柵格圖，柵格圖大小為。本文將使用Dijkstra?算法、A*?算法和GIDOA算法進行對比實驗。其其中圓形為起始點，正方形點為目標點。實驗仿真結果如下所示。

• Dijkstra算法[12]?是求一個圖中一個點到其他所有點的最短路徑的算法。它的主要思想是計算一個節點到另一個節點的最短路徑，以從起始點為中心向外層逐步擴散直到擴散涉及目標點結束。此外，Dijkstra算法的特性決定了Dijkstra算法不可以實現動態避障的功能，因此不可以在無人靶車運行過程中動態添加障礙物來模擬動態效果。圖2為Dijkstra算法運行圖。

（2）A*算法[13]是一種圖形搜索和路徑規劃算法，它是通過估價函數來選擇下一個需要遍歷的節點，逐步找到問題的最短路徑。此外，A*算法的特性決定了A*算法不可以實現動態避障，因此無法在無人靶車運行過程中動態添加障礙物模擬動態效果。A*算法的運行圖如圖3所示。

（3）GIDOA算法運行圖如圖4所示，其中黑點代表動態出現的障礙物。

（4）將Dijkstra?算法、A*?算法和GIDOA?算法分別運行20次求得算法平均運行時間如表2所示，最佳結果是GIDOA算法。

• 結語

本文提出具有動態避障功能的無人靶車路徑規劃問題，首先建立了無人靶車移動的柵格地圖模型，接著設計了一種貪心初始化動態避障算法（Greedy?Initialization?Dynamic?Obstacle?Avoidance?，?GIDOA）。通過實驗對比表明：一種貪心初始化動態避障算法（Greedy?Initialization?Dynamic?Obstacle?Avoidance?，?GIDOA）可以解決無人靶車運行過程中出現的動態障礙物。由表2可知GIDOA算法運行時間為Dijkstra算法的32.28%，為A*算法的54.99%。綜上所述，GIDOA算法可以解決一種無人靶車動態避障路徑規劃問題。此外，在算法求解效率上，GIDOA算法優于Dijkstra算法和A*算法。

參考文獻

• 郭銀景，劉琦，鮑建康，等.基于人工勢場法的?AUV?避障算法研究綜述[J].?計算機工程與應用，2020，56（4）：16-23.
• 賈慶軒，陳鋼，孫漢旭，等.基于A*算法的空間機械臂避障路徑規劃[J].機械工程學報，2010，46（13）：109-115.
• 遲旭，李花，費繼友.基于改進A*算法與動態窗口法融合的機器人隨機避障方法研究[J].儀器儀表學報，2021，42（3）：?132-140.
• 李清亮，李彬，孫國皓，等.基于精確罰函數的無人艇航跡規劃和自動避障算法[J].中國艦船研究，2021，?16（1）：?89-?95.
• 李霜琳，何家皓，敖海躍，等.基于鴿群優化算法的實時避障算法[J].北京航空航天大學學報，?2021，?47（2）：?359-365.
• 裴振兵，?陳雪波.改進蟻群算法及其在機器人避障中的應用[J].智能系統學報，?2015，?10（1）：?90-96.
• 桑海泉，王碩，譚民，等.基于紅外傳感器的仿生機器魚自主避障控制[J].系統仿真學報，?2005，?17（6）：?1400-?1404.
• 蔡卓凡.基于多超聲波傳感器避障機器人小車的設計[J].自動化技術與應用，2014，?33（5）：?85-?89.
• 薛均曉，孔祥燕，郭毅博，等.基于深度強化學習的艦載機動態避障方法[J].計算機輔助設計與圖形學學報，?2021?，33（7）：?1102-1112.
• Howden，?William?E.?"The?sofa?problem.?“The?computer?journal11.3?（1968）：?299-301.
• STENTZ?A.?Optimal?and?efficient?path?planning?for?partially-known?environments[C]//Proceedings?of?the?1994?IEEE?international?conference?on?robotics?and?automation.?IEEE，?1994.
• ZHU?D?D，SUN?J?Q?"A?new?algorithm?based?on?Dijkstra?for?vehicle?path?planning?considering?intersection?attribute."?IEEE?Access9?（2021）：?19761-19775.
• JU?C?Y，LUO?Q?H，YAN?X?Z?"Path?planning?using?an?improved?a-star?algorithm."2020?11th?International?Conference?on?Prognostics?and?System?Health?Management?（PHM-2020?Jinan）.?IEEE，?2020.