一种考虑无人机机动性约束的跳跃网格搜索方法

摘要

本发明提供了一种考虑无人机机动性约束的跳跃网格搜索方法，该搜索方法包括：将地图栅格化并且定义其中每个网格的坐标；根据无人机的当前速度和机动性约束确定下一步的跳跃网格数；根据机动性约束和跳跃网格数确定可供决策的网格；根据可供决策的网格计算搜索收益并且根据搜索收益决策无人机下一步移动的目标网格；通过搜索信息判断无人机移动之后是否完成搜索任务，如果否，则重复前述搜索决策过程，如果是，则结束搜索。应用本发明的技术方案，以解决现有搜索决策方法规划出的搜索航迹与无人机的机动能力不匹配导致搜索效率较低以及影响无人机安全性能的技术问题。

说明书

技术领域

本发明涉及多智能体协同控制技术领域，尤其涉及一种考虑无人机机动性约束的跳跃网格搜索方法。

背景技术

协同搜索技术是无人机协同应用的关键技术之一。协同搜索技术用于在广域未知环境中帮助无人机进行搜索方向决策，使无人机集群能够快速的发现目标位置。无人机集群想要减少目标搜索的时间，需要在搜索时进行探测信息共享，使集群内的无人机避免对相同区域重复搜索，同时在搜索方向决策时需要综合考虑目标存在概率、环境不确定度、无人机间距离、无人机机动能力等因素。

现有协同搜索技术主要有光栅式搜索、区域分割搜索方法、搜索决策方法以及跳点搜索(JSP)算法。前两种方法实现了避免多无人机重复搜索的功能，但是未考虑目标存在概率等其他因素；搜索决策方法中最具代表性的是基于分布式模型预测控制的多无人机搜索决策方法，该方法在栅格化地图中对目标存在概率、环境不确定度等信息进行描述，并且以这些指标构建目标函数，将网格位置作为优化变量，通过滚动时序规划方法，将集中式多无人机优化决策问题转化为小规模分布式优化问题，能够提高多无人机协同搜索效率，但是该方法在网格搜索决策时只能在相邻网格中选取，未考虑无人机机动性约束；跳点搜索算法在路径搜索的时候跳过没有意义的网格节点，只留下影响决策的关键网格节点，当查询到目标点时，只需要将这些关键的网格节点连接起来就是一条完整的路径，但是该算法解决的是已知起点和终点情况下中间路径的生成问题，无法解决目标位置未知情况下，综合考虑目标概率分布等因素的搜索方向决策问题。

发明内容

为了解决现有技术中存在的问题之一，本发明提供了一种考虑无人机机动性约束的跳跃网格搜索方法。

根据本发明的一方面，提供了一种考虑无人机机动性约束的跳跃网格搜索方法，搜索方法包括：

S1，将地图栅格化并且定义其中每个网格的坐标；

S2，根据无人机的当前速度和机动性约束确定下一步的跳跃网格数；

S3，根据机动性约束和跳跃网格数确定可供决策的网格；

S4，根据可供决策的网格计算搜索收益并且根据搜索收益决策无人机下一步移动的目标网格；

S5，通过搜索信息判断无人机移动之后是否完成搜索任务，如果否，则重复S2至S4，如果是，则结束搜索。

进一步地，S1包括：

根据搜索信息统计精度和航迹规划精度需求以正方形网格作为基本单元将地图栅格化；

