摘要
现有的精确方法虽然能减少在线搜索，但通常会保留细粒度的搜索状态或需要大量的预处理。本文提出了 Key-Interval A (KIA)，一种通过轻量级预处理构建并搜索自由空间紧凑区间级抽象的最优路径规划算法。
KIA 使用区间来表示自由空间，即可遍历单元的最大连续运行。它提取关键区间以捕捉结构边界变化，并通过连续的非关键区域将其连接。KIA 随后在生成的关键区间图上执行 A* 风格的搜索，并从区间链中构造网格路径，无需进行单元级的局部搜索。
我们证明了 KIA 在 4 连接网格上的完备性和最优性。实验结果显示，KIA 保持了精确的最短路径长度，并在八个基准组中有七个组实现了最快的运行时间，尤其在结构化和游戏地图上取得了显著的性能提升。
博主点评： KIA* 算法通过引入关键区间的概念，成功地减少了搜索状态的复杂性，提升了路径规划的效率。这种结构化的抽象方法不仅优化了运行时间，还保持了路径的准确性，为未来的路径规划研究提供了新的思路。