Issue 1
Feb.  2021
Turn off MathJax
Article Contents

HOU Y Q, TAO H, GONG J B, et al. Cooperative path planning of USV and UAV swarms under multiple constraints[J]. Chinese Journal of Ship Research, 2021, 16(1): 74–82 doi:  10.19693/j.issn.1673-3185.02091
Citation: HOU Y Q, TAO H, GONG J B, et al. Cooperative path planning of USV and UAV swarms under multiple constraints[J]. Chinese Journal of Ship Research, 2021, 16(1): 74–82 doi:  10.19693/j.issn.1673-3185.02091

Cooperative path planning of USV and UAV swarms under multiple constraints

doi: 10.19693/j.issn.1673-3185.02091
  • Received Date: 2020-08-28
  • Rev Recd Date: 2020-10-18
  • Available Online: 2021-01-15
  • Publish Date: 2021-02-07
  •   Objectives  For achieving navigational safety and continuous communication link between swarms of unmanned marine vehicle (UMV) during mission execution, the cooperative path planning of unmanned surface vehicle (USV) and unmanned aerial vehicle (UAV) swarms is studied.  Methods  Keep-in and keep-out geo-fences are used to carry out scene modelling, and the problems of threat and obstacle avoidance are transformed into geo-fence constraints. Aiming at collision avoidance and continuous communication link between vehicles, a judgment criterion for the constraints of collision avoidance and communication link via time sequence detection is proposed. The average travel time (ATT) of the swarm is taken as the path optimization function, and the multiple constraints are transformed into penalty functions. A self-adaptive differential evolution algorithm is adopted to solve the optimization problem.  Results  The proposed method can ensure safe navigation and communication link between USV and UAV swarms in hostile and obstacle-filled environment, and achieve the shortest ATT under multiple constraints.  Conclusions  This method has practical value for the off-line path planning of UMV swarms in the hostile and obstacle-filled environment.
  • [1] 张维明, 黄松平, 黄金才, 等. 多域作战及其指挥控制问题探析[J]. 指挥信息系统与技术, 2020, 11(1): 1–6.

    ZHANG W M, HUANG S P, HUANG J C, et al. Analysis on multi-domain operation and its command and control problems[J]. Command Information System and Technology, 2020, 11(1): 1–6 (in Chinese).
    [2] 张卫东, 刘笑成, 韩鹏. 水上无人系统研究进展及其面临的挑战[J]. 自动化学报, 2020, 46(5): 847–857.

    ZHANG W D, LIU X C, HAN P. Progress and challenges of overwater unmanned systems[J]. Acta Automatica Sinica, 2020, 46(5): 847–857 (in Chinese).
    [3] NIU H L, SAVVARIS A, TSOURDOS A, et al. Voronoi-visibility roadmap-based path planning algorithm for unmanned surface vehicles[J]. The Journal of Navigation, 2019, 72(4): 850–874. doi:  10.1017/S0373463318001005
    [4] YANG J M, TSENG C M, TSENG P S. Path planning on satellite images for unmanned surface vehicles[J]. International Journal of Naval Architecture and Ocean Engineering, 2015, 7(1): 87–99. doi:  10.1515/ijnaoe-2015-0007
    [5] 欧阳子路, 王鸿东, 黄一, 等. 基于改进RRT算法的无人艇编队路径规划技术[J]. 中国舰船研究, 2020, 15(3): 18–24.

    OUYANG Z L, WANG H D, HUANG Y, et al. Path planning technologies for USV formation based on improved RRT[J]. Chinese Journal of Ship Research, 2020, 15(3): 18–24 (in Chinese).
    [6] ZHOU X Y, WU P, ZHANG H F, et al. Learn to navigate: cooperative path planning for unmanned surface vehicles using deep reinforcement learning[J]. IEEE Access, 2019, 7: 165262–165278. doi:  10.1109/ACCESS.2019.2953326
    [7] BABEL L. Coordinated target assignment and UAV path planning with timing constraints[J]. Journal of Intelligent & Robotic Systems, 2019, 94(3/4): 857–869.
    [8] WU Y. Coordinated path planning for an unmanned aerial-aquatic vehicle (UAAV) and an autonomous underwater vehicle (AUV) in an underwater target strike mission[J]. Ocean Engineering, 2019, 182: 162–173. doi:  10.1016/j.oceaneng.2019.04.062
    [9] CHO J, YOON Y. How to assess the capacity of urban airspace: a topological approach using keep-in and keep-out geofence[J]. Transportation Research Part C: Emerging Technologies, 2018, 92: 137–149. doi:  10.1016/j.trc.2018.05.001
    [10] ESRI. ESRI shape file technical description - an ESRI white paper[R]. Redlands, CA, USA: Environmental Systems Research Institute, Inc, 1998.
    [11] HORMANN K, AGATHOS A. The point in polygon problem for arbitrary polygons[J]. Computational Geometry, 2001, 20(3): 131–144. doi:  10.1016/S0925-7721(01)00012-8
    [12] QIN A K, SUGANTHAN P N. Self-adaptive differential evolution algorithm for numerical optimization[C]//2005 IEEE Congress on Evolutionary Computation. Edinburgh, Scotland, UK: IEEE, 2005.
  • 加载中
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures(9)  / Tables(2)

Article Metrics

Article views(25) PDF downloads(19) Cited by()

Proportional views
Related

Cooperative path planning of USV and UAV swarms under multiple constraints

doi: 10.19693/j.issn.1673-3185.02091

