风场影响下微型无人飞行器的多分辨率路径规划方法

摘要

本发明公开了一种风场影响下微型无人飞行器的多分辨率路径规划方法，该方法有六大步骤：步骤一：获取飞行器路径规划所需要的环境区域；步骤二：选取小波变换的基函数；步骤三：构建风场影响下的飞行环境代价函数；步骤四：利用Haar小波网格分解法重构多分辨率飞行环境代价函数；步骤五：利用多分辨率环境代价函数值生成环境加权图；步骤六：寻找最优路径。本发明方法在确定环境区域不同分辨率等级过程中考虑了机载计算机的计算能力、传感器的探测范围、障碍物的分布、风场的分布及强度等因素，提高了路径规划的效率，且该方法简单可靠实用，适合于风场影响下的低空微型无人飞行器在线路径规划。

说明书

技术领域

本发明属于航空优化技术领域，尤其涉及微型无人飞行器路径规划技术领域，具体是一 种风场影响下微型无人飞行器的多分辨率路径规划方法。

背景技术

微型无人飞行器作为一种相对低成本的特殊工具在民用和军用领域越来越受到重视。在 一些危险地区或人类难以涉足的地区，微型无人飞行器具有很大优势，可以用来侦查重要军 事设施，监视实时灾害和交通状况，搜寻和搜救工作等。微型无人飞行器由于体积小，重量 轻，有效载荷小，使得机载计算机的计算能力和传感器性能受到限制。计算能力的限制要求 微型无人飞行器中算法的计算量要小，传感器的性能限制了侦查空间的有效范围，因此，针 对微型无人飞行器设计一种高效实时的路径规划算法对实际应用有重要意义。

由于传感器性能的限制，微型无人飞行器通常工作在低空区域，需要规避建筑物和树木 等障碍物，同时，由于微型无人飞行器重量轻，飞行路径极易受到风场的影响，这使得其路 径规划更加具有挑战性。但现有技术中，针对低空的微型无人飞行器的路径规划，面临着计 算能力、传感器性能有限，并且易受风场影响等实际问题。

发明内容

本发明针对现有低空微型无人飞行器在路径规划中面临的计算能力、传感器性能有限和 易受风场影响等实际问题，提供了一种风场影响下微型无人飞行器的多分辨率路径规划方法， 利用小波变换进行环境区域网格的多层次分解，从而设计了一种适合低空飞行的微型无人飞 行器在线路径规划方法，提高了在线规划的效率和鲁棒性。

本发明提出的一种风场影响下微型无人飞行器的多分辨率路径规划方法，通过如下步骤 来实现：

步骤1：获取飞行器路径规划所需要的环境区域。

步骤2：选取哈尔(Haar)小波变换基函数，构建二维空间的Haar小波基函数，并得到 用二维空间的小波变换基函数对二元函数近似逼近的函数。

步骤3：考虑飞行器与障碍物之间的距离、风场的强度、以及风场的梯度三种因素的影 响，构建飞行环境代价函数。

步骤4：利用Haar小波网格分解法重构多分辨率飞行环境代价函数。

步骤5：确定各网格单元的飞行环境代价函数值，将环境区域根据障碍物与非障碍物的 表示值，以及飞行环境代价函数值生成环境加权图，将多分辨率路径规划问题转化为图的搜 索问题。

步骤6：基于A*或Dijkstra搜索方法寻找最优路径。

所述步骤1中获取微型无人飞行器路径规划所需要的环境区域由如下步骤完成：

步骤1.1：将飞行器所处的三维环境空间区域，从高度方向上分解为不同层次的二维欧 氏空间，所得到的二维欧氏空间就是所需要的环境区域；

步骤1.2：将得到的二维欧氏空间根据地形高程和飞行器可飞行高度，划分为障碍区和 非障碍区，并确定飞行器的初始位置和目标位置；对原始数字地形高程图中第i点位置Xi表 示如下：

其中，表示障碍物空间，表示非障碍物空间，z_i表示位置X_i的地形高程，H表示飞行 器的可飞行高度；

步骤1.3：将环境区域归一化为单位方形区域，并进行网格划分。

