空中机器人路径规划算法研究

林文

（长沙航空职业技术学院，湖南长沙 410014）

1 引言

空中机器人的发展至今已有70多年历史，已经取得丰硕的研究成果。特别是其典型组成部分无人机技术已经在诸多领域取得了成功应用。当前，空中机器人在军事领域和民用领域都已经发挥了越来越重要的作用。

在军事方面，空中机器人既能够执行杀伤性任务，又能够执行非杀伤性任务。已经从担负单纯的空中侦察、靶机扩展到情报监视、指挥和控制、火力制导、导弹导航、充当诱饵、电子战、通信中继、边境巡逻、战场评估甚至战斗等任务。目前，固定翼空中机器人已经在为军队服务，在几次局部战争和反恐战争中由于其体积小、成本低、隐蔽性强无、机动灵活、无人员伤亡且战场生存能力强等特点都发挥了重要作用，取得了良好的军事效益，具有巨大的应用前景。当前的世界局势决定了未来战争将是高技术条件下的局部战争，在这种形式下空中机器人也将有更广阔的应用空间。

在民用方面，随着科技的发展，各种微小型的空中机器人凭借采购和使用费用低、使用方式灵活等优点，已经可以替代有人机完成搜救救援、空中巡逻、交通监控、资源勘探、灾情监测、电力巡线、森林防火、对地观测、农药喷洒等任务，具有光明的应用前景和市场效益。

随着空中机器人在军事领域中的作用逐渐增大，我国对于空中机器人的研究也越来越多，越来越深入，也取得了一定的研究成果。路径规划是空中机器人的主要技术之一，也成为了很多科研人员的研究方向。本文从军事角度出发，从战场威胁方面来对空中机器人的路径规划进行研究。

2 战场环境的Voronoi图构建

2.1 Voronoi图定义

Voronoi图又称为泰森多边形或者Dirichlet图。Voronoi图是对平面n个离散点而言的，它把平面分为几个区，每一个区包括一个点，该点所在的区是到该点距离最近点的集合。设P是一离散点集合P1，P2，…Pn∈P，定义Pi的Voronoi区域V（Pi）为所有到Pi距离最小点的集合：V（Pi）={P/d（P，Pi）≤d（P，Pj），j≠i，j=1，2，…n}

假设P是一离散点集合，P1，P2，…Pn∈P，定义P的Voronoi图V（P）为：V（P）={V（P1）,V（P2）,…,V（Pn）}，其中Pi称为V图生成元。

2.2 Voronoi图的特性

（1）vor（s）把平面划分为n个多边形域，每个多边形域V（pi）包含且只包含S的一个点pi。

（2）vor（s）的边是S中某对点的中垂线的一个线段或者射线。

（3）V（pi）是无界的，当且仅当pi属于凸包外界的点集。（4）Voronoi图之多有2*n-5个顶点和3*n-6条边。

（5）每个Voronoi点恰好是三条Voronoi边的交点（假设任何四点都不共圆的话）。也就是说Voronoi点就是形成三边的三点的外界圆圆心，而且所有的这些外界圆都有个特点：各自内部不含任何S点集的点（空心圆）。

从上面的Voronoi图特性可以看出，Voronoi图的边是能够最好地规避对应的两个威胁的线段，因此，选择Voronoi图来构造整个战场，不但可以把路径规划的空间进行简化，而且很大程度上提高了工作效率。

2.3 Voronoi图的构造

目前，对于Voronoi图的构造已经有了很成熟的算法，不过，根据算法计算出来的Voronoi图的顶点没有包含空中机器人的起始位置和目标位置，要对起始位置和目标位置之间的最佳路径进行规划，就必须把这两个位置添加到Voronoi图中。具体的方法是将空中机器人的起始位置作为Voronoi图的一个顶点，然后将这个顶点与Voronoi图中与之最近的3个点连接起来，对于目标位置也进行相应操作，从而计算出最短路径的Voronoi图。

3 路径段的代价计算

由于在构造Voronoi图时，是把所有的威胁的中心位置当成母点。然而，在实际的战场上，所有的威胁都是有一定作用范围的，因此，要在战场上对空中机器人进行路径规划，就必须要模拟战场的真实环境。本文从禁飞区、火力威胁和雷达探测威胁三个方面来进行路径规划研究。

3.1 禁飞区和威胁的处理

禁飞区、火力威胁和雷达探测威胁都是对空中机器人飞行障碍。具体来说，可以分为两类威胁，一类是软杀伤威胁，一类是硬杀伤威胁。软杀伤威胁包括火力威胁和雷达探测威胁，当空中机器人进入这类区域，可能会被杀伤或者被探测到，但是如果成功穿越了这类威胁的作用区域，就有不被损毁的概率；硬杀伤威胁则是主要指禁飞区，禁飞区是由于政治因素或者物理因素限定不允许飞行的区域，空中机器人一旦穿越，就会被损毁。在对空中机器人进行路径规划时，必须对软杀伤威胁和硬杀伤威胁进行计算，软杀伤威胁的相关计算信息包括威胁的中心位置，作用半径和杀伤概率，硬杀伤威胁的计算信息包括禁飞区的中心位置和半径。对空中机器人进行路径规划时，对每个Voronoi图的边的代价估计应该要对每个威胁进行相应处理。

