CN106595663A - 结合搜索与优化的飞行器自主航迹规划方法 - Google Patents

Abstract

本发明公开了一种结合搜索与优化的飞行器自主航迹规划方法，所述的方法包括以下步骤：步骤一、改进A*算法搜索可行航迹；步骤二、可行航迹的优化预处理；步骤三、粒子群进化算法最优化可行航迹；步骤四、最优航迹的后处理。该发明结合了改进A*算法的搜索能力和粒子群进化算法的优化能力，利用改进A*算法快速搜索得到一条可行航迹，保证规划方法能在很短时间内就得到可行解，提升了规划方法的鲁棒性；然后利用粒子群进化算法对搜索得到的航迹进行优化，得到更优的航迹，提升了规划方法的优化性能。

Description

结合搜索与优化的飞行器自主航迹规划方法

技术领域

本发明涉及智能化无人飞行器航迹规划领域，具体涉及一种结合搜索与优化的飞行器自主航迹规划方法。

背景技术

随着智能算法的深化，将智能算法应用于飞行器的航迹轨迹规划技术的研究也得到了很大的发展。在现有的飞行器智能航迹规划技术中，根据采用的智能算法不同，其规划技术的性能也存在差异，其主要原因是不同的智能算法在搜索与优化这两点上的侧重不同：1)A*算法及其改进算法、蚁群算法等智能算法侧重于搜索，可以快速的搜索得到一条可行路径，其优势在于算法的快速性和鲁棒性，但是一旦搜索得到一条可行路径，规划就结束了，而这条可行路径往往不会是最优路径；2)粒子群算法、量子遗传算法等智能算法则是侧重于优化，同时有一定的搜索能力。但由于算法本身更侧重于优化，虽然可以得到最优路径，但其大部分算法执行时间往往都用在了搜索过程上，影响了算法效率，甚至有可能在规定时间内无法得到符合要求航迹。分别采用这两类智能算法的航迹规划技术也因此存在性能上的不足。

发明内容

本发明克服了现有技术的不足，提供一种结合改进A*算法的搜索能力和粒子群算法的优化能力，兼顾搜索及优化两者优势的飞行器智能航迹规划方法，以解决上述规划技术存在的不足。

为解决上述的技术问题，本发明采用以下技术方案：

一种结合搜索与优化的飞行器自主航迹规划方法，所述的方法包括以下步骤：

步骤一、改进A*算法搜索可行航迹

根据飞行器的性能约束改进A*算法的搜索方式，得到一条符合约束条件的航迹；

步骤二、可行航迹的优化预处理

将得到的航迹进行处理，使该航迹便于粒子群进化算法优化；

步骤三、粒子群进化算法最优化可行航迹

将处理后的航迹输入给粒子群进化算法进行优化；

步骤四、最优航迹的后处理

处在同一直线上的所有航迹点归纳为一条直线段包含首尾两个端点。

更进一步的技术方案是所述步骤一包括：设定飞行器在飞行过程中以定高度方式飞行，并以该高度对三维地形做一个截面，同时将截面栅格化，并区分禁飞区域栅格点和可通行栅格点；根据飞行器的起飞性能约束确定在该平面内的起始点，根据打击任务约束确定在该平面内的终止点。

更进一步的技术方案是所述步骤一还包括：寻路时，按照栅格点组成的路径进行搜索，点与点之间可直接通行，那么在进行搜索时，对于当前点周围的八个点，或者再加上外围的16个点进行评价，寻找满足约束条件下花费代价最小的点作为下一步。

更进一步的技术方案是所述步骤一还包括：将启发函数描述为F＝G+H,其中，G取为从当前点到下一点的欧式距离，H取为某一点到目标点的欧式距离，F表示从当前点到目标点的总距离。

更进一步的技术方案是所述步骤一中所述约束条件包括：最大航迹长度，从起始点到终止点的总航迹长度不能超过设定值；

禁飞区约束，栅格点处于地形障碍或者威胁区域内，不可经过；

转弯半径，在寻找下一步可扩展点时，只有符合转弯半径的一部分点可扩展。

