无人靶车动态避障研究

魏振亚 魏振亚 崔国梁 宁涛 丁雨康

摘要：無人靶车是军事训练中必不可少的一部分。为了测试各类精准打击武器，需要无人靶车自主移动到目标点。由于测试武器的场地环境比较复杂，所以需要无人靶车躲避移动过程中突如其来的障碍物。基于贪心初始化算法的动态避障（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.