小型旋翼无人机具有操控灵活、携行方便、价格低廉的特点, 对于低空航拍、城市快递、反恐侦察等都有着非常广阔的应用空间, 近年来在城市商业市场的发展很是火爆。当前, 诸如中国大疆、美国谷歌等许多世界著名科技公司都已将多旋翼无人机作为主力发展产品。亚马逊也正在积极发展Prime Air计划^[1], 建立利用小型无人机在城市内实现30分钟到达的快速物流系统。然而, 无人机在为城市发展带来广阔市场的同时, 也给城市的低空安全提出了巨大挑战。2015年11月16日, 一架正在我国某繁华城市上空数百米处悬停拍摄的多旋翼无人机险些与一架喷气式军机相撞, 两机相距最近处仅数百米, 十分惊险。2016年2月4日, 一架被称为“雄峰”的小型无人机撞上纽约帝国大厦第40层。类似事件还有很多。频频发生的此类事件使城市低空无人机防碰撞安全问题正在引起人们的重要关注。

在飞控和动力系统完好的情况下, 无人机路径规划对于飞行安全的影响是非常重要的, 因此也得到了广泛的关注和研究。高晖等研究了利用动态规划算法生成最优参考航路的方法^[2];董世友等基于Voronoi图为无人机产生初始航路^[3];鲁艺等研究了基于数字形态学边缘提取的航路规划方法^[4];黄文刚等研究了基于改进A^*算法的航路规划^[5];Chen Peng等利用改进Voronoi图进行路径规划^[6];任佳等探索了在移动威胁情况下基于威胁状态预测进行路径规划的方法^[7];王怿等提出了一种基于Clothoid曲线的路径规划算法^[8];王树磊等提出了基于Laguerre图的航路规划方法^[9];刘洋等研究了面向三维环境的基于改进概率地图的多目标蚁群规划算法^[10];Xu等研究利用混沌人工蜂群方法进行路径规划^[11]。对于在城市中执行货物传送、危情侦察等任务的无人机来说, 飞行高度通常在几十到上百米左右, 飞行环境的主要特点则是楼房密集, 飞行通道窄, 碰撞危险性高。这些特点给城市低空环境的路径规划带来了新的困难, 一些传统路径规划方法的应用也因此受到局限。针对城市低空环境的新挑战, 许卓凡等探索了将Laguerre图应用于不规则障碍环境的路径规划^[12];张启瑞等引入回溯机制, 研究将A^*方法用于城市环境的航路规划^[13]。但以上研究仍关注于预先规划, 需要提前掌握飞行区域的信息。对于陌生的任务区域来说, 这一点难以满足。且对于不规则性强的复杂环境、超大规划区域等, 其执行效率会受到影响。

陌生区域最大的不同在于对环境的“飞行前陌生”。由于缺乏先知信息, 无法详细掌握飞行环境的各种情况, 也就难以提前通过预先路径规划确定出安全路径。因此, 实时的路径规划才能适应于陌生城市低空飞行的需要。考虑到基于Laguerre图的路径规划本身所具有的安全性优势, 本文拟在传统的预先完成型Laguerre图路径规划原理的基础上, 探索可在线实现的实时避撞路径规划方法。

1 基于Laguerre图的路径规划原理

基于Laguerre图的路径规划是一种基于图论的新方法^[9]。设有一组平面圆的集合S={C₁(P₁, r₁), C₂(P₂, r₂), …, C_n(P_n, r_n)}, 其中圆C_i(P_i, r_i) 的圆心为P_i, 半径为r_i。定义平面任意点Q到该圆切点的距离平方为点到圆的Laguerre距离d_L(x, C_i)=。定义由圆C_i(P_i, r_i) 和圆C_j(P_j, r_j) 确定的Laguerre边是到这两个圆的Laguerre距离相等的点构成的线, 记为LE (C_i, C_j, S)={Q|d_L(Q, C_i)=d_L(Q, C_j), ∀Q∈R²}。则将平面中到圆C_i(P_i, r_i) 的Laguerre距离小于到其他圆的Laguerre距离的点构成的多边形区域称为Laguerre图, 其数学定义由 (1) 式给出^[14]

(1)

相比基于Voronoi图的路径规划, 基于Laguerre图的路径规划将生成元从平面点扩展为圆, 圆心和半径分别表示威胁的位置及半径。同时, 以Laguerre距离代替欧氏距离, 为路径规划带来了更好的安全性优势。文献[9]的实验分析结果表明, 当2个圆形威胁区没有交叠时, Laguerre图的规划路径一定是从2个威胁区的空隙中穿过, 但Voronoi图方法不能保证获得这样的结果。如果2个圆形威胁区存在交叠, Laguerre图的规划路径必定经过2个圆的交点, 可最大程度降低路径威胁。图 1对比显示了Laguerre图方法对于路径规划安全性的优势。

