使用Dubins路径和回旋曲线进行多个无人机的路径规划

1、使用Dubins路径和回旋曲线进行多个无人机的路径规划摘要：本文讲述了对一群无人机进行路径规划的方法。进行这样研究要解决如何使一批无人机同时到达目标的问题。制定可以路径（适航、安全的路径）称为路径规划，它分为三个阶段。第一阶段使规划适航路径，第二阶段通过添加额外的约束规划安全的路径，使无人机不与其他无人机或者已知的障碍碰撞，第三阶段对路径进行规划是无人机同时到达目标。在第一阶段，每个无人机都使用Dubins路径和回旋曲线进行路径规划，这些路径是通过微分几何原理完成的。第二阶段为这些路径添加安全约束：（一）无人机间保持最小间距，（二）规划相同长度的非交叉路径，（三）飞过中间的航线点/形状，使这些

2、路径更安全。第三阶段，所有路径长度相等使无人机可以同时到达目标。一些模拟仿真结果证实了这一技术。1、 介绍 在许多应用程序中自动控制取代了人类操作，像军事系统中存在危害人类因素的地方、处理有害物质、灾难管理、监视侦察等单调的操作。需要开发自动控制系统来更换这些系统中的人类操作员，这样的自动控制系统在水陆空各种环境中都有。在无人机的研究中，水陆空等因素是作为一个集体进行研究的。无人机在军事和民用领域都有广阔的应用前景，因此有许多关于无人机的学术或商业性质的研究。廉价电子产品的飞速发展使得无人机更加实用。大自然中成群的鸟和鱼给了人们灵感，联合控制是自动控制中的一个活跃的研究方向。雇佣一批无人机可以

3、产生成本效益和容错系统。从一个地方飞到另一个地方并作为一个移动传感平台进行监视或跟踪是无人机的一个功能，实现这个功能需要为无人机提供一个合适的安全路径。路径规划是任务规划的一个分支，图1是任务规划的典型功能体系结构。图1有三个分支，分支的数量和功能会根据应用程序和任务目标的不同而改变。第一层分支的任务是跟踪目标，基于这些目标，这层为无人机分配任务和资源并且充当决策者。第二层为无人机规划路径和轨迹，这一层用路径规划和相关的算法（如避免碰撞）规划可行的轨迹/路径。第三层进行指导和控制，保证无人机在第二层规划的轨迹上飞行。本文着重于第二层的研究，在第二层，路径规划产生的轨迹使一群无人机同时到达指定位

4、置。在自动控制系统领域，路径规划仍然是一个公开的问题。路径规划是在两个或多个点之间规划出一条或多条路径，通常这些点是在存储地图上指定的。路径规划是一个复杂的问题，它需要满足操作环境和其他作战需求等物理约束，其中最重要的约束是路径必须是可以飞行的，无人机的适航路径必须满足运动学约束以确保无人机运动在操纵曲率的最高界限。图1任务规划的层次结构操纵曲率与无人机的横向加速度成正比(a=kvv)（a是横向加速度，k是曲率，v是无人机的速度），无人机路径上所有点的曲率必须小于最大曲率。因此，路径是否可以飞行是由路径曲率决定的（三维空间中它是由曲率和转矩共同决定的）。第二个重要约束是安全性。躲避障碍和其他无

5、人机的能力是衡量路径安全性的主要指标，路径必须保证无人机避免与己方无人机相撞，并且能够灵活的躲避环境障碍带来的威胁。此外，路径最短、燃料和能源消耗最小等附加约束可以提供更好的性能和效率，本文认为最短路径通常也是最节能路径。可能还存在维持复杂城市环境中的通信、完成任务的时间、基于任务目标的资源管理等约束。因此，本文的主题是在存在静态障碍的环境中为一群无人机规划长度相等的安全适航路径，确保无人机同时到达目标。2、 准备工作在近代多架无人机的路径规划的研究非常活跃。不同的应用领域（监视、搜索和跟踪、救援、灾害监测等）有不同的目标和方法。目前存在多种解决方案，每一种方案都有自己的优点。但是随着问题复杂

