浅析几种无人机安全通道生成方法

安全通道是什么呢？安全通道是指在无人机轨迹生成时，为了避免碰撞而设定的无人机可以飞行的通道。它连通了起点与终点，并且在安全通道内生成的任意轨迹都是安全无碰撞的。安全通道是轨迹生成中用于避免碰撞的重要技术，关于安全通道的生成目前已经有了许多的方法。一般来说，安全通道都是用多个连通在一起的多面体进行表示。这样安全通道的生成问题，可以转化为多个多面体生成。下面针对几种较为常见的安全通道的生成方法进行介绍。

1. 半定规划的迭代区域膨胀[1]

为了获取多面体，这个方法首先构造一个初始椭球，由一个以选定点为中心的单位球组成。然后，遍历障碍物，为每个障碍物生成一个超平面，该超平面与障碍物相切并将其与椭球分开。再次，这些超平面定义了一组线性约束，它们的交集是一个多面体。然后，可以在那个多面体中找到一个最大的椭球，使用这个椭球来定义一组新的分离超平面，从而定义一个新的多面体。选择生成分离超平面的方法，这样椭圆体的体积在迭代之间永远不会减少。可以重复这个过程，直到椭圆体的增长率低于某个阈值，此时我们返回多面体和内接椭圆体。这个方法具有迭代的思想，并且具有收敛判断的标准，算法的收敛快慢和初始椭球具有很大的关系。

2. 基于凸分解的安全通道生成[2]

基于凸分解的安全通道生成方法由四个步骤完成安全通道的生成，分别为：找到椭球、找到多面体、边界框、收缩。这四个步骤的具体介绍如下：

1）生成椭球

先形成一个球体，球的半径为两个路径点的距离，然后再进行收缩其中的两个长轴，以保证该椭球为最大椭球，最后再拉伸第三个轴（连接路径点的轴）以保证这个椭球是最大的。椭球的计算是基于路径点进行的，路径点的疏密程度，将会影响椭球的个数，因此在使用时最好能够利用计算的椭球融合其包含的路径点，这样来减少计算路径点的个数。

2）找到多面体

找到多面体。不断扩张椭球直到和障碍物相切，保存切线。重复上面的操作，获得更多的切线，直到当前地图都和其相交为止。这个过程的主要计算量都在障碍物的判断中，因此计算很快。

3）边界框

边界框的作用是分割地图，将附近的local障碍物地图从全局地图中提取出来，也就是获得local障碍物地图。其主要原因是上面的操作不能对整个地图执行，因为那样的计算量太大了，因此可以在路径点附近打上边框，这样就能降低计算量了。边框大小的选择就非常具有经验性质了，最好能够涵盖所需要的信息。

4）收缩

对安全通道进行收缩，收缩的尺度由无人机的尺寸决定，这样的处理可以让无人机变成一个质点。收缩是对生成的多面体进行的，这样的好处是不会造成两个多面体出现不相交的情况。

3. 平行凸簇膨胀方法[3]

上述的两种方法都是从点云地图出发，并且都是基于椭圆完成凸多面体的生成。而平行凸簇膨胀方法，与上面的方法不同，该方法是从栅格地图出发，利用最小凸集生成算法，完成凸多面体的生成。

其算法的思想是首先获得一个凸集，再沿着凸集的表面进行扩张，扩张之后再进行凸集检测，判断新扩张的集合是否保持为凸。一直扩张到不能再扩张为止，再提取凸集的边缘点，利用快速凸集生成算法，生成凸多面体。该算法的好处在于可以利用这种扩张的思路，将安全的多面体的体积尽可能的充满整个空间，因此获得的安全通道更大。但其也具有一定的缺点，就是计算量比较大，计算所需要的时间比较长，为了解决这个问题，在该文章中，又提出了采用GPU加速的方法，来加速计算。

总结    

安全通道的生成虽然是一个比较小的问题，但是因为它直接影响了最终生成轨迹的质量，因此也非常重要。安全通道能够直接转化为优化问题中的凸约束，这种特性应该也可以利用在其他的领域内。

参考资料

[1]R. Deits and R. Tedrake, “Computing large convex regions of obstacle-free space through semidefinite programming,” Springer Tracts Adv. Robot., vol. 107, pp. 109–124, 2015, doi: 10.1007/978-3-319-16595-0_7.

[2]S. Liu et al., “Planning dynamically feasible trajectories for quadrotors using safe flight corridors in 3-D complex environments,” IEEE Robot. Autom. Lett., vol. 2, no. 3, pp. 1688–1695, 2017, doi: 10.1109/LRA.2017.2663526.

[3]F. Gao, L. Wang, B. Zhou, X. Zhou, J. Pan, and S. Shen, “Teach-repeat-replan: A complete and robust system for aggressive flight in complex environments,” IEEE Trans. Robot., vol. 36, no. 5, pp. 1526–1545, 2020, doi: 10.1109/TRO.2020.2993215.

本文共1877字

由西湖大学智能无人系统博士后曹华姿原创

申请文章授权请联系后台相关运营人员

▌微信公众号：空中机器人前沿

▌知乎：空中机器人前沿（本文链接：https://zhuanlan.zhihu.com/p/581462695）

▌Youtube：Aerial robotics @ Westlake University

▌实验室网站：https://shiyuzhao.westlake.edu.cn