基于改进A*算法的路径规划在海战兵棋推演中的应用

doi:10.12382/bgxb.2021.0209

摘要/Abstract

摘要： 为满足海战兵棋推演中多目标路径规划的需求，解决传统A^*算法无法在兵棋推演中直接运用的问题，提出一种可供类似兵棋推演环境参考、基于改进A^*算法的路径规划方法。建立一种映射机制，实现了A^*算法在兵棋推演环境中的初步运用。构建一种既能满足多目标需求又能保证生成最优路径的估价函数。为验证算法有效性，在实际推演平台上进行了相关实验。结果表明，改进A^*算法可较好地统筹多个决策目标之间的关系，有效提升路径方案的质量，解决使用A^*算法在海战兵棋推演中进行最优路径规划的实际问题。

关键词: 海战, 兵棋推演, 路径规划, A^*算法

Abstract: A path planning method based on improved A^* algorithm is proposed, which can be used as a reference for similar war gaming environment. The proposed method is to meet the needs of multi-objective path planning in war gaming of naval warfare and solve the problem that traditional A^* algorithm cannot be directly used in war gaming. A mapping mechanism is constructed to realize the preliminary application of A^* algorithm in war gaming environment，and an evaluation function is constructed to improve the A^* algorithm, which can not only meet the multi-objective needs, but also ensure the generation of the optimal path. In order to verify the effectiveness of the improved A^* algorithm, the experiment was carried out on a war gaming platform of naval warfare. The result shows that the proposed method can be used to coordinate the relationship between multiple decision indicators well, effectively improve the quality of path scheme, and solve the practical problem of using A^* algorithm to carry out the optimal path planning in war gaming of naval warfare.

Key words: navalwarfare, wargaming, pathplanning, A^*algorithm

中图分类号:

E917

张韬, 项祺, 郑婉文, 孙宇祥, 周献中. 基于改进A^*算法的路径规划在海战兵棋推演中的应用[J]. 兵工学报, 2022, 43(4): 960-968.

ZHANG Tao, XIANG Qi, ZHENG Wanwen, SUN Yuxiang, ZHOU Xianzhong. Application of Path Planning Based on Improved A^* Algorithm in War Gaming of Naval Warfare[J]. Acta Armamentarii, 2022, 43(4): 960-968.

参考文献

