英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
带时间约束的协同目标分配与无人机航迹规划
摘要
一组自动飞行器对付若干目标是任务规划中的一个主要挑战。研究了飞行器同时或连续到达目的地且具有规定时 间延迟的协同飞行路径规划问题，同时最小化任务总时间。这包括找到飞行器对目标的最佳分配，并根据飞行器 的运动学约束生成轨迹。飞行轨迹必须避免飞行区域、威胁和其他障碍物，并且必须防止飞行器相互碰撞。该算 法首先利用基于网络的路由模型计算所有飞行器和目标之间的最短飞行路径。通过求解与最短路径长度相对应的 费用的线性瓶颈分配问题，找到最优分配和关键路径。通过自动插入航路点，其他航路被延长到关键航路的长度。 这是通过串联存储在不同最短路径树中的子路径来实现的。由于网络结构的特殊性，所有的级联飞行路径都是可 飞行的。通过根据飞行路径的长度对其进行排序，并在必要时延长它们以实现所需的时间延迟，从而实现连续到达目标。仿真结果验证了该方法的有效性
关键词：协同飞行路径规划 轨迹生成 目标分配 线性瓶颈 分配问题 无人驾驶飞行器
1 引言
近年来，无人机合作小组的部署已成为民用和军事领域的 一个主要关注领域。应用包括搜索和救援，情报监视和侦 察，压制敌人的防空，战斗行动，等等。预计一个联合系 统的能力将远远超过其各个部分的总和。通过小组成员的 合作与协调，可以更有效地完成大多数任务。在这里任务规划阶段，上下文、任务分配和路径规划起着 关键作用。
研究了一组自主飞行器对多个地面目标的作战问题。 任务是为目标分配飞行车辆和为目标分配飞行路径， 以便(1)所有飞行车辆同时到达目标地点，(2)任务总时间尽可能短。由于存在障碍、飞行限制区和危及任务 成功的威胁，这个问题进一步复杂化。同时到达的主要动机是增强出其不意的因素。另一个原因是防空系统的饱和。多枚导弹同时攻击目标比连续攻击更有可能取得成功，这仅仅是因为防空炮台已经饱和。
第二个问题是指一组飞行器必须在同一架飞机上完成多个连续任务目标。每一架飞行器都能执行每一项任务。目标是找到飞向目标的飞行路径。（1）在给定时间延迟的情况下，飞行器依次到达目标地点， (2)使总任务时间最小化。一个典型的应用是压制需要 探测、摧毁和验证(损害评估)目标的敌对防空基地。另一个例子是协调一个机队在单一跑道上着陆。在执行任务的同时，应尽可能降低飞行器的燃油消耗。
飞行路径生成的一个关键问题是所有的路径都必须是可飞行的、可行的和安全的。第一个特性是指飞行器的运动能力。飞行器必须能够沿着路径飞行，也就是说，机动必须与飞机的加速极限相一致。第二个特性规定，飞行路线必须避免所有障碍，限制区域和威胁。安全是指保证飞行器之间不发生碰撞的安全措施。这是通过保持车辆之间的安全距离来实现的。（有相当多的出版物涉及合作无人机的各个方面。这些 问题包括:(a)任务分配问题，(b)任务分配/路径规划问题， (c)带有预定义任务分配的协同飞行路径规划问题。）
武器目标分配问题是一个已经研究了几十年的最佳 化问题问题。它包括优化分配 n 个武器给 m 个目标， 这样的总预期损害的焦油得到最大化。它可以表示为 一个非线性整数规划问题，并且是 np 完全的。许多小 规模问题的精确方法和大规模问题的启发式方法已经 被提出(例如 Ahuja 等人[1]).
随机武器目标分配问题的目标数量和位置是不知道的先验已经研究，除其他外，由 Murphey[35]。无人机的一个类似问题，考虑到飞行器的故障概率，并提供一个基本的飞行路径规划，已经由贝灵厄姆等人研究[7]。作者提出了一个混合整数线性规划的问题，并解决了使用商业软件包。 贝灵厄姆等人讨论了一个多任务分配问题，其中具有不同能力的无人机必须执行一组任务。使用直线路径近似，问题是解决使用公式作为一种特殊类型的背包问题。其他应用混合整数线性规划的方法包括Schumacher 等人[40]和Weinstein 和 Schumacher 的工禁忌搜索启发法也被应用于指派问题，例如Alighanbari等人[2]。
在 Maddula 等人的文献[32]中讨论了目标分配和路径规划的联合问题。作者提出了一种启发式方法，将一组无人机分配给多个目标，从而限制了每个无人机面临的威胁，最小化了最大路径长度。其思想是通过Voronoi 分割来创建潜在的子路径，构造一个包含这些子路径的图，并计算图中目标和无人机之间的短路径。通过子路径交换，对贪婪启发式算法获得的无人机初始目标分配问题进行了改进。同时攻击和多个连续任务时间约束的类似问题已经被 Eun 和 Bang[18]用遗传算法研究和解决。然而，这两种方法都没有考虑飞行器的机动性和无人机之间可能发生的碰撞。Shima 等人[42]考虑了飞行器的飞行特性。作者研究了每个无人机需要完成三个连续任务和所有路径的累积长度必须最小化的问题。这个问题被表述为一个大型的组合优化问题，并通过遗传算法来解决，使用了可能分配的树形表示法。飞行路径由直线段和圆环段组成的 dubin 路径实现。不幸的是，该算法忽略了障碍物和相互碰撞的风险
给定目标分配的协同飞行航迹规划方法包括Schouwenaars 等人提出的燃料最优航迹规划算法[39]。无人机编队必须从预先确定的初始状态转移到预先确 定的最终状态，而不能相互碰撞，也不能与其他静止 或移动的障碍物发生碰撞，从而使燃料总消耗量尽可能小。该问题被重写为一个线性规划的混合整数/线性约束和解决使用商业优化包。然而，似乎没有充分考虑无人机的飞行特性和安全要求。Melor 等人审查和比较了一些改进方法效率的方法[34]。
已经发表了几篇论文，论述同时到达目标的避免威胁轨道的规划。Mclain 和 Beard[33]提出的算法确定了从图的起始位置到目标位置的初始路径，该算法通过 Voronoi图的边进行搜索。这些路径被离散成固定长度的段，然后通过添加或删除段和平滑结果来优化以满足所需的长度。另一种基于Voronoi 图的方法，特别强调在无人机的动态能力范围内路径的发展，是由于 Chandler 等人[11]。然而，环境保护署算法没有考虑飞行器相互碰撞的风险。
与其他无人机和静态障碍物的碰撞被 Shanmugavel等人的算法考虑在内[41]。这个三步骤的过程从生成带有回旋曲线的 dubin 路径形式的可飞行路径开始。然后，通过手动包含路径点，将这些路径修改为安全路径。第三步是通过改变路径的曲率来产生等长的路径。该方法似乎是工作良好的过度复杂的情况下，很少和小的障碍，如果最初的路径长度没有非常不同的彼此。
本文的目的在于提出一种结合任务分配和协调飞行路径规划的无人机编队航迹规划算法。该算法应该考虑目标到达的时间约束，并充分考虑飞行能力、飞行路径的可行性和安全性，从而消除以前策略的弱点。该算法应该是完全自动的，不需要操作员的干预，以适度的计算机运行时间实现相当简单，并有效地处理同样具有挑战性的场景。
我们提出了一个分为三个阶段的算法。在第一阶段，计算所有对飞行器和目标之间的最短飞行路径。这是通过生成一个复杂的网络离散位形空间和应用标准的图搜索法。第二阶段是为目标或任务寻找无人机的最佳分配。在同时到达不同目标的情况下，需要解决一个线性瓶颈分配问题，其中费用相当于最短路径的长度。如果是连续到达在一个共同的目标，它足以排序的飞行路径根据他们的长度和重新安排飞行时间。在第三阶段，飞行路径必须延长到所需的长度，并加以调整以消除无人机之间可能发生的冲突。这个想法是插入合适的航路点。修改后的飞行路径是通过连接子路径到存储在不同的最短路径树中的航路点得到的。由于网络结构的特殊性，保证了所有级联飞行路径都是可飞行的。一个足够密集的网络包含大量合适的航路点，使得可以选择一条安全的航路而不会发生冲突。
文章的其余部分如下。第二部分提出了一种单机飞行路径规划算法，为协同飞行路径规划奠定了基础。第三部分描述了目标分配和协调路径规划的策略，并详细介绍了技术实现。在第 4 节中讨论了各种情况下的模拟结果。我们在第 5 节中以最后的评论结束。
图一由随机分布的天皇草所产生的天皇网络
2 单体飞行器的航迹规划
为了解决飞行路径规划问题，随着时间的推移，出现了各种各样的技术。这包括势场方法(见 Kim 和 Khosla[25]，Waydo 和 Murray[44]) ， 细 胞 分 解 (Chazelle[12] ，Lingelbach[31])，路线图方法(Choset[13]，Kavraki 等[24])，快速探索随机树(LaValle 和 Kuffner[30])，混合线性程序 (Schouwenaars 等[39]，贝灵厄姆等[6]),(see e.g. Babel [3], Bortoff [9], Jun and Drsquo;Andrea [23]). 概率方法 (bertuckelliandHow[8] 。 dugan[17] ，Pfeifferetal.[38])和不同的基于网络的方法(例如 Babel[3]， Bortoff[9]，Jun 和 drsquo;andrea[23])。 进一步的方法旨在改进 Dijkstra[16]的图搜索算法。这 包括从 a**算法(Hart 等人[22])到增量 a**算法(Koenig 和Likhachev[26]) 、 d** 算 法 (Stentz[43]) 、 d** 精简算法 (Koenig 和 Likhachev[27]) 、 场 d** 算 法 (Ferguson 和Stentz[19])、Theta***算法(Nash 等人[36]、DeFilippis 等人 [15]) 和 *** 算 法 (niewolaandpodkowski[37]) 。Goerzenetal.[21]Latombe[28]和 LaValle[29]对路径规划算法进行了全面的综述。
我们使用了 Babel[4]引入的飞行路径算法的增强版本。该算法最适合我们的目的，因为它允许以一种非常简单和有效的方式通过插入航路点来操纵飞行路径。这反过来又使得扩展路径长度到几乎任何数量成为可能，同时保持了飞行能力和可行性(见第 3 节)主要的想法是创建一个复杂的网络离散水平位形空间。如图 1 所示，一大组有向线被扔进操作区域，就像Mikado 的稻草一样。飞行路线沿着这些线路前进。交叉线由两个平滑过渡连接起来。分支点(表示为红色圆圈)是网络的顶点，分支点之间的飞行路径段是边。边的代价是飞行路径段的长度。为了将释放点和目标点包括在内，网络通过分别带有释放方向和接近方向的两条通过这些点的线进行扩充。最后，消除网络中所有通过障碍物、限制区域和威胁的边缘。最短路径是通过应用标准的方法获得的，如 Dijkstra 的算法或 a 次/*算法。
在该算法的原始版本中，所有行都被随机抛入平面中，从而提供了一个纯概率网络。根据实际经验，我们扩展了这种方法，用适当数量的确定性线来补充随机生成的线集。给定两个多边形或圆形障碍物，我们添加这些线接触但不交叉的障碍物，同时，不交叉之间的任何其他障碍物(见图 2)。这些线，每个方向一条，允许在直线飞行中尽可能接近地通过障碍物。
交叉线之间的过渡是通过旋叶线和圆环段的组合来实 现的，见图3a。回旋线是曲率随其长度线性增长的曲线。缓和曲线从最初的直线传递到曲率线性增加的回旋线其次是一个圆形段与常曲率和第二个回旋线与线性递减曲率，最后加入第二直线。这导致了一个连续曲率的轨迹，因此平稳和无挺举横向加速度的飞行器。
图2 决定性天皇稻草
通过整合不同最大曲率对应于不同强度机动的转移，可以增加网络中可能飞行路径的变异性和数量。图 3b 示出了具有四种可能的变换的一个例子。最短曲线以最大侧向加速度实现最强的机动，其他曲线以较长的曲线以较弱的侧向加速度实现。该算法允许任意飞行方向、任意转角以及不同强度的机动，充分发挥了飞行器的飞行能力。网络中的所有路径都是可飞行的，因为直线飞行路径段之间的过渡是平滑的，与飞行器的横向加速度一致，并且是可行的，因为没有飞行路径段与障碍物碰撞。该算法的另一个优点是网络密度可以根据解的精度要求自由调整。这与常用的规则网格网络形成了鲜明的对比，在规则网格网络中，网格点用顶点来标识，从而限制了网格的分辨率。
3 协调飞行路径规划
3.1 同时抵港
我们考虑一组无人机同时从基地起飞，任务是攻击 n个目标。预先确定了带有释放方向的无人机的释放位置和带有接近方向的目标位置。所有的飞行器都是同一类型，并且在等高度飞行。这些场景可能包含威胁、禁飞区和障碍。目标是分配无人机到目标(每个目标一个无人机)，并产生可飞行的，可行的，安全的飞行路径，同时到达目标和最小的任务时间。
协同任务规划的思想在下面的算法方案中有所体现。
图 3 天皇稻草之间的过渡
（a)类回旋曲线和圆形段 （b）不同强大的演习
算法 i
-
个体
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[239014]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
