1. 引言
在无人机群侦察覆盖航路规划问题中,需要为无人机群应用协同的方式来计算覆盖航路。无人机群的协同方式可以是编队协同,也可以是分区协同。在分区协同中需要为无人机划分责任区域,目前一般采用解析的办法实现。对于单架无人机航路的规划问题,Zelinsky等人 [1] 采用仿生学的原理,模拟水平面水波的延伸,从而规划路径,这是人工势场的初期研究。从起始网格开始,通过连接相邻网格的最高势网格实现侦察覆盖路径。闫军涛等 [2] 采用元胞自动机,将单无人机侦察路径进行规划,模拟地面移动机器人的覆盖方式。Khatib等 [3] 通过引入改进人工势场算法,将网格中的无人机看做是一个质点,在势场的作用下移动到势低的位置。人工势场算法是一种简便的工具,在处理问题时可以快速求解。因而本文借鉴其人工势场的方法,对无人机群侦察任务航路规划中的多种复杂情况进行处理。
高春庆等人 [4],用方格将侦察区域离散化,并把四个小型区域看作为一个小整体,根据各无人机的初始位置划分出无人机侦察的子区域,分析了“I”型,“L”型,“T”型路径情况,解决了大部分问题。但仍存在部分特殊情况无法适用,无法分配任务、保证算法的全面适用性。
李月娟等人 [5] 将决策过程看成是有限时间序贯决策问题,把每架无人机出现的位置速度、弹药剩余量等因素量化,对其分配不同的权重,使用基于MMDP的算法进行模拟求得目标函数最优解。
湛佳等人 [6] 通过生成一个初始解的序列并随机选取插入位置,插入点算子。其采用一种双重人工蜂群算法,找到适应值最小的方案,能获得较为满意的解决方案。但该算法无法排除结果的偶然性,如果得到最优解,则该算法取得结果的准确性无法得到保证。
为了提高区域划分的适应性和自动化程度,本文对侦察区域进行网格化处理,针对区域特点的不同分别采用不同区域划分方法。针对矩形区域,仍然采用解析的办法,针对不规则区域,利用人工势场生成法进行区域划分。然后在区域划分的基础上,采用改进人工势场法规划无人机的覆盖航路。
2. 区域划分方法
2.1. 矩形区域划分
由于矩形区域存在规则性,算法可以快速实现平均划分。本文采用一种反馈的方法进行处理。在K架无人机的任务条件下,研究需要将任务区域划分成K个面积近似相等的小区域。矩形区域划分方法见表1:
Table 1. Rectangular region averaging steps
表1. 矩形区域平均划分步骤
该方法产生的结果会在后边出现一块与其他面积不同的区域,本文考虑到无人机数量较多,因此忽略其在路径规划中的影响作用。现假设以三架无人机对矩形区域进行平均分配,如图1所示:
Figure 1. Rectangular regional average distribution
图1. 矩形区域平均分配
2.2. 不规则区域的划分
相比矩形区域,不规则区域的划分方法目前有多种算法。本文采用一种改进人工势场的划分方法,对不规则区域进行面积近似相等的划分。
2.2.1. 区域内随机生成中心点
如图2,横轴正半轴为侦察区域正东方向,纵轴正半轴为侦察区域正北方向,X0,Y0为外接矩形长度值,原点O仅代表任务区域横纵方向边缘交汇点,横纵轴单位为“米”。在区域内生成若干随机点。在(0, X0)上随机生成一个值,在(0, Y0)上随机生成一个值,两个值组合成一个点。如果点在任务区域内,则保留,否则舍弃;继续抽取,直到在区域内生成K个随机点。
横轴正半轴为侦察区域正东方向,纵轴正半轴为侦察区域正北方向,X0,Y0为外接矩形长度值,原点O仅代表任务区域横纵方向边缘交汇点,横纵轴单位为“米”。
Figure 2. Irregular regions
图2. 不规则区域
2.2.2. 改进人工势场
本文给每块网格都赋予势值,可以使无人机按照势能降低或者升高的方向飞行。当势场种子落入势场中,已被赋值的区域将会逐渐散开,使得每一块元胞都获得势值。第一步得到的K个随机点则可以用于制造人工势场,势场种子即是选取的K个随机点。改进人工势场生成算法其基本步骤如表2所示:
Table 2. Generation of improved artificial potential fields
表2. 生成改进人工势场
可以看出,如果侦察区域中间有障碍区域,其势值要按照正常区域赋值。如果要生成不同的势场,可以改变种子与无人机数量。一般无人机数量是固定不变的,因此可以通过改变种子形状来制造不同种类的人工势场,从而规划出不同的航路。本文研究的人工势场中,一般种子的形状有如下几种:点型种子、直线型种子、折线型种子、以及环形种子。
本文以点型种子为例进行详细分析,以不规则区域、障碍区域为例,迭代生成改进人工势场见图3、图4:
Figure 3. Improved artificial potential field in irregular region
图3. 不规则区域改进人工势场图
Figure 4. Artificial potential field of obstacle area
图4. 障碍区域人工势场图
2.2.3. 对人工势场进行划分
按照势值的衍生来源就可以将任务区域进行划分。一般在交界处会出现单个网格多种来源,我们规定由多个种子衍生的网格优先归右边网格衍生,其次归上方网格衍生。图5、图6为不同区域三架无人机进行的划分。
Figure 5. Division of pentagonal regions
图5. 五边形区域划分
按照以上方法可以将不规则区域划分出来。该方法采用仿生学原理,处理过程中简单易懂,使用方便。
3. 改进Wavefront法
3.1. 死角问题
在生成航路的时候,可能存在陷入死循环的情况。如当前元胞空间的邻域全都标记为已覆盖,任务区域的其他位置存在空缺。
3.2. 规划覆盖航路
在任务区域都被赋值的基础上,按照以下步骤生成航路,如表3所示:
Table 3. Override route generation steps
表3. 覆盖航路生成步骤
其中需要补充说明的是:
① 突破死角时,在未被覆盖的网格中选取距离最短的网格前进,避免经过障碍区域。
② 突破死角时,如果中间存在障碍,沿着路径返回直到突破死角时中间无障碍区域。
4. 计算实验
任务区域分别采用五边形区域,矩形多障碍区域,另外以矩形无障碍区域对比,采用三个点型种子,图7、图8、图9是按照方法生成的航路图:
Figure 7. Rectangular barrier-free road map
图7. 矩形无障碍航路图
Figure 9. Route map of rectangular obstacle area
图9. 矩形障碍区域航路图
5. 结束语
本文采用改进人工势场法对无人机群进行航路规划,无人机群覆盖路线规划方法是通过几个步骤实现的:任务区域划分、在区域划分基础上制造了人工势场、生成覆盖路径。侦察覆盖航路规划的结果受无人机位置与人工势场的影响,其次受到人为规则的影响。实验中,不同的任务区域可以变换出不同的路径规划,最后规划得到了理想的结果。