一种基于Apache Spark和启发式搜索的航空器最优路径规划方法

摘要

本发明公开了一种基于Apache Spark和启发式搜索的航空器最优路径规划方法，其特征在于：根据不确定性动态空域环境，采用Apache Spark并行计算框架实现A*算法规划并选择最佳路径,包括下列步骤：步骤1、获取动态碎片信息，对其进行风险评估，根据民航可接受的风险概率确定碎片危险区边界，构建空域环境网格以及碎片风险等级图；步骤2、在传统A*算法的基础上，空域环境中的所有网格节点增设节点信息属性，根据风险等级图和危险区边界信息，建立启发式评价函数；步骤3、在Apache Spark并行计算框架下实现步骤2所提供的并行A*算法，找到最佳路径。本发明基于ApacheSpark和启发式搜索的航空器最优路径规划方法，提高算法的运行效率，实现实时性动态规划。

说明书

技术领域

本发明涉及航空器路径规划技术领域，具体为一种基于Apache Spark和启发式搜索的航空器最优路径规划方法。

背景技术

路径规划是人工智能领域的热点问题之一，已广泛应用在无人驾驶汽车、机器人、无人船等领域，其目标是在具有若干障碍物的环境下，找到一条从起点到目标点的无碰撞的安全路径；在存在大量不确定性因素的复杂空域环境中，寻找到一条飞往目标点的最优路径问题被认为是一个需要解决的NP-hard问题；当数据规模较小时，在短时间内使用一台主机可以规划出最优路径。当数据规模较大时，传统技术面临巨大的挑战，一台主机难以在短时间内取得良好的效果。

目前，许多研究人员采用并行计算框架来处理大规模的数据集，如MapReduce等。虽然MapReduce能够离线处理海量数据并实现并行计算，但是它处理延迟较高且需要静态数据源，难以进行实时计算和流式计算。因此，解决实时路径规划问题较为困难；传统A*算法是最常用的静态路径规划方法之一，但是它不适用于动态复杂环境，而且在解决复杂空域的路径规划问题时，传统A*算法的运行效率会受到极大的制约。

发明内容

本发明的目的在于提供一种基于Apache Spark和启发式搜索的航空器最优路径规划方法，提高算法的运行效率，实现实时性动态规划，有效解决上述背景技术中提出的问题。

为实现上述目的，本发明提供如下技术方案：一种基于Apache Spark和启发式搜索的航空器最优路径规划方法，其特征在于：根据不确定性动态空域环境，采用ApacheSpark并行计算框架实现A*算法规划并选择最佳路径,包括按顺序进行的下列步骤:

步骤1、获取动态碎片信息，对其进行风险评估，根据民航可接受的风险概率确定碎片危险区边界，构建空域环境网格以及碎片风险等级图；

步骤2、在传统A*算法的基础上，空域环境中的所有网格节点增设节点信息属性，包括ID值、坐标、g(n)、f(n)、状态、相对移动方向、相对移动距离，根据风险等级图和危险区边界信息，建立启发式评价函数；

步骤3、在Apache Spark并行计算框架下实现步骤2所提供的并行A*算法，找到最佳路径。

优选的，在步骤2中，所述的在传统A*算法的基础上，空域环境中的所有网格节点增设节点信息属性，包括ID值、坐标、g(n)、f(n)、状态、相对移动方向、相对移动距离，根据风险等级图和危险区边界信息建立启发式评价函数的具体步骤如下：

步骤2.1、根据风险评估情况，初始化栅格图中节点状态，分别设置为“未访问”、“高风险”、“中风险”、“低风险”；初始化节点ID值、起始节点start、目标节点end、用于存储从起点到终点的历史最佳路径p及代价f(n)；构建1个优先队列Open、1个列表Close；

步骤2.2、将起始点start放入优先队列Open中，其状态设置为“优先队列”；

步骤2.3、当Open非空时，则向下执行下个步骤；否则说明未找到最优路径，跳出循环；

步骤2.4、选取Open中F值最小的节点node，如果节点node不为目标节点end，则向下执行下个步骤；否则，说明已找到最优路径，跳出循环；

步骤2.5、将节点node从Open中删除，添加到Close，其状态设置为“已访问”；

步骤2.6、检查并扩展节点node周围16个邻域的节点，不考虑状态为“高风险”、“中风险”、“低风险”、“已访问”的节点，如果邻域节点状态为“未访问”，则将其加入到Open中，其状态设置为“优先队列”，计算并比较f(n)的大小，更新节点的父节点的ID值和代价g(n)、f(n)；如果邻域节点状态为“优先队列”，则重新计算代价g(n)、f(n)，比较f(n)的大小，更新节点的父节点的ID值和代价g(n)、f(n)，跳转到步骤2.3，

