无人机地理围栏越界探测算法改进与分析

谢东岑，梁晓龙，张佳强，付其喜，张凯

(1.中国人民解放军95140部队，惠州 516200) (2.空军工程大学 国家空管防相撞技术重点实验室，西安 710051) (3.空军工程大学 陕西省电子信息系统综合集成重点实验室，西安 710051) (4.中国人民解放军94582部队，驻马店 463225) (5.空军工程大学 空管领航学院，西安 710051)

0 引 言

在无人机行业不断兴起、无人机驾驶员成为了一种新职业的大背景下，无人机的使用越来越频繁；同时，涉及无人机的事故数量也在增加，而目前各国均缺少对无人机的相关规定，只能向无人机运营商提供建议[1]。一系列无人机空中交通事故的发生，让人们意识到低空空域无人机监管的重要性和必要性。地理围栏的发展让无人机监管越来越简单高效，无人机地理围栏是一个虚拟的栅栏边界，由垂直高度的限制和水平方向的边界组成[2]，它可以将通过GPS或雷达获取的位置信息作为输入，经运行地理围栏越界探测算法判断其是否在指定的空域内飞行，一旦无人机的飞行航向将与地理围栏边界发生冲突，它就会提前告警，并配合机载传感器和规避系统做出相应的反应，有助于提高无人机自主水平。

由于无人机地理围栏能够有效地解决无人机监管过程中的问题，国内外越来越重视这方面的研究发展。国内大疆无人机[3]的GEO(Geospatial Environment Online)就有地理围栏技术的应用，能为大疆用户提供相关信息，帮助用户在飞行时间和地点上做出合理决定，但其存在两点不足：一是技术不够成熟，不能完全可靠地实现地理围栏越界探测；二是只适用于部分机型。强明辉等[4]利用无人机感知与规避系统、基于地理围栏的地面站避让系统模型、添加了高度参数的地理围栏优化算法，实现了基于无人机地面站避让系统的地理围栏算法设计与仿真，将地理围栏算法与无人机的机载定位导航系统结合起来，不需要雷达等其他机载探测设备，具有很强的实际应用性与创新性；付其喜等[5]提出了无人机地理围栏预控制层生成算法，实现了自主飞行的无人机地理围栏算法设计，能保证自主飞行的无人机在地理围栏内安全飞行。但上述文献均未对无人机越界探测功能进行深入研究。国外同样也在开发类似的地理围栏技术。T.Gurriet等[6]利用优化方法和尽可能微小的飞行指令变动，在避免地理围栏越界的前提下，实现了平滑规避轨迹的生成，但该方法仅适用于圆形地理围栏，难以适应无人机复杂的飞行环境；M.N.Stevens等[7]提出并实现了二维和三维方向上的TWC(Triangle Weight Characterization)算法，适用于任意复杂不自相交的多边形，并且运行速度大幅提高，但是一旦地理围栏边界有所变化，则该算法的初始化步骤又要重新进行。

本文在国内外地理围栏相关研究的基础上，针对射线算法的不足进行改进，避免射线法出现错误判断的情况，提高算法的准确性；并通过仿真实现基于改进射线法的无人机地理围栏越界探测算法，对影响其运行时间的因素进行深入研究和分析说明，以便适用于复杂多变的飞行环境和更多种类的无人机。

1 无人机地理围栏算法的一般流程

地理围栏有两种类型：一种是禁出型地理围栏，它为无人机定义了一个有界的可飞空域，无人机不能飞出这一围栏空域；另一种是禁入型地理围栏，是为了防止无人机进入并且与其保持一定距离而定义的一个围栏空域。地理围栏有水平的边界和垂直高度的限制。一般地，地理围栏可以由一个禁出型地理围栏和若干个禁入型地理围栏组成，其算法基本流程如图1所示。

图1 地理围栏算法基本流程Fig.1 Basic flow of violation detection algorithm

