CN107228673A - 航路规划方法及装置 - Google Patents

Abstract

本发明实施例提供一种航路规划方法及装置，属于导航技术领域。方法包括：根据对三维空间区域进行剖分得到的立体块在二维平面上的对象模型以及为所述对象模型设置的编码，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象；在所述三维空间区域上对沿着各自对应的规划运动路径行进时存在碰撞的目标对象重新进行运动路径规划，本发明降低了空间规划的计算量，以及运动规律的复杂度，从而提高了航路规划的效率。

Description

航路规划方法及装置

技术领域

本发明实施例涉及导航技术领域，尤其涉及一种航路规划方法及装置。

背景技术

在军航、民航、通航以及无人机等航空业界，空间管控问题成为最受关注的应用问题之一，尤其一方面随着低空领域的开放，空间中各种飞行器的数量越来越多即多目标，从而导致空间管控的压力逐渐变大；另外一方面，空间中飞行器运动规律变化越来越复杂，使得航路规划的计算量呈现几何级数的增长，计算的复杂度越来越高，航路规划的计算效率较低。

因此，如何才能有效降低计算的复杂度，使航路规划的计算更加高效，从而进一步实现空间使用效率的提高、多目标条件下的目标飞行器碰撞风险的规避，最终实现对的航路规划和管控，保证目标飞行器的协同与安全，已成为空间管控亟待解决的重大瓶颈问题。

为了解决上述技术问题，现有技术中普遍以经纬度为基础，通过解算与优化大量的矢量方程，来实现对目标飞行器的航路规划和管控。但是，现有技术中使用的这种解决方案会使用大量的浮点运算来求解复杂方程，受计算复杂度的限制，一般只能适用于空域中为数不多、且运动规律不复杂的目标飞行器，一旦空域中的目标飞行器的数量增加到一定数量，或者运动规律和轨迹比较复杂时，就会存在计算瓶颈问题：要么计算量和复杂度呈指数型增长，一般的硬件资源很难胜任；要么难以列出矢量方程，完全无法求解。

国内外现行使用的各种空间管控应用系统，普遍以经纬度为基础，通过解算与优化传统的坐标方程，来实现对目标飞行器的航路规划和管控。

在这种体制的规划过程中，要使用大量的浮点运算来求解复杂方程，受计算复杂度的限制，一般只能同时计算和规划数百个简单运动的目标飞行器，一旦目标飞行器需求数目的不断增加，以及运动规律的复杂变化，比如同时有飞机、导弹等多种目标飞行器同时占用同一空域的情形，会导致空间规划的计算量将呈几何级数型增长，运动规律的复杂度更高，从而导致甚至无法求解上述复杂方程。

发明内容

有鉴于此，本发明实施例所解决的技术问题之一在于提供一种航路规划方法及装置，用以克服现有技术中上述缺陷。

本发明实施例提供一种航路规划方法，其包括：

根据对三维空间区域进行剖分得到的立体块在二维平面上的对象模型以及为所述对象模型设置的编码，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象；

在所述三维空间区域上对沿着各自对应的规划运动路径行进时存在碰撞的目标对象重新进行运动路径规划。

可选地，在本发明的任一实施例中，对三维空间区域进行剖分得到的立体块为根据GeoSOT空间剖分方式对三维空间区域进行剖分得到的立体块。

可选地，在本发明的任一实施例中，为所述对象模型设置的编码为根据北斗网格码编码方式为所述对象模型设置的编码。

可选地，在本发明的任一实施例中，所述对象模型包括：点对象数据模型、线对象数据模型、面对像数据模型中的任一种或多种的组合。

可选地，在本发明的任一实施例中，所述对象模型包括一个或多个网格，所述网格为对所述二维平面进行多叉树划分得到的区域。

可选地，在本发明的任一实施例中，所述立体块包括所述三维空间区域中空间实体对应的立体块，不同所述立体块与为所述对象模型设置的编码一一对应。

可选地，在本发明的任一实施例中，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象包括：剔除沿着各自规划的运动路径行进时不存在碰撞可能的目标对象。

可选地，在本发明的任一实施例中，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象包括：若不同目标对象沿着各自规划的运动路径行进时会位于同一对象模型中，则判定目标对象沿着各自对应的规划运动路径行进时存在碰撞。

