[1]姜晓东,任奕辰,朱晓东.基于改进人工鱼群算法的蠕虫机器人路径规划[J].郑州大学学报(工学版),2024,45(03):55-63.[doi:10. 13705/ j. issn. 1671-6833. 2024. 03. 007]
　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]
点击复制

基于改进人工鱼群算法的蠕虫机器人路径规划()
分享到：

《郑州大学学报(工学版)》[ISSN:1671-6833/CN:41-1339/T]

卷:
45
期数:
2024年03期
页码:
55-63
栏目:
出版日期:
2024-04-20

文章信息/Info

Title:
New Grid Map Path Planning Based on Improved Artificial Fish Swarm Algorithm
文章编号:
1671-6833( 2024) 03-0055-09
作者:
姜晓东1;  任奕辰2;  朱晓东1
1. 郑州大学 电气与信息工程学院,河南 郑州 450001;2. 香港科技大学 计算机科学与工程学系,香港 999077
Author(s):
JIANG Xiaodong1; REN Yichen2; ZHU Xiaodong1
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
分类号:
TP242TP391. 9
DOI:
10. 13705/ j. issn. 1671-6833. 2024. 03. 007
文献标志码:
A
摘要:
针对人工鱼群算法在机器人路径规划中存在路径长、精度不高、易陷入局部最优等问题,提出了一种改进的人工鱼群算法,旨在提高算法效率及精度。首先,在算法觅食行为中加入寻优循环,减少算法在路径规划中选取位置点的随机性,使机器人能够更快地走向目标点;其次,融合禁忌搜索算法,通过引入禁忌表来记录算法陷入局部最优的路径,使算法在选取新位置点时能够避开局部最优区域,避免算法在局部过度循环,同时对规划出的路径进行优化处理,删去重复栅格点之间的路径,保证路径中没有重复的栅格点;最后,将改进后的人工鱼群算法应用在一种新型的三维栅格地图中。实验结果表明:相较于其他对比算法,在地图1、2、3 中改进人工鱼群算法所取得的平均路径长度分别减少了10%、15%、30%,在复杂地图中路径规划的成功率提高了75%。
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.

相似文献/References:

[1]杨文强,张素君,郭昊.求解仓储作业优化问题的多物种协同进化算法[J].郑州大学学报(工学版),2020,41(06):33.[doi:10.13705/j.issn.1671-6833.2019.03.030]
　YANG Wenqiang,ZHANG Sujun,GUO Hao.Operation Optimization of Warehousing by Multispecies Co-evolution Algorithm[J].Journal of Zhengzhou University (Engineering Science),2020,41(03):33.[doi:10.13705/j.issn.1671-6833.2019.03.030]

备注/Memo

备注/Memo:
收稿日期:2023-10-25;修订日期:2023-11-16
基金项目:国家科学自然基金资助项目(61806179)
通信作者:朱晓东(1970— ),男,河南安阳人,郑州大学副教授,博士,主要从事智能控制及智能信息处理方面的研究,E-mail:zhu_xd@ zzu. edu. cn。
更新日期/Last Update: 2024-04-29