New Grid Map Path Planning Based on Improved Artificial Fish Swarm Algorithm

NAVIGATE

Table of Contents

STATISTICS

Viewed313

Downloads423

New Grid Map Path Planning Based on Improved Artificial Fish Swarm Algorithm

[HTML] PDF下载 (423)

[1]JIANG Xiaodong,REN Yichen,ZHU Xiaodong.New Grid Map Path Planning Based on Improved Artificial Fish Swarm Algorithm[J].Journal of Zhengzhou University (Engineering Science),2024,45(03):55-63.[doi:10. 13705/ j. issn. 1671-6833. 2024. 03. 007]

Copy

Journal of Zhengzhou University (Engineering Science)[ISSN 1671-6833/CN 41-1339/T] Volume: 45 Number of periods: 2024 03 Page number: 55-63 Column: Public date: 2024-04-20

Title:: New Grid Map Path Planning Based on Improved Artificial Fish Swarm Algorithm

Author(s):: JIANG Xiaodong¹; REN Yichen²; ZHU Xiaodong¹; 1. School of Electrical and Information Engineering, Zhengzhou University, Zhengzhou 450001, China; 2. School of Computer Science and Engineering, Hong Kong University of Science and Technology, Hong Kong 999077, China

Keywords:: worm robots; artificial fish swarm algorithm; path planning; tabu search; grid map

CLC:: TP242TP391. 9

DOI:: 10. 13705/ j. issn. 1671-6833. 2024. 03. 007

Abstract:: Aiming at the problems of long paths, low accuracy and prone to local optima of the artificial fish swarm algorithm in robot path planning, an improved artificial fish swarm algorithm was proposed, which aimed to improve the efficiency and accuracy of the algorithm. An improved artificial fish swarm algorithm aimed at improving algorithm efficiency and accuracy was proposed in this study. Firstly, an optimization cycle was added to the algorithm′s foraging behavior to reduce the randomness of the algorithm′s selection of location points in path planning, enabling the robot to move towards the target point faster. Then, the tabu search algorithm was integrated, and the tabu table was introduced to record the path where the algorithm might fall into the local optimum, so that the algorithm can avoid the local optimum region when selecting new location points, and could avoid the algorithm′s local excessive cycle. At the same time, it could optimize the planned path, delete the paths between duplicate grid points, and ensure that there would be no duplicate grid points in the path. When the improved artificial fish swarm algorithm was applied to a new type of 3D raster map, simulation experiments showed that compared to other comparative algorithms, the average path length obtained by improving the artificial fish swarm algorithm in maps 1, 2 and 3 was reduced by 10%, 15% and 30%, respectively, and the success rate of path planning in complex maps was increased by 75%.

