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

Full Coverage Search Algorithm Based on Topology Connection Graph in Indoor Environment

作　　者：周捷[1] 施晓东[1] 乐意 朱峰[1] ZHOU Jie;SHI Xiao-dong;LE Yi;ZHU Feng(Nanjing Research Institute of Electronic Engineering,Nanjing Jiangsu 210007,China)

机构地区：[1]中国电子科技集团公司第二十八研究所,江苏南京210007

出　　处：《计算机仿真》2023年第7期55-59,共5页Computer Simulation

基　　金：预先研究类“城市作战多维空间信息结构模型及展现技术”(301021302);预先研究类“基于对等模式的末端信息融合与协同共享技术”(315105204);预先研究类“基于智能化战术综合终端的数据融合及应用研究”(315105407)。

摘　　要：随着无人机(unmanned aerial vehicle, UAV)与多智能体协同技术的高速发展,提出了一种基于室内拓扑地图的全覆盖搜索算法,用以解决室内环境下全覆盖搜索问题。首先提取室内环境各房间之间的连接关系,构建拓扑连接图,再提取各房间的中心点,抽象成一系列需要访问的节点,则可将此问题转化为旅行商问题(traveling salesman problem, TSP),利用蚁群优化算法(ant colony optimization, ACO)进行求解得到访问序列,并利用构建好的拓扑连接图来评价访问顺序的可行性,最后,对每个房间进行全覆盖搜索,通过仿真验证了所提算法在室内环境下的全覆盖搜索效果,实验结果证明了算法的可靠性和可行性。into a series of nodes that need to be visited.This problem can be transformed into a traveling salesman problem(TSP),and the ant colony optimization algorithm(ACO)can be used to solve the problem and obtain the passable sequence.The constructed topological connection graph was used to evaluate the feasibility of the passable sequence.Finally,the simulation experiment verifies the full coverage search effect of the proposed algorithm in the indoor environment,which ensures the reliability and feasibility of the search.

关 键 词：全覆盖 无人机 室内环境 旅行商问题 拓扑连接图 蚁群优化算法 

分 类 号：TP20[自动化与计算机技术—检测技术与自动化装置]