Abstract:   Objectives  For achieving navigational safety and continuous communication link between swarms of unmanned marine vehicle (UMV) during mission execution, the cooperative path planning of unmanned surface vehicle (USV) and unmanned aerial vehicle (UAV) swarms is studied.  Methods  Keep-in and keep-out geo-fences are used to carry out scene modelling, and the problems of threat and obstacle avoidance are transformed into geo-fence constraints. Aiming at collision avoidance and continuous communication link between vehicles, a judgment criterion for the constraints of collision avoidance and communication link via time sequence detection is proposed. The average travel time (ATT) of the swarm is taken as the path optimization function, and the multiple constraints are transformed into penalty functions. A self-adaptive differential evolution algorithm is adopted to solve the optimization problem.  Results  The proposed method can ensure safe navigation and communication link between USV and UAV swarms in hostile and obstacle-filled environment, and achieve the shortest ATT under multiple constraints.  Conclusions  This method has practical value for the off-line path planning of UMV swarms in the hostile and obstacle-filled environment.

HOU Y Q, TAO H, GONG J B, et al. Cooperative path planning of USV and UAV swarms under multiple constraints[J]. Chinese Journal of Ship Research, 2021, 16(1): 74–82 doi:  10.19693/j.issn.1673-3185.02091
Citation: HOU Y Q, TAO H, GONG J B, et al. Cooperative path planning of USV and UAV swarms under multiple constraints[J]. Chinese Journal of Ship Research, 2021, 16(1): 74–82 doi:  10.19693/j.issn.1673-3185.02091
    • 自美军2011年提出空海一体战以来,随着多域战、多域作战等作战概念的递进演变,当前作战环境已不再局限于单一作战域,而是逐步向跨域协同、多域融合过渡[1]。在多域作战思想的引领下,结合无人作战的广阔前景,海上无人集群作战这一新兴作战概念应运而生。目前,海上无人集群在任务规划、航迹规划、环境感知和编队协同等方面的研究尚处于起步阶段,仍面临着诸多挑战[2]

      海上无人集群由无人艇(USV)和无人机(UAV)集群组成,综合考虑无人艇和无人机跨域特点的协同航迹规划是其中一项重要的关键技术。目前,大部分文献都是针对USV或UAV的航迹规划问题展开的研究。Niu等[3]结合Voronoi图和可视图的优点,采用Dijkstra搜索算法求解了USV最短路径规划问题,在相同计算效率下能够得到比传统Voronoi图方法更短的航行路径,但缺点是不能对具有非零区域的威胁区建模。Yang等[4]将卫星热图像转换为二值图像,为航迹规划提供了环境信息,并在考虑USV的转弯性能和环境约束的基础上,采用有限角度A*算法求解了USV的最短无碰撞路径。该方法的平均求解时间约为0.05 s,可作为实时航迹规划算法,但卫星图像的实时准确性难以保证。在USV编队航迹规划方面,欧阳子路等[5]基于改进快速搜索随机数算法进行USV编队路径规划,提出了一种非严格保形修正向量,能够在避开障碍物的情况下最大程度地保持队形稳定。Zhou等[6]基于深度强化学习方法为USV编队规划了可靠的避障路径,通过设计2个奖励函数,对保持固定编队形状和灵活变化编队形状这2种行为予以了训练学习,在障碍物杂乱的环境中,该方法的效果较好。相对USV,针对多UAV航迹规划问题的研究起步则相对较早,目前,最新的研究主要集中在UAV之间的协同上,例如,设计同时到达的航迹来提升协同攻击效果。Babel[7]针对多UAV攻击多目标的航迹规划问题,提出了基于最短路径的同时到达优先算法,在考虑威胁和障碍的情况下,能够为多架UAV规划满足时间约束的航迹。而在考虑跨域特点的协同航迹规划问题方面,相关研究则相对较少,Wu[8]针对无人潜航器和水空两栖无人机协同攻击目标航迹规划问题,对不同介质中的约束条件和优化指标进行建模,提出了水面搜索和水下攻击两阶段协同航迹规划方法,通过采用粒子群优化算法进行求解,实现了跨域协同攻击的效果。

      由上述文献研究情况看,现有方法主要集中在解决同构平台的航迹规划方面,较少考虑跨域异构平台之间的耦合约束条件。USV和UAV集群协同航迹规划问题中需要考虑的耦合约束包括通信保持和到达时间约束。由于USV与岸端指挥中心的直接通信距离和UAV相比较短,所以通常需要通过UAV来进行通信中继,以扩大其作战半径。因此,在USV与UAV协同航行的过程中,需要始终保持通信距离约束。此外,为了确保跨域集群到达作战区域时的整体协同性,USV与UAV的到达时间约束也需要重点考虑。

      本文拟针对USV和UAV集群的协同航迹规划问题,在考虑威胁规避、机动特性和碰撞冲突约束的基础上,基于USV和UAV跨域通信的需求,进一步考虑通信保持约束,以使USV和UAV集群在航行过程中能够始终保持通信连接。然后,设计航迹优化函数,将多约束条件转化为惩罚函数,并且采用自适应差分进化算法对优化问题进行求解。

    • 在执行任务的初始阶段,USV集群从岸端指定水域出航,UAV集群则从指定起降场起飞,经过一段路径的机动航行后,安全到达各自的任务区域执行后续的巡逻、搜索、侦察、定位、跟踪和攻击等作战任务。所谓的USV/UAV集群协同航迹规划问题,是指以USV/UAV平台初始位置为起点,以指定任务区域的进入点为终点,在综合考虑威胁规避、机动特性、碰撞冲突、通信连接、到达时间等因素的基础上,形成航迹性能达到最优的集群航行路径,从而使集群平台能够安全、快速地到达任务区域。图1所示为USV和UAV集群协同航迹规划示意图。

      Figure 1.  Diagram of cooperative path planning for USV and UAV swarms

      在协同航迹规划问题中,路径起点和终点的位置已知,可通过在起点和终点之间插入有限个中间点的方式生成一段航行路径。设USV和UAV的数量分别为${N_{\rm{S}}}$${N_{\rm{A}}}$,平台总数量$N{\rm{ = }}{N_{\rm{S}}} + {N_{\rm{A}}}$,按照USV和UAV的顺序依次编号为$1,2, \cdots ,N$。对于USV/UAV集群中编号为$i$的平台${U_i}( i = 1,2, \cdots ,N )$,给定起点${{p}}_0^{(i)}$和终点${{p}}_{\rm{f}}^{(i)}$,综合考虑威胁信息和多种约束条件,通过优化技术求解得跨域集群中所有平台的最优航迹集合${{{P}}^*}$

      $$ \begin{split} & \qquad{{{P}}^*}{\rm{ = }}\left\{ {{{P}}_1^{},{{P}}_2^{}, \cdots ,{{P}}_N^{}} \right\} \\& {{P}}_i^{}{\rm{ = }}\left( {{{p}}_0^{(i)},{{p}}_1^{(i)},{{p}}_2^{(i)}, \cdots ,{{p}}_{{n_i}}^{(i)},{{p}}_{\rm{f}}^{(i)}} \right) \end{split}$$ (1)

      式中:${{p}}_j^{(i)}$为路径点坐标,表示平台${U_i}$的第$j$个路径点;${n_i}$为除起点和终点外的中间路径点数量,不同航迹的路径点数量不一定相同,可根据需要进行设置。解决USV/UAV集群协同航迹规划问题需要对场景和约束条件进行适当的建模,构建符合现实需求的航迹优化函数,然后借助优化技术求解跨域无人集群的最优航迹集合${{{P}}^*}$

    • USV/UAV集群的运动空间为海域和空域,其不仅需要将平台的运动空间限制在海域和空域的指定边界内,还要考虑规避其中存在的威胁和障碍。针对场景建模问题,需要建立统一的模型来描述环境空间,这是后续进行协同航迹规划的基础。

      空域建模采用多边形和圆形电子地理围栏[9]来描述空域的边界和威胁信息。空域边界为空中禁出地理围栏,用于限定UAV在指定的空域范围内航行,确保UAV在执行任务过程中的安全。由于敌方威胁、恶劣天气等原因,空中还存在着禁止UAV飞入的禁飞区,即空中禁入地理围栏。为减少油耗,UAV在前往任务区域的过程中应避免高度机动,故通常采用平飞方式。本文假设UAV在同一高度层飞行,将空域简化为指定高度的多边形和圆形区域。首先,定义一个多边形地理围栏,包含的属性和参数为:

      $${{B}}{\rm{ = }}\left\{ {\kappa ,h,m,\left( {{{{p}}_1},{{{p}}_2}, \cdots ,{{{p}}_m}} \right)} \right\}$$ (2)

      式中:$\kappa $为地理围栏属性,当$\kappa {\rm{ = }}1$时为禁出地理围栏,当$\kappa {\rm{ = 0}}$时为禁入地理围栏;$h$为地理围栏高度;$m \geqslant 3$,为多边形顶点个数;${{{p}}_i}$i=1,2,··· ,m)为地理围栏顶点坐标。顶点坐标的排列通常为顺时针或逆时针方向,且根据需要具体确定。针对圆形区域,与式(2)的定义方式类似,其主要参数为圆心坐标和半径,顶点个数定义为$m{\rm{ = }}1$。空域${{{E}}_{\rm{A}}}$是由一个空中禁出地理围栏和多个空中禁入地理围栏共同组成的区域:

      $${{{E}}_{\rm{A}}}{\rm{ = }}\left\{ {{{{B}}_{{\rm{A}}0}},{{{B}}_{{\rm{A}}1}},{{{B}}_{{\rm{A}}2}}, \cdots } \right\}$$ (3)

      式中:${{{B}}_{{\rm{A}}0}}$为空中禁出地理围栏;${{{B}}_{{\rm{A}}1}},{{{B}}_{{\rm{A}}2}}, \cdots $,为空中禁入地理围栏。在实际应用中,地理围栏是对任务区边界、威胁区、障碍物等的统一表示,在设定地理围栏时,要对区域进行缩放,留出一定的冗余区域,用以确保航行安全。

      海域通常依托电子海图[10]进行建模。常见的ShapeFile格式电子海图包含了30多个图层,有一些对任务用途不大的图层信息可无需考虑,只需要分析处理对任务、导航和控制有用的图层,包括海洋/陆地、障碍物、航道、区域界线、地貌等图层即可。二维海图是采用多边形来拟合海岸线、岛屿、半岛和滩涂的形状,相当于用多条相连的线段拟合边缘不规则的平面图形,这种处理与空域的建模方式相同。海岸线为海面禁出地理围栏,岛屿、半岛和通信浮标等威胁及障碍物则为海面禁入地理围栏。因此,海域${{{E}}_{\rm{S}}}$也是由一个海面禁出地理围栏和多个海面禁入地理围栏共同组成的区域:

      $${{{E}}_{\rm{S}}}{\rm{ = }}\left\{ {{{{B}}_{{\rm{S}}0}},{{{B}}_{{\rm{S}}1}},{{{B}}_{{\rm{S}}2}}, \cdots } \right\}$$ (4)

      式中:${{{B}}_{{\rm{S}}0}}$为海面禁出地理围栏;${{{B}}_{{\rm{S}}1}},{{{B}}_{{\rm{S}}2}}, \cdots $,为海面禁入地理围栏。

      电子海图中的集合轮廓信息十分准确,一个岛屿一般由上百条边构成,一条海岸线则多达几千甚至是上万条边。这些庞大的图形信息需要消耗大量的计算资源,会导致算法效率大大降低,且精确的海岸线和岛屿轮廓信息对航迹规划的意义并不大。因此,在实际应用时需要对电子海图进行预处理,对海岸线和岛屿边界进行粗粒度简化处理,尽可能生成边数少、几何关系简单的场景模型。

    • 本节将以集群航行时间为指标建立航迹优化函数,并考虑地理围栏、转弯机动、碰撞冲突、通信连接等多种约束条件,以将协同航迹规划问题转化为带约束的优化问题。鉴于自适应差分进化(self-adaptive differential evolution,SaDE)算法在求解高维非线性优化问题上的优势,采用SaDE算法对优化问题进行求解。

    • 航迹规划的主要目的是使跨域集群能够安全、快速地到达指定区域,评价航迹性能优劣的指标通常有航行距离、航行时间、航迹平滑度等。在航行距离方面,由于各平台的航行速度不同,故对航行距离进行优化不适用于性能有差异的异构平台。相比之下,航行时间的优化则更加符合航迹规划的目的,其优化的目标更加明确、具体。在航迹平滑度方面,从安全航行的角度来看,航迹的平滑程度只需满足平台转弯约束即可。航迹平滑度越好,平台转弯角度越小,航行时间越短,这与航行时间的优化目标是一致的。因此,选取航行时间这一优化指标即可满足航迹规划中快速到达指定区域的要求,而航行安全则通过设计约束条件来实现。本文从任务时效性需求出发,考虑到跨域无人集群的整体协同性,将选取集群平均航行时间为优化目标。平台${U_i}$的航行路径长度为相邻路径点的距离之和,用$D\left( {{{{P}}_i}} \right)$表示:

      $$D\left( {{{{P}}_i}} \right){\rm{ = }}\sum\limits_{j = 0}^{{n_i}} {\left\| {{{p}}_j^{(i)}{{p}}_{j + 1}^{(i)}} \right\|} $$ (5)

      式中,$\left\| \cdot \right\|$为向量的欧氏范数。平台${U_i}$的航行时间用$T\left( {{{{P}}_i}} \right)$表示:

      $$T\left( {{{{P}}_i}} \right) = \frac{{D\left( {{{{P}}_i}} \right)}}{{{v_i}}}$$ (6)

      式中,${v_i}$为平台${U_i}$的航行速度大小。为确保证跨域无人集群系统的整体协同性,提高执行后续任务的连贯性,通常需要各平台在尽可能短的时间内到达。因此,以平均航行时间为优化目标:

      $$J\left( {{P}} \right) = \frac{1}{N}\sum\limits_{i = 1}^N {T\left( {{{{P}}_i}} \right)} $$ (7)

      式中,${{P}}{\rm{ = }}\left( {{{P}}_1^{},{{P}}_2^{}, \cdots ,{{P}}_N^{}} \right)$,为所有航迹的集合。$J\left( {{P}} \right)$越小,则集群平均航行时间越短。

    • 在跨域协同航迹规划中,需要综合考虑的因素包括任务区域的威胁/障碍物分布、无人平台机动特性、集群各平台之间的避碰冲突以及通信保持。上述约束条件是影响航行安全的重要因素,必须将其作为航迹规划的硬性条件。本节将上述约束条件模型化为地理围栏约束、转弯机动约束、碰撞冲突约束和通信保持约束。

    • 在执行任务过程中,各平台要始终保持在禁出地理围栏之内安全航行,同时,也要防止进入禁入地理围栏。针对圆形地理围栏,只需判断点与圆心的距离即可得到平台与地理围栏的位置关系。针对多边形地理围栏,可以采用现有的经典几何方法来判断平台${U_i}$的航迹${{{P}}_i}$与地理围栏之间的关系[11]。这里不再赘述判断方法,只予以简单叙述。

      对于禁入地理围栏${{B}}$,由于给定的起点${{p}}_0^{(i)}$和终点${{p}}_{\rm{f}}^{(i)}$一定不在${{B}}$内,只要航迹${{{P}}_i}$的所有航段${{p}}_k^{(i)}{{p}}_{k + 1}^{(i)}\left( {k = 0,1,2, \cdots {n_i}} \right)$均不与地理围栏${{B}}$相交,则航迹${{{P}}_i}$不与${{B}}$相交,记为$\left( {{{{P}}_i}\; {\rm{out}} \left\{ {{{{B}}_1},{{{B}}_2}, \cdots } \right\}} \right)$。若要判断航段${{p}}_k^{(i)}{{p}}_{k + 1}^{(i)}$是否与${{B}}$相交,只需逐一判断${{B}}$的各条边与${{p}}_k^{(i)}{{p}}_{k + 1}^{(i)}$的相交关系即可。

      对于凸多边形禁出地理围栏${{{B}}_0}$,由于起点${{p}}_0^{(i)}$和终点${{p}}_{\rm{f}}^{(i)}$一定位于${{{B}}_0}$内,只要航迹${{{P}}_i}$的所有中间路径点${{p}}_k^{(i)}\left( {k = 1,2, \cdots {n_i}} \right)$均位于${{{B}}_0}$内,则航迹${{{P}}_i}$位于${{{B}}_0}$内,记为$\left( {{{{P}}_i}\; {\rm{in}}\; {{{B}}_0}} \right)$。采用射线法计算相交点的个数即可判断路径点${{p}}_k^{(i)}$是否位于${{{B}}_0}$内,这里不再详述。对于凹多边形禁出地理围栏${{{B}}_0}$,上述方法不再适用,需要增加一个判断条件:航迹${{{P}}_i}$的所有航段${{p}}_k^{(i)}{{p}}_{k + 1}^{(i)}$均不与禁出地理围栏${{{B}}_0}$相交。

      以USV的一段航迹${{{P}}_i}$为例,对于海域${{{E}}_{\rm{S}}}{\rm{ = }} \left\{ {{{{B}}_{{\rm{S}}0}},{{{B}}_{{\rm{S}}1}},{{{B}}_{{\rm{S}}2}}, \cdots } \right\}$,地理围栏约束${S_1}\left( {{{{P}}_i}} \right)$可以表示为

      $${S_1}\left( {{{{P}}_i}} \right) \!\!=\!\! \left\{\!\!\!\! {\begin{array}{*{20}{l}} {1,}&{{\rm{if}}\; \left( {{{{P}}_i}\; {\rm{in}}\; {{{B}}_{{\rm{S}}0}}} \right) {\rm{\& }} \left( {{{{P}}_i}\; {\rm{out}} \left\{ {{{{B}}_{{\rm{S}}1}},{{{B}}_{{\rm{S}}2}}, \cdots } \right\}} \right)} \\ {0,}&{{\rm{else}}} \end{array}} \right.$$ (8)

      当且仅当航迹${{{P}}_i}$位于禁出地理围栏${{{B}}_{{\rm{S}}0}}$内,并与禁入地理围栏$ \left\{ {{{{B}}_{{\rm{S}}1}},{{{B}}_{{\rm{S}}2}}, \cdots } \right\}$不相交时,满足地理围栏约束,${S_1}\left( {{{{P}}_i}} \right) = 1$;否则,不满足地理围栏约束,${S_1}\left( {{{{P}}_i}} \right) = 0$

    • 在进行航迹规划时,需要考虑平台转弯机动约束,生成满足平台机动特性的可行航迹。若相邻3个路径点之间的距离较近,且航段之间的夹角较小,则完成转弯的半径可能会小于平台的最小转弯半径。可见,转弯半径约束限制了相邻3个路径点的相对位置关系。下面,给出转弯半径约束的判断准则,对于3个相邻的路径点${{p}}_{k - 1}^{(i)}$${{p}}_k^{(i)}$${{p}}_{k + 1}^{(i)}$,将3个点相连形成折线段,其最大内切圆如图2所示。

      Figure 2.  Diagram of maximum inscribed circle during turning

      两段路径之间的夹角$\alpha $

      $$\alpha {\rm{ = }}\arccos \frac{{{{\left\| {{{p}}_{k - 1}^{(i)}{{p}}_k^{(i)}} \right\|}^2} + {{\left\| {{{p}}_k^{(i)}{{p}}_{k + 1}^{(i)}} \right\|}^2} - {{\left\| {{{p}}_{k - 1}^{(i)}{{p}}_{k + 1}^{(i)}} \right\|}^2}}}{{2\left\| {{{p}}_{k - 1}^{(i)}{{p}}_k^{(i)}} \right\| \cdot \left\| {{{p}}_k^{(i)}{{p}}_{k + 1}^{(i)}} \right\|}}$$ (9)

      两段路径中长度较短一段路径的长度$\ell $

      $$\ell {\rm{ = min}}\left\{ {\left\| {{{p}}_{k - 1}^{(i)}{{p}}_k^{(i)}} \right\|,\left\| {{{p}}_k^{(i)}{{p}}_{k + 1}^{(i)}} \right\|} \right\}$$ (10)

      最大内切圆的半径$\rho $

      $$\rho \left( {{{p}}_{k - 1}^{(i)},{{p}}_k^{(i)},{{p}}_{k + 1}^{(i)}} \right){\rm{ = }}\ell \tan \frac{\alpha }{2}$$ (11)

      最大内切圆半径即极限转弯半径,若平台最小转弯半径大于该极限,则无法顺利完成转弯。假设平台的最小转弯半径为${R_{\rm{t}}}$,转弯约束可以表示为

      $${S_2}\left( {{{p}}_{k - 1}^{(i)},{{p}}_k^{(i)},{{p}}_{k + 1}^{(i)}} \right) = \left\{ {\begin{array}{*{20}{c}} {1,}&{\rho \geqslant {R_{\rm{t}}}} \\ {0,}&{\rho < {R_{\rm{t}}}} \end{array}} \right.$$ (12)

      当转弯机动约束${S_2}\left( {{{p}}_{k - 1}^{(i)},{{p}}_k^{(i)},{{p}}_{k + 1}^{(i)}} \right){\rm{ = }}1$时,满足转弯半径约束;当${S_2}\left( {{{p}}_{k - 1}^{(i)},{{p}}_k^{(i)},{{p}}_{k + 1}^{(i)}} \right){\rm{ = 0}}$时,不满足转弯半径约束。对于一段完整的航迹${{{P}}_i}$,判断其转弯半径约束需将航迹分解为若干个路径段来考虑,每个路径段都采用上述方法判断。最后,将各段的转弯半径约束求并集,得到整个航迹的转弯半径约束${S_2}\left( {{{{P}}_i}} \right)$

      $${S_2}\left( {{{{P}}_i}} \right) = \prod\limits_{j = 1}^{{n_i}} {{S_2}\left( {{{p}}_{k - 1}^{(i)},{{p}}_k^{(i)},{{p}}_{k + 1}^{(i)}} \right)} $$ (13)

      式中:$\prod {\left( \cdot \right)} $为累乘计算,即只要有一个路径段不满足转弯半径约束,便会使得${S_2}\left( {{{{P}}_i}} \right) = 0$,即整个航迹不满足转弯半径约束。只有当所有路径段都满足转弯半径约束时,才有${S_2}\left( {{{{P}}_i}} \right) = 1$,即整个航迹满足转弯半径约束。

    • USV/UAV集群协同航迹规划问题需要同时考虑空间和时间的跨域协同关系,分别为集群协同关系在空间域和时间域上的体现。通过协调平台出发时间实现时间协同,并在此基础上考虑空间约束关系以进行碰撞冲突约束和通信保持约束的判断。对于协同航路规划问题,多平台之间极有可能发生碰撞冲突。碰撞冲突的研究对象是同构平台,即USV与USV之间以及UAV与UAV之间的碰撞冲突,必须确保同构平台之间的距离始终大于安全半径。但仅从航迹空间关系上无法判断是否存在冲突,需要从时空耦合的角度进行冲突检测。首先,确定时序关系,采用到达时间对齐、调整出发时间的方式来实现集群的同时到达。平台${U_i}$的出发时间${t_i}$

      $${t_i} = - T\left( {{{{P}}_i}} \right) + \mathop {\max }\limits_{i = 1,2, \cdots ,N} T\left( {{{{P}}_i}} \right)$$ (14)

      然后,在时间统一的基础上进行空间冲突约束的判断。以时间间隔$\Delta T$进行离散化,得到一系列碰撞检测时序$k\Delta T\left( {k \geqslant 1} \right)$,其时序关系示意图如图3所示。

      Figure 3.  Time sequence diagram of collision detection

      在碰撞检测时刻点$k\Delta T$,给定平台${U_i}$的运动速度${v_i}$,可以很容易推算得到${U_i}$$k\Delta T$时刻所处的位置,记为${{{P}}_i}[k]$(其中,k为碰撞检测点序号)。对于同构平台${U_i}$${U_j}$,相同序号碰撞检测点之间的相对距离应满足如下约束:

      $$\mathop {\min }\limits_{j \ne i} \left\| {{{{p}}_i}[k]{{{p}}_j}[k]} \right\| \geqslant R_{\rm{S}}^{(i)}{\rm{ + }}R_{\rm{S}}^{(j)}$$ (15)

      式中:$R_{\rm{S}}^{(i)}$$R_{\rm{S}}^{(j)}$分别为平台${U_i}$${U_j}$的防撞安全半径;${{{p}}_i}[k]$${{{p}}_j}[k]$分别为平台${U_i}$${U_j}$序号为k的碰撞检测点坐标。针对各同构平台的航迹,需按照上述方法对碰撞检测点逐一进行检测。当所有时序检测点${{{p}}_i}[k]$均满足碰撞冲突约束时,规划的航迹${{{P}}_i}$不会与其他平台产生碰撞冲突,此时,将碰撞冲突约束记为${S_3}\left( {{{{P}}_i}} \right) = 1$。反之,当${S_3}\left( {{{{P}}_i}} \right) = 0$时,航迹之间存在碰撞冲突。

    • USV/UAV集群协同执行任务的能力是建立在可靠的通信网络上的,保持良好的通信连接是完成任务的前提条件,尤其是在复杂的条件下保持岸端、空中和海上的跨域联合通信。与同构集群不同,UAV集群与USV集群不仅要保持群内通信连接,跨域平台之间也要保持通信连接,即UAV与USV需要保持一定的空间关系以确保通信连接。

      根据平台通信能力的不同,各平台与其他平台的通信距离各不相同。在考虑通信保持的情况下,规划的航迹需要各平台始终保持在通信范围内,从而使整个跨域无人系统保持稳定的通信连接。设${U_i}$${U_j}$之间的通信半径为$R_{\rm{C}}^{(ij)}$,通信保持约束的检测方式与碰撞冲突约束相同,即相同序号检测点之间的距离小于通信半径:

      $$\mathop {\max }\limits_{j \ne i} \left\| {{{{p}}_i}[k]{{{p}}_j}[k]} \right\| \leqslant R_{\rm{C}}^{(ij)}$$ (16)

      通常,无人集群在海上执行任务时,需要部分关键节点之间保持通信,但不一定需要所有的节点都保持通信约束。若${U_i}$${U_j}$之间不需要保持通信连接,则令其通信半径$R_{\rm{C}}^{(ij)}{\rm{ = }}\infty $即可。当所有检测点之间的距离都满足通信保持约束时,整个异构无人集群便能保证稳定的通信连接。令通信约束为${S_4}\left( {{{{P}}_i}} \right) = 1$,反之,令${S_4}\left( {{{{P}}_i}} \right) = 0$

    • 考虑到上述多约束条件,跨域无人集群协同航迹规划问题可以转化为如下优化问题:

      $$ \begin{split} & \quad\;{{{P}}^*} = \arg \min J\left( {{P}} \right) \\&\qquad {\rm{s}}{\rm{. t}}{\rm{.}}\; {S_j}\left( {{{{P}}_i}} \right) = 1 \\& i = 1, \cdots ,N;\;j = 1, \cdots ,4. \end{split} $$ (17)

      式中,${{{P}}^*}$是使$J\left( {{P}} \right)$取值最小的最优航迹集合。所谓约束条件,是指所有平台的航迹必须同时满足地理围栏约束、转弯机动约束、碰撞冲突约束和通信保持约束。为便于优化求解,将约束条件转化为惩罚函数,得到如下优化问题:

      $${{{P}}^*} = \arg \min \left[ {J\left( {{P}} \right) + M\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^4 {\left( {1 - {S_j}\left( {{{{P}}_i}} \right)} \right)} } } \right]$$ (18)

      式中,$M$为惩罚因子,取值为较大的正数。

      当所有约束条件均满足时,惩罚项取值为0;当所有约束条件均不满足时,惩罚项的惩罚力度最大,取值为$4MN$;当存在部分航迹不满足约束条件时,该项的取值为$M$的整数倍,其取值大小与不满足约束条件的个数有关。上述设计的优势在于,使航迹代价函数保持了一定的梯度,在优化过程中,满足约束条件个数较多的个体更容易被保留,进而逐渐产生符合约束条件的可行解。惩罚因子$M$应尽量大于$J\left( {{P}} \right)$的估算值,以保证惩罚项在寻优过程中的有效性。

      由于平台数量和路径点个数较多,故该优化问题属于高维非线性优化问题。考虑到SaDE算法在求解高维非线性优化问题上的优势[12],这里采用该算法进行求解。差分进化算法是一种基于群体智能理论的随机启发式搜索算法,其通过群体内个体间的合作与竞争进行寻优。同时,该算法特有的记忆能力还使其可以动态跟踪当前的搜索情况,便于调整搜索策略,因此具有较强的鲁棒性和全局寻优能力。采用SaDE算法求解上述航迹规划问题的算法步骤如下。

      步骤1:路径编码。SaDE算法采用的是实数编码形式,一个个体对应一个解,每个个体由若干实数位组成,每一位表示一个变量。首先,给定平台数量和中间路径点个数,确定编码的长度。平台${U_i}$的中间路径点个数为${n_i}$,在给定高度的情况下,中间路径点为二维变量,则平台${U_i}$的中间路径变量个数为$2{n_i}$。编码总长度$D$为UAV和USV路径变量个数的总和:

      $$D{\rm{ = }}2\left( {\sum\limits_{i{\rm{ = }}1}^{{N_{\rm{A}}}} {n_i^{}} + \sum\limits_{j{\rm{ = }}{N_{\rm{A}}} + 1}^{{N_{\rm{A}}} + {N_{\rm{S}}}} {n_j^{}} } \right)$$ (19)

      该公式中的第1项为${N_{\rm{A}}}$架UAV的路径变量总数,第2项为${N_{\rm{S}}}$艘USV的路径变量总数。编码方式如图4所示。

      Figure 4.  Real number coding of SaDE algorithm

      ${{p}}_{{n_i}}^{(i)}$的路径编码为$D$维矢量,随着平台数量和路径点个数的增加,其搜索空间维度不断扩大。当环境复杂程度较高时,需要选择较多的路径点来避开障碍物,这样会增加计算时间;当环境复杂程度较低时,应减少路径点数量,以使规划计算时间较短。

      步骤2:产生初始种群,将进化代数初始化为1。根据地理围栏信息,确定路径点的规划空间,进而确定每个变量的上界和下界。设定种群规模为NP,随机生成NP个满足上、下界约束的初始个体。

      步骤3:计算适应度函数。按照步骤1中的编码方法,逆向操作解码以得到各个平台的航迹信息集合${{P}}$,然后代入航迹代价函数中,计算每个个体的适应度函数值。

      步骤4:进化操作。根据进化代数自适应调整变异算子,对种群进行变异操作和交叉操作,对边界条件进行处理以得到临时种群。对临时种群和原始种群中对应的个体,进行“一对一”的选择操作,选出优胜个体进化为新种群。

      步骤5:终止优化。判断是否满足终止条件或达到最大进化代数,若是,则进化终止,否则,进化代数+1,返回步骤3。

      在协同航迹规划优化过程中,随机生成的初始航迹通常不满足约束条件,在惩罚项的影响下适应度函数值较高。在优化初期,主要是寻找满足约束条件的“可行航迹”,需要设置较大的变异算子,提高种群的多样性,并寻找到尽可能多的“可行航迹”,防止“早熟”现象。而在优化后期,则主要是在“可行航迹”集中寻找最优航迹,需要设置较小的变异算子,提高全局最优解的精度。因此,采用具有自适应变异算子的SaDE算法,自适应变异算子F设计如下:

      $$F{\rm{ = }}{{\rm{2}}^\lambda }{F_0},\;\;\lambda = {{\rm {e}}^{1 - \frac{{{G_{\rm{m}}}}}{{{G_{\rm{m}}} + 1 - G}}}}$$ (20)

      式中:${F_0}$为常数变异算子;${G_{\rm{m}}}$为最大进化代数;$G$为当前进化代数;$\lambda $为随$G$自适应变化的参数。在SaDE算法中,变异算子决定了个体变异的幅值大小,决定了随机变异的精细程度。在进化初期,自适应变异算子为${\rm{2}}{F_0}$,保持了个体的多样性。随着不断的进化,变异算子逐步降低至${F_0}$,以保留优良航迹,提高搜索到全局最优航迹的概率。

    • 为了验证所提协同航迹规划方法的有效性,本文采用1.2节中建立的场景模型,以某湖试验场为任务区域进行模拟仿真验证。空域高度设置为500 m,空中禁出地理围栏为海域上方的矩形空域,并随机设置2个空中禁入地理围栏和3个海面禁入地理围栏。假设UAV在指定区域起飞至指定高度,将完成起飞后的坐标点设为UAV的起点,USV以岸端布放位置为起点。

      仿真中,设置跨域集群平台数量为7,记为${U_1},{U_2}, \cdots ,{U_7}$,其中3架UAV记为${U_1}\sim {U_3}$,4艘USV记为${U_4}\sim {U_7}$,UAV和USV的初始状态信息分别如表1表2所示。各同构平台之间的安全半径均为100 m。UAV之间的最大通信距离为12 km,UAV与USV之间的最大通信距离为10 km,USV之间的最大通信距离为5 km。

      平台坐标/m速度
      /(m·s−1)
      最小转弯
      半径/m
      路径点
      个数
      起点终点
      ${U_1}$(2 923,14 673)(12 976,6 012)20551
      ${U_2}$(1 429,13 945)(12 427,7 843)23752
      ${U_3}$(2 016,12 864)(11 789,5 122)251001

      Table 1.  Initial status information of UAV

      平台坐标/m速度
      /kn
      最小转弯
      半径/m
      路径点
      个数
      起点终点
      ${U_4}$(3 317,4 994)(9 785,8 685)302001
      ${U_5}$(3 170,5 415)(9 035,8 247)251402
      ${U_6}$(2 822,6 020)(11 330,11 900)302001
      ${U_7}$(2 794,7 129)(10 340,7 781)353002

      Table 2.  Initial status information of USV

      根据平台数量及其中间路径点个数,可以得到SaDE算法实数编码变量长度为20。在SaDE算法中,设置种群中个体数量为${\rm{2}}00$,最大进化代数为$500$,常数变异因子${F_0} = 0.3$,交叉因子为$0.1$。其他参数取值为:惩罚因子$M{\rm{ = }}{10^3}$,离散时间间隔$\Delta T = 5\;{\rm{s}}$。仿真结果如图5图9所示。

      图5示出了仿真场景下空中和海面禁入、禁出地理围栏,并给出了USV/UAV集群的航迹规划结果。UAV在高度为500 m的空域中运动,USV在海面上航行,航迹起点均位于靠近左侧岸端的位置,航迹终点分布于右侧远端的任务区域。图5中,黑色虚线为空中和海面禁出地理围栏,所有航迹均保持在禁出地理围栏以内;红色和蓝色实线分别为空中、海面禁入地理围栏,为尽可能节省航行时间,部分航迹与禁入地理围栏距离较近,甚至出现了与地理围栏几乎“相切”的现象。这不会影响到航行的安全性,因为在设计地理围栏时已留有一定的冗余距离。仿真结果验证了前文所设计地理围栏约束的有效性。

      Figure 5.  Results of path planning of USV and UAV swarms

      航迹优化函数随迭代次数的变化曲线如图6所示。在优化初期,由于惩罚函数的作用,函数值较高,此时产生的解均不满足约束条件。从第1代迭代至第100代,主要是寻找符合约束条件的可行解,此时函数值逐渐降低至1 000以下,所产生的解满足约束条件,验证了前文设计的惩罚函数的合理性。从100代以后,主要是寻找使优化函数值最小的解,最后到第500代时适应度函数值收敛至565.8,也即USV/UAV集群的平均航行时间为568.5 s。

      Figure 6.  Optimization process of path optimization function

      图7示出了USV/UAV集群平台的航行时序关系。图中,横轴为航行时间,纵轴为平台编号,圆圈为平台出发时间,方格为平台到达时间。以航行时间最长的平台${U_1}$的出发时间为基准,平台${U_2}\sim {U_7}$的出发时间分别为101,150.7,175.5,154.2,7.3,244.7 s。

      Figure 7.  Navigation sequence diagram of USV/UAV swarms

      为了验证碰撞冲突约束和通信保持约束的有效性,图8~图9给出了USV/UAV集群平台间的实时距离变化情况。本节设定的安全半径均为100 m,因此安全距离为200 m。由图中可以看到,平台间的距离始终大于安全距离,验证了碰撞冲突约束的有效性。

      图9给出了3组平台间的最大距离及其上限值,其中实线为平台间的实时最大距离,虚线为最大通信距离。从图中可以看到,所有平台的实时距离均小于最大通信距离,保证了USV/UAV集群的通信连接,验证了前文所提通信保持约束的有效性。

      Figure 8.  Variation curves of minimum distance between platforms with time

      Figure 9.  Variation curves of maximum distance between platforms with time

    • 本文提出了基于自适应差分进化算法的USV和UAV集群协同航迹规划方法,实现了多约束条件下的协同航迹规划,并能够在障碍环境中实现集群安全航行和通信保持,具有一定的应用价值。通过地理围栏和时序检测方法,将障碍规避、平台防撞和通信保持问题建模为多个约束条件,并通过罚函数法将航迹规划问题转化为了无约束的优化问题。采用SaDE算法进行了优化求解,其优势在于能够保持搜索初期的多样性和后期的精确性,保证最优航迹的求解,但随着路径点个数的增加,求解时间会不断增大。受求解时效性的限制,所提方法只能应用于离线航迹规划,后续将针对实时在线规划展开更深入的研究。

Reference (12)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return