[1]李孟锡,何博侠,周 俣.基于A*和蚁群算法的移动机器人多目标路径规划方法[J].机械与电子,2021,(06):61-65.
　LI Mengxi,HE Boxia,ZHOU Yu.Multi-target Path Planning Method for Mobile Robot Based on A* and Ant Colony Algorithm[J].Machinery & Electronics,2021,(06):61-65.
点击复制

基于A*和蚁群算法的移动机器人多目标路径规划方法()
分享到：

机械与电子[ISSN:1001-2257/CN:52-1052/TH]

卷:
期数:
2021年06期
页码:
61-65
栏目:
智能工程
出版日期:
2021-06-23

文章信息/Info

Title:
Multi-target Path Planning Method for Mobile Robot Based on A* and Ant Colony Algorithm
文章编号:
１００１-２２５７ ( ２０２１ ) ０６-００６１-０５
作者:
李孟锡; 何博侠; 周 俣
南京理工大学机械工程学院,江苏 南京 ２１００９４
Author(s):
LI Mengxi ;  HE Boxia ;  ZHOU Yu
( School of Mechanical Engineering , Nanjing University of Science and Technology , Nanjing ２１００９４ , China )
关键词:
移动机器人; 多目标路径规划;  A*算法' target="_blank" rel="external">">*算法; 蚁群算法; 最优路径; 二维栅格地图
Keywords:
mobile robot ;  multi-target path planning ;  A* algorithm ;  ant colony algorithm ;  optimal path ;  two-dimensional grid map
分类号:
TP２４２
文献标志码:
A
摘要:
针对二维栅格地图下,移动机器人以最短路径遍历所有目标点的路径规划问题,提出一种基于启发信息扩展节点的 A*算法与混合蚁群算法相结合的路径规划方法.通过基于启发信息的节点扩展函数,解决A*算法扩展节点时,会造成无用计算的问题,提升规划效率.为改善蚁群算法易陷入局部最优解的缺点,提出一种混合蚁群算法,将粒子群算法思想融入蚁群算法加以优化,通过自适应方法调整蚁群算法信息素挥发因子,与最优解交叉变异,增强全局搜索能力.仿真实验表明:基于启发信息扩展节点的 A *算法相较于 A *算法,搜索节点减少 １３.１８％ ;混合蚁群算法求解的最优路径和平均路径均好于蚁群算法,并且在迭代过程中,不易陷入局部最优解.现实环境下,采用仿真参数进行实验,实验的结果也证明了该方法的有效性.
Abstract:
Aiming at the path planning problem of the mobile robot traversing all target points with the shortest path under the two-dimensional grid map , a path planning method based on the combination of the A* algorithm and hybrid ant colony algorithm based on heuristic information expansion node is proposed．Through the node expansion function based on heuristic information , it solves the problem of useless calculation when the A* algorithm expands the node , and improves the planning efficiency．In order to improve the shortcomings of the ant colony algorithm that is easy to fall into the local optimal solution , a hybrid ant colony algorithm is proposed．The particle swarm algorithm is integrated into the ant colony algorithm to optimize it so as to eliminate cross mutation and enhance global search capabilities．The simulation experiment shows that the A* algorithm based on heuristic information to expand nodes can reduce the search nodes by １３.１８％ compared with the A* algorithm ; the optimal path and average path solved by the hybrid ant colony algorithm are better than the ant colony algorithm , and in the iterative process , It is not easy to fall into the local optimal solution．In the real environment , the simulation parameters are used for experiments , and the experimental results also prove the effectiveness of the method．

参考文献/References:

[１] 蒲兴成,李俊杰,吴慧超,等 ． 基于改进粒子群算法的移动机器人多目标点路径规划[J] ． 智能系统学报, ２０１７ ,１２ ( ３ ): ３０１-３０９．

