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.
翻译：路径规划(CPP)旨在找到覆盖整个空间的最佳路径。由于NP-硬性,CPP仍然是一个具有挑战性的问题。由生物驱动的算法,如Ant Colonony优化(ACO),已被利用来解决问题,因为它们可以利用超常信息来减轻路径规划的复杂性。本文建议快速覆盖Ant Conony优化(FASACO),其中蚂蚁可以以各种速度探索环境。这样,速度较高的蚂蚁可以找到目的地或障碍更快,并通过在路径上的Pheromone轨迹传递这类信息,从而保持较低速度的蚂蚁知情。这个机制可以确保在缩短总体路径规划时间的同时找到(次)~最佳路径。实验结果表明,FASaCO在CPU时间方面比ACO效率更高19.3-32.3 $($),并且重新覆盖比ACO少6.9-12.5美元。这使得FSACO在实时和节能应用中具有吸引力。
相关内容
微信扫码咨询专知VIP会员