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

周 捷,施晓东,乐 意,朱 峰

(中国电子科技集团公司第二十八研究所, 江苏 南京 210007)

1 引言

覆盖路径规划(coverage path planning,CPP)是确定一条路径,该路径通过一个区域或感兴趣的体积的所有点,同时避免障碍[1-2]。这一任务是许多机器人应用的组成部分,如真空清洗机器人、油漆机器人、自主水下机器人创建图像马赛克、排雷机器人、割草机、自动收割机、窗户清洁工和复杂结构的检查[3-4]。CPP要遵循一定的规则,机器人/无人车不走重复的路径;在覆盖目标区域的同时应避开所有的障碍物;要将任务区域全部覆盖;遵循一定的运动模式;覆盖过程中走的路径尽量短。

无人机(unmanned aerial vehicle,UAV)由于其快速灵巧的特点经常应用于山地、野外以及城市环境中的搜索、监视、侦察、跟踪等任务。对目标的侦察监视以及跟踪任务的前提是对任务区域进行搜索,直到发现目标,才会触发后续的任务流程。所以,UAV对任务区域快速高效地全覆盖起着至关重要的作用。

城市环境对UAV执行搜索、监视、侦察等任务会产生各种各样不同程度的影响。城市环境又分为室外环境和室内环境。城市室外环境,高楼林立树木繁多,车辆行人不断运动,而且运动杂乱无章毫无规律可寻。这就会对UAV的运动产生极大的威胁。例如,高楼和树木的存在会对UAV的视觉产生遮挡,运动中的车辆和行人可视为UAV的动态障碍物等。同理,复杂狭小的城市室内环境对UAV执行搜索、监视、侦察等任务也会产生影响。首先,室内通道狭窄,加上UAV有一定的安全距离,UAV在室内环境飞行并不是畅通无阻的;其次,室内通道大部分由门连接,门的开关状态对于UAV来说存在着极大的不确定性;然后,室内空间狭小结构复杂遮挡严重,对UAV的视觉能力也会产生一定的衰减。所以,针对室内环境下UAV的研究就显得尤为重要。

室内环境下UAV在执行任务之前,首先需要对任务区域进行划分和分解,对于分解得到的任务子区域进行有效的、安全的任务分配,UAV对于得到的子任务内容进行路径规划,最终UAV前往各个任务区域执行相应的搜索、侦察等任务[5-6]。

本文重点对室内环境下无人机全覆盖搜索任务展开研究。由于室内特殊的环境结构,以及各个房间之间的连通性,首先对室内环境提取出房间之间的拓扑连通图,将各个房间抽象成一个个的点,则可以将问题转化为一个旅行商问题(traveling salesman problem,TSP)[7-8],优先解决TSP问题,规划出对各个房间的访问序列,由于各个房间之间不是全部互相连通的,所以规划出访问序列之后根据连通性来评价此访问序列的可行性,并确定最终访问顺序,最后对每个房间进行全覆盖搜索。

2 问题分析

2.1 问题描述

复杂室内环境下UAV对于任务区域的全覆盖搜索问题可以进行如下建模:给定n架异构无人机Ui,i=1,…,n,因为UAV搭载的传感器种类不同,所以UAV的工作能力也不同,对给定的任务区域P执行搜索、侦察等任务,使得对于任务区域尽可能大的覆盖,也就是尽可能多地完成任务,也要保证UAV规划出来的路径没有重复,尽可能快速。分析此问题的特性发现使用双层的思想对此问题进行求解最合适。

首先,将室内的任务场景以房间为单位划分为一个个子任务,根据每个子任务的区域大小不同以及房间内部的连通关系,对无人机的第一层路径即各个房间的访问顺序进行规划,当UAV进入房间执行全覆盖搜索任务时,再规划UAV在房间内部的全覆盖搜索路径。如图1所示为无人机的任务区域,黄色方格为门的位置,黑色条状区域为墙,黑色矩形为障碍物或威胁区域。

室内环境下UAV的全覆盖问题框架如图2所示,首先,对任务场景进行预处理,以房间为单位对室内的整体场景进行分解将任务区域P划分成n个不相重叠的子区域P1,…,Pn,然后通过室内各个房间门的分布情况构建拓扑连接关系将子区域P1,…,Pn进行连接;然后,将子区域P1,…,Pn抽象为一个个点,需要确认对抽象出来的点的访问顺序,则此问题可建模为TSP问题模型,利用蚁群优化算法(ant colony optimization,ACO)进行求解求得访问顺序,当进入每个房间时UAV切换到全覆盖搜索模式,进入此模式时,UAV需要规划搜索的方向和全覆盖搜索的路径点以及飞行的高度,合适的飞行高度有利于UAV的传感器的探测范围wi达到最大,从而减少由于对搜索区域产生的叠加导致的UAV能耗的浪费,直到遍历完所有的任务区域。

图2 全覆盖问题框架

2.2 算法描述

为便于讨论,并结合实际全覆盖搜索、侦察问题进行以下假设:①UAV匀速进行搜索;②子任务以房间为单位进行划分;③不考虑门的开关状态,默认门的状态都为开,即可连通;④UAV的初始位置为已知的。

合理的性能评估与任务区域分配将使得UAV整体执行任务的效能最大,即UAV协同执行任务的代价最小[9]。所以,建立UAV全覆盖搜索任务代价模型可以很好地检测性能评估方法和区域分配方法是否有效。

