一种无人机编队任意图形变换时的防碰撞轨迹仿真算法

摘要

一种无人机编队任意图形变换时的防碰撞轨迹仿真算法。将原状态的图形作为源散点图(以下简称源图)，将预设的变换后的图形作为目标散点图(以下简称目标图)；将源图中的单个点与目标图中点的位置做对应点匹配并得到各点的出发时间。本发明解决了无人设备的防碰撞问题以及在防碰撞的前提下，快速进行坐标匹配并作出图像变换。

说明书

技术领域

本发明涉及图形变换的算法领域，特别涉及一种用于无人机、无人车或无人船等无人控制设备的无人机编队任意图形变换时的防碰撞轨迹仿真算法。

背景技术

自英特尔公司实现了Shooting Star^TM编队飞行进行灯光秀表演，创造出美轮美奂的夜间空中景观以来，无人机群凭借其对图形的精确控制能力、呈现出的多样艺术化视觉效果以及良好的环保特性，被越来越多地应用于艺术、娱乐和灯光秀等领域，目前大多数灯光秀工程大多会采用多个图案的切换显示方案以增加视觉效果，这里首要解决的是多个无人设备在运动过程中的防碰撞问题，同时还要兼顾构成不同图案的切换速度。

发明内容

为了解决背景技术中的问题，本发明提供一种无人机编队任意图形变换时的防碰撞轨迹仿真算法。

本发明解决其技术问题所采用的技术方案是：一种无人机编队任意图形变换时的防碰撞轨迹仿真算法，将原状态的图形作为源图，将预设的变换后的图形作为目标图；将所述源图中的各个点与所述目标图中点的位置做对应点匹配，对应点匹配过程如下：

步骤一：初始化；

源图和目标图以相同的几何中心为坐标原点O，建立坐标系；初始化k＝1；以源图上所有点的坐标构成集合A，第i个元素记为(x_i，y_i)；以目标图上所有点的坐标构成集合B，第j个元素记为

其中，x_i和y_i为源图中第i个点的坐标，和为目标图中第j个点的坐标；

步骤二：计算源图中每个点到目标图中每个点的欧式距离，并将其保存在矩阵D中，即：

其中，D_ij为所述源图的第i个点到所述目标图的第j个点的距离，x_i和y_i为源图中第i个点的坐标，和为目标图中第j个点的坐标；

步骤三：计算源图上点i到目标图的最短距离

求得所有点对应的最短距离中最大的距离

求得最大距离对应的源图中的点

求得最大距离对应的目标图中的点

其中，M为集合A中元素的个数；

步骤四：根据求得的源坐标目标位置的坐标以及它们之间

的距离s得到矩阵E

将集合A与集合B中的对应点删去

步骤五：若匹配工作结束完成，否则令k＝k+1，返回步骤三。

所述对应点匹配完成后，计算各点延时出发的时间

t＝(E(k,5)-E(1,5))/v

其中，E(k,5)对应的元素为第k个点的移动距离，E(1,5)对应的元素为第一个点的移动距离，v为匀速移动的速度。

源图中的点a的移动方向前方有其它点b，且点a的所需移动距离较点b的所需移动距离更远，则点a与点b同时出发。

所述方法同时适用于源图为致密的实心圆，目标图为稀疏型点阵图形；源图是稀疏型点阵图形，目标图是致密的实心圆；源图和目标图均为稀疏型点阵图形或源图和目标图均为稀疏点阵的三维图形。

本发明的有益效果是：解决了智能机群的防碰撞问题以及在防止碰撞的前提下，快速进行坐标匹配并实现所有个体同时到达指定坐标作出图像变换。

附图说明

图1为本发明防碰撞优化示意图。

图2为图案切换设计效果图。

图3、图4为图案变换前后的示意图。

图5中(a)、(b)、(c)、(d)为密集散点扩散过程示意图。

具体实施方式

下面结合附图对本发明实施例作进一步说明：

本发明实施例以解决无人机群编队过程中的防碰撞问题为例做仿真说明，所述方法过程如下：

将原状态的无人机群构成的图形作为源图，将预设的变换后的无人机群构成的图形作为目标图；将源图中的单个无人机与目标图中的位置对应匹配，对应位置的匹配步骤如下：

步骤一：初始化；

