论文部分内容阅读
机器人集群搜索多目标点的最短路径是路径规划问题中的研究热点问题。本文旨在求解机器人搜索目标点的最短巡回路径,使用群体智能算法规避在大规模TSP(Traveling Salesman Problem)问题求解时的计算量问题,提高机器人执行搜索任务的效率。首先对问题模型运用聚类算法进行点集聚类,将聚类特性相近的目标点归为组,将mTSP(Multiple Traveling Salesman Problem)问题分解为小规模的单一TSP问题求解。FCM(Fuzzy C-means)聚类算法相较于K-MEANS聚类算法在后续最短路径求解上取得更好的结果。对每一组搜索点,用粒子群算法(Particle Swarm Optimization,PSO)和遗传算法(Genetic Algorithm,GA)两种群体智能算法进行求解,比较求解结果以及算法收敛的速度。针对遗传算法的收敛迭代次数的问题,使用改良圈算法先对种群个体进行先择优,获得的个体再进行遗传算法的求解,改进后的遗传算法在总路径最小值以及分组路径最小值的求解效果上有明显提升,同时明显减少求解迭代次数,减少了运算时间损耗。最后利用turtlebot3机器人平台进行仿真路线运行试验,完成多机器人协同搜索目标点的任务。通过对两种智能算法的改进与对比,本文使用的智能算法在求解机器人最短巡回路径的总距离以及分组最长路径问题上都取得了良好的效果。