输入参数为r和g，r=(x,y)为当前无人机横向平面位置，用于探测是否存在地理围栏冲突。地理围栏由G=[gi,go]指定，其中gi为禁出型地理围栏边界多边形；go={go1，…，gon}是一组禁入型地理围栏边界；gok是n个禁入型地理围栏边界多边形的第k个。pointinpolygon()函数是一种点包容算法，可以是射线算法，也可以是TWC算法，如果地理围栏边界为圆形，还可以是圆形地理围栏算法。只要没有发生地理围栏冲突，它就会为每个新的状态执行循环。

2 无人机地理围栏越界探测算法改进

无人机地理围栏越界探测算法根据地理围栏边界的形状可以分为：圆形地理围栏算法、矩形地理围栏算法、复杂多边形地理围栏算法[8]。复杂多边形地理围栏算法更符合实际应用，也能节省更多的空域资源，提高空域利用率。该算法中目前用得最多的是射线法算法[9]。

2.1 基于射线法的地理围栏越界探测算法

(1) 算法原理

从无人机测试点r投影出一条射线s(如图2所示)，如果这条射线相交于奇数条多边形的边，则测试点r包含在地理围栏p中，否则r在p之外。

图2 射线法示意图Fig.2 Schematic diagram of ray cast algorithm

(2) 判定规则

①若为禁入型地理围栏，设置“c为奇数”为地理围栏冲突事件，具体判定规则如下：

判定规则1：c为奇数时，无人机此时已进入禁飞区，其飞行器系统相应模块应作出反应。

判定规则2：c为偶数时，无人机没有进入禁飞区。

②若为禁出型地理围栏，设置“c为偶数”为地理围栏冲突事件，具体判定规则如下：

判定规则1：c为偶数时，无人机此时已飞出指定空域，其飞行器系统相应模块应作出反应。

判定规则2：c为奇数时，无人机此时在指定空域内飞行。

2.2 基于改进射线法的地理围栏越界探测算法

使用原始射线法可能出现特殊情况(如图3所示)，即射线会与多边形顶点相交、射线经过多边形的一条边[10]，甚至测试点p就在多边形边上[11]。若仍使用原始射线法进行交点计数，则会产生错误的判断，因此将射线法原理进行改进，提高其准确性。

图3 原始射线法可能出现的特殊情况Fig.3 Special cases that may occur with the original ray cast algorithm

(1) 算法原理

在原始射线法的基础上，设置一个用于判断特殊情况的缓冲距离D，规定引出的射线是y方向的，当测试点的x坐标在地理围栏边界顶点的x坐标的缓冲距离内时，将地理围栏边界顶点的x坐标减去2倍的缓冲距离，即2D，使得测试点引出的y方向的射线避开地理围栏边界的顶点；再进行测试点与边的判断：当测试点在边的缓冲距离内时，直接视为该测试点在地理围栏之外；随后判断射线与地理围栏每条边是否只有一个交点，若是，则交点计数加1；通过交点计数的奇偶性判定测试点与地理围栏的位置关系，判定规则同原始射线法。

改进射线法的具体流程如图4所示，其中rx和ry分别为测试点r的横坐标和纵坐标；地理围栏g={p1,p2,…,pi,…,pn}由p1,p2,…,pn点顺时针或逆时针连接而得；s为从点r沿y轴方向引出的一条射线；pix为pi点的横坐标；pix,D为pi点在经缓冲距离D处理之后的横坐标。

图4 改进的射线算法流程图Fig.4 Improved ray cast algorithm flow chart

图4与原始射线法不同之处就是图中灰色部分，不仅解决了射线与非凸地理围栏边界顶点相交的问题、测试点在地理围栏边上的问题，还解决了射线经过地理围栏边界边的问题。

(2) 判定规则

具体判定规则同原始射线法。

3 仿真与实验结果分析

3.1 改进射线法假设背景

(1) 为了凸显可解决的问题，绘制横向地理围栏边界，如图5所示，黑色实线边界为禁出型地理围栏，灰色虚线边界为禁入型地理围栏。

(2) 地理围栏边界在无人机飞行期间保持不变。