约定源图和目标图具有相同的几何中心并以该几何中心为坐标原点O，建立坐标系；初始化k＝1，以源图上所有点的坐标构成集合A，第i个元素记为(x_i，y_i)；以目标图上所有点的坐标构成集合B，第j个元素记为

其中，x_i和y_i为第i架无人机的分布位置对应在源图中的坐标，和为预设图形中无人机需所处的第j个位置对应在目标图中的坐标。

步骤二：计算源图中每个点到目标图中每个点的欧式距离，并将其保存在矩阵D中，即：

其中，D_ij为所述源图的第i个点到所述目标图的第j个点的距离，x_i和y_i为源图中第i个点的坐标，和为目标图中第j个点的坐标。

步骤三：计算源图上无人机i到目标图的最短距离

求得所有无人机对应的最短距离中最大的距离

求得最大距离对应的源图中的无人机

求得最大距离对应的目标图中的预设位置

其中，M为集合A中元素的个数。

步骤四：根据求得的无人机对应的源坐标目标位置的坐标

以及它们之间的距离s得到矩阵E

将集合A与集合B中的对应点删去

步骤五：若匹配工作结束，否则令k＝k+1，返回步骤三。

匹配完成后，为实现同时到达指定位置的目标，需要移动距离最远的无人机第一个出发，其他无人机以不同的延时时间出发，并与第一个无人机同时到达目的地。根据对应点匹配计算可知，第一个无人机的移动距离为E(1,5)，第k个无人机的移动距离为E(k,5)，若无人机飞行速度为v，则第k个无人机的延时出发时间可以由

(E(k,5)-E(1,5))/v

计算得到；

经延时出发后，各无人机做匀速直线扩散运动，同时到达匹配位置。

根据实际情况分析，所述方法还有如下优化设计：

如图1所示，假设图形转换还有最后两点a₁，a₂，要分别移动到b₁，b₂，|a₁b₁|>|a₁b₂|>|a₂b₁|>|a₂b₂|，根据步骤2可知距离矩阵D为按照算法应该移动a₂到b₁，移动a₁到b₂，由于|a₁b₂|>|a₂b₁|，因此a₁要先出发，这样就有可能发生碰撞，故优化为：如果后面点的移动距离更远，那么出发时间要与前一个同步，即a₁、a₂同时出发，该优化大幅减少了碰撞问题。

原算法中对应点匹配算法的时间复杂度为O(N³)，所以当N较大时，运算时间会比较长。为了提高运算效率，我们对算法进行了优化，运用贪婪算法的思想，选取目标图中离圆心最远的若干点(如矩阵B中的前32个点)和源图中的最外围点(源图各行和各列的两端共个点)进行距离计算，取得了几乎相同的运算结果，但算法的时间复杂度降低为O(N^3/2)，运行速度也大幅提升。

如图2所示，为验证算法所设计的图案变换效果图，在前六幅图中，钟盘展示5秒倒计时动态效果，计时为“0”时，要求在最短时间内由时钟散点(密集型点阵图形)向艺术字散点(稀疏型点阵图形)扩散，同时散点无交叉碰撞情况。

扩散过程如下，图3、图4为图形变换的散点处理效果，图5为密集散点图向稀疏散点图扩散扩散的示意图。

本方法实现的图案切换模型经计算机仿真实验，验证了模型既能有效防范无人机的碰撞，又能较快地实现不同图像间的转换，是一种可操作性很强的无人机群队形转换方案。本例以致密的实心圆的源图和稀疏型点阵图形的目标图作仿真实验，也可以推广应用到以下三种情况：

1.源图是稀疏型点阵图形，目标图是致密的实心圆：该情况是“密集散点扩散”算法的逆操作，只需将出发点、到达点对换，再同时出发就可以；

2.源图和目标图均为稀疏型点阵图形：先将源图生产致密的实心圆点阵图，再变换为目标图，这样能实现任意两个二维图案的切换；

3.源图和目标图均为稀疏点阵的三维图形，只需用三维空间距离替换欧式平面距离，以“密集散点扩散”算法生成致密的实心圆点阵图；再逆操作变换为目标图。这样也能方便地实现任意两个三维图案的切换。

各位技术人员须知：虽然本发明已按照上述具体实施方式做了描述，但是本发明的发明思想并不仅限于此发明，任何运用本发明思想的改装，都将纳入本专利专利权保护范围内。