其中，节点的路径代价公式如下所示：

f(n)＝g(n)+h(n)

在上面各式中：f(n)为节点n的总代价、g(n)为航空器从起始点飞到节点n的用欧式距离表示的实际距离代价和h(n)为航空器从节点n飞到目标点的成本代价；

其中，n

上式中，α表示危险区横截面的最大风险值，β表示当前节点相对危险区移动方向的位置，max(γ)表示当前危险区的最右边界；根据危险区的位置移动，动态改变每个路段的代价。

优选的，所述步骤2.1中，所述优先队列Open用于存放待检测节点，列表Close用于存放已检测节点以及风险等级图中“高风险”、“中风险”、“低风险”的节点。

优选的，在步骤3中，所述的在Apache Spark并行计算框架下实现并行A*算法的具体步骤如下：

步骤3.1、读取空域环境栅格节点信息以及航空器位置信息，包括每个节点的ID值、坐标、g(n)、f(n)、相对移动方向、相对移动距离以及节点状态；

步骤3.2、预处理空域环境栅格节点信息后，将节点映射到弹性分布式数据集RDD上，所有机器或处理器均可访问节点信息；

步骤3.3、根据节点的状态信息，对节点进行过滤；

步骤3.4、主节点Master接收到f(n)值最小的节点后，向从节点Worker广播f(n)值最小的节点；

步骤3.5、每个从节点Worker接收到主节点Master的广播后，开始在接收点上工作，启动Executors进程，并执行Tasks，将块中的所有点映射到接收点上；每个从节点Worker执行Executors进程后，需要进行过滤操作；在本地提取f(n)值最小的节点，然后将f(n)值最小的节点发送给SparkContext，跳转到步骤3.3，直到找到目标节点为止。

优选的，所述步骤3.1中的所述ID值是节点的唯一标识符；g(n)为航空器从起始点飞到节点n的实际距离代价；f(n)为节点n的总代价。所有节点的g(n)和f(n)均初始化为零，障碍节点的状态有三种模式，分别为“高风险”、“中风险”、“低风险”，非障碍节点的状态有三种模式，分别为“未访问”、“已访问”、“优先队列”，在非障碍节点中，起始节点的状态初始化为“优先队列”状态，其他节点的状态均初始化为“未访问”状态，将读取到的信息添加至数据集文件，并用如下格式表示节点信息：(id,(x,y),g(n),f(n),direction,distance,state)。

优选的，所述步骤3.3中在所述过滤过程中，只需要考虑状态为“优先队列”的节点，将状态为“优先队列”的节点按照f(n)值的大小升序排序。读取f(n)值最小的节点，将该节点设置为当前节点，如果当前节点位置等于目标节点位置，则说明已找到最优路径；否则，继续使用改进A*算法寻找最优路径。Spark Context将f(n)值最小的节点传递给主节点Master，如果没有状态为“优先队列”的节点，则说明寻路失败。

与现有技术相比，本发明的有益效果是：

1、本发明考虑空域中的危险区域的边界、横截面积、移动方向等各项属性，改进启发式评价函数，动态改变每个路段的代价；

2、本发明同时采用Apache Spark并行计算平台加快路径规划的数据处理速度，通过不断迭代寻找f(n)值最小的节点，从而实现A*算法的实时处理和并行处理，减少时间开销，提高寻路效率。

附图说明

图1为本发明基于ApacheSpark和启发式搜索的航空器最优路径规划方法流程图；

图2为本发明方法中改进A*算法流程图；

图3为本发明方法中危险区风险评估等级图；

图4为本发明方法中ApacheSpark数据处理流程图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

请参阅图1-4，本发明提供一种技术方案：一种基于Apache Spark和启发式搜索的航空器最优路径规划方法，根据不确定性动态空域环境，采用Apache Spark并行计算框架实现A*算法规划并选择最佳路径,包括按顺序进行的下列步骤:

步骤1、获取动态碎片信息，对其进行风险评估，根据民航可接受的风险概率确定碎片危险区边界，构建空域环境网格以及碎片风险等级图；

步骤2、在传统A*算法的基础上，空域环境中的所有网格节点增设节点信息属性，包括ID值、坐标、g(n)、f(n)、状态、相对移动方向、相对移动距离，根据风险等级图和危险区边界信息，建立启发式评价函数；