可选地，在本发明的任一实施例中，所述航路规划方法还包括：判断不同目标对象在对应的规划路径上沿着第一方向行进时不同目标对象之间的距离是否小于预设的距离，如果小于，则判定不同目标对象沿着各自对应的规划运动路径行进时存在碰撞，否则判定不同目标对象沿着各自对应的规划运动路径行进时不存在碰撞；

或者，所述航路规划方法还包括：判断不同目标对象在对应的规划路径上沿着第一方向行进时以目标对象为中心的位置矢量是否会发生重合，如果是，则判定不同目标对象沿着各自对应的规划运动路径行进时存在碰撞，否则判定不同目标对象沿着各自对应的规划运动路径行进时不存在碰撞。

可选地，在本发明的任一实施例中，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象包括：根据不同目标对象沿着各自规划出的运动路径行进时对应的状态索引，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象。

可选地，在本发明的任一实施例中，所述编码为聚合编码，所述聚合编码主要由所述对象模型所在角点定位面片的编码、沿纬向的面片跨度、沿经向的面片跨度组成。

本发明实施例还提供一种航路规划装置，其包括：路径规划单元、碰撞确定单元，碰撞确定单元用于根据对三维空间区域进行剖分得到的立体块在二维平面上的对象模型以及为所述对象模型设置的编码，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象，所述路径规划单元用于在所述三维空间区域上对沿着各自对应的规划运动路径行进时存在碰撞的目标对象重新进行运动路径规划。

由以上技术方案可见，本发明实施例中，通过根据对三维空间区域进行剖分得到的立体块在二维平面上的对象模型以及为所述对象模型设置的编码，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象；在所述三维空间区域上对沿着各自对应的规划运动路径行进时存在碰撞的目标对象重新进行运动路径规划，降低了空间规划的计算量，以及运动规律的复杂度，从而提高了航路规划的效率。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明实施例中记载的一些实施例，对于本领域普通技术人员来讲，还可以根据这些附图获得其他的附图。

图1为本发明实施例一中航路规划方法的流程示意图；

图2为本发明实施例二中多层级网格剖分示意图；

图3A、3B、3C分别为本发明实施例三中点对象模型、线对象模型、面对像模型的示意图；

图4为本发明实施例四中编码的示意图；

图5为本发明实施例五中编码的示意图；

图6为本发明实施例六中基于目标对象的信息组织方式示意图；

图7为本发明实施例七中基于状态的静态信息组织方式；

图8为本发明实施例八中根据图6和图7建立的状态索引关系图；

图9为本发明实施例中在二维平面上进行三维冲突检测示意图；

图10为本发明实施例对碰撞位置进行预警示意图；

图11为本发明实施例单个目标对象的原航路示意图；

图12为本发明实施例中对原航路重新规划后的防撞规划路径示意图。

图13为本发明实施例航路规划装置的结构示意图。

具体实施方式

当然，实施本发明实施例的任一技术方案必不一定需要同时达到以上的所有优点。

为了使本领域的人员更好地理解本发明实施例中的技术方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本发明实施例一部分实施例，而不是全部的实施例。基于本发明实施例中的实施例，本领域普通技术人员所获得的所有其他实施例，都应当属于本发明实施例保护的范围。

本发明下述实施例中，通过根据对三维空间区域进行剖分得到的立体块在二维平面上的对象模型以及为所述对象模型设置的编码，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象；在所述三维空间区域上对沿着各自对应的规划运动路径行进时存在碰撞的目标对象重新进行运动路径规划，降低了空间规划的计算量，以及运动规律的复杂度，从而提高了航路规划的效率。

下面结合本发明实施例附图进一步说明本发明实施例具体实现。

在实现本发明的过程中，发明人对导致上述技术问题的原因做进一步分析如下，但是，需要说明的是下述任一或者多种的原因都可能会导致上述技术问题的发生。

下面对可能导致这些发生的原因进行示例性分析，可能是如下一种或多种原因。

首先，航路规划一般是分别对单个目标飞行器进行的航迹规划，在目标自身性能约束(如最大航程、最大爬升角、最小步长、最小转弯半径)和威胁约束(如雷达威胁、导弹威胁、高炮威胁、大气威胁、地形威胁)等多约束条件下，根据目标飞行器的任务点进行路径选择因而是一个多约束条件的组合优化问题。目前针对不同的约束条件分别提出一些航路规划的方法有多种，常用的有基于A*算法提出的面向实时鲁棒性航路规划的稀疏A*算法、Voronoi图方法、蚁群算法、遗传算法等。现实中由于空域中通常有多个目标飞行器，因此，按照上述航路规划方法对大量目标飞行器同时进行航路规划，需要考虑各目标之间的相互影响和协同配合，最优航迹的选择不能以某一个目标飞行器的航路最优化而定，需要综合考虑各目标飞行器的航路整体最优而定，因而上述诸如蚁群算法、遗传算法等智能优化算法在处理此问题时，就会出现空间规划的计算量将呈几何级数型增长，运动规律的复杂度更高，从而导致甚至无法求解上述复杂方程。