[２] 胡立坤,王帅军,吕智林,等 ． 移动机器人多目标搜寻的D*-蚁群融合算法[J] ． 小型微型计算机系统, ２０２０ , ４１(３ ): ４７１- ４７６．
[３] 曹祥红,李欣妍,魏晓鸽,等 ． 基于 Dijkstra-ACO 混合算法的应急疏散路径动态规划[J] ． 电子与信息学报,２０２０ , ４２ ( ６ ): １５０２-１５０９
[４] 黄辰,费继友,刘洋,等 ． 基于动态反馈 A*蚁群算法的平滑路径规划方法[J] ． 农业机械学报,２０１７ , ４８ ( ４ ):３４-４０ , １０２．
[５] 贾现召,戚恒亮,贾其苏,等 ． 实时路况下同城生鲜农产品配送路径优化[J] ． 江苏农业科学, ２０１７ , ４５ ( １７ ): ２９２-２９５．
[６] 王学武,严益鑫,顾幸生 ． 基于莱维飞行粒子群算法的焊接机器人路径规划[ J ] ． 控制与决策,２０１７ , ３２ ( ２ ):３７３-３７７．
[７] 于莹莹,陈燕,李桃迎 ． 改进的遗传算法求解旅行商问题[J] ． 控制与决策, ２０１４ , ２９ ( ８ ): １４８３-１４８８．
[８] 何庆,吴意乐,徐同伟 ． 改进遗传模拟退火算法在 TSP 优化中的应用[J] ． 控制与决策, ２０１８ , ３３ ( ２ ): ２１９-２２５．
[９] 高海昌,冯博琴,朱利 ． 智能优化算法求解 TSP 问题[J] ． 控制与决策, ２００６ , ２１ ( ３ ): ２４１-２４７ , ２５２．
[１０] 陶丽华,马振楠,史朋涛,等 ． 基于 TSP 问题的动态蚁群遗传算法 [J] ． 机 械设 计 与制 造,２０１９ ( １２ ): １４７-１４９ , １５４．
[１１] 张玉茹,王晨旸 ． 引入变异算子的改进贪心和蚁群混合算法[J] ． 计算机集成制造系统, ２０２０ , ２６ ( ３ ): ８６０-８７０．
[１２] LIN M X , YUAN K , SHI C Z , et al．Path planning of mobile robot based on improved A* algorithm [ C ]//２０１７ ２９th Chines Control and Decision Conference．New York : IEEE , ２０１７ : ３５７０-３５７６．[１３] 王雷,李明,刘志虎 ． 基于吸引场的蚁群算法在 TSP中的应用[J] ． 江苏大学学报(自然科学版), ２０１５ , ３(５ ): ５７３-５７７ , ５８２．
[１４] COUSINS S , GERKEY B , CONLEY K , et al．Sharing?software with ROS[ J ] ．IEEE?Robotics and automation magazine , ２０１０ , １７ ( ２ ): １２-１４．

相似文献/References:

[1]姜烽,申燚,张成,等.基于差分进化遗传优化的移动机器人轨迹跟踪控制[J].机械与电子,2016,(07):67.
　JIANG Feng,SHEN Yi,ZHANG Cheng,et al.[J].Machinery & Electronics,2016,(06):67.
[2]赵健,张阳.基于典型栅格地图的代价地图改进方法[J].机械与电子,2018,(12):73.
　ZHAO Jian,ZHANG Yang.Cost Map Improvement Method Based on Typical Grid Map[J].Machinery & Electronics,2018,(06):73.
[3]薛连杰,张彪,张霄远,等.移动机器人基于激光点云定位建图的汽车宽度与方位估计[J].机械与电子,2018,(06):76.
　XUE Lianjie,ZHANG Biao,ZHANG Xiaoyuan,et al.Width and Orientation Identification of Cars Based on Lidar Localization and Mapping[J].Machinery & Electronics,2018,(06):76.
[4]刘利波,张文明.基于智能蚁群算法的移动机器人轨迹规划[J].机械与电子,2017,(11):62.
　LIU Libo,ZHANG Wenming.Trajectory Planning of Mobile Robot Based on Intelligent Ant Colony Algorithm[J].Machinery & Electronics,2017,(06):62.
[5]李 涛,魏 强,付 龙,等.四旋翼两栖机器人姿态求解与控制[J].机械与电子,2015,(10):62.
　LI Tao,WEI Qiang,FU Long,et al.Attitude Solving and Control of an Amphibious Robot Based on Four-rotor[J].Machinery & Electronics,2015,(06):62.
[6]李明磊,赵 杰,李 戈.面向方形节点拓扑地图下的移动机器人路径规划算法研究[J].机械与电子,2015,(10):67.
　LI Minglei,ZHAO Jie,LI Ge.Research on Path Planning Algorithm for Mobile Robot Based on Square Nodes in Topological Map[J].Machinery & Electronics,2015,(06):67.
[7]王雄奇１,柯艳国２,吴贤斌３,等.基于虚拟墙的移动机器人路径跟踪与实时避障方法[J].机械与电子,2019,(11):76.
　,i,et al.A Virtual Wall-Based Path Tracking and Obstacle Avoidance Method for Mobile Robot[J].Machinery & Electronics,2019,(06):76.
[8]武 刚,许家元,邸 迪.基于快速进行平方算法的巡检机器人路径规划研究[J].机械与电子,2024,42(02):74.
　WU Gang,XU Jiayuan,DI Di.Research on Path Planning of Inspection Robot Based on Fast Marching Square Method Algorithm[J].Machinery & Electronics,2024,42(06):74.
[9]姜海猛,张志安,潘孝斌.基于 A * 与 DWA 算法的融合优化策略研究[J].机械与电子,2024,42(10):15.
　JIANG Haimeng,ZHANG Zhi an,PAN Xiaobin.Research on Fusion Optimization Strategy Based on A* and Dynamic Window Approach Algorithms[J].Machinery & Electronics,2024,42(06):15.

备注/Memo

备注/Memo:
收稿日期: ２０２１-０１-１８
基金项目:国家自然科学基金资助项目(５１５７５２８1);中央高校基本科研业务费专项资金资助项目(３０９１６０１１３０４)
作者简介:李孟锡 (１９９６－),男,河南济源人,硕士研究生,研究方向为机器人导航;何博侠 (１９７２－),男,甘肃西和人,博士,副教授,研究方向为机器视觉、工业人工智能等,通信作者;周 俣 (１９９７－),男,江苏东台人,硕士研究生,研究方向为机器人导航与控制.
更新日期/Last Update: 2021-06-22