更进一步的技术方案是所述步骤二包括：

将处在同一直线上的所有航迹点归纳为一条直线段包含首尾两个端点；

或者，将处在同一弧线上的所有航迹点则归纳为两条切线段，包含首尾两个端点和非别过首尾两点的两条切线的交点。

更进一步的技术方案是所述步骤三包括：

步骤1，确定DE控制参数和所采用的具体策略；

步骤2，随机产生初始种群，进化代数t＝1；

步骤3，对初始航迹线进行评价，即计算初始种群中每个个体的适应度值；

步骤4，判断是否达到终止条件或进化代数达到最大，若是，则进化终止，将此时的最佳个体作为输出，若否，继续；

步骤5，进行变异和交叉操作，对边界条件进行处理，得到临时航迹线；

步骤6，对临时航迹线进行评估，计算临时航迹线中每个航迹点的适应度值；

步骤7，进行选择操作，得到新航迹线；

步骤8，进化代数t＝t+1，转步骤4。

更进一步的技术方案是所述步骤1中DE控制参数包括：种群数量、变异算子、交叉算子、最大进化代数、终止条件。

与现有技术相比，本发明实施例的有益效果之一是：本发明的实施例利用改进A*算法快速搜索得到一条可行航迹，保证规划方法能在很短时间内就得到可行解，提升了规划方法的鲁棒性；然后利用粒子群进化算法对搜索得到的航迹进行优化，采用群体优化的概念，通过个体间的协作与竞争，实现复杂空间中最优解的搜索,实现航迹的规划选择，得到更优的航迹，提升了规划方法的优化性能。该航迹规划方法鲁棒性好，保证能搜索出航迹的同时，通过粒子群进化算法进行了航迹优化，由于优化的输入量较传统粒子群进化算法大量减少，大大降低了粒子群进化算法的迭代次数，有效地提高了算法的搜索能力,加快了算法的收敛速度。

附图说明

图1为本发明一个实施例中改进A*算法规划出的航迹路线图。

图2为本发明一个实施例中预处理后的航迹路线图。

图3为本发明一个实施例中粒子群进化算法优化并后处理的航迹路线图。

具体实施方式

本说明书中公开的所有特征，或公开的所有方法或过程中的步骤，除了互相排斥的特征和/或步骤以外，均可以以任何方式组合。

本说明书(包括任何附加权利要求、摘要和附图)中公开的任一特征，除非特别叙述，均可被其他等效或具有类似目的的替代特征加以替换。即，除非特别叙述，每个特征只是一系列等效或类似特征中的一个例子而已。

下面结合附图及实施例对本发明的具体实施方式进行详细描述。

本实施例公开一种结合搜索与优化的飞行器自主航迹规划方法，首先根据飞行器的性能约束改进A*算法的搜索方式，得到一条符合约束条件的航迹。接着将得到的航迹进行处理，使该航迹便于粒子群进化算法优化。最后则将处理后的航迹输入给粒子群进化算法进行优化，并得到最优航迹。

具体的，本实施例结合搜索与优化的飞行器自主航迹规划方法，该方法的具体操作步骤包括四个部分：步骤一、改进A*算法搜索可行航迹；步骤二、可行航迹的优化预处理；步骤三、粒子群进化算法最优化可行航迹；步骤四、最优航迹的后处理。

其中，步骤一、改进A*算法搜索可行航迹主要包括以下步骤：

降维处理步骤：设定飞行器在飞行过程中以定高度方式飞行，并以该高度对三维地形做一个截面，同时将截面栅格化，并区分禁飞区域栅格点和可通行栅格点。根据飞行器的起飞性能约束确定在该平面内的起始点A，根据打击任务约束确定在该平面内的终止点B。

关于算法思路，寻路时，按照栅格点组成的路径进行搜索，点与点之间可以直接通行，那么在进行搜索时，对于当前点周围的八个点，或者再加上外围的16个点进行评价，寻找满足约束条件下花费代价最小的点作为下一步。

