Coverage path planning acts as a key component for applications such as mobile robot vacuum cleaners and hospital disinfecting robots. However, the coverage path planning problem remains a challenge due to its NP-hard nature. 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 a new variant of ACO - 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 targets or obstacles faster and keep lower velocity ants informed by communicating such information via trail pheromones. This mechanism ensures the 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, and re-covers $6.9-12.5\%$ fewer cells than ACO. This makes FaSACO more appealing in real-time and energy-limited applications.
翻译：覆盖路径规划是移动机器人真空清洁剂和医院消毒机器人等应用的关键组成部分。然而,覆盖路径规划问题仍因其NP-硬性性质而构成挑战。诸如Ant Colonony优化(ACO)等受生物启发的算法被利用来解决问题,因为它们可以利用杂乱的信息来减轻路径规划的复杂性。本文提出了ACO-快速穿透Ant-colon优化(FASACO)的新变种,其中蚂蚁可以以各种速度探索环境。这样,速度较高的蚂蚁可以更快地找到目标或障碍,并通过路径光素传递这类信息来保持较低速度的蚂蚁。这个机制可以确保找到最佳路径,同时缩短总体路径规划时间。实验结果表明,FASCO比ACO更有效19.3-32.3美元,再覆盖比ACO少6.9-12.5美元。这使得FSACO在实时和节能应用中更具吸引力。
相关内容
微信扫码咨询专知VIP会员