6、性的增加，我们需要新的解决方案。大多数的解决方案都可以由一个简化框图（见图2）表示图2 现有方法的路径规划使用这种方法进行路径规划需要输入航迹点、障碍位置和大小、以及相关的不确定因素，通过优化技术将这些数据进行路径规划。这些解决方案没有固定的曲率约束，因此，产生的路径通常是多边形的。在某些情况下，新规划的路线是可行的，在另一些情况下，要想消除不可飞行的路线产生适航路径，这些路线还需要进一步优化。从输入数据来规划路线的方法有很多，通过泰森多边形图解法生成的路线是一个定义了一组静态障碍物的地图。操作时，每次弹出遇到威胁，泰森多边形法都会进行更新。Mclain和Beard认为，一个连接端点的链模型可

7、以通过定义链连部队减少方向改变进行路径规划。通过定义一个与障碍物相关的排斥力来劲性路径规划，这些力使路径在遇到障碍物时外形和距离产生巨大变化。Bortoff使用类似的方法通过定义虚拟部队进行研究。Judd和McClain提出使用带有轨迹平滑的三次样条函数进行轨迹规划，Chandler、Pachter和Rasmussen主张用弧进行轨迹规划。Zhang、Wang、Yu还有Shima、Rasmussen、Sparks是假设一个任务中分配多个机器人进行直线轨迹规划，混合整数线性规划等优化技术、进化算法也被应用与无人机的路径规划。Segovia, Rombaut, Preciado和 Meizel提出

8、了对路径规划进行全面检查。有研究表明，这个路径规划是整体的一部分。Chandler et al提出使用一个指定的应用程序进行轨迹协调规划。Zabarankin,Uryasev,Pardalos提出使用离散化的分析优化方法满足路径长度约束规划出一条避免被雷达发现的最优路径。Eagle和Yee认为可以把路径规划问题看做是在分隔开的单元格内进行搜索的问题。Boreoff的研究中可以看到使用图表、最优控制、势场方法进行躲避敌方雷达的路径规划的比较结果。Shanmu-gavel, Tsourdos, Zbikowski, White, Rabbath和 Lechevin使用参数曲线进行路径规划。Shan

9、mugavel, Tsourdos, Zbikowski, White 和 Shanmugavel, Tsourdos, Zbikowski, White 使用Dubins路径进行路径规划。本文介绍了一种新的路径规划方法（见图3），这种方法使用适航路径进行路径规划。图3路径规划的新方法 适航路径的第一步规划分别与航迹点和航迹形状相关，由此规划出的轨迹是满足无人机运动约束的可行轨迹，随后调整这些路径以产生满足额外安全约束的安全路径，这个适航路径是基于Dubins路径的，但是将设计原理中的圆弧换成回旋曲线。在机器人应用程序中可以看到早期的回旋曲线。但是，经过笔者的努力，本文是第一篇使用基于回旋曲线

10、原理的Dubins路径进行路径规划的论文。本文的主要贡献是使用微分几何原理设计了一个飞行路径并进行了多个无人机的路径规划。摘要：第三部分讲述了任务目标和仿真，第四部分将阐述路径规划问题的制定，第五部分讲述解决方案和技术参数等细节，第七部分进行适航路径的数学推导，第八部分给出在自由环境和凌乱空间中的仿真结果，最后一部分是本文得出的结论。3、 场景对应的问题见图4.图4.方案：r(1)航线 路径 (x,y,z)方位 坐标一批N架无人机离开基地，它们必须同一时间到达目标区域。假设每个无人机的开始和结束位置坐标(x,y,z)和方向角(f,f)是先验的。假设这批无人机的类型相同、飞行速度相同并且飞行在相

11、同的固定高度上。每个无人机具有相同的最大曲率约束并且环境中有静态障碍物。这些无人机要像躲避静态障碍物一样躲避其他无人机以及空间中存在的其他障碍。4、 问题公式化考虑一个单独的无人机从基地到目标位置的无约束初步路径规划问题。起点ps在基地，终点pf在目标位置，标签r表示路径连接，路径规划产生一个路径把开始位置ps(xs,ys,zs,s,s)和终点位置pf(xf,yf,zf,f,f)连接起来。t表示路径长度函数。(,)表示取向，红色表示障碍区，i表示第i架无人机或路径。将公式（1）扩展到N架无人机，每架无人机飞过np个位置点，得到： t代表路径转矩，k代表路径曲率，Kmax是最大曲率，Tmax是最