其次，现有的航迹规划多是在二维平面(或三维空间的某个截面、或三维空间在平面的投影)，同时将地形作为约束，在二维空间内根据目标任务点求取最优路径。现实中则是在三维空间中，需要同时考虑目标在水平方向和垂直方向的航迹规划以及地形、雷达、大气等三维要素。如果再加上目标飞行器的动态特性(时间)，进一步会出现空间规划的计算量将呈几何级数型增长，运动规律的复杂度更高，从而导致甚至无法求解上述复杂方程。

再者，现有目标航迹规划是在静态环境中进行，对某一目标飞行器而言是在固定的节点间(静态节点)比如目标飞行器起飞前通过组合优化确定最优航路。但是，在，对任一目标飞行器，除了静态节点，还要考虑动态节点 (如其他目标飞行器的存在)对原规划航路的影响，动态节点的出现会导致突发的威胁约束条件，进一步会出现空间规划的计算量将呈几何级数型增长，运动规律的复杂度更高，从而导致甚至无法求解上述复杂方程。

最后，现有航路规划多为离线航迹规划，即在目标飞行器起飞前加载已经规划好的航路，在飞行的过程中不再改变航路，但是，现实情况中由于动态威胁约束的出现，需要进行在线航迹规划，即在目标飞行过程中根据需要动态的不断修改规划好的航路，进一步会出现空间规划的计算量将呈几何级数型增长，运动规律的复杂度更高，从而导致甚至无法求解上述复杂方程。

下述将结合具体实施例对本发明进行示例性解释。

图1为本发明实施例一中航路规划方法的流程示意图；如图1所示，其包括：

S101、选取应用于航路规划方法的三维试验空间区域；

本实施例中，比如该实验空间区域某地长约8公里，宽约6公里，高为 500～2500米的空域。

S102、对所述三维试验空间区域进行剖分得到多个立体块并映射到二维平面上的对象模型。

本实施例中，在对三维空间区域进行剖分时，可以根据GeoSOT空间剖分方式对三维空间区域进行剖分得到的多个立体块，该多个立体块相互之间体积形状相似、既无缝隙也不重叠，该多个立体块可形成多层次的离散网络。

当将本发明实施例应用于航空业界时，三维试验空间区域相对来说是比较复杂的三维空间，其中的空间实体包含大量的静态目标对象，还可能包括多个动态目标对象，静态目标对象比如包括地形、山丘、楼宇等，动态目标对象比如包括导弹、高炮、无人机。考虑到无论静态目标或动态目标从物理层面上都占据一定的地理空间，因此，在对三维试验空间区域进行剖分时，将地理空间作为地理现象的基本属性来进行剖分从而得到多个立方体，从而实现空间中静态目标对象、动态目标对象的关联，将目标对象(包括静态目标对象、动态目标对象)按照它们所占据的地理空间关联至对应的立体块内，从而从中实现了三维试验空间区域中目标对象之间的关联关系的建立。

本实施例中，再通过映射到二维平面上，与二维平面上的对应模型建立对应关系，再对映射了立体块的对象模型进行编码，比如根据北斗网格码编码方式为所述对象模型设置编码。

本实施例中，所述对象模型包括：点对象数据模型、线对象数据模型、面对像数据模型中的任一种或多种的组合。进一步地，所述对象模型包括一个或多个网格，所述网格为对所述二维平面进行多叉树划分得到的区域。

具体地，本实施例中，对点对象数据模型、线对象数据模型、面对像数据模型分别详细说明如下，并不限定本实施例中会同时存在点对象数据模型、线对象数据模型、面对像数据模型。

