计算机科学

计算机科学 ›› 2024, Vol. 51 ›› Issue (6A): 230500145-9.doi: 10.11896/jsjkx.230500145

• 人工智能 • 上一篇    下一篇

基于改进自适应蚁群算法的移动机器人路径规划

魏书鑫1,2, 王群京1,2, 李国丽1,2, 许家紫1,2, 文彦1,3   

  1. 1 安徽大学电气工程与自动化学院 合肥 230601
    2 安徽大学高节能电机及控制技术国家地方联合实验室 合肥 230601
    3 安徽大学互联网学院 合肥 230601
  • 发布日期:2024-06-06
  • 通讯作者: 王群京(wangqunjingii@ahu.edu.cn)
  • 作者简介:(z21301088@stu.ahu.edu.cn)
  • 基金资助:
    国家自然科学基金重点项目(51637001)

Path Planning for Mobile Robots Based on Modified Adaptive Ant Colony Optimization Algorithm

WEI Shuxin1,2, WANG Qunjing1,2, LI Guoli1,2, XU Jiazi1,2, WEN Yan1,3   

  1. 1 School of Electrical Engineering and Automation,Anhui University,Hefei 230601,China
    2 National Engineering Laboratory of Energy-Saving Motor & Control Technology,Anhui University,Hefei 230601,China
    3 School of Internet Academy,Anhui University,Hefei 230601,China
  • Published:2024-06-06
  • About author:WEI Shuxin,born in 1999,master.His main research interest is mobile robot path planning.
    WANG Qunjing,born in 1960,Ph.D,professor.His main research interests include electrical machines and their control systems,power electronics and electric drives.
  • Supported by:
    Key Program of the National Natural Science Foundation of China(51637001).

PDF (PC)

321

摘要： 针对传统的蚁群算法(Ant Colony Optimization,ACO)存在收敛速度慢、效率低、容易陷入局部最优值等缺点,提出了一种新的ACO变体。首先引入了一种新的具有方向信息的启发式机制,在迭代过程中添加方向指导,进一步提高了算法的收敛速度。其次,提出了一种改进的启发式函数,以增强目标的目的性并减少路径的转弯次数。然后,引入了一种改进的状态转移概率规则,提高了搜索效率并增加了种群多样性。此外,提出了一种不均匀分布初始信息素浓度的新方法,以避免盲目搜索。形成的新的ACO变体称为改进的自适应蚁群优化算法(Modified Adaptive Ant Colony Optimization,MAACO)。为了验证所提出的MAACO的有效性,基于3种不同的空间环境模式,与现有其他7种算法进行了一系列实验。在所有的仿真实验中,所提出的MAACO生成了标准偏差为零的最短路径,并且在最小收敛生成内实现了最少的转弯次数;就3个实验而言,其与最佳现有结果相比,转弯次数平均减少了两次,平均减少比例为22.2%。实验结果证明了MAACO在减少路径长度、减少转弯次数和提高收敛速度方面的优点和其在路径规划中的实用性和高效性。

关键词: 蚁群算法, 启发函数, 转移概率, 移动机器人, 路径规划

Abstract: For the traditional ACO has the disadvantages of slow convergence,low efficiency and easy to fall into local optimum,a new variant of ACO is proposed.Firstly,a new heuristic mechanism with directional information is introduced to add directional guidance in the iterative process,which further improves the convergence speed of the algorithm.Second,an improved heuristic function is proposed to enhance the purpose of the objective and reduce the number of turns in the path.Then,an improved state transfer probability rule is introduced to improve the search efficiency and increase the population diversity.In addition,a new method of unevenly distributing the initial pheromone concentration is proposed to avoid blind search.The new ACO variant is called the modified adaptive ant colony optimization algorithm(MAACO).To verify the effectiveness of the proposed MAACO,a series of experiments are conducted with seven other existing algorithms based on three different obstacle distribution environment patterns.In all simulation experiments,the proposed MAACO generates the shortest path with zero standard deviation and achieves the minimum number of turns within the minimum convergence generation.For the three experiments,the average reduction in the number of turns compared to the best available results is two,with a typical reduction of 22.2%.Experimental results demonstrate the advantages of MAACO in reducing path length,reducing the number of turns and increasing the convergence speed and its usefulness and efficiency in path planning.

Key words: Ant colony algorithm, Heuristic function, Transfer probability, Mobile robot, Path planning

中图分类号: 

  • TP242