目前关于Laguerre图路径规划的研究需要提前将非圆形威胁区转化为圆形威胁区, 并只能预先完成全部的路径规划^{[9, 12]}。对于陌生城市环境来说, 由于预先无法掌握任务区域详细的地理与环境信息, 从而难以利用预先规划的方法为无人机确定出安全可飞路径。可行的方法必须是实时规划。可充分利用机载CCD相机、摄像机等光电探测设备实时感知前方一定距离内的环境状态, 并由机上图像处理系统实时抽取出前方飞行区域的障碍物轮廓, 辨析出可能的飞行通道。在此基础上, 为无人机在线规划出可视区域内的安全飞行路径。为此, 本文拟发挥传统Laguerre路径规划的安全性优势, 研究能够在复杂低空环境中进行实时规划的新方法。

2 基于航段分解的Laguerre规划模型

传统的基于Laguerre图的路径规划是面向全局的预先规划。为实现实时的路径规划, 首先研究单航段Laguerre图路径规划的特点和规划模型。

2.1 基于航段分解的滚动Laguerre路径规划机理

尽管面向全局的路径规划是直接给出从起点到终点的完整路径, 但无人机则是要按照航点逐段飞行的。借鉴动态规划中逐段递推优化的思想^[15], 将Laguerre图的规划流程按照航段和航点展开的顺序进行延展, 再按照无人机经过各航点的时间窗口进行匹配, 即可将整个规划路径分解为若干个航段。这样, 就可把基于Laguerre图的规划过程建模为遵循Laguerre图运算规则的单航段递进搜索、逐层扩展并收敛到目标航点的过程。从而得到基于航段分解的滚动Laguerre路径规划模型如图 2所示。按照图 2模型, 可以把路径规划过程看成是在全航点空间中, 运用Laguerre图运算规则逐段搜索航点子集的过程。在每个航段, 当前时刻的航点是下一段航点的起点, 2个相邻航点间的航路可看作是航点搜索的空间增量。

记k时刻的可行航点集为M (k)={m|m为k时刻的一个可行航点}, k+1时刻的一个可行航点为n。设航点m到n之间的航段长度为l, 方向角为φ, 将该航段记为ΔL (l, φ)。则可将图 3描述的路径规划过程写成如下递推形式的航点生成算式

(2)

根据 (2) 式, 即可构建基于Laguerre图的逐段滚动递进的分段规划过程。这就为基于Laguerre图的实时路径规划提供了运行机理。为此, 需要考察单航段的Laguerre防碰撞路径。

2.2 单航段Laguerre路径的避撞特性

将2个城市楼房之间的空间看作拟飞通道, 视为一个单独航段, 考察该航段Laguerre路径的特性。如图 3所示, 阴影矩形A和B表示2个形状相同的楼房, 2楼之间的通道宽度为L。则根据Laguerre图原理, 可以得到如下的单航段路径引理。

单航段Laguerre路径引理    单航段拟飞通道的Laguerre路径是沿通道纵向距离楼房A边界为的直线, b为2个建筑物外接圆的圆心距。

证明    根据题设, 令A₁A₂=B₁B₂=2a。设楼房A和B的外接圆圆心分别为P点和O点, 半径为r_A和r_B, 则OP=b。

按照Laguerre图原理, 两圆之间的Laguerre路径必是在由2个圆决定的Laguerre边上, 设圆O和圆P确定的Laguerre边是图中直线C₁C₂, 与楼房A的垂直距离为L_A, 与楼房B的距离为L_B。从该Laguerre边上的任意点G向2个外接圆做切线, 切点分别为Q和H, 则有GH=GQ。则根据图中的直角三角形几何关系可以得到

(3)

(4)

另外, PG=PF+L_A, OG=OE+L_B, 进而可以导出

(5)

(6)

L=L_A+L_B, PF+OE+L=b, 则有

(7)

引理得证。此引理给出了单航段的Laguerre路径与楼房边界的距离。从防碰撞安全的角度看, 希望该路径与拟飞通道两侧楼房的距离达到最佳安全距离。为此, 需要进一步考察和处理城市楼房间的位置关系, 构建防碰撞实时路径规划。

3 基于边界归一化的避撞实时路径规划

为消除城市建筑物间多样位置关系对Laguerre路径的影响, 首先探讨通过边界归一化建立单航段的最佳安全路径。在此基础上, 构建面向复杂低空环境的实时避撞航路规划方法。

3.1 面向障碍物异型位置关系的边界归一化

在现代化大城市中, 楼房等建筑物往往形状各异, 位置关系也较复杂。对于单通道的Laguerre路径规划来说, 这种多样性会造成相似的通道状况却具有不一致的Laguerre路径, 不仅会干扰安全路径的规划, 也与实际的飞行要求不一致。为解决这种异型位置关系导致的Laguerre路径不一致问题, 受模型辨识和机器学习中对数据进行归一化处理的启发, 对拟飞通道两侧障碍物的边界进行归一化处理, 使相似拟飞通道可以按照Laguerre图规划出一致的可飞路径。

首先, 考察拟飞通道两侧被视作障碍物的楼房的边界, 以其中最大最平直的边界作为归一化标尺。之后, 按照该边界的长度和方向扩展对侧的障碍边界, 完成归一化。例如, 在图 4中, 对建筑物A和建筑物B之间的拟飞通道, 以A₁A₂为归一化标尺, 对边界B₁B₂归一化, 得到新的归一化边界为B₁B′₂。完成障碍边界的归一化后, 即可进一步分析归一化单航段的Laguerre安全路径。