本实施例中，对于点对象数据模型，由于地理概念上点没有尺寸只有位置，因此，本实施例中在剖分时，点目标对象采用单个网格表达，为了达到更高的表达精细程度，可以增加剖分网格的级别，即GeoSOT空间剖分进行多层级剖分，从而使用多个网格表达。本实施例中，对于线对象数据模型，可以表达为一串首尾相连、线状延伸的网格集合。与点对象模型相同，线对象模型可以选定一定的剖分网格精度，即GeoSOT空间剖分进行多层级剖分，从而采用更多个网格进行表达。当然，在本发明的另外一实施例中，在某一剖分层级上，如果目标对象某一位置的某一方向(可以为四邻域方向、八邻域方向)上不止一个网格，则该线状对象也可以等效为作面对象数据模型。

本实施例中，对于面对象数据模型，目标对象采用一定剖分精度的一组网格集合表达，面对象的模型可为一系列网格的编码组合。

由上可见，在剖分空间来看，点对象模型可由某一尺度的网格单元表达点目标对象；而线和面对象模型进一步由一组球面相邻的网格单元集合表达线目标对象、面目标对象，在网格单元中记录目标对象的灰度值，相当于形成栅格数据，一个网格可以等效为一个像素。

示例性地，图2为本发明实施例二中多层级网格剖分的示意图。如图3A、 3B、3C为对象模型分别为点对象数据模型、线对象数据模型、面对像数据模型时的多层级剖分示意图，层级越高，对应的网格数越多，精度也就越高。

S103、为步骤S102中的对象模型进行编码。

本实施例中，所述立体块包括所述三维空间区域中空间实体对应的立体块，为此，不同所述立体块与为所述对象模型设置的编码一一对应。

本实施例中，当对象模型为点对象数据模型、线对象数据模型、面对像数据模型对应的网格根据剖分的层级进行编码，比如按照多叉树比如四叉树、六杈树、九叉树等进行多层级剖分，从而形成多层级的编码。具体地，GeoSOT 网格编码分为三段：度级、分级、秒级及秒以下网格编码。当可以利用编码长度来隐含网格层级时，编码越长表明网格越细；当无法利用编码长度来隐含网格层级时，需要额外的网格层级编码。GeoSO网格编码有四种形式：四进制1维编码、二进制1维编码、二进制2维编码、十进制2维编码。

图3A、3B、3C分别为本发明实施例三中点对象模型、线对象模型、面对像模型的示意图；图4为本发明实施例四中编码的示意图；如图3A-3C、以及图4所示，将空间的目标对象抽象为点、线、面三种对象模型，按四叉树 Z序对各种对象模型进行编码。在其他实施例中，也可以按照八叉树反Z序对各种对象模型进行编码。

具体地，本实施例中，据GeoSOT编码模型的统一架构设计，空间信息的 GeoSOT区位标识是以GeoSOT剖分层级(剖分尺度)下的面片聚合(网格) 表达空间目标对象的空间位置和区域范围，因此，GeoSOT编码可以采用以空间目标对象在GeoSOT面片中的角点面片为位置向量，以沿纬向的面片跨度和沿经向的面片跨度为尺度向量的聚合编码，将空间定位、尺度、范围和结构集于一体，即(C0，M，N)，如图5所示为本发明实施例五中编码的示意图；其中，C0为角点定位面片编码，M为沿纬向的面片跨度，N为沿经向的面片跨度，M和N取值范围为{1，2，3，…，n}，n为正整数，n的大小取决于剖分的级别；当M＝1和N＝1时，即纬向和经向面片跨度均为1时，(C0，1， 1)＝C0。

S104、根据对三维空间区域进行剖分得到的立体块在二维平面上的对象模型以及为所述对象模型设置的编码，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象；

本实施例中，在步骤S104中，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象时，若不同目标对象沿着各自规划的运动路径行进时会位于同一对象模型中，则判定目标对象沿着各自对应的规划运动路径行进时存在碰撞。

具体地，本实施例中，步骤S104中，通过判断不同目标对象在对应的规划路径上沿着第一方向行进时不同目标对象之间的距离是否小于预设的距离，如果小于，则判定不同目标对象沿着各自对应的规划运动路径行进时存在碰撞，否则判定不同目标对象沿着各自对应的规划运动路径行进时不存在碰撞；其中，第一方向具体可以为水平方向，通过水平方向上不同目标对象的距离与预设的距离进行比对，从而可以判断在水平方向上两个目标对象之间是否存在碰撞。如果第一方向是垂直方向，还可以判断在垂直方向上两个目标对象之间是否存在碰撞。本实施例中，目标对象之间的距离可以是目标对象的几何中心之间的距离。