References:: [1] TIAN X, LIU L, LIU S, et al. Path planning of mobile robot based on improved ant colony algorithm for logistics[J]. Mathematical Biosciences and Engineering: MBE,2021, 18(4): 3034-3045.
[2] 欧阳海滨 , 全永彬 , 高立群 , 等 . 基于混合遗传粒子群优化算法的层次路径规划方法 [J]. 郑州大学学报 ( 工学版 ), 2020, 41(4): 34-40.OUYANG H B, QUAN Y B, GAO L Q, et al. Hierarchical path planning method for mobile robots based on hybrid genetic particle swarm optimization algorithm [ J].Journal of Zhengzhou University (Engineering Science),2020, 41(4): 34-40.
[3] 裴以建 , 杨超杰 , 杨亮亮 . 基于改进 RRT ∗ 的移动机 62 郑州大学学报 (工学版) 2024 年器人路径规划算法[J]. 计算机工程, 2019, 45(5):285-290, 297.PEI Y J, YANG C J, YANG L L. Path planning algorithm for mobile robot based on improved RRT ∗ [ J]. Computer Engineering, 2019, 45(5): 285-290, 297.
[4] 姚正华 , 任子晖 , 陈艳娜 . 基于人工鱼群算法的煤矿救援机器人路径规划 [J]. 煤矿机械 , 2014, 35(4):59-61.YAO Z H, REN Z H, CHEN Y N. Path planning formine rescue robot based on AFSA[ J]. Coal Mine Machinery,2014, 35(4): 59-61.
[5] 李晓磊 . 一种新型的智能优化方法 - 人工鱼群算法 [D]. 杭州 : 浙江大学 , 2003.LI X L. A new intelligent optimization method-artificialfish school algorithm[D]. Hangzhou: Zhejiang University,2003.
[6] 聂黎明 , 周永权 . 基于人工鱼群算法的机器人路径规划 [J]. 计算机工程与应用 , 2008, 44(32): 48-50, 63.NIE L M, ZHOU Y Q. Path planning of robot based on artificial fish-swarm algorithm[J]. Computer Engineering and Applications, 2008, 44(32): 48-50, 63.
[7] 张文辉 , 林子安 , 刘彤 , 等 . 基于改进人工鱼群算法的机器人路径规划 [J]. 计算机仿真 , 2016, 33(12):374-379, 448.ZHANG W H, LIN Z A, LIU T, et al. Robot path planning method based on modified artificial fish swarm algorithm [J]. Computer Simulation, 2016, 33(12): 374-379, 448.
[8] 黄宜庆 , 彭凯 , 袁梦茹 . 基于多策略混合人工鱼群算法的移动机器人路径规划 [J]. 信息与控制 , 2017, 46(3): 283-288.HUANG Y Q, PENG K, YUAN M R. Path planning for mobile robots based on multi-strategy hybrid artificial fish swarm algorithm[J]. Information and Control, 2017, 46(3): 283-288.
[9] 梁雪慧 , 赵嘉祺 . 人工鱼群与遗传混合算法在无人艇路径规划中的应用 [J]. 计算机工程与科学 , 2019, 41(5): 942-947.LIANG X H, ZHAO J Q. A hybrid algorithm of artificial fish swarm and genetic algorithm and its application in collision avoidance of unmanned surface vessels[J]. Computer Engineering & Science, 2019, 41(5): 942-947.
[10] 罗如学, 陈妙娜, 林继灿. 基于改进人工鱼群算法的机器人路径规划[ J]. 科学技术与工程, 2020, 20(23): 9445-9449.LUO R X, CHEN M N, LIN J C. Robot path planning based on improved artificial fish swarm algorithm [ J].Science Technology and Engineering, 2020, 20 ( 23):9445-9449.
[11] 胡致远, 王征, 杨洋, 等. 基于人工鱼群-蚁群算法的UUV 三维全局路径规划[ J]. 兵工学报, 2022, 43(7): 1676-1684.HU Z Y, WANG Z, YANG Y, et al. Three-dimensional global path planning for UUV based on artificial fish swarm and ant colony algorithm[J]. Acta Armamentarii,2022, 43(7): 1676-1684.
[12] LI F F, DU Y, JIA K J. Path planning and smoothing of mobile robot based on improved artificial fish swarm algorithm[J]. Scientific Reports, 2022, 12: 659.
[13] LI G Q, LIANG D W, ZHAO Q Y, et al. Improved artificial fish swarm algorithm approach to robot path planning problems[C]∥2020 5th International Conference on Automation, Control and Robotics Engineering ( CACRE). Piscataway: IEEE, 2020: 71-75.
[14] WANG F, ZHAO L, BAI Y. Path planning for unmanned surface vehicles based on modified artificial fish swarm algorithm with local optimizer [ J]. Mathematical Problems in Engineering, 2022, 2022: 1283374.
[15] QI B L, XIONG L Y, WANG L J, et al. A weights and improved adaptive artificial fish swarm algorithm for path planning[C]∥2019 IEEE 8th Joint International Information Technology and Artificial Intelligence Conference (ITAIC). Piscataway: IEEE, 2019: 1698-1702.
[16] 玄世龙, 许志远, 孙帅, 等. 基于禁忌搜索算法的无人船路径规划[J]. 船舶工程, 2022, 44(4): 8-13, 37.XUAN S L, XU Z Y, SUN S, et al. Path planning of unmanned ship based on the tabu search algorithm[J]. Ship Engineering, 2022, 44(4): 8-13, 37.
[17] 赵江, 王晓博, 郝崇清, 等. 栅格图特征提取下的路径规划建模与应用[J]. 计算机工程与应用, 2020, 56(10): 254-260.ZHAO J, WANG X B, HAO C Q, et al. Path planning modeling and application based on feature extraction of grid graph[J]. Computer Engineering and Applications, 2020, 56(10): 254-260.
[18] 樊征, 曹其新, 杨扬, 等. 面向移动机器人的拓扑地图自动生成[J]. 华中科技大学学报(自然科学版),2008, 36(增刊1): 163-166.FAN Z, CAO Q X, YANG Y, et al. Automatically generationof topological map for mobile robot[J]. Journal of Huazhong University of Science and Technology (Nature Science Edition), 2008, 36(S1): 163-166.
[19] 张三川, 明珠. 基于主动安全的改进人工势场局部路径规划研究[J]. 郑州大学学报(工学版), 2021, 42(5): 32-36, 55.ZHANG S C, MING Z. Research on improved local path planning of artificial potential field based on active safety[J]. Journal of Zhengzhou University (Engineering Science), 2021, 42(5): 32-36, 55.
[20] YOON S, YOON S E, LEE U, et al. Recursive path planning using reduced states for car-like vehicles on grid maps[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(5): 2797-2813.
[21] 朱晓东, 姜晓东, 曾庆山, 等. 一种仿生机器人的夹爪: CN113799164A[P]. 2021-12-17.ZHU X D, JIANG X D, ZENG Q S, et al. Clamping jaw of bionic robot: CN113799164A[P]. 2021-12-17.
[22] 朱晓东, 姜晓东, 曾庆山, 等. 一种机器人伸缩摆动机构及仿生机器人: CN114851245A[P]. 2022-08-05.ZHU X D, JIANG X D, ZENG Q S, et al. Robot telescopic swing mechanism and bionic robot: CN114851245A[P]. 2022-08-05.
[23] 彭金柱, 张建新, 曾庆山. 基于改进差分进化的3-RPS 机器人逆运动学参数标定[J]. 郑州大学学报(工学版), 2022, 43(5): 1-7, 38.PENG J Z, ZHANG J X, ZENG Q S. Inverse kinematic parameters calibration of 3-RPS parallel robot based on modified differential evolution[J]. Journal of Zhengzhou University (Engineering Science), 2022, 43(5): 1-7, 38.
[24] MIAO C W, CHEN G Z, YAN C L, et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[ J]. Computers & Industrial Engineering, 2021, 156: 107230.
[25] NAGAOKA K, MINOTE H, MARUYA K, et al. Passive spine gripper for free-climbing robot in extreme terrain [J]. IEEE Robotics and Automation Letters, 2018, 3(3): 1765-1770.
[26] 张蓝天, 王光霞, 刘旭, 等. 机器人栅格地图编码与索引方法[J]. 测绘工程, 2022, 31(3): 23-30.ZHANG L T, WANG G X, LIU X, et al. Coding and indexing method of robot grid maps [ J]. Engineering ofSurveying and Mapping, 2022, 31(3): 23-30.
[27] LI X Y, GAO L. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J ]. International Journal of Production Economics, 2016, 174: 93-110.
[28] ZHANG D Y, FU P. Robot path planning by generalized ant colony algorithm[J]. Applied Mechanics and Materials, 2014, 494-495: 1229-1232.

Similar References:

Memo

Last Update: 2024-04-29