【作者】 李响；

【导师】 刘利强； 周祖洋；

【作者基本信息】 哈尔滨工程大学 ， 工程硕士（专业学位）， 2020， 硕士

【摘要】 随着科学技术的发展,越来越多的机器人能代替人们完成复杂和危险的任务,而很多复杂的问题单个机器人无法高效地完成,需要多个机器人合作完成,多机器人任务分配问题是协调机器人高效合作的关键,也是多机器人系统研究的重点。本文针对需要机器人移动并合理分配任务这一应用场景,采用多旅行商(multiple traveling salesman problem,MTSP)模型对问题进行建模,并对实际中存在的应用场景进行仿真模拟求解,最终解决这一问题并使得分配结果更加合理。蚁群算法是解决多机器人任务分配常用的算法,其优点有正反馈特性和分布式计算等,缺点是前期收敛速度慢和易陷入局部最优解等。本文采用遗传算法对蚁群算法进行改进,同时对蚁群算法中信息素更新方式进行改进,增强了算法的寻优能力,并用该算法解决多机器人任务分配问题。首先,研究解决多机器人任务分配问题需要的步骤有数学建模和优化算法,其中,采用MTSP模型对多机器人任务分配进行建模,分析两者的相同点和不同点,包括起点不同和出现断点的情况等,指出对MTSP问题引入一定的限制条件就能对应多机器人任务分配的某个具体应用的建模,解决MTSP问题是解决多机器人任务分配的关键。优化算法是求解多机器人任务分配问题的核心,本文重点讲述如何用算法求解问题以及对蚁群算法进行优化。其次,研究蚁群算法的基本原理和数学模型,分析蚁群算法的参数对算法性能的影响,用试凑方法求得一组蚁群算法的参数,并用遗传算法对蚁群算法的参数进行优化,得出另一组参数,用这两组参数分别求解MTSP问题,对比两组实验的寻优效果和收敛速度,用遗传算法改进参数后,算法的寻优性能和收敛速度有了很大的提升。然后,对蚁群算法进行改进,改进蚁群算法中信息素浓度的更新策略,使得算法有更强的搜索能力,同时将蚁群算法求解的初步解当成遗传算法的初始种群,用遗传算法进行进一步求解,能有效地改进蚁群算法容易陷入局部最优解的缺点。本文在TSPLIB数据集中引入5个问题,分别用传统蚁群算法、最大最小蚁群算法、基于排序改进蚁群算法和本文提出的蚁群-遗传改进算法对问题进行求解,通过对实验结果的对比和分析,证明了本文提出的遗传-蚁群改进算法有更强的寻优能力。最后,用本文提出的蚁群-遗传改进算法求解多机器人任务分配问题,其中包括起点相同的机器人清洁太阳能电池板问题和起点不同的机器人配送邮件问题,实验引入了王旭和秦新立采用的优化算法当作对照组,通过用MATLAB进行仿真实验和对实验结果进行比较分析,本文提出的蚁群-遗传优化算法能很好地解决多机器人任务分配问题,在寻优性能方面比引入的两种方法都要优秀,特别是在求解复杂度较高的问题时,寻优性能的优势表现得更加突出。更多还原

【Abstract】 With the development of science and technology,more and more robots can replace people to complete complex and dangerous tasks.However,many complex problems cannot be completed efficiently by a single robot.Multiple robots are required to complete cooperation.The problem of multi-robot task allocation is to coordinate robots.The key to efficient cooperation is also the focus of multi-robot system research.In this paper,the MTSP model is used to model the problem for the application scenario that requires the robot to move and allocate tasks reasonably,and the actual application scenario is simulated to solve the problem,which finally solves the problem and makes the distribution result more reasonable.The ant colony algorithm is a commonly used algorithm for solving multi-robot task assignment.Its advantages include positive feedback characteristics and distributed computing.The disadvantages are that the early convergence speed is slow and it is easy to fall into the local optimal solution.In this paper,the genetic algorithm is used to improve the ant colony algorithm,and the pheromone update method in the ant colony algorithm is improved at the same time,which enhances the optimization ability of the algorithm,and uses the algorithm to solve the problem of multi-robot task assignment.The main content of this article includes the following aspects:First,the steps required to solve the multi-robot task allocation problem are mathematical modeling and optimization algorithms.Among them,the MTSP model is used to model the multi-robot task allocation.The similarities and differences between the two are analyzed,and it is pointed out that solving the MTSP problem is a solution.The key to multi-robot task assignment.The optimization algorithm is the core of solving the problem of multi-robot task assignment.This article focuses on how to use the algorithm to solve the problem and optimize the ant colony algorithm.Secondly,study the basic principle and mathematical model of ant colony algorithm,analyze the influence of ant colony algorithm parameters on algorithm performance,use trial and error method to find a group of ant colony algorithm parameters,and use genetic algorithm to optimize ant colony algorithm parameters,Get another set of parameters,use these two sets of parameters to solve the MTSP problem respectively,compare the optimization effect and convergence speed of the two sets of experiments,and get the conclusion that after using genetic algorithm to improve the parameters,the optimization performance and convergence speed of the algorithm have Great improvement.Then,the ant colony algorithm is improved to improve the pheromone concentration update strategy in the ant colony algorithm,so that the algorithm has a stronger search ability,and the initial solution of the ant colony algorithm is regarded as the initial population of the genetic algorithm,and the genetic algorithm is used Further solution can effectively improve the ant colony algorithm and easily fall into the shortcomings of local optimal solution.This paper introduces five problems in the TSPLIB data set,using traditional ant colony algorithm,maximum and minimum ant colony algorithm,improved ant colony algorithm based on ranking and the ant colony-genetic improvement algorithm proposed in this paper,by comparing the experimental results And analysis proves that the improved genetic-ant colony algorithm proposed in this paper has a stronger ability to seek optimization.Finally,the ant colony-genetic improved algorithm proposed in this paper is used to solve the multi-robot task allocation problem,which includes the problem of robot cleaning solar panels with the same starting point and the problem of robot delivery mail with different starting points.The experiment introduces the optimization algorithm adopted by Wang Xu and Qin Xinli As a control group,through MATLAB simulation experiments and comparative analysis of the experimental results,it is concluded that the ant colony-genetic optimization algorithm proposed in this paper can solve the problem of multi-robot task assignment well,and it is better than the introduction of optimization performance.Both methods should be excellent,especially when solving higher complexity problems,the advantage of seeking performance is more prominent.更多还原