和/或，在其他实施例中，可替代体，步骤S104中，通过判断不同目标对象在对应的规划路径上沿着第一方向行进时以目标对象为中心的位置矢量是否会发生重合，如果是，则判定不同目标对象沿着各自对应的规划运动路径行进时存在碰撞，否则判定不同目标对象沿着各自对应的规划运动路径行进时不存在碰撞。具体地，位置矢量可以形成一定空间形状，通过判断两个目标对象分别对应的空间形状(如球体)是否存在重合，从而确定两个目标对象是否会发生碰撞。

可选地，在步骤S104中确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象时，可以根据不同目标对象沿着各自规划出的运动路径行进时对应的状态索引，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象。

具体地，参见图6所示，为本发明实施例六中基于目标对象的信息组织方式示意图；如图6所示，其中按照列从左到右分别为目标对象ID、时刻t、以及状态p，状态p反映目标对象与网格的实时对应关系。

图7为本发明实施例七中基于状态的静态信息组织方式；如图7所示，其中从左到右分别为状态p、时刻t以及目标对象ID。

图8为本发明实施例八中根据图6和图7建立的状态索引关系图，如图 8所示，根据该状态索引关系图从而建立了不同目标对象之间的联系，某一时刻t处于状态p0(对应到网格)的目标对象ID，从而进一步参考上述判断碰撞的具体方式，得知两个目标对象在为其规划的航路上行进时是否会发生碰撞。

S105、在所述三维空间区域上对沿着各自对应的规划运动路径行进时存在碰撞的目标对象重新进行运动路径规划。

在上述步骤S104或者步骤S105中，进一步对发生碰撞的具体情形进行确定，比如发生碰撞的时刻t、发生碰撞的状态p，空间和时间描述成一个四维空间内的网格，将四个维度内具有目标对象的网格标记为1，无目标对象的网格标记为0，通过求解可使得f(x，y，z，t)＝(x_0，y_0，z_0)+(m，n， p)·t等于0的一条直线匀速运动通过四维空间区，(x_0，y_0，z_0)相当于 C0在三维空间中的坐标，从而确定出对应m(即为上述M)、n(即为上述N)、 p(即为上述状态p)，从而确定再结合上述状态索引确定出发生碰撞的时刻 t、发生碰撞的状态p，其中图9为在二维平面上进行三维冲突检测示意图。进一步，可以如图10对碰撞位置进行预警。

本实施例中，在进行路径的重新规划时，可以基于如下原则进行确定：

(1)考虑目标在水平方向和垂直方向的路径调整，真三维空间加上目标本身的动态特性(时间)给航路规划带来约束条件。

(2)对任意目标对象，除了静态状态即其自身的航路，还要考虑动态状态(即其他目标对象)对其航迹规划的影响，另一目标对象的出现会导致原本最优路径需重新规划，而其他目标对象的出现具有不确定性，航路规划需要动态进行。

(3)可选择当前场景中的目标对象ID，参照上述(1)(2)设置约束条件，从而为其规划规避碰撞的路径。

(4)对当前场景新增的目标对象参照上述(1)-(3)规划不发生碰撞的路径。

(5)可选择当前场景的所有目标对象，对所有目标对象进行防撞规划，以达到当前场景所有对标对象不会发生碰撞的效果。其中，图11为单个目标对象的原航路示意图，一定空间区域进行三维网格化后，标识网格的可通过性，图中黑色方块表示被建筑物占据的空间，无人机不可通过，图示单个无人机网格路径，飞行时绕过不可通过的立体网格。图12为对原航路重新规划后的防撞规划路径示意图，当同一空域另一架无人机飞入时，两架无人机在飞行过程中会发生碰撞，在发生碰撞的网格处，需要对第一架无人机的路径进行了调整，图中为向下调整网格，来规避碰撞。

在上述实施例的基础上，在确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象时，还可以剔除沿着各自规划的运动路径行进时不存在碰撞可能的目标对象，不纳入航路重新规划的范围，从而减少数据量。

图13为本发明实施例航路规划装置的结构示意图；如图13所示，其包括：路径规划单元1301、碰撞确定单元1302，碰撞确定单元1302用于根据对三维空间区域进行剖分得到的立体块在二维平面上的对象模型以及为所述对象模型设置的编码，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象，所述路径规划单元1301用于在所述三维空间区域上对沿着各自对应的规划运动路径行进时存在碰撞的目标对象重新进行运动路径规划。

本实施例中，路径规划单元1301、碰撞确定单元1302可以执行上述方法实施例中具体或者进一步的技术，详细不再赘述。