按照栅格化地图的行列顺序将每个网格的坐标定义为(x

进一步地，通过以下公式根据无人机的当前速度和机动性约束确定下一步的跳跃网格数：

上式中，R表示无人机的最小转弯半径，v表示无人机当前在地面坐标系中的速度，a表示无人机的最大可用过载，r表示单个网格的边长，j表示跳跃网格数。

进一步地，S3包括：

将以无人机当前所在网格为中心以跳跃网格数为半径的一圈网格作为初步决策网格；

根据机动性约束从初步决策网格中进一步选定可供决策的网格。

进一步地，无人机的机动性约束为保持直线运动，根据机动性约束从初步决策网格中进一步选定可供决策的网格包括：

将初步决策网格中与无人机的速度延长线相交的网格定义为直线网格；

将直线网格及其左右相邻的两个网格作为可供决策的网格。

进一步地，S4包括：

对初步决策网格进行编号以对应确定可供决策网格的编号；

根据可供决策网格的编号生成包含预设步数的航迹规划序列；

计算每一个航迹规划序列的搜索收益，并且将搜索收益最大的航迹规划序列中的第一步对应的可供决策网格作为下一步移动的目标网格。

进一步地，计算每一个航迹规划序列的搜索收益包括：

将航迹规划序列中每个可供决策网格的编号转换为网格的坐标；

利用模型预测方法根据转换后的网格的坐标计算搜索收益。

进一步地，对初步决策网格进行编号以对应确定可供决策网格的编号包括：以[-4j，4j]内的整数对初步决策网格进行连续编号，其中+4j和-4j代表同一个网格，当初步决策网格被选定为可供决策网格时沿用编号。

进一步地，通过以下公式将航迹规划序列中每个可供决策网格的编号转换为网格的坐标：

上式中，Δx

进一步地，初步决策网格对应的航向角选择粒度为(45/j)°。

应用本发明的技术方案，提供了一种考虑无人机机动性约束的跳跃网格搜索方法，该方法通过将地图栅格化，根据无人机当前速度和机动性约束确定跳跃网格数，再根据机动性约束和跳跃网格数确定可供决策的网格，最终以搜索收益为决策判据从可供决策的网格中选定一个作为下一步移动的目标网格，无人机每移动一步都重复这一决策流程，从而实现在线滚动决策，直至完成搜索任务。该方法将无人机的机动性约束和目标概率分布同时纳入搜索决策的过程中，规划出的搜索航迹更为符合无人机的机动能力，从而显著提高搜索效率，并且提升无人机的安全性能，在多智能体协同在线搜索决策以及搜索航迹规划方面具有很好地应用前景。

附图说明

所包括的附图用来提供对本发明实施例的进一步的理解，其构成了说明书的一部分，用于例示本发明的实施例，并与文字描述一起来阐释本发明的原理。显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1示出了根据本发明的具体实施例提供的考虑无人机机动性约束的跳跃网格搜索方法的流程示意图；

图2A示出了根据本发明的具体实施例之一提供的跳跃网格数为1时可供决策的网格的示意图；

图2B示出了根据本发明的具体实施例之二提供的跳跃网格数为1时可供决策的网格的示意图；

图3A示出了根据本发明的具体实施例之一提供的跳跃网格数为2时可供决策的网格的示意图；

图3B示出了根据本发明的具体实施例之二提供的跳跃网格数为2时可供决策的网格的示意图；

图3C示出了根据本发明的具体实施例之三提供的跳跃网格数为2时可供决策的网格的示意图；

图4示出了根据本发明的具体实施例提供的不同跳跃网格数对应的无人机最小转弯半径；

图5示出了根据本发明的具体实施例提供的初步决策网格的编号及每个网格对应的航向角；

图6示出了跳跃网格数为1时预测的三步可供选择的航迹规划序列对应的栅格化示意图；

图7示出了跳跃网格数为2时预测的三步可供选择的航迹规划序列对应的栅格化示意图；

图8示出了跳跃网格数为3时高机动无人机协同搜索结果示意图；

图9示出了跳跃网格数为7时低机动无人机协同搜索结果示意图；

图10示出了应用该搜索方法的无人机集群的协同搜索流程示意图。

具体实施方式

需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。以下对至少一个示例性实施例的描述实际上仅仅是说明性的，决不作为对本发明及其应用或使用的任何限制。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本申请的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。

除非另外具体说明，否则在这些实施例中阐述的部件和步骤的相对布置、数字表达式和数值不限制本发明的范围。同时，应当明白，为了便于描述，附图中所示出的各个部分的尺寸并不是按照实际的比例关系绘制的。对于相关领域普通技术人员已知的技术、方法和设备可能不作详细讨论，但在适当情况下，所述技术、方法和设备应当被视为授权说明书的一部分。在这里示出和讨论的所有示例中，任何具体值应被解释为仅仅是示例性的，而不是作为限制。因此，示例性实施例的其它示例可以具有不同的值。应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步讨论。

如图1所示，根据本发明的具体实施例提供了一种考虑无人机机动性约束的跳跃网格搜索方法，该搜索方法包括：

S1，将地图栅格化并且定义其中每个网格的坐标；

S2，根据无人机的当前速度和机动性约束确定下一步的跳跃网格数；

S3，根据机动性约束和跳跃网格数确定可供决策的网格；

S4，根据可供决策的网格计算搜索收益并且根据搜索收益决策无人机下一步移动的目标网格；

S5，通过搜索信息判断无人机移动之后是否完成搜索任务，如果否，则重复S2至S4，如果是，则结束搜索。

应用此种配置方式，提供了一种考虑无人机机动性约束的跳跃网格搜索方法，该方法通过将地图栅格化，根据无人机当前速度和机动性约束确定跳跃网格数，再根据机动性约束和跳跃网格数确定可供决策的网格，最终以搜索收益为决策判据从可供决策的网格中选定一个作为下一步移动的目标网格，无人机每移动一步都重复这一决策流程，从而实现在线滚动决策，直至完成搜索任务。该方法将无人机的机动性约束和目标概率分布同时纳入搜索决策的过程中，规划出的搜索航迹更为符合无人机的机动能力，从而显著提高搜索效率，并且提升无人机的安全性能，在多智能体协同在线搜索决策以及搜索航迹规划方面具有很好地应用前景。与现有技术相比，本发明的技术方案能够解决现有搜索决策方法规划出的搜索航迹与无人机的机动能力不匹配导致搜索效率较低以及影响无人机安全性能的技术问题。

在搜索任务开始前将地图栅格化并确定每个网格的坐标，便于对搜索结果进行统计并且明确无人机在地图中的位置。本发明实施例中，S1包括：

根据搜索信息统计精度和航迹规划精度需求以正方形网格作为基本单元将地图栅格化；

按照栅格化地图的行列顺序将每个网格的坐标定义为(x

其中，正方形网格的尺寸除了根据搜索信息统计精度和航迹规划精度确定以外，也可以适当考虑搜索范围、无人机移动速度以及无人机探测能力。确定网格的坐标时，其实就是按照栅格地图的横向和纵向网格编号，也就是说，x

进一步地，本发明实施例中，通过以下公式根据无人机的当前速度和机动性约束确定下一步的跳跃网格数：

上式中，R表示无人机的最小转弯半径，v表示无人机当前在地面坐标系中的速度，a表示无人机的最大可用过载，r表示单个网格的边长，j表示跳跃网格数。

也就是说，确定的跳跃网格数j应能够使不等式右边的计算结果大于左边无人机的最小转弯半径R，通常j取整数，通过此种方式，在搜索航迹规划时将无人机的机动性约束也考虑进来，能够使后续规划出的航迹与无人机的机动能力更匹配。图4示出了跳跃网格数分别为1、2、3时对应的无人机最小转弯半径，其中r代表正方形网格边长，当跳跃网格数为1时，最小转弯半径为2r(直径4r)，当跳跃网格数为2时，最小转弯半径为6.5r(直径13r)，当跳跃网格数为3时，最小转弯半径为14r(直径28r)。

本发明实施例中，S3包括：

将以无人机当前所在网格为中心以跳跃网格数为半径的一圈网格作为初步决策网格；

根据机动性约束从初步决策网格中进一步选定可供决策的网格。

也就是说，在栅格化地图中各正方形网格紧密排列，以无人机当前所在的网格为中心，如果跳跃网格数为1，即j＝1，则以与当前网格相邻的第1圈网格(上、下、左、右、左上、左下、右上、右下共计8个网格)为初步决策网格，如果跳跃网格数为2，即j＝2，则以与当前网格相邻的第2圈网格(将第1圈网格以及无人机所在网格看作一个整体大网格，该大网格的上、下、左、右、左上、左下、右上、右下共计16个网格)为初步决策网格，以此类推。之后考虑无人机的机动性约束情况从初步决策网格中进一步选定可供决策的网格。

进一步地，作为本发明的一个具体实施例，无人机的机动性约束为保持直线运动，根据机动性约束从初步决策网格中进一步选定可供决策的网格包括：

将初步决策网格中与无人机的速度延长线相交的网格定义为直线网格；

将直线网格及其左右相邻的两个网格作为可供决策的网格。

基于该实施例，请参考图2A和图2B所示的跳跃网格数为1时可供决策的网格的分布情况，以及图3A、图3B和图3C所示的跳跃网格为2时可供决策的网格的分布情况，其中，花纹状网格代表上一时刻无人机的位置，黑色网格代表无人机当前的位置，灰色网格代表无人机下一时刻可供决策的位置，均包括一个直线网格以及与之左右相邻的两个网格，也就是首先将上一时刻无人机所在网格和当前时刻无人机所在网格的延长线与初步决策网格相交的网格确定为直线网格，然后将该直线网格以及左右相邻的两个网格均确定为可供决策的网格。

通过以上步骤，能够规划出无人机下一步移动对应的可供决策的网格，依此规律完成连续多步的规划，即可生成多条可供决策的规划路径，分别计算每条规划路径的搜索收益，选择搜索收益最大的规划路径作为最优路径，之后无人机移动至该最优路径中的第一步网格所在位置(仅执行路径中的第一步)，并在该位置进行下一轮决策，实现在线滚动决策。为了实现该过程，本发明实施例中，S4包括：

对初步决策网格进行编号以对应确定可供决策网格的编号；

根据可供决策网格的编号生成包含预设步数的航迹规划序列；

计算每一个航迹规划序列的搜索收益，并且将搜索收益最大的航迹规划序列中的第一步对应的可供决策网格作为下一步移动的目标网格。

其中，编号方式根据实际情况进行确定，由于以无人机所在网格为中心向外扩展的第j圈共有8j个网格，因此，作为本发明的一个具体实施例，对初步决策网格进行编号以对应确定可供决策网格的编号包括：以[-4j，4j]内的整数对初步决策网格进行连续编号，其中+4j和-4j代表同一个网格，当初步决策网格被选定为可供决策网格时沿用编号。其中，每个网格对应一个期望的航向角指令，编号为0的网格代表地面坐标系下航向角为0，本发明实施例中，初步决策网格对应的航向角选择粒度为(45/j)°，相较于传统三叉树寻路策略可供选择的航向角颗粒度45度而言，能够使无人机在搜索方向决策中具有更细化选项，通过调整跳跃网格数j可以改变决策选项对应的航向角变量，使航迹规划结果更好的满足无人机机动能力。请参考图5的实施例，以跳跃网格数等于2为例，将第二层网格作为初步决策网格并进行连续编号，其中0到8的网格对应0到180度的航向角，0到-8对应0到-180度的航向角，每个网格对应的偏航角度即期望航向角为180/8度，即45/2度。

进一步地，如果上一时刻决策的网格编号为n，那么以n为中心再编号，可以确定当前时刻可供决策的网格的编号为n-1，n，n+1，使用若干连续的可供决策网格的编号构建成的序列[n

为了计算搜索收益，本发明实施例中，计算每一个航迹规划序列的搜索收益包括：

将航迹规划序列中每个可供决策网格的编号转换为网格的坐标；

利用模型预测方法根据转换后的网格的坐标计算搜索收益。

例如，预测未来3步对应的可供决策的网格，则会生成27个网格序列，选取搜索收益最大的网格序列作为优化结果，当网格序列较多时，可以采用遗传算法等启发式算法获取次优解，加快优化求解速率。其中利用模型预测方法计算搜索收益为本领域技术人员所熟知，在此不再赘述。

进一步地，本发明实施例中，通过以下公式将航迹规划序列中每个可供决策网格的编号转换为网格的坐标：

上式中，Δx

图8展示了跳跃网格数为3的高机动无人机搜索航迹，图9展示了跳跃网格数为7的低机动无人机搜索航迹，二者搜索范围相同，且地图栅格化尺寸均为2m。图8中高机动无人机的探测范围是以自身位置为中心的矩形，无人机通过高机动(小转弯半径)搜索航迹实现对目标的全发现。图9中低机动无人机的探测范围是前置矩形，无人机通过搜索决策也实现了对所有目标的发现。由此可见使用本法提出的跳跃网格搜索方法可以合理地规划无人机搜索航迹并且充分满足机动性约束条件。如图10所示，将该方法应用于无人机集群分布式决策时，每个无人机i单独执行本发明的搜索决策流程，再通过搜索信息共享来判断是否完成搜索任务。

此外，传统相邻网格搜索方法需要根据无人机机动能力设计合适的网格尺寸，造成搜索结果统计精度较低，本方法提出的跳跃网格搜索方法可以任意调整网格尺寸，使地图栅格化更细密，即网格尺寸更小，从而使搜索结果的统计精度更高。

综上所述，本发明提供了一种考虑无人机机动性约束的跳跃网格搜索方法，该方法通过将地图栅格化，根据无人机当前速度和机动性约束确定跳跃网格数，再根据机动性约束和跳跃网格数确定可供决策的网格，最终以搜索收益为决策判据从可供决策的网格中选定一个作为下一步移动的目标网格，无人机每移动一步都重复这一决策流程，从而实现在线滚动决策，直至完成搜索任务。该方法将无人机的机动性约束和目标概率分布同时纳入搜索决策的过程中，规划出的搜索航迹更为符合无人机的机动能力，从而显著提高搜索效率，并且提升无人机的安全性能，在多智能体协同在线搜索决策以及搜索航迹规划方面具有很好地应用前景。与现有技术相比，本发明的技术方案能够解决现有搜索决策方法规划出的搜索航迹与无人机的机动能力不匹配导致搜索效率较低以及影响无人机安全性能的技术问题。

为了便于描述，在这里可以使用空间相对术语，如“在……之上”、“在……上方”、“在……上表面”、“上面的”等，用来描述如在图中所示的一个器件或特征与其他器件或特征的空间位置关系。应当理解的是，空间相对术语旨在包含除了器件在图中所描述的方位之外的在使用或操作中的不同方位。例如，如果附图中的器件被倒置，则描述为“在其他器件或构造上方”或“在其他器件或构造之上”的器件之后将被定位为“在其他器件或构造下方”或“在其他器件或构造之下”。因而，示例性术语“在……上方”可以包括“在……上方”和“在……下方”两种方位。该器件也可以其他不同方式定位(旋转90度或处于其他方位)，并且对这里所使用的空间相对描述作出相应解释。

此外，需要说明的是，使用“第一”、“第二”等词语来限定零部件，仅仅是为了便于对相应零部件进行区别，如没有另行声明，上述词语并没有特殊含义，因此不能理解为对本发明保护范围的限制。

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。