(3) 为了给无人机定义一个可飞空域，地理围栏包含了垂直方向和水平方向的边界。

图5 横向地理围栏边界Fig.5 The horizontal geo-fence boundary

(4) 垂直地理围栏边界(高度上限和下限)在地面(AGL)或平均海平面(MSL)以上是恒定的。

(5) 无人机飞行高度恒定，使研究重点集中在横向地理围栏越界探测算法上，应注意，该算法在未来的工作中可以进行扩展优化，以消除高度等假设带来的影响。

(6) 每个地理围栏边界都不是自相交的，自相交多边形如图6所示。

图6 自相交的多边形Fig.6 Self-intersecting polygon

(7) 边界指定为按顺时针或逆时针顺序的顶点列表，可以是GPS纬度和经度，也可以是相对位置点。

3.2 基于改进射线法的地理围栏越界探测算法仿真与分析

为了验证改进射线法的可行性，在Matlab R2014a的环境下对地理围栏越界探测算法进行仿真验证。首先，通过plot()函数将各个顶点逆时针连接起来建立多边形地理围栏边界，随机生成若干个测试点，然后，分别进行顶点缓冲距离的判断和边缓冲距离的判断，以及射线与边的交点判断，执行图4中算法灰色部分，进而进行与射线交叉的边的数目的计算，最后判定测试点是否在多边形内。

实验分三个步骤进行：

(1) 验证改进射线法的可行性，并与原始射线法在准确性上作比较分析；

(2) 分析测试点个数对地理围栏越界探测算法运行时间的影响，并与原始射线法作比较；

(3) 分析地理围栏边界的顶点数对基于改进射线法的地理围栏越界探测算法运行时间的影响。

对实验结果的分析：

(1) 改进射线法可行性验证及其与原始射线法在特殊情况下的比较。

为了对改进射线法进行可行性验证，随机产生50 000个测试点，仿真结果如图7所示，将被判定在规定区域外的点标为浅灰色，被判定在规定区域内的点标为深色。

图7 改进射线法随机生成50 000个测试点仿真结果Fig.7 Simulation results of 50 000 test points randomly generated by the improved ray cast algorithm

从图7可以看出：在随机生成的50 000个测试点中，判定结果基本正确，在地理围栏边界附近能看到有个别测试点被判定为浅灰色，这是由于缓冲距离的设置，同时也能起到提前告警的作用，以便无人机及时做出规避动作。表明本文改进的射线法在地理围栏越界探测中是可行的。

另外，还仿真出原始射线法和改进射线法在其中一特殊情况下的判断，即当测试点引出的y方向射线与地理围栏顶点相交。程序设置时仍将射线与边的交点为奇数的点判定在地理围栏内，用深色标记；为偶数的点判定在地理围栏外，用浅灰色标记，均取500个随机点。原始射线法和改进射线法在类似情况下的仿真结果分别如图8～图9所示。

图8 原始射线法特殊情况下的仿真结果Fig.8 Simulation results of the original ray cast algorithm under special circumstances

图9 改进射线法特殊情况下的仿真结果Fig.9 Simulation results of the improved ray cast algorithm under special circumstances

从图8～图9可以看出：原始射线法在该特殊情况下的判断全错，但是改进射线法解决了这一问题。此外，图7的结果也表明：基于改进射线法的地理围栏越界探测算法还可以解决测试点在地理围栏边界上的问题和射线经过地理围栏边界的问题，这都是原始射线法无法解决的。因此，改进射线法的准确性相比原始射线法大幅提高。

(2) 测试点个数对地理围栏越界探测算法运行时间的影响，并将改进射线法与原始射线法作比较。

为了得到原始射线法和改进射线法的运行时间与测试点个数的关系，设置在图5所示地理围栏中测试点随机产生的个数分别为1、10、50、100、150、200、250、300个，利用tic/toc函数分别计时，各进行100次实验，结果如图10(a)所示；分别计算出100次结果的平均值，将8个点连接起来，如图10(b)所示。

(a) 地理围栏越界探测算法运行不同测试点数的时间