关于启发函数，A*算法是一种启发式搜索算法，其启发函数可描述为F＝G+H,其中，F表示从当前点到下一点的花费的总代价，它由即时代价G和固定代价H构成，在本算法中，G取为从当前点到下一点的欧式距离，H取为某一点到目标点的欧式距离，因此F表示从当前点到目标点的总距离。

关于约束条件，在二维平面内的航迹飞行主要包括最大航迹长度约束、禁飞区约束和转弯半径约束。最大航迹长度：从起始点到终止点的总航迹长度不能超过设定值。禁飞区约束：栅格点处于地形障碍或者威胁区域内，不可经过。转弯半径：在寻找下一步可扩展点时，只有符合转弯半径的一部分点可扩展。如图1所示。其中米字点表示可扩展，而其它点因为不符合转弯半径要求，不可扩展。

其中步骤二、可行航迹的优化预处理主要包括以下步骤：

之所以需要对改进A*算法搜索得到航迹进行处理，是由于改进A*算法的搜索方式是逐步搜索，因此每搜索一步，就会得到一个航迹点，最终由所有航迹点组合成一条航迹。若终点距离较远，得到的航迹往往包含几十上百个航迹点，这样的航迹是不符合航迹规划要求的，并且，对于量子遗传算法来说，一条航迹上的航迹点越多，其优化复杂度会成级数增长。预处理的具体操作包括两种情况：处在同一直线上的所有航迹点归纳为一条直线段包含首尾两个端点；处在同一弧线上的所有航迹点则归纳为两条切线段，包含首尾两个端点和非别过首尾两点的两条切线的交点。预处理后的航迹路线图如图2所示。

关于步骤三、粒子群进化算法最优化可行航迹主要包括以下步骤：

粒子群(PSO)算法是近几年来最为流行的进化算法，采用群体优化的概念，通过个体间的协作与竞争，实现复杂空间中最优解的搜索，将A*算法得出的初始航迹点作为PSO算法的初始种群，每个航迹点转化为问题的一个可行解，并且目标函数为确定一个适应值，PSO不像其他进化算法那样对于个体使用进化算法，而是将每个个体看成三维搜索空间中的一个没有体积重量的粒子，每个粒子将在解空间中运动，并由一个速度决定其方向和距离通常粒子将追随当前的最优粒子而运动逐代搜索得到最优解，在每一代中，粒子将跟踪两个极值，一为粒子本身迄今找到的最优解，另一为全种群迄今找到的最优解，具体算法如下：

步骤1，确定DE控制参数和所采用的具体策略；

步骤2，随机产生初始种群，进化代数t＝1；

步骤3，对初始航迹线进行评价，即计算初始种群中每个个体的适应度值；

步骤4，判断是否达到终止条件或进化代数达到最大，若是，则进化终止，将此时的最佳个体作为输出，若否，继续；

步骤5，进行变异和交叉操作，对边界条件进行处理，得到临时航迹线；

步骤6，对临时航迹线进行评估，计算临时航迹线中每个航迹点的适应度值；

步骤7，进行选择操作，得到新航迹线；

步骤8，进化代数t＝t+1，转步骤4。

关于步骤四、最优航迹的后处理主要包括以下步骤：由于没有了弧线，最优航迹的后处理工作为：处在同一直线上的所有航迹点归纳为一条直线段包含首尾两个端点。粒子群进化算法优化并后处理的航迹路线图如图3所示。

本实施例结合了改进A*算法的搜索能力和粒子群进化算法的优化能力，利用改进A*算法快速搜索得到一条可行航迹，保证规划方法能在很短时间内就得到可行解，提升了规划方法的鲁棒性；然后利用粒子群进化算法对搜索得到的航迹进行优化，得到更优的航迹，提升了规划方法的优化性能。

在本说明书中所谈到的“一个实施例”、“另一个实施例”、“实施例”等，指的是结合该实施例描述的具体特征、结构或者特点包括在本申请概括性描述的至少一个实施例中。在说明书中多个地方出现同种表述不是一定指的是同一个实施例。进一步来说，结合任一个实施例描述一个具体特征、结构或者特点时，所要主张的是结合其他实施例来实现这种特征、结构或者特点也落在本发明的范围内。