3.2 代价计算

在Voronoi图构造完成之后，图中的边是最后规划路径的组成，称为路径段。要进行路径规划，就必须要对每个路径段进行代价计算，代价计算主要有两个方面，一个是威胁接近代价，一个是燃料代价。这两个代价的加权和就是这个路径段总代价。具体公式如下：

其中，Ji是路径段的总代价，Jit是威胁接近代价，Jif是燃油代价，k是加权系数，范围在0-1之间。在计算路径段总代价的时候，需要根据任务的安全要求和燃油要求，对k的值进行相应调整。根据路径段总代价的计算方法，对Voronoi图中的每条边进行代价计算，然后就对最优路径进行计算。

4 最优路径生成

4.1 初始路径生成

根据上面的步骤完成Voronoi图中每条边的代价和之后，再把各条边的代价值的有向图G计算出来，G=（V，A，W），V是Voronoi顶点的集合，A是顶点之间Voronoi边的集合，W表示边的代价值，其中，V（v1，v2，v3·······vn），n是顶点的个数。利用有解有向图的Dijstra最短路径法来进行计算，从而得出指定节点之间的最短路径，进而得出空中机器人的起始位置和目标位置之间的初始路径。

4.2 路径修正

Dijstra算法只是能够计算出最短路径，也就是Voronoi图中的最佳路径，然而，这是否符合空中机器人的是实际情况，是否适应空中机器人的实际飞行需求，还需要进一步的修正。具体来说，需要从以下几个方面来进行修正：第一，是否能够进一步缩短空中机器人的飞行距离；第二，在Voronoi图中的两条边，其夹角是不是满足空中机器人飞行的最小转弯半径，如果不能满足，就必须要进行相应修正；第三，如果空中机器人的初始航向角与路径规划时的起始航向角之间差异太大，也需要进行修正。

4.2.1 缩短距离的处理

从Voronoi图的定义和特点来看，Voronoi图的边会最大程度地避免母点，因此，Voronoi图是在战场进行空中机器人路径规划的最佳方案。然而，在实际的战场上面，空中机器人只需要避免威胁，而不需要围着每个威胁来走折线。因此，在进行路经修正时，可以通过直线化来缩短飞行距离。

具体方法如下：假设初始路径中的各个点分别是（xs，ys）（x1，y1）（x2，y2）（x3，y3）···（xi，yi）···（xn，yn）（xt，yt）。其中，（xs，ys）为起始位置，（xt，yt）是目标位置，在整条路径上，总共有n个节点数。缩短路径的步骤就是把当前点当作目标点，从当前点出发依次向之前的点进行连线，如果连线穿越了威胁，记录这个点之前的那个点当作当前点，把这个当前点与上一个当前点之间的节点删除。然后重复这些步骤，重新从这个当前点出发，再继续往前连线，直到到达初始点位置。

4.2.2 路径中的拐角的平滑处理

在Voronoi图中的两条边，如果夹角太过尖锐，就会让空中机器人无法正常转弯，因此，需要对太过尖锐的夹角进行平滑处理。进行平滑处理就是在尖锐的拐角处加一个圆弧，这个圆弧的半径通常都是选择空中机器人的最小转弯半径，从而，可以让空中机器人顺利转弯。

4.2.3 初始航向角处理

如果空中机器人的初始航向角与路径规划时的起始航向角之间差异太大，需要对航向角进行相应修正。对航向角进行修正，首先需要沿着与当前位置相连的圆弧进行飞行，然后转入第二个圆弧，第二个圆弧是与第一个圆弧光滑连接的，然后并接入第一段路径，第一段圆弧与空中机器人航向光滑衔接。这两个圆弧的连接点，就是路径上面空中机器人当前状态到达期望路径的转节点。需要注意的是，两个圆弧之间的半径应该要大于等于空中机器人的最小转弯半径，从而保证空中机器人能够顺利转弯。这样，就可以在路径出发点不变的情况下，只需要进行少量调整，就可以改变空中机器人的飞行航向角。

通过缩短距离的处理、路径中的拐角的平滑处理和初始航向角处理，就可以得出空中机器人的最优路径，这也是在已经给定威胁分布的战场环境下，空中机器人的飞行最优路径。

5 结论

本文对已经明确威胁分布的战场环境下，空中机器人的飞行最优路径进行了研究。在已经明确威胁分布的战场环境中，通过Voronoi图构建避免威胁的初始路径段，然后根据这些威胁的具体情况，计算出待选路径段的代价值，再利用Dijstra算法计算出初始路径，最后再进行缩短距离的处理、路径中的拐角的平滑处理和初始航向角处理，从而得出空中机器人的飞行最优路径。

[1]丁希仑；俞玉树.一种多旋翼多功能空中机器人及其腿式壁面行走运动规划[J].航空学报，2010，56(10)：175-186.

[2]张银玲;牛小梅.蚁群算法在移动机器人路径规划中的仿真研究[J].计算机仿真，2011，28(06)：237-240.

[3]邬再新;李艳宏;刘涛.多移动机器人路径规划技术的研究现状与展望 [J].机械，2008，47(01)：6-8+21.