步骤3、在Apache Spark并行计算框架下实现步骤2所提供的并行A*算法，找到最佳路径。

在步骤2中，所述的在传统A*算法的基础上，空域环境中的所有网格节点增设节点信息属性，包括ID值、坐标、g(n)、f(n)、状态、相对移动方向、相对移动距离，根据风险等级图和危险区边界信息建立启发式评价函数的具体步骤如下：

步骤2.1、根据风险评估情况，初始化栅格图中节点状态，分别设置为“未访问”、“高风险”、“中风险”、“低风险”；初始化节点ID值、起始节点start、目标节点end、用于存储从起点到终点的历史最佳路径p及代价f(n)；构建1个优先队列Open、1个列表Close；

步骤2.2、将起始点start放入优先队列Open中，其状态设置为“优先队列”；

步骤2.3、当Open非空时，则向下执行下个步骤；否则说明未找到最优路径，跳出循环；

步骤2.4、选取Open中F值最小的节点node，如果节点node不为目标节点end，则向下执行下个步骤；否则，说明已找到最优路径，跳出循环；

步骤2.5、将节点node从Open中删除，添加到Close，其状态设置为“已访问”；

步骤2.6、检查并扩展节点node周围16个邻域的节点，不考虑状态为“高风险”、“中风险”、“低风险”、“已访问”的节点，如果邻域节点状态为“未访问”，则将其加入到Open中，其状态设置为“优先队列”，计算并比较f(n)的大小，更新节点的父节点的ID值和代价g(n)、f(n)；如果邻域节点状态为“优先队列”，则重新计算代价g(n)、f(n)，比较f(n)的大小，更新节点的父节点的ID值和代价g(n)、f(n)，跳转到步骤2.3；其中，节点的路径代价公式如下所示：

f(n)＝g(n)+h(n)

在上面各式中：f(n)为节点n的总代价、g(n)为航空器从起始点飞到节点n的用欧式距离表示的实际距离代价和h(n)为航空器从节点n飞到目标点的成本代价；

其中，n

上式中，α表示危险区横截面的最大风险值，β表示当前节点相对危险区移动方向的位置，max(γ)表示当前危险区的最右边界；根据危险区的位置移动，动态改变每个路段的代价。

步骤2.1中，所述优先队列Open用于存放待检测节点，列表Close用于存放已检测节点以及风险等级图中“高风险”、“中风险”、“低风险”的节点。

在步骤3中，所述的在Apache Spark并行计算框架下实现并行A*算法的具体步骤如下：

步骤3.1、读取空域环境栅格节点信息以及航空器位置信息，包括每个节点的ID值、坐标、g(n)、f(n)、相对移动方向、相对移动距离以及节点状态；

步骤3.2、预处理空域环境栅格节点信息后，将节点映射到弹性分布式数据集RDD上，所有机器或处理器均可访问节点信息；

步骤3.3、根据节点的状态信息，对节点进行过滤；

步骤3.4、主节点Master接收到f(n)值最小的节点后，向从节点Worker广播f(n)值最小的节点；

步骤3.5、每个从节点Worker接收到主节点Master的广播后，开始在接收点上工作，启动Executors进程，并执行Tasks，将块中的所有点映射到接收点上；每个从节点Worker执行Executors进程后，需要进行过滤操作；在本地提取f(n)值最小的节点，然后将f(n)值最小的节点发送给SparkContext，跳转到步骤3.3，直到找到目标节点为止。

步骤3.1中的所述ID值是节点的唯一标识符；g(n)为航空器从起始点飞到节点n的实际距离代价；f(n)为节点n的总代价。所有节点的g(n)和f(n)均初始化为零，障碍节点的状态有三种模式，分别为“高风险”、“中风险”、“低风险”，非障碍节点的状态有三种模式，分别为“未访问”、“已访问”、“优先队列”，在非障碍节点中，起始节点的状态初始化为“优先队列”状态，其他节点的状态均初始化为“未访问”状态，将读取到的信息添加至数据集文件，并用如下格式表示节点信息：(id,(x,y),g(n),f(n),direction,distance,state)。

步骤3.3中在所述过滤过程中，只需要考虑状态为“优先队列”的节点。将状态为“优先队列”的节点按照f(n)值的大小升序排序。读取f(n)值最小的节点，将该节点设置为当前节点。如果当前节点位置等于目标节点位置，则说明已找到最优路径。否则，继续使用改进A*算法寻找最优路径。Spark Context将f(n)值最小的节点传递给主节点Master。如果没有状态为“优先队列”的节点，则说明寻路失败。

需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素，此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性。

尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。