室内环境下基于拓扑连接图的全覆盖搜索算法

摘要

随着无人机(unmanned aerial vehicle, UAV)与多智能体协同技术的高速发展,提出了一种基于室内拓扑地图的全覆盖搜索算法,用以解决室内环境下全覆盖搜索问题。首先提取室内环境各房间之间的连接关系,构建拓扑连接图,再提取各房间的中心点,抽象成一系列需要访问的节点,则可将此问题转化为旅行商问题(traveling salesman problem, TSP),利用蚁群优化算法(ant colony optimization, ACO)进行求解得到访问序列,并利用构建好的拓扑连接图来评价访问顺序的可行性,最后,对每个房间进行全覆盖搜索,通过仿真验证了所提算法在室内环境下的全覆盖搜索效果,实验结果证明了算法的可靠性和可行性。