尽管这里参照发明的多个解释性实施例对本发明进行了描述，但是，应该理解，本领域技术人员可以设计出很多其他的修改和实施方式，这些修改和实施方式将落在本申请公开的原则范围和精神之内。更具体地说，在本申请公开权利要求的范围内，可以对主题组合布局的组成部件和/或布局进行多种变型和改进。除了对组成部件和/或布局进行的变型和改进外，对于本领域技术人员来说，其他的用途也将是明显的。

Claims (8)

1.一种结合搜索与优化的飞行器自主航迹规划方法，其特征在于：所述的方法包括以下步骤：

步骤一、改进A*算法搜索可行航迹

根据飞行器的性能约束改进A*算法的搜索方式，得到一条符合约束条件的航迹；

步骤二、可行航迹的优化预处理

将得到的航迹进行处理，使该航迹便于粒子群进化算法优化；

步骤三、粒子群进化算法最优化可行航迹

将处理后的航迹输入给粒子群进化算法进行优化；

步骤四、最优航迹的后处理

处在同一直线上的所有航迹点归纳为一条直线段包含首尾两个端点。

2.根据权利要求1所述的结合搜索与优化的飞行器自主航迹规划方法，其特征在于所述的步骤一包括：设定飞行器在飞行过程中以定高度方式飞行，并以该高度对三维地形做一个截面，同时将截面栅格化，并区分禁飞区域栅格点和可通行栅格点；根据飞行器的起飞性能约束确定在该平面内的起始点，根据打击任务约束确定在该平面内的终止点。

3.根据权利要求2所述的结合搜索与优化的飞行器自主航迹规划方法，其特征在于所述的步骤一还包括：寻路时，按照栅格点组成的路径进行搜索，点与点之间可直接通行，那么在进行搜索时，对于当前点周围的八个点，或者再加上外围的16个点进行评价，寻找满足约束条件下花费代价最小的点作为下一步。

4.根据权利要求3所述的结合搜索与优化的飞行器自主航迹规划方法，其特征在于所述的步骤一还包括：将启发函数描述为F＝G+H,其中，G取为从当前点到下一点的欧式距离，H取为某一点到目标点的欧式距离，F表示从当前点到目标点的总距离。

5.根据权利要求4所述的结合搜索与优化的飞行器自主航迹规划方法，其特征在于所述的步骤一中所述约束条件包括：最大航迹长度，从起始点到终止点的总航迹长度不能超过设定值；

禁飞区约束，栅格点处于地形障碍或者威胁区域内，不可经过；

转弯半径，在寻找下一步可扩展点时，只有符合转弯半径的一部分点可扩展。

6.根据权利要求1所述的结合搜索与优化的飞行器自主航迹规划方法，其特征在于所述的步骤二包括：

将处在同一直线上的所有航迹点归纳为一条直线段包含首尾两个端点；

或者，将处在同一弧线上的所有航迹点则归纳为两条切线段，包含首尾两个端点和非别过首尾两点的两条切线的交点。

7.根据权利要求1所述的结合搜索与优化的飞行器自主航迹规划方法，其特征在于所述的步骤三包括：

步骤1，确定DE控制参数和所采用的具体策略；

步骤2，随机产生初始种群，进化代数t＝1；

步骤3，对初始航迹线进行评价，即计算初始种群中每个个体的适应度值；

步骤4，判断是否达到终止条件或进化代数达到最大，若是，则进化终止，将此时的最佳个体作为输出，若否，继续；

步骤5，进行变异和交叉操作，对边界条件进行处理，得到临时航迹线；

步骤6，对临时航迹线进行评估，计算临时航迹线中每个航迹点的适应度值；

步骤7，进行选择操作，得到新航迹线；

步骤8，进化代数t＝t+1，转步骤4。

8.根据权利要求7所述的结合搜索与优化的飞行器自主航迹规划方法，其特征在于所述的步骤1中DE控制参数包括：种群数量、变异算子、交叉算子、最大进化代数、终止条件。