连续运动规划的网格近似A*搜索是否为分辨率最优？

结论 #

你的理解存在偏差，基于规则网格离散化的A*规划方法确实不具备严格的分辨率最优性，即便分辨率趋近于无穷大，也无法保证收敛到连续空间的精确最优路径。

原因1：邻域运动方向的固有约束 #

常规4/8邻域网格的单步运动方向是固定的有限集合：

• 4邻域仅支持上下左右4个正交方向
• 8邻域额外增加4个对角线方向
  无论分辨率提升到多高，算法搜索出的路径本质都是上述固定方向短步的拼接，而连续空间的最短路径可以是任意角度的直线，拼接路径的总长度始终会比连续最优路径长固定比例的偏差，该偏差不会随分辨率提升归零。
  举个直观例子：从(0,0)到(3,1)的连续空间最短路径是长度√10≈3.162的直线，即使将网格分辨率提升到1nm每格，8邻域A*输出的路径总长度也会稳定在约3.209，始终和最优值存在固定误差。

原因2：启发式函数的适配偏差 #

A*的最优性前提是启发式函数可采纳（即不会高估到终点的代价），但离散网格场景下常用的启发式：

• 4邻域对应曼哈顿距离
• 8邻域对应切比雪夫距离
  二者本质都是对连续空间欧氏距离的近似，从搜索基准上就和连续空间最优解的代价度量存在偏差，进一步导致输出解的质量无法收敛到连续最优。

原因3：两个特性的定义边界完全不同 #

分辨率完备性：只要问题存在可行解，当分辨率足够高时，算法一定能找到至少一条可行路径，不对路径质量做任何承诺。
分辨率最优性：当分辨率趋近于无穷大时，算法输出路径的代价会严格收敛到连续空间最优解的代价。
你所查阅的文献表述是准确的，规则网格类的单元分解法仅满足分辨率完备性，不满足分辨率最优性。如果需要实现分辨率最优，可以采用支持任意角度运动的混合A算法，或对网格A的输出路径做弦剪枝、梯度平滑等后处理，消除离散化带来的锯齿状偏差。

内容的提问来源于stack exchange，提问作者bluetintsprite