方法
本节介绍规划器如何对机器人的运动、环境和协方差约束进行建模，并说明如何将 A* 离散节点上的 EKF 实现为连续时间相关系统。
不确定性指标
为量化定位不确定性，可以使用任何基于 EKF 协方差得出的标量指标。本文采用位置协方差的迹。
协方差矩阵的迹之所以适用，是因为该矩阵对称且半正定。因此，其所有对角元素均为非负数，得到的标量为正。
不确定性约束如下：
位置协方差的迹必须低于用户定义的阈值。
两个节点之间任何违反该约束的轨迹段，都视为不可行。
考虑不确定性的边评估
使用算法 1 生成路径段后，会通过不确定性检查函数评估每个候选路径段，该函数总结于算法 2。机器人运动与 EKF 传播会同时进行仿真，并在执行过程中持续监测不确定性指标。不满足约束的节点将被舍弃。
理论分析
本节为所提出的受不确定性约束 A* 规划器提供最优性方面的理论保证。该问题被表述为图搜索问题，其中边是否有效严格取决于 EKF 协方差上界。
图的表述
边的代价是胡萝卜追踪控制器生成轨迹的弧长。
实验与结果
本节展示在 GPS 拒止环境中评估所提出的受不确定性约束规划器的仿真结果。实验说明，施加定位不确定性上界会如何影响不同规划器的路径可行性、估计精度和路径质量。
地标密度的影响
通过改变地标百分比，同时保持障碍物密度和不确定性阈值不变，评估地标密度的影响。对于每种情况，报告所有规划器成功运行结果的平均成功率、路径长度和计算时间。评估障碍物密度和不确定性阈值的影响时，也采用相同流程。
在路径长度方面，A 在所有地标密度下都能稳定生成最短路径。其路径长度接近欧氏下界，体现了其可采纳启发式所保证的最优性。PRM 和 RRT 由于随机探索以及路线图连通性欠佳，生成的路径明显更长。提高地标密度可降低所有规划器的路径长度波动，但从行进距离来看，A* 仍然效率最高。
A 的总体计算时间最短，其次是 PRM，最后是 RRT。随着地标密度增加，所有规划器的计算时间都会上升。
障碍物密度的影响
在所有障碍物密度下，A 都能稳定生成最短路径，展现了即使在拥挤环境中，其最优性保证依然稳健。PRM 和 RRT 由于随机采样造成的绕行以及局部连通性有限，生成的路径更长。随着障碍物密度增加，所有规划器的路径长度均略有增加，但相对排序保持不变。
在所有障碍物密度下，A 的计算时间都最短，其次是 PRM，最后是 RRT。这反映出基于采样的规划器在拥挤环境中需要扩展更多节点。
不确定性阈值的影响
评估不确定性阈值时，地标密度固定为 10%，障碍物密度固定为 5%。
结论
本文研究了 GPS 拒止环境中的路径规划问题，其中航位推算会导致定位不确定性增大。受不确定性约束的 A* 保持其最优性保证，并在所有满足不确定性约束的可行轨迹中返回最短路径，同时总体计算时间较短。
实验结果表明，几何上最优的路径往往不符合不确定性约束，而该方法能够成功识别经过地标密集区域的可行绕行路线。不过，该方法假设环境和地标位置已知，而现实中的 GPS 拒止场景未必总是满足这一条件。未来工作将致力于放宽这些假设、处理动态障碍物，并探索用于不确定条件下多机器人导航的智能体间信念滤波器。
常见问题
规划器如何衡量定位不确定性？ 它使用从 EKF 得出的位置协方差的迹。
轨迹段在什么情况下会被视为不可行？ 如果两个节点之间的轨迹段违反用户定义的不确定性阈值，该轨迹段就不可行。
边的代价如何定义？ 它是胡萝卜追踪控制器生成轨迹的弧长。
该方法采用了哪些假设？ 它假设环境和地标位置已知。