所述步骤2中构建二维空间的小波变换基函数以及用二维空间的小波变换基函数对二元 函数近似逼近的方法具体是：

步骤2.1：选取一维空间的Haar基本小波，将Haar基本小波通过伸缩和平移操作得到 一组形状相似的小波，得到一维空间的Haar小波基函数：

${\phi }_i^j\left(x\right)=\sqrt{2^j}\phi (2^{j}x-i),$${\psi }_i^j\left(x\right)=\sqrt{2^j}\psi (2^{j}x-i)$

j＝0，1，…J_maxand i＝0，1，…，2j-1

其中，j表示分辨率等级，2^j表示伸缩因子，i表示平移量，分别表示伸缩 和平移后的Haar尺度函数和Haar母小波函数，x表示一维空间的位置变量；

步骤2.2：由一维空间的Haar小波基函数构造二维空间的Haar小波基函数如下：

${\Phi }_{m,n}^j(x,y)={\phi }_m^j\left(x\right){\phi }_n^j\left(y\right)$

${\Psi }_{m,n}^{1,j}(x,y)={\phi }_m^j\left(x\right){\psi }_n^j\left(y\right)$

${\Psi }_{m,n}^{2,j}(x,y)={\psi }_m^j\left(x\right){\phi }_n^j\left(y\right)$

${\Psi }_{m,n}^{3,j}(x,y)={\psi }_m^j\left(x\right){\psi }_n^j\left(y\right)$

其中，(x，y)表示二维空间的位置变量，m，n为二维空间两个方向的位置标号；表 示二维空间的Haar尺度函数，表示在n方向的Haar母小波函数，表示 在m方向的Haar母小波函数，表示在对角线方向的Haar母小波函数；

步骤2.3：将任意一个二元函数用二维空间的Haar小波基函数近似 逼近，得到：

其中，J表示最低分辨率等级，表示整数；为近似逼近中二维空间Haar尺度函数 的系数，${\lambda }_{m,n}^j={\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }f(x,y){\Phi }_{m,n}^j(x,y)\mathrm{dx><mo>;</mo>}$为近似逼近中二维空间Haar母小波函 数的系数，不同层次逼近的形式就是多分辨表示的形 式，逼近分为两部分，步骤2.3得到的式子的右边的第一项对f(x，y)的粗略近似，右边的第 二项包含了f(x，y)的更多细节信息。

所述的步骤3中所构建的飞行环境代价函数f(X)为：

f(X)＝α·rm₁(X)+β·rm₂(X)+γ·rm₃(X)

其中，X表示当前飞行器的位置坐标，α，β和γ是调节三种因素在代价函数中相对重要性的参 数，取值范围为0～1之间；rm₁(X)表示飞行器与障碍物之间的距离因素对飞行环境的影响， rm₂(X)表示风场的强度对飞行环境的影响，rm₃(X)表示风场的梯度对飞行环境的影响。

所述步骤4中利用Haar小波网格分解法重构多分辨率飞行环境代价函数由如下步骤完 成：

步骤4.1：根据原始数字地形高程图的分辨率和机载计算机的计算资源确定环境区域表 示的最高分辨率等级J_max，根据规划问题的具体需求确定环境区域表示的最低分辨率等级 J_min；

步骤4.2：将任意一个分辨率等级的网格单元、同一层次分辨率区域范围、以及同一层 次分辨率区域中心坐标进行公式化表示；

步骤4.3：将步骤3得到的飞行环境代价函数，采用步骤2中的二维空间的Haar小波 变换基函数近似逼近，重构多分辨率飞行环境代价函数。

所述的步骤5中生成的环境加权图，该环境加权图中的每个节点对应一个网格单元，节 点的值表示该处是障碍物还是非障碍物，如果两个网格单元相邻，则用相应的两个节点的边 来表示，边上的值表示从一个节点转移到另一个节点的飞行环境代价函数的值。

本发明方法的优点和积极效果在于：

(1)采用多分辨率路径规划减少了环境表示的数据量，在满足规划要求的条件下，降低 了对机载计算资源的消耗，提高了在线规划的实时性，且本发明的方法简单可靠实用，易于 操作，适合于风场影响下的低空微型无人飞行器在线路径规划；