UAV在执行全覆盖搜索任务的过程中要付出的代价包括UAV飞行路径代价、油耗以及执行侦察任务的时间代价。并且约束有油耗不能超过UAV的最大载油量,侦察时间不能超过传感器的最大工作时间。

针对问题的特性对ACO算法进行如下两点改进,一是引入自适应参数调整机制,目的是提高算法搜索初期寻优速度;有效的摆脱局部最优的情况;二是引入双向搜索机制,目的是为了加快搜寻最优解的速度。

综合以上UAV的代价和约束条件,可以将UAV室内全覆盖搜索、侦察任务的数学模型进行总结,如下如公式(1)所示:

(1)

模型求解的结果为优化的无人机任务区域分配面积百分比,使得多UAV任务执行代价最小。比较模型求解得出的区域面积分配百分比与基于性能评估的任务区域分配百分比之间的差异,以及所对应的多UAV任务执行代价之间的差异,可以分析基于性能评估的任务区域分配方法的有效性。

2.3 传感器探测范围

对于执行侦察任务的无人机,其执行任务的效果很大程度决定于载荷的能力,即无人机机载传感器的性能。传感器的能力通常可以用传感器的探测范围w来表示。如图3所示,当无人机以固定的高度水平飞行时,公式(2)描述了机载传感器的地面探测范围w

图3 无人机的传感器探测区域

图4 全覆盖游走模式

w=2·H·tanγ[cosα+sinαtan(π/2-α-β)]

(2)

其中,H为UAV的飞行高度,α为传感器的安装角,角度β和γ的取值与传感器性能相关,由传感器的视场角和焦距决定。所以,不同焦距下,传感器的视场角也有差异,β和γ的取值也不相同,所以传感器对于地面探测区域范围也不同。当H固定时,β和γ取值越大,w值越大。

2.4 全覆盖搜索模式

在CPP问题中,最优的覆盖路线是基于来回的路线或螺旋形的路线[10-11]。

如图所示4,沿着任务区域的长边进行搜索需要最小的匝数,减少转弯的次数,因此可以最小化总能耗。

3 基于拓扑地图的全覆盖搜索算法

基于拓扑地图的全覆盖搜索算法主要分为以下三个步骤:首先,将先验的室内地图栅格化;其次,结合拓扑地图信息将抽象出来的TSP问题进行求解,并对求得的访问序列进行可行性验证;最后,按照第二步求得的访问顺序依次遍历各个房间,并在各个房间内部进行全覆盖搜索。

3.1 拓扑地图的构建

为了方便无人机进行快速搜索,首先需要对室内不规则的障碍物进行扩展处理,处理后得到规则的四边形,处理效果示意图如图5所示,蓝色为障碍物区域,处理后的效果如周围的矩形所示。

图5 障碍物处理规则

对无人机执行全覆盖任务的建筑物内部房间进行标号,R1-R8代表8个房间,黄色区域代表连接房间的门,如图6中标号1-12所示。

表1 房间中心点坐标

图6 室内结构标号示意图

根据重心法规则可得到每个房间的中心点,提取出来的R1-R8的坐标点如下表所示,将中心点抽象为一个个节点,以便于利用这些节点进行TSP问题的求解。

根据房间之间的连通性,对室内环境进行处理,建立拓扑连接关系,如图7所示,红色节点代表房间标号,连线代表这两个房间之间可连通。

图7 拓扑连接图

3.2 TSP问题的求解

旅行商问题是图论中一个经典的组合优化问题。经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市一次并且仅一次之后,回到出发城市。那么他应如何选择在城市之间的行程路线,以使他走过的总路程最短。从图论的角度来看,该问题其实就是在一个赋权的无向图中,去找一个哈密尔顿回路,并且使得该回路的总权值最小。

本文同理需要无人机遍历所有的房间,尽量不要重复,在可通行的情况下以保证走过的路径尽量短。利用ACO求解抽象出来的TSP问题,对所求得的访问序列利用房间之间的连通性判断序列是否可行。

3.3 全覆盖搜索

如图8所示,从上述TSP规划的结果来看,首先从R3房间出发,经过R2、R1等最终在R5结束搜索任务,以R3为例首先进行小规模仿真,如图9所示为房间R3全覆盖之后的效果示意图。

图8 拓扑路线图

图9 房间R3全覆盖效果示意图

4 仿真验证

在已建立好的地图上,首先根据房间之间的连通关系建立拓扑连接图,再根据一系列各个房间的中心点来规划访问顺序,并用建立好的拓扑连接图来评价访问顺序的可行性。当进入每个节点时,即进入每个房间时,先进行全覆盖搜索,再进入下一个访问节点进行全覆盖搜索,直到遍历完所有的房间节点,如图10所示,为室内环境下全覆盖搜索示意图,绿点处为起点,红点处为重点。

图10 室内环境下全覆盖效果示意图

5 结束语

本文以室内无人机全覆盖搜索为背景,使用基于拓扑地图的全覆盖搜索算法,结合室内存在障碍物、各个房间之间的连通性以及拓扑关系等多维信息进行模拟仿真。虽然前期对建筑物室内结构进行了拓扑关系的构建,房间中心点的选取,却极大地保障了规划的访问顺序的可靠性和可行性。