［1］胡晓峰, 贺筱媛, 陶九阳. AlphaGo的突破与兵棋推演的挑战［J］. 科技导报, 2017, 35(21):49-60.
HU X F, HE X Y, TAO J Y. The breakthrough of A-lphaGo and the challenge of wargame deduction［J］. Science & Technology Review, 2017, 35(21):49-60. (in Chinese)
［2］孟二龙, 高桂清, 王康, 等. 智能化战争中计算机兵棋发展建设［J］. 兵工自动化, 2020, 39(10):76-79.
MENG E L, GAO G Q, WANG K, et al. Development and construction of computer war game in intelligent warfare［J］. Ordnance Industry Automation, 2020, 39(10):76-79. (in Chinese)
［3］任双堂, 曹亚铂, 赵林. 战争的再现——兵棋推演的发展脉络［J］. 军事文摘, 2020(19):7-11.
RENG S T, CAO Y B, ZHAO L. Reappearance of war: the development of wargame deduction［J］. Military Digest, 2020(19):7-11. (in Chinese)
［4］杨旭, 王锐, 张涛. 面向无人机集群路径规划的智能优化算法综述［J］. 控制理论与应用, 2020, 37(11):2291-2302.
YANG X, WANG R, ZHANG T. Review of unmanned aerial vehicle swarm path planning based on intelligent optimization［J］. Control Theory & Applications, 2020, 37(11):2291-2302. (in Chinese)
［5］ FRANTISEK D, ANDREJ B, MARTIN K, et al. Path planning with modified a star algorithm for a mobile robot［J］. Procedia Engineering, 2014, 96:59-69.
［6］ SIREGAR B, GUNAWAN D, ANDAYANI U, et al. Food delivery system with the utilization of vehicle using geographical information system (GIS) and A-Star algorithm［J］. Journal of Physics: Conference Series,2017, 801(1):012038.
［7］张新艳, 邹亚圣. 基于改进A^*算法的自动导引车无碰撞路径规划［J］. 系统工程理论与实践, 2021, 41(1):240-246.
ZHANG X Y, ZOU Y S. Collision-free path planning for automated guided vehicles based on improved A^* algorithm［J］. Systems Engineering-Theory & Practice, 2021, 41(1):240-246. (in Chinese)
［8］ WEI L X, PAN D, LIAO M J. Application of reverse car-seeking in large underground parking lot based on A-Star algorithm: a real case［J］. Scientific Research and Reviews, 2020, 13:116.
［9］ BAGHERI S M, TAGHADDOS H, MOUSAEI A, et al. An A-Star algorithm for semi-optimization of crane location and configuration in modular construction［J］. Automation in Construction, 2021, 121:103447.
［10］ MONTOYA-ARAQUE E A, SUAREZ-BURGOA L O. Automatic generation of tortuous failure surfaces in block-in-matrix materials for 2D slope stability assessments［J］. Computers and Geotechnics, 2019, 112:17-22.
［11］ HASEEB K, ISLAM N, SABA T, et al. LSDAR: a light-weight structure based data aggregation routing protocol with secure internet of things integrated next- generation sensor networks［J］. Sustainable Cities and Society, 2020, 54:101995.
［12］岳秀, 张超峰, 张伟, 等. 基于A^*和改进模拟退火算法的航迹规划［J］. 控制工程, 2020, 27(8):1365-1371.
YUE X, ZHANG C F, ZHANG W, et al. UAV path planning based on A^* algorithm and improved simulated annealing algorithm［J］. Control Engineering of China, 2020, 27(8):1365-1371. (in Chinese)
［13］张哲, 吴剑, 代冀阳, 等. 基于改进A^*算法的多无人机协同战术规划［J］. 兵工学报, 2020, 41(12): 2530-2539.
ZHANG Z, WU J, DAI J Y, et al. Cooperative tactical planning for multi-UAVs based on improved A^* algorithm［J］. Acta Armamentarii, 2020, 41(12): 2530-2539. (in Chinese)
［14］梁文勇, 严碧武, 王海涛, 等. 自动航迹规划在无人机电力巡检中的应用［J］. 电工技术, 2019(10):144-146， 149.
LIANG W Y, YAN B W, WANG H T, et al. Application of automatic path planning in power inspection with UAV［J］. Electric Engineering, 2019(10):144-146， 149. (in Chinese)
［15］杨瑶, 付克昌, 蒋涛, 等. 改进A^*算法的智能车路径规划研究［J］. 计算机测量与控制, 2020, 28(10):170-176.
YANG Y, FU K C, JIANG T, et al. Research on intelligent vehicle path planning based on improved A^* algorithm［J］. Computer Measurement & Control, 2020, 28(10):170-176. (in Chinese)
［16］ HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths［J］. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2):100-107.
［17］ KANG N K, SON H J, LEE S H. Modified A-Star a-lgorithm for modular plant land transportation［J］. Journal of Mechanical Science and Technology, 2018, 32 (12):5563-5571.
［18］ YANG D, XU B, RAO K Y, et al. Passive infrared (PIR)-based indoor position tracking for smart homes using accessibility maps and A-Star algorithm［J］. Sensors, 2018, 18(2):332.
［19］劳彩莲, 李鹏, 冯宇. 基于改进A^*与DWA算法融合的温室机器人路径规划［J］. 农业机械学报, 2021, 52(1):14-22.
LAO C L, LI P, PENG Y. Path planning of greenho-use robot based on fusion of improved A^* algorithm and dynamic window approach［J］. Transactions of the Chinese Society for Agricultural Machinery, 2021, 52(1):14-22. (in Chinese)
［20］ KUMAR N, VAMOSSY Z, SZABO-RESCH Z M. H-euristic approaches in robot navigation［C］∥Proceedings of the 2016 IEEE 20th Jubilee International Conference on Intelligent Engineering Systems. Budapest, Hungary: IEEE, 2016:219-222.



下3篇留版

[1]	郭威，吴凯，周悦，孙洪鸣，徐高飞，高森. 基于蚁群算法的深海着陆车路径规划[J]. 兵工学报, 2022, 43(6): 1387-1394.
[2]	田洪清，王建强，黄荷叶，丁峰. 越野环境下基于势能场模型的智能车概率图路径规划方法[J]. 兵工学报, 2021, 42(7): 1496-1505.
[3]	邓海鹏，麻斌，赵海光，吕良，刘宇. 自主驾驶车辆紧急避障的路径规划与轨迹跟踪控制[J]. 兵工学报, 2020, 41(3): 585-594.
[4]	张哲，吴剑，代冀阳，李品伟. 基于改进A^*算法的多无人机协同战术规划[J]. 兵工学报, 2020, 41(12): 2530-2539.
[5]	孙鹏耀，黄炎焱，潘尧. 基于改进势场法的移动机器人路径规划[J]. 兵工学报, 2020, 41(10): 2106-2121.
[6]	黄涛，刘志兵，王西彬，潘霖，闫正虎，冷寿阳. 刀轴侧倾角对薄壁叶片加工变形的影响[J]. 兵工学报, 2018, 39(3): 577-583.
[7]	王续跃，吕书森，胡亚峰，王连吉，徐文骥. 模具钢微流道沟槽的激光铣削试验研究[J]. 兵工学报, 2010, 31(5): 592-597.
[8]	纪小刚，龚光容. 三坐标测量机中基于遗传算法的多特征测量路径规划研究[J]. 兵工学报, 2005, 26(3): 392-396.
[9]	1:谷东兵，宋正勋;2:胡豁生，布雷德.麦克. 移动机器人的局部路径规划与控制[J]. 兵工学报, 2000, 21(1): 53-56.