基于多目标快速探索随机树的移动机器人巡检路径优化方法.pdf

专题：人机智能协同系统第12 卷第4期2023年7 月引文格式：张可,宋呈群,程俊，等.基于多目标快速探索随机树的移动机器人巡检路径优化方法 .集成技术,2 0 2 3,12(4):3 2-41.Zhang K,Song CQ,Cheng J,et al.Multi-objective rapidly-exploring random tree robot patrol path optimization methodJ.Journal of Integration Technology,2023,12(4):32-41.集成技术JOURNAL OF INTEGRATIONTECHNOLOGYVol.12No.4Jul.2023基于多目标快速探索随机树的移动机器人巡检路径优化方法张可-2 宋呈群1.21(中国科学院深圳先进技术研究院中国科学院人机智能协同系统重点实验室深圳518 0 55)2(香港中文大学香港9990 7 7)摘要针对移动机器人需要访问多目标的巡检路径规划问题，该文提出一种多目标快速探索随机树路径优化方法。首先，根据提供的环境地图与巡检目标点，该文采用一种RRT-Connect-ACO算法得到目标点的巡检顺序和可行路径；然后，通过引入信息子集，对路径进行优化，得到最终的最优路径。实验结果表明，与现有的多目标路径规划算法相比，该方法考虑了地形的影响，得到的最优路径更符合实际情况。关键词多目标路径规划；快速探索随机树；旅行商；蚁群算法；信息子集；移动机器人中图分类号号TP 242程俊12*张锲石12曾驳12文献标志码Adoi:10.12146/j.issn.2095-3135.20220721001Multi-objective Rapidly-Exploring Random Tree Robot Patrol PathOptimization MethodZHANG Kel:2(CAS Key Laboratory of Human-Machine Intelligence-Synergy Systems,Shenzhen Institute of Advanced Technology,Abstract A multi-objective rapidly-exploring random tree path optimization method is proposed for the multi-objective patrol path planning of mobile robots.According to the provided environment map and patrol targetpoints,a new method RRT-Connect-ACO is used to obtain the patrol sequence and feasible path of the targetpoints.Then the optimal path is obtained by introducing informed subset to optimize the path.The experiment收稿日期：2 0 2 2-0 7-2 1修回日期：2 0 2 2-0 9-15基金项目：国家自然科学基金项目（U21A20487）；深圳市科技计划项目（JCYJ20180507182610734，K CXFZ 2 0 2 0 12 2 117 3 4110 3 2）；中国科学院关键技术人才项目作者简介：张可，硕士研究生，研究方向为机器人路径规划等；宋呈群（通讯作者），副教授，研究方向为计算机视觉、机器人等，E-mail：；程俊（通讯作者），教授，研究方向为计算机视觉、机器人等，E-mail：j u n.c h e n g s i a t.a c.c n；张锲石，高级工程师，研究方向为智能驾驶与机器人、行为识别与分析等；曾驳，硕士研究生，研究方向为计算机视觉、同时定位与建图等。SONG Chengqun.2Chinese Academy of Sciences,Shenzhen 518055,China)2(The Chinese University of Hong Kong,Hong Kong 999077,China)Corresponding Authors:;CHENG Jun2*ZHANG Qieshil2ZENG Bo l24期张可，等：基于多目标快速探索随机树的移动机器人巡检路径优化方法33results show that the method considers the influence of terrain and obtains an optimal path that is more consistentwith the actual situation,which is different from the existing multi-objective path planning algorithms.Keywords multi-objective path planning;rapidly-exploring random tree;travelling salesman problem;antcolony optimization;informed subset;mobile robotsFunding This work is supported by National Natural Science Foundation of China(U21A20487),ShenzhenTechnology Project(JCYJ20180507182610734,KCXFZ20201221173411032),CAS Key Technology Talent Program1 引 言随着计算机技术、传感器技术的飞速发展，移动机器人已广泛应用于日常生产生活，并迎来了发展高峰期。面向巡检任务 的移动机器人在巡检过程中的路径规划极为重要，最优的路径可以及时发现隐患和安全事故 2 。本文将巡检问题视作旅行商问题（travelling salesman problem，TSP)3和路径规划(path planning，PP)问题 4-1 的结合，根据给定的环境地图和任务需求访问的多个点，确定访问顺序，并得到最优的访问路径。巡检机器人的路径规划可以被简单描述为TSP。T SP是组合优化问题中的一个著名难题，传统的TSP可以叙述为：需要推销员去若干城市推销产品，规定推销员必须到达每个城市且只去一次，最后还需回到出发城市。TSP的目标函数是找到符合上述条件的最短访问路线。在TSP中，每个顶点即为需要访问的城市，边为两个城市之间的距离。此类问题用一般的算法很难得到最优解，早期使用分支界定 6 、动态规划法 7 等精确算法 8-9 求解，但随着解决问题规模的扩大，将难以获得精确结果，因而启发式算法被提出。启发式算法得到的结果虽然不能证明是最优解，但可以有效地提供次优或者可能最优的解，其分为传统启发式算法和元启发式算法 3.8 。传统启发式算法 7 包括最近邻算法（nearest neighbor，NN）、爬山法等，此类算法原理简单，但优化结果与全局最优解差距明显；元启发算法是基于启发式算法的改良，不依赖特定问题，采用通用启发式策略寻优，如模拟退火（simulated annealing，SA)8.10、遗传算法(genetic algorithm，G A)1-2 、蚁群算法(antcolony optimization,ACo)1315等。ACO是一种群智能算法，由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。ACO最早由意大利学者Colorni 等 13 提出。经过3 0 多年的发展，ACO在理论以及应用研究上取得了巨大的进步。ACO最早用于求解TSP，其具有分布式特性，鲁棒性强且易与其他算法结合，表现出了较强的优越性，但同时存在收敛速度慢、容易陷入局部最优等缺点。路径规划是机器人学的一个基础研究领域，其目的是为机器人找到一条可行的路径，同时避免环境中的障碍物。其主要分为基于网格和基于采样这两种方法。基于网格的算法，如A*16-17、D*18 可以找到最佳路径，但时间成本和计算量会随着规模增加而呈指数增长。基于采样的算法，如概率路线图 19-2 0 和快速探索随机树(rapidly-exploring random tree,RT)21,因其能够有效解决多约束和高维路径规划问题而被广泛应用。特别是RRT可有效处理具有微分约束的系统，因此，RRT成为许多机器人平台上34流行的一种路径规划算法 15。RRT算法在规划路径之前必须获取状态空间的全部信息，然后以起始点为根节点，在状态空间内进行随机抽样，通过特定的约束条件逐步扩展随机树。当随机树上的点到达目标点的邻域范围内时，即可找到一条从起始点到目标点的有效路径。RRT算法的双向变体已成功应用于复杂的路径规划，Kuffner 等 2 2 提出一种快速RRT算法，即在起始点和目标点同时构建RRT，并交替展开两棵随机树。与单向RRT算法相比，该算法可以更快地找到一条可行路径。尽管RRT算法相对高效，可以较好地处理带有非完整约束的路径规划问题，但不能保证得到的可行路径是相对优化的。为进一步改进RRT算法，Karaman 等 2 3 提出了RRT*算法，通过重新连接节点优化生成路径。与RRT算法相比，RRT*算法的主要优化过程为：重新选择父节点和重布线随机树。RRT*具有渐进最优性，且不能在有限时间内得到最优路径，故其收敛时间是一个较为突出的问题，表现为收敛速度缓慢。基于RRT*的框架，相关学者提出了许多路径规划的变体，如Gammell 等 2 4 提出一种informed-RRT*方法，将采样范围限制在椭圆内，对规划问题的状态维度和范围的依赖性较小，可提高收敛速度。目前，针对多目标路径规划的研究较少，大部分多目标路径规划的方法是直接采用两点间的欧氏距离，如Wang等 15 的研究，其应用场景是较为空旷的机场，因此可以忽略障碍物的影响，直接采用欧氏距离作为任意两目标点之间的路径代价，但对于略微复杂的环境，该方法将可能引起较大的路径代价。为解决上述移动机器人访问多目标的巡检路径规划问题，本文提出一种多目标快速探索随机树巡检路径优化方法。与已有的多目标路径规划策略不同，本文利用RRT-Connect-ACO算法得集成技术到各重点监测点间的可行路径，并以路径长度作为各点之间的路径代价，得到更具可靠性的巡检顺序，同时，大大降低了由于迭代次数不足导致无法生成路径的风险。此外，本文还引入信息子集，缩小采样空间，提高了路径优化效率。2方法本文方法的流程如图1所示，根据提供的环境地图与指定的巡检多目标点，利用RRT-Connect-ACO算法得到目标点的巡检顺序和可行路径，通过引入信息子集对路径进行优化，最终得到最优路径。开始输入环境地图、起始点和重点监测点+RRT-Connect得到任意两点间的可行路径及对应的路径代价ACO得到巡检顺序通过巡检顺序选定可行路径引用信息子集对选定路径进行优化输出最终路径结束图1方法流程图Fig.1 Method flow chart2.1 RRT-Connect-ACO 算法假设一个具有n个需要重点监测节点x的环境地图X，每对节点通过Edge(xi,x)连接，由二进制变量x；判定每条边是否属于巡检路径，当Xij=1 时，Edge(xi,x)属于巡检路径，否则不属于。每个Edge(x,x)包含信息素追踪强度t和常2023年4期量启发值ni，在每次迭代的时候由蚂蚁更新。其中，i和j为重点监测点对应的节点序号。算法的目标是使最终巡检路径的总路径代价最小化，如公式(1)所示。mini=1 ji,j=2S.t.X,e(0,1)i,j=1,2,n itji1如公式(2)所示，x,取值0 或1，表示节点i和j之间的路径是否被选择；公式(3)表示任意节点为端点的路径只有一条被选中，保证每个节点只经过一次。将m个蚂蚁放置在随机选择的节点上，信息素T。的初始值赋予在每条边上：二To，启发值n采用节点x和x,之间路径代价c，的倒数进行初始化，如公式(4)所示。1nii节点x;上的蚂蚁k移动到下一个节点x,的概率计算公式如下：(5)jeNk其中，为信息启发因子；为期望启发因子；N为节点x,上蚂蚁k尚未访问的节点集。和是两个正参数，分别用于确定T，和ni的权重，相比于的值越大，蚁群选择之前走过的路径可能性越大，值越小，蚁群容易选择局部最短路径，减少搜索范围，容易陷入局部最优。当所有的蚂蚁根据以上约束完成一次旅行后，根据公式（6)更新信息素。ti=pt,+Atj其中，p为系数，取值范围为0 pl；1-p 为信息素的蒸发率；PT，为保留的上一次旅行的信息张可，等：基于多目标快速探索随机树的移动机器人巡检路径优化方法素浓度；T，的计算公式如下。A,-2Atmk=1t 为第k只蚂蚁从节点x移动到x留下的信息素，计算公式如下：(1)Ati=c(2)0,others传统方法大多将巡检问题视作旅行商问题，(3)但在一些复杂环境中，仅以两点间的欧氏距离作为两点间的路径代价是不合理的，易导致实际路径无法达到最优，故本文将RRT-Connect得到的路径长度作为蚁群算法的代价输入。RRT-Connect采用双向拓展平衡的连结型双树RRT算法，该算法基于双向RRT算法并加入了贪心启发函数，一定程度上提升了算法的收敛速度，有利于快速得到路径代价。此外，双向算法避免了终点与起点的不同选择导致路径存在差异的问题，使路径代价更可靠。基本步骤如下：(4)(1)在已知的空间环境X中，定义起始点Xsart、目标区域点Xgoal和额定步长入，初始化两棵扩展树 T,和 Tb。i(2)在空间中随机生成一个点xrand，遍历扩展树Ta，找到距离Xrand最近的节点Xnear，选择两点间连线上距离xnear为额定步长入的点作为新节点Xnewo(3)监测xnew与Xnear之间是否与障碍物发生碰撞，若未发生碰撞则将xnew加入扩展树T。中，否则重新执行步骤（2）。遍历扩展树T,，找到距离xnew最近的节点xnear，选择两点间连线上距离xnear为额定步长的点作为新节点xnew。(4)监测xnew与xnear之间是否与障碍物发生碰撞，若未发生碰撞则将xnew加入扩展树T，中，(6)否则经过步骤(6)的判断后，重新执行步骤(2)。(5)选择xnew和xnew之间连线上距离xnew为额定步长的点作为新节点监测与35(7)(8)36xnew之间是否与障碍物发生碰撞，若未发生碰撞，则将xnew加入拓展树T,中，将xnew重新定义为新的xnew，重复执行步骤(5)；若监测到xnew与xnew之间与障碍物发生碰撞，则跳出循环，执行下一步。若xnew和xnew是相同节点，则结束流程，依次寻找父节点并进行连接，即完成起始点到目标点的路径规划；否则，重复当前步骤。(6)若T,的节点数小于T。的节点数，则交换两棵扩展树T。和T，并重新执行步骤(2)。RRT-Connect-ACO算法的伪代码如算法1所示。其中，x为目标点列表，为经过所有目标点的可行路径，将任意两点间的路径和代价进行初始化，RRT_Connect()可得到x,x,两点之间的可行路径，Cost()返回生成的路径的长度c，将点列表x和代价矩阵c作为输入，通过ACO()可以得到目标点的巡检顺序ox，使用Path()根据巡检顺序和已经生成的路径可得到一条可行的巡检路径。集成技术问重点监测地区的顺序和可行路径，将该条路径进行优化可得到一条最优路径。针对提供环境地图较大、排序后路径经过区域较小的问题，本文采用RRT*算法对自由空间Xfre进行均匀采样，但导致搜索树上生成很多穴余的分支，造成RRT*收敛速度相对较慢。本文引用信息子集 2 5 的概念，它是状态空间X的子集，利用椭圆采样代替了全局均匀采样。代价函数f(x)可分为两个部分：从xsart到x的路径代价g(x)以及从x到xgal 的路径代价h()。为得到估计代价()，需要定义从起始点到x的代价估算g()和x到终止点的代价估算h()。欧几里得距离是寻找路径最小长度问题的启发式方法，因此，改善当前解决方案最优代价Cbest的椭圆信息子集可被定义如公式(9)所示，即椭圆的一般方程。9best2023年算法1RRT-Connect-ACO Algorithm输入:xgoal point list输出:A feasible path,t h r o u g h a l l t h e g o a l p o i n t s;I:init:Finit(x),cinit(x)2:for i=1 to number of x do:3:for j=i+1 to number of x do:4:T,=F,=RRT_Connect(x,x,)5:c,=c,=Cost(r,)6:end7：end8:0,=ACO(x,c)9:,=Path(F,o.)由于RRT-Connect-ACO算法具备快速性和低成本性，本文采用这种算法对任意两中间监测位置的路径代价进行粗略估计，与传统方法中直接采用两点间欧氏距离作为路径代价相比，该方法更具可靠性。此外，由于生成路径的可行性，提高了优化效率。2.2Informed RRT*-Connect 算法RRT-Connect-ACO算法可用于确定机器人访图2 是以xstart和xXgoal为焦点的椭圆信息子集，长轴的长度为ca，短轴的长度为+c。其中，Cmin为Xstart和Xgoal之间的欧几里得距离。每次迭代过程均在椭圆信息子集X，内均匀采样，通过重新选择父节点和重布线进行优化，计算优化后的估计代价子()，取其中最优代价定义为Chest。若CbestCmin，则更新最优路径信息和椭圆采样区域。搜索新生成的节点xnew额定半径内的节点，chet+cabestminFig.2 Sample diagram of elliptic informed subsetCminCbest图2 椭圆信息子集示例图4期排除其中经过障碍物的节点，将符合要求的节点加入节点列表Xnearo重新选择父节点的过程为：计算节点Xnew到起始点Xstart的路径代价Cmin；依次选择Xnear中的节点作为节点xnew的父节点，计算对应的路径代价，取其中最小值Cnew，若CnewCmin，那么Cmin=Cnew，Xn e w 的父节点更改为Xnear中的对应节点Xnearo重布线随机树的过程为：计算Xnear中每个节算法2 Informed RRT*-Connect Algorithm输入:XEnvironmental Map,T,Xs o l n,a Step Length,n Number of Iterations输出:An optimal path。f r o m Xa n r t o Xg o l1：init:XstarTirst,2:init:*ol-Tusrt3:init:Cmn-Cost(+xgol,ar)4:for i=1 to n do:5:6:7:8:9:10:11:12:13:14:15:16:17:18:19:20:21:22:23:24:2526:27:28:29:end30:F。E x t r a c t Pa t h(x b e s张可，等：基于多目标快速探索随机树的移动机器人巡检路径优化方法Xrna-Sample(X,Cost)Xaerest-Nearest(xiana,T)Xnew-Steer(xana Xrer,2)if CollisionFree(xnew,Xnar)T.addNode(xnew)Xnear-Near(xnew,T)forXnear:Xnear do:Canew=Cost(xr)+Line(xnear,new)ifCnowCcminne-parent-XrarCmininCnewendendforXnear:XnarnearCner=Cost(Xnear)Chnew=Cost(Xnew)+Line(Xnew,ner)ifCnewwCnearnearthen:Xnear parent Cnew，那么对应节点Xnear的父节点将更改为XnewoInformed RRT*-Connect算法的伪代码如算法2 所示。3仿真与分析为验证本算法性能，本实验通过两个方案进行仿真分析。由于机器人存在自身半径，无法直接视作一个质点，仿真实验中对障碍物进行了膨化处理，进而可将机器人看作一个质点。仿真地图如图3 所示，所有环境的地图规模均为50 0 m300m，以地图左下角为坐标原点，最优路径长度为lop，最大迭代次数为n。then:图3 仿真地图Fig.3The simulation mapthen:首先通过RRT-Connect-ACO得到一条粗略的可行巡检路径，如图4所示。do:图4使用RRT-Connect-ACO得到可行路径Fig.4Feasible path obtained by RRT-Connect-ACO利用Informed RRT*-Connect算法对该路径进38行优化，最终得到一条最优路径，如图5所示。图5优化后的巡检路径Fig.5Optimized inspection pathWang等 15 研究的应用场景为较空旷的地方，障碍物较少，两点之间的欧氏距离与实际路径代价基本一致，所以其采用欧氏距离作为路径预估代价，对实验结果影响不大。对于如图3 所示地图，采用欧氏距离和使用RRT-Connect实际可行路径长度作为预估代价的结果也相差较小，如图6 所示。集成技术图6(a)的路径成本lopt=1590.2m，图6(b)的路径成本lopt=1558.4m，与直接采用欧氏距离的方案相比，采用RRT-Connect实际路径作为预估代价的路径成本略低，但优势不明显。但对于一些特殊地形(图7)，最终得到的路径结果差异明显。图7(a)为采用欧氏距离作为预估代价最终得到的结果lopt=1909.7m，忽略了地形对巡检路径的影响，导致大量重复路径，增加了路径代价。图7(b)为采用RRT-Connect实际路径长度作为预估代价最终得到的结果lopt=1728.7m，该结果明显优于采用欧氏距离得到的结果。两幅图的差异主要集中在矩形框标注部分，本文算法考虑了地形对巡检路径的影响，得到了路径更短的巡检顺序。由于直接采用欧氏距离作为预估代价，没有生成可行路径的过程，需直接采用InformedRRT*进行路径规划，即根据欧氏距离得到的路2023年(a)采用欧氏距离作为预估代价的最优巡检路径Fig.6 The final paths generated at the cost of Euclidean distance and actual path length,respectively(b)采用RRT-Connect实际路径长度作为预估代价的最优巡检路径图6 分别以欧氏距离与实际路径长度作为代价所生成的最终路径(a)采用欧氏距离作为预估代价的最优巡检路径图7 特殊地形下，分别以欧氏距离与实际路径长度作为代价所生成的最终路径Fig.7 Under the special map,the final paths generated at the cost of Euclidean distance and actual path length,respectively(b)采用RRT-Connect实际路径长度作为预估代价的最优巡检路径4期径巡检顺序，采用InformedRRT*进行两点之间的路径规划。在采用相同的迭代次数时，则更易出现规划路径失败的结果。在较少迭代次数下，以欧氏距离与实际路径长度为预估代价生成的最终路径对比图如图8 所示。其中，图8(a)为采用欧氏距离作为预估代价的最优巡检路径，图8(b)为采用RRT-Connect实际路径长度作为预估代价的最优巡检路径。如图8 所示，当n=500时，图8(a)存在5条未规划出的路径，由于其Informed RRT*属于单树的RRT算法，一边扩展一边优化，提高了优化的效率，但极有可能在迭代次数较小的情况下不能生成一条可行路径。故相同迭代次数的情况下，本文提出的算法更易得到较优路径。(a)采用欧氏距离作为代价的最优巡检路径(b)采用RRT-Connect实际路径长度作为代价的最优巡检路径图8 在较少选代次数的情况下，以欧氏距离与实际路径长度作为代价所生成的最终路径Fig.8In the case of fewer iterations,the final pathsgenerated at the cost of Euclidean distance and actual此外，对优化过程进行对比，采用图7 中的地图，对于生成的同一条可行路径（路径长度为张可，等：基于多目标快速探索随机树的移动机器人巡检路径优化方法IntroduceInformed Set图9是否引入信息子集的路径优化结果对比Fig.9Comparison of path optimization results wheater tointroduceinformed subset综上所述，本文方法可以生成一条最优巡检路径。此外，与其他方法对比，本文方法对巡检顺序的优化得益于可行路径的生成，考虑到了障碍物对计算两点间路径代价的影响，得到了可以生成更短路径的巡检顺序。而信息子集的引入，克服了基本的RRT优化方法随机性强、采样效率低的缺点，在保证较少迭代次数的前提下，不仅生成了可行路径，还进一步提高了优化效率。4结论path length,respectively针对巡检机器人多目标复杂路径规划难题，本文提出一种多目标快速探索随机树巡检路径优39=2108.4m)，都采用重新选择父节点与重布线随机树的方式进行路径优化，在相同的迭代次数n=5000的条件下，将引入信息子集的路径优化结果与未引入信息子集的结果进行对比实验，每种方法运行50 次，实验结果如图9所示。如图9所示，其中，左侧为采用信息子集的数据结果，右侧为未采用的数据结果，两种方法的平均长度分别为17 7 5.6 m和17 95.2 m。采用信息子集的方法虽然异常值较多，但优化结果优于未采用信息子集的方法，因此，采用信息子集的算法得到的结果更优。1800179517908178517801775Not IntroduceInformed Set40化方法。首先利用RRT-Connect-ACO算法快速得到一条粗略的巡检路径，提高了巡检顺序的可靠性；然后利用Informed RRT*-Connect算法优化路径，以获取最优路径。对于大的子集，当解决方案接近理论最小值时，通过全局采样或均匀采样改善解决方案的可行性较小。本文采用椭圆信息子集，将子集范围缩小，提高了优化效率。值得注意的是，本文方法仅针对静态情况，对环境信息发生的变化无法动态改变路径，未来可根据巡检结果进行进一步动态巡检，使巡检过程更加智能高效。参考文献1 Hoshino S,Ishiwata T,Ueda R.Optimal patrollingmethodology of mobile robot for unknown visitorsJ.Advanced Robotics,2016,30(16):1072-1085.2 Wang JH,Fu G,Yan MW.Comparative analysisof two catastrophic hazardous chemical accidentsin China JJ.Process Safety Progress,2020,39(1):e12137.3 Halim AH,Ismail I.Combinatorial optimization:comparison of heuristic algorithms in travellingsalesman problem J.Archives of ComputationalMethods in Engineering,2019,26(2):367-380.4Wang JK,Meng QH.Optimal path planning usinggeneralized voronoi graph and multiple potentialfunctions J.IEEE Transactions on IndustrialElectronics,2020,67(12):10621-10630.5 Khanmirza E,Haghbeigi M,Nazarahari M,et al.A comparative study of deterministic andprobabilistic mobile robot path planning algorithmsC/Proceedings of the 2017 5th RSI InternationalConference on Robotics and Mechatronics,2017:534-539.6Poikonen S,Golden B,Wasil EA.A branch-and-bound approach to the traveling salesman problemwith a drone J.INFORMS Journal on Computing,2019,31(2):193-410.7Chauhan C,Gupta R,Pathak K.Survey of methods集成技术of solving TSP along with its implementation usingdynamic programming approach J.InternationalJournal of Computer Applications,2012,52(4):12-19.8ilhan i,Gokmen G.A list-based simulatedannealing algorithm with crossover operator for thetraveling salesman problem J.Neural Computingand Applications,2022,34(10):7627-7652.9Behmanesh R,Rahimi I,Gandomi AH.Evolutionary many-objective algorithms forcombinatorial optimization problems:a comparativestudy J.Archives of Computational Methods inEngineering,2021,28(2):673-688.10 Zhou YM,XuWQ,Fu ZH,et al.Multi-neighborhood simulated annealing-based iteratedlocal search for colored traveling salesmanproblems J.IEEE Transactions on IntelligentTransportation Systems,2022,23(9):16072-16082.1l Liu JJ,Li WZ.Greedy permuting method forgenetic algorithm on traveling salesman problemC/Proceedings of the 2018 8th InternationalConference on Electronics Information andEmergency Communication,2018:47-51.12Hussain A,Muhammad YS,Nauman SM,et al.Genetic algorithm for traveling salesman problemwith modified cycle crossover operator J.Computational Intelligence and Neuroscience,2017,2017:7430125.13 Colorni A,Dorigo M,Maniezzo V.Distributedoptimization by ant colonies C/Proceedings ofthe First European Conference on Artificial Life,1991:134-142.14I Du PZ,Liu N,Zhang HF,et al.An improved antcolony optimization based on an adaptive heuristicfactor for the traveling salesman problem J.Journal of Advanced Transportation,2021,2021:6642009.15 Wang JK,Meng QH.Real-time decision makingand path planning for robotic autonomous luggagetrolley collection at airports J.IEEE Transactionson Systems,Man,and Cybernetics:Systems,2021,52(4):2174-2173.2023年4期16郭耕辰，冯良炳，邓亮，等.基于A*算法与自适应分片的大规模最优路径规划 J.集成技术，2 0 14,3(2):68-77.Guo GC,Feng LB,Deng L,et al.Large scale routeplanning A*algorithm based on self-adaptivehierarchy method J.Journal of IntegrationTechnology,2014,3(2):68-77.17 Zhang J,Wu J,Shen X,et al.Autonomous landvehicle path planning algorithm based on improvedheuristic function of A-Star J.InternationalJournal of Advanced Robotic Systems,2021,18(5).https:/doi.org/10.1177/17298814211042730.18 Liu LS,Lin JF,Yao JX,et al.Path planning forsmart car based on Dijkstra algorithm and dynamicwindow approach J.Wireless Communicationsand Mobile Computing,2021,2021(4):1-12.19 Chen G,Luo N,Liu D,et al.Path planning formanipulators based on an improved probabilisticroadmap method J.Robotics and Computer-Integrated Manufacturing,2021,72:102196.20 Alarabi S,Luo CM,Santora M.A PRM aproachto path planning with obstacle avoidance of anautonomous robot C/Proceddings of the 20228th Internatio