图搜索（规划）

图搜索是一类寻路方法，用于当世界已经被简化成一张“图”的时候——这张图是一堆点（叫做节点），每个点代表机器人可能所处的一个地方或一种状态，点与点之间由线（叫做边）连起来，边的意思是“你可以从这个点直接迈到那个点”，通常还附带一个代价，表示这一步有多贵、有多远。想象一张地铁线路图：车站是那些点，站与站之间的轨道段是那些线，而你想找出从你这一站到目的地的最佳走法。图搜索说白了，就是在这样一张连接之网里找出那个最佳走法的、有章法的步骤。

要把它用到机器人运动上，你得先把那片平滑、连续的姿态空间，变成这样的一张图——通常的做法是把它切成一格一格的网格，或者撒下一批采样姿态、再把邻近的安全姿态连起来。一旦这张图建好，图搜索算法就从起点向外探索，沿着边一圈圈扩散，并且记下到目前为止抵达每个节点的最便宜走法，直到它触及目标；随后它顺着这份记录倒着回溯，把那条胜出的路线读出来。这是一大批实用规划器的骨干——大名鼎鼎的 Dijkstra 算法和 A* 都是图搜索——而它最大的长处是一条保证：只要图里存在一条路线，这些搜索就一定能找到它，而且（对 Dijkstra，或对采用可采纳代价估计的 A*）找到的还是图里最便宜的那条。