粒子滤波器

粒子滤波器估计某物在哪里，靠的是同时维护一大群猜测，而不是只有一个。每一个猜测——一个粒子——都是一个完整的可能答案：就在这个确切的位置、朝着那个确切的角度。一台被丢进某栋楼里、完全不知道自己从哪儿出发的机器人，可能会撒出一千个粒子、铺满整张平面图，每个都说“我赌的最好答案是这里”。所有粒子组成的这整团云，合起来代表机器人的“信念”：粒子扎堆的地方，它认为自己多半在那儿；粒子稀疏的地方，它认为自己多半不在。

这群粒子通过一个“适者生存”的循环不断变好。首先，每个粒子都按机器人的运动被移动——机器人往前滚了一米，每个粒子也往前一米，外加一点随机抖动来表示不确定性。接着来了一次测量，比如一次激光扫描，于是每个粒子都按“它预测看到的景象，与传感器实际看到的有多吻合”被打分。最后是重采样：得分高的粒子被复制，得分低的粒子被淘汰，于是整群粒子朝真相漂移、聚拢。把这个循环跑得足够快，一团乱撒的云雾就会在几秒内坍缩到机器人真实的位置上。

这种方法的厉害之处在于它不做任何整齐的假设。卡尔曼那一家子坚持信念必须是单独一个整洁的钟形团块；而粒子滤波器可以持有任何形状的信念——甚至同时有好几个分开的团簇，这对一台在两条长得一模一样的走廊之间犹豫不决的机器人来说再合适不过。代价则是计算量：要达到不错的精度可能需要成千上万个粒子，而且随着问题维度增加，粒子数必须陡增，所以它在二维机器人定位这类任务上大放异彩，却在维度极高的状态上吃力。