12、大扭矩，代表安全约束，代表安全长度。5.2.15.2.3部分的长度约束为：如果航线在固定的高度，那么公式（2）可以简化为：使用有曲率约束的二维Dubins方法可以解出公式（1），这表明最短路径可以由三个切向圆弧（）或者两个切向圆弧加一条直线（）得到，其中代表圆弧，代表直线。、解决方案如果所有无人机的速度相等，可以通过规划长度相等的路径来实现同时到达，这可以通过解公式（）和一个额外的路径约束：（）（）得到，这样，路径和路径的长度是相等的。随着约束的增加复杂性也增加了，这样就可能得不到一个解决方案，这个问题可以分解为三个阶段：第一阶段为每架无人机规划一条最短路径，第二阶段添加安全约束，第三阶段建立

13、长度相等的飞行路径。.第一阶段：选择适航路径在第一阶段，每架无人机的适航路径都是从开始位置到结束位置相连。具有连续曲率的最短路径被称为适航路径，它能够满足无人机的最大曲率约束。在第一种情况下，选择有回旋曲线且有一条直线与两个圆弧相切（）的Dubins路径。这条路径的曲率轮廓有两个不连续的点。因此，回旋曲线在有坡道曲率轮廓的地方取代圆弧，修改之后，过渡弧和线段之间的曲率变的平滑了，图表示路径及其曲率概要。图适航路径以及他们的曲率路径的曲率与横向加速度成正比，连同其他地点、速度、位置形成一个闭环指导系统进行路径跟踪（图中的第三层）。路径规划和路径跟踪形成一个闭环反馈，确保无人机能够准确的按照给定的

14、路径飞行。.第二阶段：满足安全约束在第二阶段，要给可以飞行的路径加上安全约束。这些约束既要考虑已知的障碍，又要避免与其他无人机相撞，假设每个无人机位于它的质量中心有一个安全半径，这个半径值小于传感器探测范围大于最小曲率半径，这确保无人机能够感知到障碍或者其他无人机，且有足够的机动能力躲避障碍。两个约束条件：（一）间距最小（二）路径长度相等且非交叉，如图所示第三个安全约束通过建立中间航迹点形状来处理弹出的威胁。这些将在.节讨论图安全路径.最小分离距离任何两个飞行路径之间的距离应该小于一个阙值，这个值称为最小分离距离，在这里是指安全半径的两倍（见图）。如果两个路径的安全圈重叠，将会产生碰撞。为了通

15、过新的航迹基准点位置或者通过因弧线曲率的改变而改变的轨迹形状，我们需要重新规划路径。dk,m代表路径rk(t)和rm(t)之间的距离。最小分离距离约束是：5.2.2 长度相等的非交叉路径 前面的约束条件是针对无人机的直线轨迹，不能解决无人机曲线轨迹的飞行问题。如果将“最小分离距离”用于曲线路径将会得到错误的结果。如图6所示，路径rk(t)和rm(t)在点X处相交，因此，它们不满最小距离约束。但是，如果每个无人机从起点从交点走过的距离是不相等的，那么得到的这个结果有可能是错误的。因此，如果每架无人机从起点到交点的长度之差大于安全圈值，那么碰撞是可以避免的。dk,int和dm,int就是路径rk(

16、t)和rm(t)从起点到交点的长度。对适航路径进行安全约束测试。如果路径满足方程式（6）和（7），就不需要重新进行规划。否则，必须通过改变回旋曲线的曲率或者飞过中间航迹点重新进行路径规划。5.2.3 使用中间航途基准点/位置处理威胁通过规划中间航途基准点/位置完美的解决了避碰和处理静态障碍这两个约束。当路径与障碍相交时，我们规划出一个中间航途基准点来躲避障碍。考虑为一组给定的位置/航迹点规划一条适航路径r(t)。这种威胁回避算法是通过选择一个新的航途基准点/位置重新规划一条路径来提前躲避障碍物，原理概念见图7。图中中央阴影部分代表一个障碍，中间障碍C的位置决定了中间航途基准点M的选择，它在点X

17、1，X2连线的左边或者右边。如果中心C在直线X1X2的左边，那么点M在障碍区的右边选择，反之亦然。安全圈内的点M和N是中间航途基准点。这些点是直线X1X2与安全圈的交点。图中，r(t)代表最初的路径，r1(t)和r2(t)代表由中间航途基准点M规划的新路径，wp1和wp2代表航迹点/位置。 图7 通过中间航途基准点处理威胁6、 第三阶段：路径长度相等任务要求无人机同时到达目的地，这就要求所有的路径长度都是相等的。然而，满足安全约束和曲率约束的可行路径的长度是不相等的。因此，将可行路径的长度调整到等于参考路径的长度。选择一群无人机重的中的最长路径作为参考路径，将其他路径的长度都增加到等于参考路径

