·210· 智能系统学报 第15卷 携带的燃料、无人机所允许的飞行速度和飞行时间。 少无人机在执行任务阶段因链路中断，导致规划 3)可飞性约束。现有算法规划出的路径多是 失败。 由直线组成，而在实际的飞行中直线交叉位置很 1.2.2多无人机路径规划的分类标准 难保证路径的可行性。Dubinsts6-s8)路径、二维 根据规划空间的特性可分为二维路径规划和 Clothoid、PH曲线S9-6o和Metropolisriterion可 三维路径规划；根据规划的时间特性分为预先静 用于平滑处理无人机的飞行路径。在用Dubins 态路径规划和实时动态路径规划：根据规划对象 曲线平滑处理路径时，由于Dubin曲率的不变性， 的数量分为单机路径规划和多机协同路径规划。 可将Dubins曲线结合Clothoid或PH曲线来优化 预先静态路径规划是指无人机起飞前，已知威胁 路径。 和目标位置等信息，所规划出的路径精度高，但 4)威胁约束。无人机路径规划面临的威胁主 实时性差。实时动态路径规划，重在“实时性” 要有地形威胁、环境威胁和敌方威胁，根据威胁 在规划中遇到威胁时，无人机能够实时调整路 的强度和覆盖范围将其分为点威胁和区域威胁。 线，重新规划出满足新的约束条件的路径。 点威胁指无人机仅受某单一威胁源影响。区域威 1.2.3多无人机路径规划的基本方法 胁指由多个威胁源组成的扇状威胁域。威胁的大 近年来关于无人机路径规划的研究已有很 小和强度将直接影响规划中无人机的路径选择、 多，这里将求解路径规划的方法分为数学规划方 载荷约束和武器的使用。 法、人工势场法6、基于图形学的方法和智能优 5)时限性约束。无人机路径规划的时限性主 化算法4种。 要指无人机系统的时间约束、空间约束和顺序约 1)数学规划方法。数学规划方法有动态规划 束。时间约束是指在执行飞行任务时，根据执行 算法和非线性规划算法。其中，非线性规划方法 任务的优先级和无人机自身机动性能约束，规划 于1939年首次被提出后，主要用于求解非线性目 出无人机飞行时间的先后顺序；空间约束保证了 标函数或约束条件中含有非线性约束的问题。非 每架无人机的飞行路径无交叉碰撞。顺序约束是 线性规划问题又可分为有约束的非线性规划问题 指规划出无人机飞行的先后顺序。时间约束、空 和无约束的非线性规划问题。 间约束和顺序约束是密不可分的，可通过时间调 2)人工势场法。美国斯坦福大学教授Ous 配避开空间规划和顺序规划的冲突，也可以通过 sama Khatib于20世纪80年代首次提出了人工势 空间调配避免时间规划和顺序规划上的冲突等。 场法26，该算法主要是在无人机任务规划空间 6)优先级约束。无人机任务规划中，为了便 中虚拟出指向目标的引力和远离障碍物的斥力 于任务分配和避免无人机在飞行中发生碰撞等， 从而组成人工力场。人工势场法多用于求解局部 由不同的规划系统和平台，给出机上编号、任务 最优问题，其模型简单、计算量小、实时性好、效 的重要度、目标的重要度和规划路径的长短等优 率高、导向性强且易实现。 先级评价指标，现给出以下约定。 3)基于图形学的方法。基于图形学的路径规 ①在任务规划中任务急迫解决的程度越高， 划方法有拓扑法6、Dijkstra路径搜索算法、模拟 优先级越高； 退火算法、栅格法I66、A'算法、Voronoi图法和随 ②在任务规划中任务的重要程度越高，优先 机路标图PRM)法等。 级就越高； Dijkstra路径搜索算法6)于1959年由荷兰科 ③在任务规划中，当遇到地形、环境威胁和 学家Dijkstra提出，用于扫描搜索从初始位置到 碰撞威胁时，优先解决使目标函数最优的无人机 目标位置的最短路径。该算法简单易行，多用于 路线和相应的任务分配 规模较小的网络。 能量约束。考虑到无人机在执行任务阶段 栅格法s8-69于1968年由W.E.Howden首次 可能出现因能量不足而导致规划失败的问题，规 提出，并应用在路径规划中。为了便于计算机处 划中安排携带能量少的无人机执行路径较短、级 理，将连续空间离散化为网格单元，然后采用启 别较轻的任务，携带能量较多的无人机执行级别 发式算法在网格单元中搜索最优路径。栅格化的 较高、路径较长的任务。 网格大小将直接影响算法的性能。在路径规划 8)载荷和链路约束。为每架无人机实现“量 中，蚁群算法、遗传算法6刀和神经网络算法都会 力而行”，即根据不同无人机执行任务的类型和功 对任务区域做栅格化处理。 能不同，为不同无人机分配适宜的任务载荷，减 模拟退火算法(simulated annealing,.SA)受启携带的燃料、无人机所允许的飞行速度和飞行时间。 3) 可飞性约束。现有算法规划出的路径多是 由直线组成，而在实际的飞行中直线交叉位置很 难保证路径的可行性。Dubins[56-58] 路径、二维 Clothoid、PH 曲线 [59-60] 和 Metropolis criterion[46] 可 用于平滑处理无人机的飞行路径。在用 Dubins 曲线平滑处理路径时，由于 Dubin 曲率的不变性， 可将 Dubins 曲线结合 Clothoid 或 PH 曲线来优化 路径[4]。 4) 威胁约束。无人机路径规划面临的威胁主 要有地形威胁、环境威胁和敌方威胁，根据威胁 的强度和覆盖范围将其分为点威胁和区域威胁。 点威胁指无人机仅受某单一威胁源影响。区域威 胁指由多个威胁源组成的扇状威胁域。威胁的大 小和强度将直接影响规划中无人机的路径选择、 载荷约束和武器的使用。 5) 时限性约束。无人机路径规划的时限性主 要指无人机系统的时间约束、空间约束和顺序约 束。时间约束是指在执行飞行任务时，根据执行 任务的优先级和无人机自身机动性能约束，规划 出无人机飞行时间的先后顺序；空间约束保证了 每架无人机的飞行路径无交叉碰撞。顺序约束是 指规划出无人机飞行的先后顺序。时间约束、空 间约束和顺序约束是密不可分的，可通过时间调 配避开空间规划和顺序规划的冲突，也可以通过 空间调配避免时间规划和顺序规划上的冲突等。 6) 优先级约束。无人机任务规划中，为了便 于任务分配和避免无人机在飞行中发生碰撞等， 由不同的规划系统和平台，给出机上编号、任务 的重要度、目标的重要度和规划路径的长短等优 先级评价指标，现给出以下约定。 ①在任务规划中任务急迫解决的程度越高， 优先级越高； ②在任务规划中任务的重要程度越高，优先 级就越高； ③在任务规划中，当遇到地形、环境威胁和 碰撞威胁时，优先解决使目标函数最优的无人机 路线和相应的任务分配 7) 能量约束。考虑到无人机在执行任务阶段 可能出现因能量不足而导致规划失败的问题，规 划中安排携带能量少的无人机执行路径较短、级 别较轻的任务，携带能量较多的无人机执行级别 较高、路径较长的任务。 8) 载荷和链路约束。为每架无人机实现“量 力而行”，即根据不同无人机执行任务的类型和功 能不同，为不同无人机分配适宜的任务载荷，减 少无人机在执行任务阶段因链路中断，导致规划 失败。 1.2.2 多无人机路径规划的分类标准 根据规划空间的特性可分为二维路径规划和 三维路径规划；根据规划的时间特性分为预先静 态路径规划和实时动态路径规划；根据规划对象 的数量分为单机路径规划和多机协同路径规划。 预先静态路径规划是指无人机起飞前，已知威胁 和目标位置等信息，所规划出的路径精度高，但 实时性差。实时动态路径规划，重在“实时性”， 在规划中遇到威胁时，无人机能够实时调整路 线，重新规划出满足新的约束条件的路径。 1.2.3 多无人机路径规划的基本方法 近年来关于无人机路径规划的研究已有很 多，这里将求解路径规划的方法分为数学规划方 法、人工势场法[61] 、基于图形学的方法和智能优 化算法 4 种。 1) 数学规划方法。数学规划方法有动态规划 算法和非线性规划算法。其中，非线性规划方法 于 1939 年首次被提出后，主要用于求解非线性目 标函数或约束条件中含有非线性约束的问题。非 线性规划问题又可分为有约束的非线性规划问题 和无约束的非线性规划问题。 2) 人工势场法。美国斯坦福大学教授 Ous￾sama Khatib 于 20 世纪 80 年代首次提出了人工势 场法[62-64] ，该算法主要是在无人机任务规划空间 中虚拟出指向目标的引力和远离障碍物的斥力， 从而组成人工力场。人工势场法多用于求解局部 最优问题，其模型简单、计算量小、实时性好、效 率高、导向性强且易实现。 3) 基于图形学的方法。基于图形学的路径规 划方法有拓扑法[65] 、Dijkstra 路径搜索算法、模拟 退火算法、栅格法 [66] 、A *算法、Voronoi 图法和随 机路标图 (PRM)法等。 Dijkstra 路径搜索算法[67] 于 1959 年由荷兰科 学家 Dijkstra 提出，用于扫描搜索从初始位置到 目标位置的最短路径。该算法简单易行，多用于 规模较小的网络。 栅格法[68-69] 于 1968 年由 W. E. Howden 首次 提出，并应用在路径规划中。为了便于计算机处 理，将连续空间离散化为网格单元，然后采用启 发式算法在网格单元中搜索最优路径。栅格化的 网格大小将直接影响算法的性能。在路径规划 中，蚁群算法、遗传算法[67] 和神经网络算法都会 对任务区域做栅格化处理。 模拟退火算法 (simulated annealing，SA) 受启 ·210· 智 能 系 统 学 报 第 15 卷