(b) 地理围栏越界探测算法运行不同测试点数的时间平均值图10 地理围栏越界探测算法运行时间与测试点数的关系Fig.10 The relationship between the running time of the geo-fence violation detection algorithm and the test points

从图10可以看出：地理围栏越界探测算法运行时间与测试点个数成正比，测试点越多，算法运行的时间越长。因此地理围栏越界探测系统需安装在无人机上，在飞行之前就输入地理围栏各个参数，由无人机自行根据其GPS模块或雷达传输的数据进行判断，这样每架无人机每个时刻只运行自己的位置点，速度快，能及时反应；相反，如果地理围栏越界探测由地面设备来运行，一旦同一时刻同一地理围栏内的无人机过多，算法运行时间就会增长，加之由地面反馈到无人机也需要一定的时间，无法保证实时性。

此外，原始射线法运行时间比改进射线法快，但是将地理围栏系统应用到机载设备上，每次只进行一个测试点的判断，改进射线法的运行时间与原始射线法相差不大，对于无人机这样“低、慢、小”的飞行器，这个差值可以忽略不计。即在保证准确性的前提下，改进射线法的越界探测功能优于原始射线法。

(3)地理围栏边界的顶点数对基于改进射线法的地理围栏越界探测算法运行时间的影响。

因为实验(1)和实验(2)已经证明改进射线法优于原始射线法，所以在此不再考虑原始射线法。为了得到基于改进射线法的地理围栏越界探测算法运行时间与地理围栏边界顶点数的关系，设置相同的测试点数1个，一个随机生成的禁出型地理围栏，且顶点数分别为3、6、9、12、15、18、21、24个，分别进行100次实验，结果如图11(a)所示，计算各顶点数运行时间的平均值，结果如图11(b)所示。

(a) 地理围栏越界探测算法不同顶点数的运行时间

(b) 地理围栏越界探测算法不同顶点数的运行时间平均值图11 地理围栏越界探测算法运行时间与边界顶点数的关系Fig.11 The relationship between running time of geo-fence violation detection algorithm and the number of boundary vertices

从图11可以看出：基于改进射线法的地理围栏越界探测算法运行时间与边界顶点数成正相关，边界顶点越多，算法运行的时间越长，因为此算法要遍历每一条边。之所以不完全成正比例的关系，从编程角度上来说，只有当从测试点引出的y方向射线与地理围栏其中一条边相交，才会执行相应的条件语句，如果不相交，就会直接跳过，节省时间，图11(a)中的时间分布也能印证这点，当地理围栏顶点数较少时，地理围栏边界相对简单，随机产生的测试点引出的射线与地理围栏相交的边数普遍较少，算法执行时间短，分布集中；当地理围栏顶点数较多时，边界相对复杂，随机产生的测试点引出的射线与地理围栏相交的边数有多有少，所以不同点执行算法的时间跨度相对较大。

综上所述，基于改进射线法的地理围栏越界探测算法运行时间不仅与地理围栏边界顶点数成正相关的关系，还与测试点在地理围栏中的相对位置有关系，从测试点引出的y方向射线与地理围栏边界相交的边数越多，算法的运行时间越长，相交的边数越少，运行时间越短。

4 结 论

(1) 基于改进射线法的无人机地理围栏越界探测算法的运行时间与测试点个数成正比，测试点个数越多，算法运行时间越长。因此应将地理围栏系统主要应用于机载设备上。

(2) 基于改进射线法的无人机地理围栏越界探测算法的运行时间与地理围栏边界顶点数成正相关的关系，顶点数越多，算法运行时间越长。控制地理围栏边界顶点数可以提高无人机地理围栏越界探测的效率和实时性。

(3) 基于改进射线法的无人机地理围栏越界探测算法的运行时间与测试点在地理围栏中的相对位置有关，从测试点引出的y方向射线与地理围栏边界相交的边数越多，算法的运行时间越长。因此对相对于地理围栏较为复杂的位置，地面人员应加强监督和管控，保证空域内的飞行安全。