(2)考虑了风场对低空微型无人飞行器路径规划的影响，多分辨率表示可以使微型无人 飞行器更好地规避风场的影响；在确定环境区域不同分辨率等级过程中考虑了机载计算机的 计算能力、传感器的探测范围、障碍物的分布、风场的分布及强度等因素，提高了路径规划 的效率和鲁棒性。

附图说明

图1为本发明的多分辨率路径规划方法的整体步骤流程图；

图2为一个原始数字地形高程图的示例；

图3为采用本发明方法多分辨率表示环境区域的示意图；

图4为未采用多分辨率和采用多分辨率后的路径规划运行时间效率曲线；

图5为未考虑风场影响下的路径规划效果图；

图6为考虑了风场影响后的路径规划效果图。

具体实施方式

下面结合附图和实施例对本发明的方法进行具体说明。

本发明方法的主要思想是：在路径环境模型表示满足一定逼真度和精确度的前提下，根 据机载计算机计算能力、机载传感器性能和环境详细信息对环境区域采用不同细节层次的模 型表示，减少环境模型的复杂度和计算量，取得环境模型表示的复杂度、逼真度、精确度和 计算效率之间的折中。通过利用Haar小波函数对飞行器路径上的环境信息进行多分辨率表 示，将环境空间划分成一系列依次嵌套的子空间来自动生成多尺度的空间表示，而且Haar 小波变换可以使环境数据中包含的环境特征在不同尺度上被提取出来，保留了环境信息的结 构特征，为路径规划的多分辨率处理与表达提供了有效方法。在环境区域的不同细节层次， 即不同分辨率层次确定过程中，机载计算机的计算能力确定了分辨率的最高细节，传感器的 探测范围和风场分布范围确定了分辨率的空间区域，障碍物分布、风场强度、风场变化程度 确定了分辨率的不同等级。

如图1所示，本发明的风场影响下微型无人飞行器的多分辨率路径规划方法可以按照如 下步骤完成：

步骤一：获取飞行器路径规划所需要的环境区域。

步骤1.1：三维空间可以从高度方向上分解为不同层次的二维空间，假设微型无人飞行器 路径规划所需要的环境区域为二维欧氏空间，表示为

步骤1.2：飞行器不可穿越的山体、建筑等障碍物空间表示为则非障碍物空间表 示为路径规划问题抽象为：如果无人飞行器的初始位置点为和目标位置 点为在空间中寻找一系列的可飞行位置点，以满足一定的约束条件和目标条件。本 发明实施例中选用的环境区域为1024×1024像素的数字地形高程图。当地形高程q_i高于飞行 器可飞行高度H，则该区域为障碍物区域；当地形高程q_i低于飞行器可飞行高度H，该区域为 无障碍物区域，可采用式(1)表示：

X_i表示数字地形高程图中的某一点位置，q_i表示位置X_i的地形高程。所述的飞行器可飞行 高度H是微型无人飞行器安全飞行的最低高度(相对于海平面)，低于此高度飞行则可能发生 危险。

步骤1.3：为了使算法的描述具有可读性，不失一般性，环境区域归一化为单位方形区 域，表示为[0，1]×[0，1]，可以分解的最精细网格为2^N×2^N，间隔为1/2^N，由于原始地形图 为1024×1024像素，所以选取的N＝10。如果最高分辨等级为J_max，则J_max不能大于N。

如图2所示，为一个原始数字地形高程图，原始数字地形高程图的分辨率决定了可以达 到的最精细网格，环境区域表示的最高分辨率受最精细网格划分的限制。

步骤二：选取小波变换的基函数。

步骤2.1：选取Haar基本小波，确定一维空间的Haar小波基函数。

在多分辨率建模过程中，环境代价函数是通过小波变换基函数来逼近重构的，不同层次 的逼近代表不同等级的分辨率。选择合适的小波变换基函数对环境代价函数进行逼近，使得 小波变换能方便准确地描述多分辨率环境空间的特征。本发明中选用Haar小波基函数，Haar 小波基函数是最简单适用的具有紧支撑性的正交小波函数。由于环境区域为二维欧氏空间， 可由一维空间的Haar小波基函数构造二维空间的小波基函数。一维空间中的Haar基本小 波表示为：

