[1]蔡军,钟志远.改进蚁群算法的送餐机器人路径规划[J].智能系统学报,2024,19(2):370-380.[doi:10.11992/tis.202205056]
CAI Jun,ZHONG Zhiyuan.Path planning of a meal delivery robot based on an improved ant colony algorithm[J].CAAI Transactions on Intelligent Systems,2024,19(2):370-380.[doi:10.11992/tis.202205056]
点击复制
CAI Jun,ZHONG Zhiyuan.Path planning of a meal delivery robot based on an improved ant colony algorithm[J].CAAI Transactions on Intelligent Systems,2024,19(2):370-380.[doi:10.11992/tis.202205056]
改进蚁群算法的送餐机器人路径规划
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
19
期数:
2024年第2期
页码:
370-380
栏目:
学术论文—智能系统
出版日期:
2024-03-05
- Title:
- Path planning of a meal delivery robot based on an improved ant colony algorithm
- Keywords:
- ant colony algorithm; genetic algorithm; state transition formula; fitness function; guiding element; local optimum; initial population; time window constraint; path planning
- 分类号:
- TP273
- 文献标志码:
- 2023-11-17
- 摘要:
- 蚁群算法拥有良好的全局性、自组织性、鲁棒性，但传统蚁群算法存在许多不足之处。为此，针对算法在路径规划问题中的缺陷，在传统蚁群算法的状态转移公式中，引入目标点距离因素和引导素，加快算法收敛性和改善局部最优缺陷。在带时间窗的车辆路径问题（vehicle routing problem with time windows，VRPTW）上，融合蚁群算法和遗传算法，并将顾客时间窗宽度以及机器人等待时间加入蚁群算法状态转移公式中，以及将蚁群算法的解作为遗传算法的初始种群，提高遗传算法的初始解质量，然后进行编码，设置违反时间窗约束和载重量的惩罚函数和适应度函数，在传统遗传算法的交叉、变异操作后加入了破坏?修复基因的操作来优化每一代新解的质量，在Solomon Benchmark算例上进行仿真，对比算法改进前后的最优解，验证算法可行性。最后在餐厅送餐问题中把带有障碍物的仿真环境路径规划问题和VRPTW问题结合，使用改进后的算法解决餐厅环境下送餐机器人对顾客服务配送问题。
- Abstract:
- The ant colony algorithm has advantages, such as good global ability, self-organization, and robustness, but the conventional ant colony algorithm has several drawbacks. Herein, with the goal of addressing these drawbacks, in the path planning problem, according to the conventional ant colony algorithm, the distance factor of the target point and the guide element are added to the state transition formula to optimize the convergence of the ant colony algorithm in the path planning and enhance the defect of local optimal point. On the vehicle routing problem with time window (VRPTW), the ant colony algorithm and genetic algorithm are combined, and the customer time window width and robot waiting time are added to the state transition formula of the ant colony algorithm. The solution of the ant colony algorithm is taken as the initial population of the genetic algorithm to enhance the quality of the initial solution of the genetic algorithm, and subsequently, coding is conducted. The penalty function and fitness function violating the time window constraint and load are set. After the mutation and crossover operation of the conventional genetic algorithm, the damage and repair gene operation is added to optimize the quality of each generation of new solutions. Simulations are performed on the Solomon benchmark example, and the optimal solutions before and after enhancement of the algorithm are compared to confirm the feasibility of the algorithm. To apply this to a real-world problem, the path planning problem in a simulative environment with obstacles and the VRPTW problem are joined using the enhanced algorithm to solve the customer service delivery problem of the restaurant delivery robot.
- 参考文献/References:
-
[1] 陶永, 王田苗, 刘辉, 等. 智能机器人研究现状及发展趋势的思考与建议[J]. 高技术通讯, 2019, 29(2): 149–163
TAO Yong, WANG Tianmiao, LIU Hui, et al. Insights and suggestions on the current situation and development trend of intelligent robots[J]. Chinese high technology letters, 2019, 29(2): 149–163
[2] KUANG Hua, XU Zhipeng, LI Xingli, et al. An extended car-following model accounting for the average headway effect in intelligent transportation system[J]. Physica A:statistical mechanics and its applications, 2017, 471: 778–787.
[3] POOLE A, KOTSIALOS A. Swarm intelligence algorithms for macroscopic traffic flow model validation with automatic assignment of fundamental diagrams[J]. Applied soft computing, 2016, 38: 134–150.
[4] CHMIEL W, DA?DA J, DZIECH A, et al. INSIGMA: an intelligent transportation system for urban mobility enhancement[J]. Multimedia tools and applications, 2016, 75(17): 10529–10560.
[5] 程志, 张志安, 李金芝, 等. 改进人工势场法的移动机器人路径规划[J]. 计算机工程与应用, 2019, 55(23): 29–34
CHENG Zhi, ZHANG Zhian, LI Jinzhi, et al. Mobile robots path planning based on improved artificial potential field[J]. Computer engineering and applications, 2019, 55(23): 29–34
[6] WANG Xiuhong, LIU Xuehao, WANG Yongcheng, et al. Research on path planning of mobile robot based on improved A* algorithm[C]//IE&EM 2019. Singapore: Springer, 2020: 153-161.
[7] WANG Huijuan, YU Yuan, YUAN Quanbo. Application of Dijkstra algorithm in robot path-planning[C]//2011 Second International Conference on Mechanic Automation and Control Engineering. Hohhot. IEEE, 2011: 1067-1069.
[8] ELHOSENY M, THARWAT A, HASSANIEN A E. Bezier curve based path planning in a dynamic field using modified genetic algorithm[J]. Journal of computational science, 2018, 25: 339–350.
[9] SONG Baoye, WANG Zidong, SHENG Ligang. A new genetic algorithm approach to smooth path planning for mobile robots[J]. Assembly automation, 2016, 36: 138–145.
[10] FERNANDES C M, MORA A M, MERELO J J, et al. KANTS: a stigmergic ant algorithm for cluster analysis and swarm art[J]. IEEE transactions on cybernetics, 2014, 44(6): 843–856.
[11] 陈嘉林, 魏国亮, 田昕. 改进粒子群算法的移动机器人平滑路径规划[J]. 小型微型计算机系统, 2019, 40(12): 2550–2555
CHEN Jialin, WEI Guoliang, TIAN Xin. Smooth path planning for mobile robots based on improved particle swarm optimization algorithm[J]. Journal of Chinese computer systems, 2019, 40(12): 2550–2555
[12] ALAM M S, RAFIQUE M U, KHAN M U. Mobile robot path planning in static environments using particle swarm optimization[EB/OL]. (2020-08-23)[2021-01-01].https://arxiv.org/abs/2008.10000.pdf.
[13] PATLE B K, PANDEY A, JAGADEESH A, et al. Path planning in uncertain environment by using firefly algorithm[J]. Defence technology, 2018, 14(6): 691–701.
[14] JIANG Tao, WANG Jianzhong. Study on path planning method for mobile robot based on fruit fly optimization algorithm[J]. Applied mechanics and materials, 2014, 536/537: 970–973.
[15] PANDA M, DAS B, PATI B B. Grey wolf optimization for global path planning of autonomous underwater vehicle[C]//Proceedings of the Third International Conference on Advanced Informatics for Computing Research. New York: ACM, 2019: 1-6.
[16] 楼传炜, 葛泉波, 刘华平, 等. 无人机群目标搜索的主动感知方法[J]. 智能系统学报, 2021, 16(3): 575–583
LOU Chuanwei, GE Quanbo, LIU Huaping, et al. Active perception method for UAV group target search[J]. CAAI transactions on intelligent systems, 2021, 16(3): 575–583
[17] 徐玉琼, 娄柯, 李志锟. 基于变步长蚁群算法的移动机器人路径规划[J]. 智能系统学报, 2021, 16(2): 330–337
XU Yuqiong, LOU Ke, LI Zhikun. Mobile robot path planning based on variable-step ant colony algorithm[J]. CAAI transactions on intelligent systems, 2021, 16(2): 330–337
[18] 夏小云, 周育人. 蚁群优化算法的理论研究进展[J]. 智能系统学报, 2016, 11(1): 27–36
XIA Xiaoyun, ZHOU Yuren. Advances in theoretical research of ant colony optimization[J]. CAAI transactions on intelligent systems, 2016, 11(1): 27–36
[19] CAO Jingang. Robot global path planning based on an improved ant colony algorithm[J]. Journal of computer and communications, 2016, 4(2): 11–19.
[20] TSAI P W, NGUYEN T T, DAO T K. Robot path planning optimization based on multiobjective grey wolf optimizer[C]// International Conference on Genetic and Evolutionary Computing. Cham: Springer, 2017: 166-173.
[21] 张毅, 杨光辉, 花远红. 基于改进人工鱼群算法的机器人路径规划[J]. 控制工程, 2020, 27(7): 1157–1163
ZHANG Yi, YANG Guanghui, HUA Yuanhong. Robot path planning based on improved artificial fish swarm algorithm[J]. Control engineering of China, 2020, 27(7): 1157–1163
[22] BRAND M, YU Xiaohua. Autonomous robot path optimization using firefly algorithm[C]//2013 International Conference on Machine Learning and Cybernetics. Tianjin: IEEE, 2014: 1028-1032.
[23] DORIGO M, MANIEZZO V, COLORNI A. The ant system: an autocatalytic optimizing process Technical Report91-O16[R]. Milan: Dipartimento di Elettronica, Politecnicl di Milano, 1991.
[24] DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating agents[C]//IEEE Transactions on Systems, Man, and Cybernetics, Part B. Cybernetics: IEEE, 2002: 29-41.
[25] 董炫良, 赵桂清. 人工势场引导蚁群算法的机器人导航路径规划[J]. 机械设计与制造, 2021(6): 169–173
DONG Xuanliang, ZHAO Guiqing. Robot navigation path planning based on ant colony algorithm guided by artificial potential field[J]. Machinery design & manufacture, 2021(6): 169–173
[26] 李琳, 刘士新, 唐加福. 改进的蚁群算法求解带时间窗的车辆路径问题[J]. 控制与决策, 2010, 25(9): 1379–1383
LI Lin, LIU Shixin, TANG Jiafu. Improved ant colony algorithm for solving vehicle routing problem with time windows[J]. Control and decision, 2010, 25(9): 1379–1383
- 相似文献/References:
-
[1]周本达,陈明华.随机化均匀设计混合遗传算法求解图的二划分问题[J].智能系统学报,2009,4(1):91.
ZHOU Ben-da,CHEN Ming-hua.Solving the 2-way graph partitioning problem using a genetic algorithm based on randomized uniform design[J].CAAI Transactions on Intelligent Systems,2009,4():91.
[2]冀俊忠,刘椿年,黄 振.基于信息素扩散模型解耦控制策略的蚁群算法[J].智能系统学报,2007,2(4):1.
JI Jun-zhong,LIU Chun-nian,HUANG Zhen.An ant colony optimization algorithm based on a decouplingcontrol strategy of pheromone diffusion model[J].CAAI Transactions on Intelligent Systems,2007,2():1.
[3]康 琦,汪 镭,刘小莉,等.基于群体智能框架理念的遗传算法总体模式描述[J].智能系统学报,2007,2(5):42.
KANG Qi,WANG Lei,LIU Xiao-li,et al.General mode description genetic algorithms based on a framework of swarm intelligence[J].CAAI Transactions on Intelligent Systems,2007,2():42.
[4]马 炫,张亚龙.基于遗传算法的大规模矩形件优化排样[J].智能系统学报,2007,2(5):48.
MA Xuan,ZHANG Ya-long.A genetic algorithm for the layout of large scale rectang ular parts[J].CAAI Transactions on Intelligent Systems,2007,2():48.
[5]徐 雄.人工情感的进化控制系统实现[J].智能系统学报,2008,3(2):135.
XU Xiong.Implementation of an evolutionary control system based on artificial emotion[J].CAAI Transactions on Intelligent Systems,2008,3():135.
[6]刘 胜,李高云,孙天英.一种基于种群多样度的实数编码并行遗传算法[J].智能系统学报,2008,3(5):423.
L IU Sheng,L I Gao-yun,SUN Tian-ying.A real coding parallel genetic algorithm based on diversity of population[J].CAAI Transactions on Intelligent Systems,2008,3():423.
[7]张 涛,费树岷,李晓东.基于GARBF神经网络及边界不变特征的车辆识别[J].智能系统学报,2009,4(3):278.
ZHANG Tao,FEI Shu-min,LI Xiao-dong.Vehicle recognition using boundary invariants and a genetic algorithm trained radial basis function neural network[J].CAAI Transactions on Intelligent Systems,2009,4():278.
[8]秦世引,高书征.面向救援任务的地面移动机器人路径规划[J].智能系统学报,2009,4(5):414.[doi:10.3969/j.issn.1673-4785.2009.05.005]
QIN Shi-yin,GAO Shu-zhen.Path planning for mobile rescue robots in disaster areas with complex environments[J].CAAI Transactions on Intelligent Systems,2009,4():414.[doi:10.3969/j.issn.1673-4785.2009.05.005]
[9]周树德,孙增圻.遗传算法中的联结关系[J].智能系统学报,2009,4(6):483.[doi:10.3969/j.issn.1673-4785.2009.06.003]
ZHOU Shu-de,SUN Zeng-qi.Linkage in genetic algorithms[J].CAAI Transactions on Intelligent Systems,2009,4():483.[doi:10.3969/j.issn.1673-4785.2009.06.003]
[10]印 峰,王耀南,刘 炜,等.个体速度差异的蚁群算法设计及仿真[J].智能系统学报,2009,4(6):528.[doi:10.3969/j.issn.1673-4785.2009.06.010]
YIN Feng,WANG Yao-nan,LIU Wei,et al.Design and simulation of an ant colony algorithm based on individual velocity differences[J].CAAI Transactions on Intelligent Systems,2009,4():528.[doi:10.3969/j.issn.1673-4785.2009.06.010]
[11]程显毅,巩向普.改进的模糊C-均值算法在医学图像分割中的应用[J].智能系统学报,2010,5(1):80.
CHENG Xian-yi,GONG Xiang-pu.An improved fuzzy Cmeans algorithm for segmentation of medical images[J].CAAI Transactions on Intelligent Systems,2010,5():80.
备注/Memo
收稿日期:2022-05-31。
基金项目:国家自然科学基金项目(61673079,61703068)；重庆市基础研究与前沿探索项目(cstc2018jcyjAX0160).
作者简介:蔡军，教授，主要研究方向为机器人技术、信号处理、模式识别。主编和参编教材 5 部，发表学术论文 9 篇。E-mail：1073230317@qq.com;钟志远，硕士研究生，主要研究方向为机器人路径规划。E-mail：879202752@qq.com
通讯作者:蔡军. E-mail：1073230317@qq.com
更新日期/Last Update:
1900-01-01