基于改进人工势场方法的无人机群侦察覆盖航路规划算法研究

Research on the Route Planning Algorithm of UAV Group Reconnaissance Coverage Based on Improved Artificial Potential Field Method

摘要: 随着无人机平台技术的逐渐成熟和广泛应用，利用无人机平台执行侦察任务的效费比也越来越高。无人机群的航路规划是侦察任务规划中的核心问题。面对复杂的侦察任务，基于解析的方法适应性不强、自动化程度较低。因此，本文提出了一种基于人工势场的无人机群侦察航路规划方法。在无人机责任区域划分的研究中，针对规则区域仍然采用基于解析的方法，针对不规则区域的划分，设计了基于人工势场的区域划分方法，提高了算法的适应性和自动化程度。在无人机航路生成算法中，利用种子的概念提高了无人机航路生成模式的多样性。最后通过计算实验，验证了方法的高效性和适应性。

Abstract: With the maturity and wide application of UAV platform technology, the effective cost ratio of using UAV platform to perform reconnaissance missions is also increasing. The route planning of UAV group is the core problem in reconnaissance mission planning. In the face of complex reconnaissance tasks, the analytical-based method is less adaptable and less automated. Therefore, this paper proposes a method of UAV group reconnaissance route planning based on artificial potential field. In the study of UAV responsibility region division, for the regular regions, the analytical-based method is still adopted; for the division of irregular regions, an artificial potential field region division based on artificial potential field is designed to improve the adaptability and automation of the algorithm. In UAV route generation algorithm, the concept of seed is used to improve the diversity of UAV route generation modes. Finally, the high efficiency and adaptability of the method are verified by computational experiments.

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，横轴正半轴为侦察区域正东方向，纵轴正半轴为侦察区域正北方向，X₀，Y₀为外接矩形长度值，原点O仅代表任务区域横纵方向边缘交汇点，横纵轴单位为“米”。在区域内生成若干随机点。在(0, X₀)上随机生成一个值，在(0, Y₀)上随机生成一个值，两个值组合成一个点。如果点在任务区域内，则保留，否则舍弃；继续抽取，直到在区域内生成K个随机点。

横轴正半轴为侦察区域正东方向，纵轴正半轴为侦察区域正北方向，X₀，Y₀为外接矩形长度值，原点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. 五边形区域划分

Figure 6. Regional division of barriers

图6. 障碍区域划分

按照以上方法可以将不规则区域划分出来。该方法采用仿生学原理，处理过程中简单易懂，使用方便。

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 8. Irregular areas route map

图8. 不规则区域航路图

Figure 9. Route map of rectangular obstacle area

图9. 矩形障碍区域航路图

5. 结束语

本文采用改进人工势场法对无人机群进行航路规划，无人机群覆盖路线规划方法是通过几个步骤实现的：任务区域划分、在区域划分基础上制造了人工势场、生成覆盖路径。侦察覆盖航路规划的结果受无人机位置与人工势场的影响，其次受到人为规则的影响。实验中，不同的任务区域可以变换出不同的路径规划，最后规划得到了理想的结果。