$\phi \left(x\right)=\left(\begin{array}{cc}1& x\in \left[\mathrm{0,1}\right)\\ 0& x\notin \left[\mathrm{0,1}\right)\end{array}\right),$$\psi \left(x\right)=\left(\begin{array}{cc}1& x\in [\mathrm{0,1}/2)\\ -1& x\in [1/\mathrm{2,1})\\ 0& x\notin \left[\mathrm{0,1}\right)\end{array}\right)---\left(2\right)$

其中，φ(x)表示Haar尺度函数，ψ(x)表示Haar母小波函数，x表示一维空间的位置变 量。

将式(2)通过伸缩和平移操作得到一组形状相似的小波，得到一维空间的Haar小波基 函数：

${\phi }_i^j\left(x\right)=\sqrt{2^j}\phi (2^{j}x-i),$${\psi }_i^j\left(x\right)=\sqrt{2^j}\psi (2^{j}x-i)$(3)

j＝0，1，…and i＝0，1，…，2^j-1

其中，j表示伸缩因子2^j的指数，能表征分辨率等级，i表示平移量，表示伸 缩和平移后的Haar小波基函数。

步骤2.2：构造二维空间的Haar小波基函数，二维空间的小波基函数为多分辨率表示的 基本元素。根据式(3)构造二维空间的Haar小波基函数如式(4)所示：

${\Phi }_{m,n}^j(x,y)={\phi }_m^j\left(x\right){\phi }_n^j\left(y\right)$

${\Psi }_{m,n}^{1,j}(x,y)={\phi }_m^j\left(x\right){\psi }_n^j\left(y\right)$(4)

${\Psi }_{m,n}^{2,j}(x,y)={\psi }_m^j\left(x\right){\phi }_n^j\left(y\right)$

${\Psi }_{m,n}^{3,j}(x,y)={\psi }_m^j\left(x\right){\psi }_n^j\left(y\right)$

上式中上标j可表示分辨率的等级，j越大，可以包括更多的细节信息，分辨率的等级越高； m，n为二维空间两个方向的位置标号，(x，y)表示二维空间的位置变量，表示二维空 间的Haar尺度函数，表示在n方向的Haar母小波函数，表示在m方向 的Haar母小波函数，表示在对角线方向的Haar母小波函数。

步骤2.3：将任意一个二元函数用二维空间的小波基函数形式进行逼近，不同层次逼近的 形式即为多分辨表示的形式，逼近分为两部分，第一部分为粗略近似，第二部分为细节近似。 任意一个函数用式(4)近似逼近为：

(5)

其中，为近似逼近中二维空间Haar尺度函数的系数，为近似逼近中二维空间 Haar母小波函数的系数，具体根据式(6)得到：

${\lambda }_{m,n}^{J_{\min }}={\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }f(x,y){\Phi }_{m,n}^{J_{\min }}(x,y)\mathrm{dx>}$(6)

式(5)中等式右边的第一项是对f(x，y)的粗略近似，近似等级为J_min， 第二项包含了f(x，y)的更多细节信息。J_min为最低分辨率等级， 表示整数，为在二维空间上绝对平方可积的函数集合。

步骤三：构建风场影响下的飞行环境代价函数。

本发明的飞行环境代价函数定义在环境区域上，由三种因素共同影响，分别为微型无 人飞行器与障碍物之间的距离、风场的强度、以及风场的梯度。飞行器与障碍物之间的距离 因素对飞行环境的影响rm₁(X)采用公式(7)表示为：

其中X表示当前微型无人飞行器的位置坐标，Y表示障 碍物的位置坐标。飞行器与障碍物的距离越近，飞行威胁越大。

风场强度对飞行环境的影响rm₂(X)如公式(8)所示：

其中Vp是非障碍物空间中任意一点p的风场速度。V_max计算出 区域中最大的风场强度，||V_Z||∞计算出在Z点处的风场强度，所述的风场强度是指风场速度 的数值大小。飞行器距离风场越近，风场强度越大，则飞行威胁越大。

风场梯度对飞行环境的影响rm₃(X)采用公式(9)表示如下：

