一种基于分步遗传算法的多无人清洁车区域覆盖路径规划方法

为了解决不规则区域内多无人清洁车区域覆盖路径的全局规划问题,提出一种基于分步遗传算法的区域覆盖方法。首先,将目标区域依据清洁车大小进行栅格化,将多车辆区域覆盖路径规划问题转化为多旅行商(MTSP)问题。然后,使用分步遗传算法求解多旅行商问题:第1步采用模糊c均值聚类方法将求解多旅行商问题转化为求解多个单旅行商(TSP)问题;第2步使用了分步遗传算法对每个单旅行商问题进行求解,并使用杂草入侵算法中子父代共存的思想对遗传算法的选择机制进行改进。最后,分别在模拟的校园场景和小区场景中进行仿真实验。实验结果表明,在两个场景中提出的方法能够实现多无人清洁车完成区域路径覆盖,提出的分步遗传算法比分组遗传算法收敛速度更快;在校园场景中,提出的分步遗传算法相比于分组遗传算耗时减少54%,最优解路径长度减少38%;在小区场景中,提出的分步遗传算法相比于分组遗传算耗时减少55%,最优解路径长度减少44%。

Method of area coverage path planning of multi-unmanned cleaning vehicles based on step by step genetic algorithm

In order to solve the problem of global planning of multi-unmanned vehicle coverage paths in irregular areas, a regionalcoverage method based on stepwise genetic algorithm is proposed. First, the target area is rasterized according to the size of the cleaningvehicle, and the multi-vehicle area coverage path planning problem is transformed into a multi-travel agent (MTSP) problem. Then, themulti-traveler problem is solved by using the stepwise genetic algorithm. The first step is to transform the multi-traveler problem into themulti-traveler (TSP) problem by using the fuzzy C-means clustering method. In the second step, a stepwise genetic algorithm is used tosolve each single traveling salesman problem, and the selection mechanism of the genetic algorithm is improved by using the idea ofneutron parent coexistence of weed invasion algorithm. Finally, simulation experiments are carried out in the simulated campus scene andcommunity scene respectively. The experimental results show that the proposed method in the two scenarios can achieve multi-unmannedcleaning vehicles to complete the regional path coverage, and the proposed step-genetic algorithm has a faster convergence rate than thegrouping genetic algorithm. In campus scenarios, the proposed stepwise genetic algorithm is 54% less time-consuming and 38% lessoptimal solution path length than the grouped genetic algorithm. In the cell scenario, the proposed stepwise genetic algorithm reduces thetime consumption by 55% and the optimal solution path length by 44% compared with the grouped genetic algorithm.