圖搜尋（規劃）

圖搜尋是一類尋路方法，用於當世界已經被簡化成一張「圖」的時候——這張圖是一堆點（叫做節點），每個點代表機器人可能所處的一個地方或一種狀態，點與點之間由線（叫做邊）連起來，邊的意思是「你可以從這個點直接邁到那個點」，通常還附帶一個代價，表示這一步有多貴、有多遠。想像一張地鐵線路圖：車站是那些點，站與站之間的軌道段是那些線，而你想找出從你這一站到目的地的最佳走法。圖搜尋說白了，就是在這樣一張連接之網裡找出那個最佳走法的、有章法的步驟。

要把它用到機器人運動上，你得先把那片平滑、連續的姿態空間，變成這樣的一張圖——通常的做法是把它切成一格一格的網格，或者撒下一批採樣姿態、再把鄰近的安全姿態連起來。一旦這張圖建好，圖搜尋演算法就從起點向外探索，沿著邊一圈圈擴散，並且記下到目前為止抵達每個節點的最便宜走法，直到它觸及目標；隨後它順著這份記錄倒著回溯，把那條勝出的路線讀出來。這是一大批實用規劃器的骨幹——大名鼎鼎的 Dijkstra 演算法和 A* 都是圖搜尋——而它最大的長處是一條保證：只要圖裡存在一條路線，這些搜尋就一定能找到它，而且（對 Dijkstra，或對採用可採納代價估計的 A*）找到的還是圖裡最便宜的那條。