碰撞检测

碰撞检测，就是针对机器人的某一种姿态，问出一个干脆的是或否的问题：在这个确切的姿态下，机器人有没有哪个部位和障碍物重叠——或者和它自己重叠？它正是那个告诉规划器一种姿态落在界线哪一边、是自由还是禁止的工具。其内部其实是几何运算：软件为机器人的各个连杆和障碍物都准备了简单的替身形状（长方体、圆柱、球），然后检验这些形状里有没有谁相交。要是什么都没重叠，这个姿态就是安全的；只要有任何重叠，这个姿态就处于碰撞之中。

这个不起眼的检验是运动规划的主力，因为规划器在搜索路线时会成千上万次、乃至上百万次地调用它，所以它首先必须够快。这里还藏着一个更隐蔽的陷阱：只检查单个姿态是不够的。机器人在一小段移动的起点是安全的、终点也是安全的，却可能在中途径直穿过一堵墙。所以规划器还得对每一个候选步骤做连续检测或扫掠检测——把那一小段运动整个都验一遍，而不只是验它的两个端点。碰撞检测里始终存在一种张力：速度对抗谨慎——检得太粗，会漏掉一次碰撞；检得太细，规划又会慢如蜗牛。