碰撞檢測

碰撞檢測，就是針對機器人的某一種姿態，問出一個乾脆的是或否的問題：在這個確切的姿態下，機器人有沒有哪個部位和障礙物重疊——或者和它自己重疊？它正是那個告訴規劃器一種姿態落在界線哪一邊、是自由還是禁止的工具。其內部其實是幾何運算：軟體為機器人的各個連桿和障礙物都準備了簡單的替身形狀（長方體、圓柱、球），然後檢驗這些形狀裡有沒有誰相交。要是什麼都沒重疊，這個姿態就是安全的；只要有任何重疊，這個姿態就處於碰撞之中。

這個不起眼的檢驗是運動規劃的主力，因為規劃器在搜索路線時會成千上萬次、乃至上百萬次地調用它，所以它首先必須夠快。這裡還藏著一個更隱蔽的陷阱：只檢查單個姿態是不夠的。機器人在一小段移動的起點是安全的、終點也是安全的，卻可能在中途逕直穿過一堵牆。所以規劃器還得對每一個候選步驟做連續檢測或掃掠檢測——把那一小段運動整個都驗一遍，而不只是驗它的兩個端點。碰撞檢測裡始終存在一種張力：速度對抗謹慎——檢得太粗，會漏掉一次碰撞；檢得太細，規劃又會慢如蝸牛。