Falco: Fast likelihood‐based collision avoidance with extension to human‐guided navigation.

Zhang, Ji, et al. "Falco: Fast likelihood‐based collision avoidance with extension to human‐guided navigation." Journal of Field Robotics 37.8 (2020): 1300-1313.PDF

1. 概述

该论文所解决的是路径规划问题，使复杂环境下快速自主飞行。路径规划问题仍然具有挑战性，因为规划路径需要创建和更新环境表示，搜索动力学上可行的路径，以躲避机载传感器发现的障碍。

贡献点： 提出了一种大大降低计算复杂度的方法，从而可以通过在飞行器上使用非常低的计算量来确保安全飞行。

通过避免在线搜索来降低计算量；
该方法不寻找最低成本路径（通常是最短路径），而是在确定执行导航的下一步时最大化实现目标的概率。

所规划的路径可以是长度最短的，但此类可能引导车辆通过狭窄区域，如果由于动态障碍物或环境变化导致先前的地图更新而发现更多障碍物，那么车辆躲避新出现障碍物的选择就会很少。

该方法使轻型飞行器能够在复杂森林环境中以10 m/s的速度飞行。

2. 方法

问题描述： 从 $x_s$ 出发，使得每一步到达 $B$ 的概率 $P_B$ 最大。

x_s^*=arg \ \underset{x_s}{max}P_B(x_s)

当车辆沿着路径行驶时，每一步都解决了上述问题，即车辆在导航过程中每一时刻达到B的概率最大化。

2.1 概率模型

$S$ 是传感器扫描区域，从 $x_s$ 到 $B$ 可以划分为 $x_s \ -> \ x_f \ -> \ B$ 。车辆从 $x_f$ 到达 $B$ 的概率密度，可以从先验地图上的障碍物中得到，有

p_B(x_s)=\int p_B(x_f)p(x_f|x_s) {\rm d}x_f

根据抽样的蒙特卡罗理论可以建立

\int p_B(x_f)p(x_f|x_s) {\rm d}x_f ≈_{n\uparrow∞} 1/n\sum_{i=1}^{n}p_B(ξ_i)

因此可以得到概率的简化公式

p_B(x_s)=1/n\sum_{i=1}^{n}p_B(ξ_i)

2.2 局部概率

在最上面一行中，根据自上而下的视图中显示了从左到右弯曲的7个路径组。在下面一行，展示了侧视图中从向下到向上的5个路径组。同时考虑水平方向和垂直方向，共有7个×5 = 35个路径组。

这些示例路径可以被称为运动原语，是基于车辆运动约束而生成的，每个运动原语都与路径体素相匹配。该方法并不局限于特定的运动模型，并且可以支持各种路径组配置。当出现障碍时，去除对应的运动原语。

因为障碍的存在，并非每条路径都是可行的，可以建立对应的boolean值公式：

c(ξ_i)=\left\{ \begin{aligned} 1, \ ξ_i \ is\ unoccluded \\ 0, \ \ \ \ \ \ \ \ \ \ \ otherwise \end{aligned} \right.

由此可以将公式4再一次简化：

P_B(x_s)≈\frac {\sum_{i=1}^nc(ξ_i)p_B(ξ_i)} {\sum_{i=1}^n c(ξ_i)}

2.3 全局概率

环境用体素表示，与传统的体素表示不同，该论文的体素同时包含位置和方向信息。

通过体素之间信息的传递，可以将概率密度公式写为

在2D环境中，每个体素都会和三个方向关联进行传播，3D环境类似，增加了竖直方向。

在初始化过程中，概率密度均匀地分布在包含 $B$ 的体素中的各个方向上。概率的传播是通过一个迭代过程。随着概率密度的传播，体素越亮的地方，表示概率密度越高。

3. 实验

路径测试：现有规划方法，如RRT*，往往会寻找最短路径，也就是左边的狭窄路径；该论文的方法可以寻找到宽阔路径，提高到达目标的概率。

对照实验：在2D、3D的随机环境和迷宫中进行测试，与RRT、RRT*、RRT-connect、BIT*进行对比

3D环境测试结果与2D类似，在随机环境中，该论文的方法与RRT、RRT*具有相近处理速度，但路径更加有效；在迷宫环境中，有最快的处理速度。

4. 结论

通过运动原语来存储可行路径，再计算概率密度，选择出最佳路径，指导运动。

目录