3.2 归一化航段的最佳避撞路径规划

当无人机在2个建筑物之间飞行时, 其防碰撞路径规划需要同时考虑对两侧建筑物的碰撞, 最佳的安全路径应是对两侧建筑物防碰撞综合最优的路径。为此, 定义拟飞通道的Laguerre路径的避撞安全误差为E_S=。进而可以导出单个归一化航段的Laguerre最佳避撞路径规划定理。

[最佳避撞路径规划定理] 对于单个归一化的拟飞航段, 其Laguerre最佳避撞路径位于该航段通道的中位路径上。

证明:以图 4所示的单个归一化航段为证。设该航段的Laguerre最佳避撞路径为C₁C₂, 分别距离两侧障碍建筑物L_A和L_B。因为是最佳路径, 应有

(8)

因为2L_A²-2LL_A+L²≠0, 则可解得

(9)

根据最佳避撞路径规划定理, 可以很方便地为各个单航段规划出最佳避撞路径。再运用2.1节建立的基于航段分解的实时Laguerre路径规划模型, 即可构建出新的Laguerre实时避撞路径规划方法。

3.3 面向低空避撞的Laguerre实时路径规划

根据Laguerre实时路径规划机理模型, 在无人机飞经某个拟飞通道前, 可以首先利用机载CCD相机等光电探测设备获取前方飞行环境的图像信息, 并利用机上图像识别系统提取障碍建筑物的边界信息, 识别出拟飞通道。然后, 基于这些信息对当前拟飞通道进行障碍边界归一化, 再运用Laguerre最佳避撞路径规划定理建立该航段的最佳避撞路径。路径指令经过飞控系统的执行, 确保无人机安全飞越该通道。完成该航段的飞行后, 即进入下一航段, 机上路径规划系统再次滚动执行上述单航段的实时规划过程。这一过程直至无人机到达目标航点时终止。图 5说明了该方法的运行流程。

4 路径规划实验与分析

本节考察文中方法对于复杂低空环境实时防碰撞的有效性。图 6a)是取自Google地图的某城市小区的建筑物分布关系, 参照该图设计图 6b) 所示的具有复杂位置关系的模拟低空飞行场景。设想一架传递包裹的小型旋翼无人机要穿越这些建筑物从图中STA点飞行到END点。分别使用3种不同的面向城市区域的路径规划方法。方法1是文献[12]的基于Laguerre图的自优化A^*方法 (LA-STAR), 方法2为文献[13]提出的综合路径规划方法 (LBT), 本文建立的全过程实时Laguerre避撞路径规划方法 (GRTLP) 作为方法3。

3种方法得到的路径分别如图 7中的3条曲线所示。对比分析该项实验结果可以看出:(1) 从路径的综合避撞效果看, 本文方法规划出的路径对于两侧建筑物均具有较好的安全距离, 因而也具有更好的避撞安全性。(2) 从路径规划方法的使用看, 在LA-STAR方法中, 需要为拟飞区域中的每个建筑物首先建立一个图 8所示的外接圆, 这需要提前知道所有建筑物的分布和特征信息。LBT方法在运用时同样需要提前知道拟飞区域的建筑物分布信息。而本文方法面向陌生城市环境设计, 不需要提前掌握这些信息, 可以满足实时在线应用的需求。

考虑到不同路径所经历的通道不一样, 各个飞行通道的宽度也不尽相同, 为客观定量评价各个规划路径对于通道两侧障碍的防碰撞安全性, 定义路径的无量纲避撞安全指标。其中L为当前航点所在飞行通道的宽度, L_A和L_B分别为当前航点与所在飞行通道左右两侧边界的垂直距离, 且L_A+L_B=L。沿飞行纵向任意选定若干参考点, 对应这些参考点, 在每条路径上选取相应数量的航点。计算每个路径上各个航点的无量纲避撞安全指标值, 绘制3种方法路径的无量纲避撞安全指标曲线如图 9所示。分析误差曲线可知, 本文方法的路径避撞安全指标总体较小, 且趋势较平稳, 反映了规划出的路径具有更好的避撞安全性。

5 结论

本文以小型无人机引起的城市低空飞行安全问题为背景, 针对在陌生城市低空区域飞行的防碰撞需要, 研究了适宜于城市低空实时避撞的无人机路径规划方法。基于航段分解建立了滚动Laguerre路径规划模型, 为基于Laguerre图的实时路径规划提供了实现机理。通过障碍物边界归一化, 解决了城市建筑物异型位置关系可能导致的Laguerre路径不一致问题。建立的单航段最佳避撞路径规划定理和全过程Laguerre实时避撞路径规划方法, 有效实现了面向复杂陌生城市环境的安全防碰撞。文中工作为Laguerre技术的在线实现和应用进行了有益的创新探索。今后将深入研究大区域飞行的实时路径规划需要, 在考虑防碰撞安全约束的基础上, 综合考虑路径最短等多种约束, 进一步丰富Laguerre技术的在线应用理论和方法。