其中是非障碍物空间中任意一点p的风场梯度。计 算出区域中风场中的最大梯度，计算出在Z点处风场的梯度。风场梯度越大， 飞行威胁越大。

如果微小型无人飞行器当前的位置坐标为X＝(x，y)，rm₁(X)可以反映位置Y处的障碍物 对飞行器的碰撞威胁，主要和飞行器和障碍物之间的距离有关；rm₂(X)和rm₃(X)分别反映了 位置Z处的风场强度和风场变化强度对飞行器的影响，都为指数函数形式，可以看出影响大小 除了与风场强度和风场变化有关外，还与风场与飞行器的距离有关。

三种因素综合影响下的飞行环境代价函数构建为：

f(X)＝α·rm₁(X)+β·rm₂(X)+γ·rm₃(X)            (10)

其中α，β和γ是调节三种因素在代价函数中相对重要性的参数，取值范围为0～1之间。

步骤四：利用Haar小波网格分解法重构多分辨率飞行环境代价函数。

步骤4.1：在利用Haar小波网格分解法重构多分辨率飞行环境代价函数过程中，最高 分辨率等级J_max和最低分辨率等级J_min的选择由机载计算资源和问题的具体需求有关，根据 原始数字地形高程图的分辨率和机载计算机的计算资源确定环境区域表示的最高分辨率，根 据规划问题的具体需求确定环境区域表示的最低分辨率。

步骤4.2：将任意一个分辨率等级的网格单元、同一层次分辨率区域范围、以及同一层 次分辨率区域中心坐标进行公式化表示。

环境区域中的任意一个等级的分辨率j，满足J_min≤j≤J_max。在分辨率等级为j时，网 格间隔为1/2^j，任一单元网格可以表示为：

上式中，$h_m^j=[m/2^j,(m+1)/2^j],$表示在分辨率等级为j情况下，m方向的空间间 隔，表示在分辨率等级为j情况下，n方向的空间间隔，$h_n^j=[n/2^j,(n+1)/2^j].$在j分辨 率等级下的网格点中心坐标集合为：

式(12)中r^j表示在j分辨率等级下的区域范围，r^j＞r^j+1，较高分辨率等级区域嵌套在 较低分辨率等级区域中，Y表示环境区域中的某一个位置坐标。

步骤4.3：将步骤三得到的飞行环境代价函数，按步骤二中的二维空间的Haar小波变 换基函数近似逼近，进行Haar小波网格分解法重构。

环境代价函数可以由Haar小波分解为：

其中，N(J_min)表示在分辨率等级为J_min的情况下的位置标号的取值集合，具体可将J_min代 入式(14)中可得到：

N(j)表示在分辨率等级为j情况下，位置标号的取值集合。

G(j)表示在分辨率等级为j情况下，考虑了障碍物和风场区域后，m方向的位置标号取值 序列，根据式(15)得到：

(15)

H(j)表示在分辨率等级为j情况下，考虑了障碍物和风场区域后，n方向的位置标号取值 序列，根据式(16)得到：

(16)

式(15)和式(16)中，X＝(x，y)，Z＝(z_x，z_y)分别是微型无人飞行器和风场中心位置的坐标。 从G(j)和H(j)可以看出，离飞行器和风场越近的环境区域，表示的分辨率越高。

步骤五：利用多分辨率环境代价函数值生成环境加权图。

通过式(13)将飞行环境代价函数分解为多分辨率形式，分解的单元网格结果与环境加 权图G＝(V，E)对应，V表示图中节点的集合，E表示节点之间边的集合。每个网格单元对应 加权图中相应的一个节点，如果两个网格单元相邻则用相应的两个节点的边来表示。节点的 值表示该处是障碍物还是非障碍物，若是障碍物用表示障碍物空间的符号来标记该节点的 值，若是非障碍物用表示非障碍物空间均符号标记该节点的值，边上的值表示从一个节点 转移到另一个节点的飞行环境代价函数f(X)的值。对于两个相邻的网格单元，对应的两个节 点间会有边，边是有方向的，边上的值为第一个节点所指向的第二个节点的飞行环境代价函 数的值。

步骤六：基于A*或Dijkstra搜索方法寻找最优路径。

生成环境加权图后，即可以利用常用的A*或Dijkstra搜索方法来寻找最优路径。