18、。路径长度是回旋曲线的长度与这些弧切线的长度之和，通过减小回旋曲线的曲率来增加路径的长度，反之亦然。通过下式计算曲率值kS代表路径长度，s是路径长度的集合，N代表无人机的数量，Serf代表参考路径的长度。7、 适航路径的设计7.1、Frenet-Serret框架适航路径是根据线性代数和微分几何原理进行设计的。根据微分几何原理，二维空间内的一条曲线是由一个ortho-normal框架移动产生的。曲线上的每个点都有一条切线和一个法向量，它们构成了一系列的ortho-normal框架，这些框架被称为Frenet-Serret框架。考虑一下图8中的曲线r(t)上的点Q。 图8 二维空间内的Frenet

19、-Serret框架Q点上的切线和法向量分别用T和N表示。切线T与X轴有一个角度，过点Q的路径长度为s。通过增加路径长度对框架进行优化，下面是在Q点的框架的方程式7.2、回旋曲线下式给出回旋曲线的弧角随着轨迹变化而改变的计算公式：K是弧长s处的曲率，t是弧长变量， 向量v是速度。这个向量的终点由坐标x，y表示，通过积分得到：角t是角沿着弧长s移动的轨迹，。因此，这些积分是按比例缩小了的菲涅尔积分 通过改变变量来对这个积分进行评估公式可以整理为通过法向量vr重新建立等式并且与向量va建立联系。和代表两个向量的长度，tr和ta是单位长度的依据向量，单位向量tr和ta可以写成： 通过转换成角度。这意味

20、着回旋曲线没有简便解法，要解出答案就必须计算切线和法向量。因此可以通过曲率轮廓k(s)设计回旋曲线。7.3、有回旋曲线的Dubins路径图9是一个CLC类型的Dubins路径。 图9 回旋曲线代替圆弧的Dubins路径图中两个圆的半径分别为何，（t，n）形成一个单位框架，下标s和f分别表示开始和完成，向量ac是连接向量。两个位置之间的中线可以作为这个策略的标志。在任何位置上，从切向量到中心向量C的转换（不管是有益的还是有害的）都可以作为每个策略中曲率的标志。从图中得到：Rs是最初策略中的半径。类似的Rf是最终策略中的半径。Frenet基础向量与下列式子有关：ef=R()es （32）通过改变开

21、始和终点轴心来改变轴线，这个旋转矩阵用R()表示。因此R()=esef (33)连接向量as，af，ac组成一个正交向量组，为了确定这些向量，连接向量ac应该通过开始和终点轴心线确定。ec是定义连接向量的基础。因此，总旋转矩阵R()为：R()=R(f)R(s) （35）如果向量pf减去向量ps可以通过开始轴心es测量：因此，在开始轴心处的向量和为：方程的左边表示向量沿着圆转，因此中心向量c可以通过开始轴心得出Ect是中心向量的基础向量组。剩下的连接向量s，f，ac可以根据开始轴心处的基础向量得出（38） 中的中心向量变成正常化单位中心向量，得到这是一个代表单位向量旋转的旋转方程，因此，右旋向量

22、必须是单位大小的，得到可以通过 来测试一个方案的可行性。为了计算旋转角s，方程可以改为扩展公式并求出s最后，可以求出角f：另一种解法：扩展之后得到：相关的菲涅尔积分为：级数展开式为：8、 模拟对两组数据进行了模拟计算。第一种情况是三个无人机在无障碍环境下的路径规划。无障碍环境下，公式（5）可以改为：仅限于躲避无人机的内部冲突。图10显示了无人机UAV1，UAV2，UAV3的初始路径，连接基地和目标的最初路径满足最大曲率约束。对这些适航路径进行安全性测试，确保它们满足安全约束。从图中可以看出UAV1与其他两条路径相交，不满足“最小分离距离”约束。用UAV1的路径作为必要条件进行测试（见公式（7），发现UAV2和UAV3的路径到中间航途点的距离之差大于安全半径2Rs，因此，UAV2和UAV3都满足安全约束。UAV1，UAV2，UAV3的路径长度分别为：20.21，20.44,17.10.因此，把UAV2的路径作为参考路径。通过减小回旋曲线的曲率增加UAV1和UAV2的路径长度。图12中新生成的路径长度都等于20.44 。在新生成的路径上再一次进行安全性测试以确保避免碰撞。另一种情况，在复杂环境中，五架有四个中间航途