论文标题
用于移动机器人覆盖路径计划的快速跨蚂蚁殖民地优化（Fasaco）
Fast-Spanning Ant Colony Optimisation (FaSACO) for Mobile Robot Coverage Path Planning
论文作者
论文摘要
覆盖路径计划（CPP）旨在找到覆盖整个给定空间的最佳路径。由于NP坚硬的性质，CPP仍然是一个具有挑战性的问题。生物启发的算法（例如蚂蚁菌落优化（ACO））已被利用以解决该问题，因为它们可以利用启发式信息来缓解路径计划的复杂性。本文提出了快速跨度的蚂蚁菌落优化（Fasaco），蚂蚁可以以各种速度探索环境。通过这样做，具有较高速度的蚂蚁可以更快地找到目的地或障碍物，并通过通过路径上的信息素步道传达此类信息来保持较低的速度蚂蚁。该机制可确保在减少总体路径计划时间时找到（子）〜最佳路径。实验结果表明，在CPU时间方面，Fasaco的效率比ACO高19.3-32.3 \％$，并且将$ 6.9-12.5 \％$的细胞比ACO重新覆盖。这使得Fasaco在实时和能源有限的应用中具有吸引力。
Coverage Path Planning (CPP) aims at finding an optimal path that covers the whole given space. Due to the NP-hard nature, CPP remains a challenging problem. Bio-inspired algorithms such as Ant Colony Optimisation (ACO) have been exploited to solve the problem because they can utilise heuristic information to mitigate the path planning complexity. This paper proposes the Fast-Spanning Ant Colony Optimisation (FaSACO), where ants can explore the environment with various velocities. By doing so, ants with higher velocities can find destinations or obstacles faster and keep lower velocity ants informed by communicating such information via pheromone trails on the path. This mechanism ensures that the (sub-)~optimal path is found while reducing the overall path planning time. Experimental results show that FaSACO is $19.3-32.3\%$ more efficient than ACO in terms of CPU time, and re-covers $6.9-12.5\%$ less cells than ACO. This makes FaSACO appealing in real-time and energy-limited applications.