通过上述方法的描述可以看出，由于低空飞行的微型无人飞行器计算能力和传感器性能 有限，而且飞行路径易受风场的影响，利用Haar小波网格分解法重构的多分辨率路径规划 可以减少环境表示的数据量，降低机载计算资源的消耗，提高在线规划实时性。根据飞行器 与障碍物之间的距离关系，风场的位置、强度及变化程度确定环境多分辨率表示的范围和等 级，有效地考虑了风场对低空微型无人飞行器路径规划的影响，使微型无人飞行器更好地规 避障碍物和风场。

本发明方法用计算机程序实现描述：微型无人飞行器在初始时刻t＝t₀的位置为 x(t₀)＝x₀，在每个时间步长t_i(i＝0，1，…)构建环境区域的多分辨率网格分解，该分解结果 与t_i时刻的环境加权图G_i＝(V_i，E_i)相对应。针对环境加权图，在每个时间步长内迭代执 行A*或Dijkstra搜索方法，则得到不同时刻的位置序列{x(t₀)，x(t₁)，…，x(t_f)}，该过程直到满 足条件||x(t_f)-x_f||_∞＜1/2^J_max时结束。x(t_f)表示微型无人飞行器在时刻t_f的位置。

上述设计方法在Intel Pentium(R)双核2.40GHz处理器，2.0G物理内存上实现， 软件条件为Matlab R2010a，对未经过多分辨率表示的环境区域和本发明提出的多分辨表 示环境区域进行微型无人飞行器路径规划仿真，通过对运行时间的比较，如图4与表1所示， 可以看出：在环境区域比较小时，采用未经过多分辨率表示的环境区域进行微型无人飞行器 路径规划仿真和采用本发明方法进行微型无人飞行器路径规划仿真的运行时间相差不大，但 随着环境区域的扩大，采用本发明方法进行路径规划的时间明显小于采用未经过多分辨率表 示的环境区域情况下的路径规划的运行时间，从而看出，采用本发明方法提高了微型无人飞 行器路径规划的运行效率。实验结果如表1所示：

表1两种方法运行时间的影响

图2为路径规划原始地形高程图颜色较暗区域对应较高的地形高程，颜色较亮区域对应 较低的地形高程。图3为路径规划环境区域多分辨率表示的示意图，多分辨率表示采用的最 高分辨率要低于原始地形高程图的分辨率，图中用三个等级的分辨率表示环境区域，星号标 识为微型无人飞行器的当前位置，在远离飞行器的环境区域方向上分辨率等级逐步降低。

图5和图6中的圆圈和方块分别标识为微型无人飞行器的初始位置和目标点位置，两个 位置点之间的连线为微型无人飞行器规划的路径，图5给出了未考虑风场影响下的路径规划 效果图，在时间t＝t₃₀时，飞行器周围环境采用了三种分辨率表示；图6给出了考虑了风场 影响下的路径规划效果图，在时间t＝t₃₅时，飞行器周围环境和风场环境采用了多分辨率表 示，通过对图5，6的比较可以看出，由于考虑了风场的分布及强度，飞行器的在线规划轨 迹得到了修正。

为了降低计算负担，提高微型无人飞行器路径规划的实时性，将微型无人飞行器的飞行 环境用不同层次的分辨率表示，距离飞行器较近的障碍物和风场变化剧烈的区域采用较高分 辨率，距离飞行器较远的障碍物和风场变化平缓的区域采用较低分辨率，这种表示方法使得 需要处理的数据量减少，一方面提高了算法的实时性，另一方面考虑了风场对路径规划的影 响，是一种简单实用的新方法。本发明方法通过将Haar小波网格分解理论应用于对飞行环 境的多分辨率表示中，使得微型无人飞行器在距离障碍物和风场较近的区域，风场强度和梯 度变化较大的区域采用较高的分辨率，这样既提高了飞行器在线规划的效率，解决了机载计 算机计算资源有限的问题，又可以更加有效地规避障碍物和风场，减少路径上的环境威胁。 本发明具有较强的实用性，为风场影响下低空飞行的微型无人飞行器在线路径规划提供了一 种简单实用的新方法。