[1]FOUNTAS N A,VAXEVANIDIS N M,STERGIOUS C I,et al.A virus evolutionary multi-objective intelligent tool path optimization methodology for 5axis sculptured surface CNC machining[J].Engineering With Computers,2016,33(7):375-391.
[2]WANG Q,TANG C L.Deep reinforcement learning for transportation network combinatorial optimization:A survey[J].Knowledge-Based Systems,2021 233(2):231-239.
[3]TAKWA T,SAOUSSEN K.A Simulated annealing-based re-commender system for solving the tourist trip design problem[J].Expert Systems with Applications,2021,186:115723-115731.
[4]HUYNH T,PHAM D,THANG T.New approach to solvingthe clustered shortest-path tree problem based on reducing the search space of evolutionary algorithm[J].Knowledge-Based Systems,2019,180(4):12-25.
[5]CHEN Y Q,GUO J L,YANG H D.Research on navigation of bidirectional A* algorithm based on ant colony algorithm[J].The Journal of Supercomputing,2021,77(2):1958-1975.
[6]OROZCO ROSAS U,PICOS K,PANTRIGO J J.Mobile robot path planning using a QAPF learning algorithm for known and unknown environments[J].IEEE Access,2022,10:84648-84663.
[7]LI Y J,WEI W,GAO Y,et al.PQ-RRT*:An improved path planning algorithm for mobile robots[J].Expert Systems with Applications,2020,152:113425-113436.
[8]ZHAO Y J,ZHENG Z,LIU Y.Survey on computational-intelligence-based UAV path planning[J].Knowledge-Based Systems,2018,158(5):54-64.
[9]LYU D D,CHEN Z W,CAI Z S.Robot path planning by leveraging the graph-encoded Floyd algorithm[J].Future Generation computer Systems,2021,122(7):204-208.
[10]HOLLAND J H.Adaptation in natural and artificial systems:An Introductory Analysis with Applications to Biology,Control,and Artificial Intelligence[M].Ann Arbor:University of Michigan Press,1975.
[11]CHONG Y,CHAI H Z,LI Y H.Automatic recognition of geomagnetic suitability areas for path planning of autonomous underwater vehicle[J].Marine Geodesy,2021,44(4):1-15.
[12]KATHEN M,FLORES I J,REINA D G.An informative path planner for a swarm of asvs based on an enhanced PSO with gaussian surrogate model components intended for water monitoring applications[J].Electronics,2021,10(13):1605-1609.
[13]DORIGO M,GAMBARDELLA L M.Ant colony system:A cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.
[14]DORIGO M,BIRATTARI M,STUTZLE,T.Ant colony optimization:artificial ants as a computational intelligence technique[J].IEEE Computational Intelligence Magazine,2006,1(6):28-39.
[15]FATEMIDOKHT H,RAFSANJANI M K.F-Ant:An effective routing protocol for ant colony optimization based on fuzzy logic in vehicular ad hoc networks[J].Neural Computing and Applications,2018,29(6):127-137.
[16]WANG X Y,YANG L,ZHANG Y,et al.Robot path planning based on improved potential field ant colony algorithm[J].Control and Decision,2018,33(10):1775-1781.
[17]ZHU Y,YOU X M,LIU S,et al.Research on Robot Path Planning Problem Based on Improved Ant Colony Algorithm[J].Computer Engineering and Applications,2018,54(19):129-134.
[18]HUI T.Research on robot optimal path planning method based on improved ant colony algorithm[J].International Journal of Computing Science and Mathematics,2021,13(1):80-89.
[19]MIAO C W,CHEN G Z,YAN C L.Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J].Computers and Industrial Engineering,2021,156(6):107230-107241.
[20]TAO Y,GAO H,REN F.A mobile service robot global path planning method based on ant colony optimization and fuzzy control[J].Applied Sciences,2021,11(8):3605-3621.
[21]HSU C H,JUANG C H.Multi-Objective continuous Ant-Colony-Optimized FC for robot Wall-Following control[J].Computational Intelligence Magazine IEEE,2013,8(3):28-40.
[22]LI X X,HU P.Robot 3D Path Planning Algorithm Based on Improved Elitist Potential Field Ant Colony Algorithm[J].Computer Science and Application,2021,11(4):849-858.
[23]ZHANG S C,PU J,SI Y N.An adaptive improved ant colony system based on population information entropy for path planning of mobile robot[J].IEEE Access,2021,9:24933-24945.
[24]LIU J H,YANG J G,GENG P.Robot global path planningbased on ant colony optimization with artificial potential field[J].Transactions of The Chinese Society of Agricultural Machinery,2015,46(9):18-27.
[25]LUO Q,WANG H B,ZHENG Y.Research on path planning of mobile robot based on improved ant colony algorithm[J].Neural Computing and Applications,2020,32:1555-1566.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发