基于蚁群算法的完全遍历路径规划研究

Complete Coverage Path Planning Based on Ant Colony Algorithm

提出了一种局部区域遍历和全局运动规划相结合的完全遍历路径规划方法;针对基于Boustrophedon单元分解所得区域的特点,机器人可在局部区域内采用往复运动的方式实现遍历。该方法定义了遍历空间中子区域间综合连通距离,综合连通距离包括区域之间的连通关系、区域之间的最短距离、区域之间的障碍物情况等要素,整个遍历空间中的连通关系由一个完全赋权连通矩阵表示。采用蚁群算法对子空间遍历距离进行优化,得到了最短全局遍历顺序。最后以一个模拟环境为求解实例,证明了算法的有效性。

A complete coverage path planning algorithm integrating local region coverage with global planning was proposed. According to the characteristics of Boustrophedon cellular decomposition,the robot covered local region through back and forth motion. The distance among every regions was redefined, what including connectivity, least distance, and number of obstacles among regions. The new distance matrix of regions in environment was built for global planning. Based on ant colony algorithm,the robot used the distance matrix to get the optimization sequence of the regions after decomposed the coverage environment. Experiments under simulation environment verify the validity of the proposed algorithm.