以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的模块可以是或者也可以不是物理上分开的，作为模块显示的部件可以是或者也可以不是物理模块，即可以位于一个地方，或者也可以分布到多个网格模块上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性的劳动的情况下，即可以理解并实施。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件。基于这样的理解，上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，所述计算机可读记录介质包括用于以计算机(例如计算机) 可读的形式存储或传送信息的任何机制。例如，机器可读介质包括只读存储器(ROM)、随机存取存储器(RAM)、磁盘存储介质、光存储介质、闪速存储介质、电、光、声或其他形式的传播信号(例如，载波、红外信号、数字信号等)等，该计算机软件产品包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网格设备等)执行各个实施例或者实施例的某些部分所述的方法。

最后应说明的是：以上实施例仅用以说明本申请实施例的技术方案，而非对其限制；尽管参照前述实施例对本申请进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本申请各实施例技术方案的精神和范围。

本领域的技术人员应明白，本发明实施例的实施例可提供为方法、装置 (设备)、或计算机程序产品。因此，本发明实施例可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明实施例可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本发明实施例是参照根据本发明实施例的方法、装置(设备)和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和 /或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

Claims (12)

1.一种航路规划方法，其特征在于，包括：

根据对三维空间区域进行剖分得到的立体块在二维平面上的对象模型以及为所述对象模型设置的编码，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象；

在所述三维空间区域上对沿着各自对应的规划运动路径行进时存在碰撞的目标对象重新进行运动路径规划。

2.根据权利要求1所述的航路规划方法，其特征在于，对三维空间区域进行剖分得到的立体块为根据GeoSOT空间剖分方式对三维空间区域进行剖分得到的立体块。

3.根据权利要求1所述的航路规划方法，其特征在于，为所述对象模型设置的编码为根据北斗网格码编码方式为所述对象模型设置的编码。

4.根据权利要求1所述的航路规划方法，其特征在于，所述对象模型包括：点对象数据模型、线对象数据模型、面对像数据模型中的任一种或多种的组合。

5.根据权利要求1所述的航路规划方法，其特征在于，所述对象模型包括一个或多个网格，所述网格为对所述二维平面进行多叉树划分得到的区域。

6.根据权利要求1所述的航路规划方法，其特征在于，所述立体块包括所述三维空间区域中空间实体对应的立体块，不同所述立体块与为所述对象模型设置的编码一一对应。

7.根据权利要求1所述的航路规划方法，其特征在于，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象包括：剔除沿着各自规划的运动路径行进时不存在碰撞可能的目标对象。

8.根据权利要求1所述的航路规划方法，其特征在于，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象包括：若不同目标对象沿着各自规划的运动路径行进时会位于同一对象模型中，则判定目标对象沿着各自对应的规划运动路径行进时存在碰撞。

9.根据权利要求8所述的航路规划方法，其特征在于，还包括：判断不同目标对象在对应的规划路径上沿着第一方向行进时不同目标对象之间的距离是否小于预设的距离，如果小于，则判定不同目标对象沿着各自对应的规划运动路径行进时存在碰撞，否则判定不同目标对象沿着各自对应的规划运动路径行进时不存在碰撞；

或者，所述航路规划方法还包括：判断不同目标对象在对应的规划路径上沿着第一方向行进时以目标对象为中心的位置矢量是否会发生重合，如果是，则判定不同目标对象沿着各自对应的规划运动路径行进时存在碰撞，否则判定不同目标对象沿着各自对应的规划运动路径行进时不存在碰撞。

10.根据权利要求1所述的航路规划方法，其特征在于，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象包括：根据不同目标对象沿着各自规划出的运动路径行进时对应的状态索引，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象。

11.根据权利要求1-10任一项所述的航路规划方法，其特征在于，所述编码为聚合编码，所述聚合编码主要由所述对象模型所在角点定位面片的编码、沿纬向的面片跨度、沿经向的面片跨度组成。

12.一种航路规划装置，其特征在于，包括：路径规划单元、碰撞确定单元，碰撞确定单元用于根据对三维空间区域进行剖分得到的立体块在二维平面上的对象模型以及为所述对象模型设置的编码，确定沿着各自对应的规划运动路径行进时存在碰撞的目标对象，所述路径规划单元用于在所述三维空间区域上对沿着各自对应的规划运动路径行进时存在碰撞的目标对象重新进行运动路径规划。