单边矩形扩展A^*算法

来源：机器人杂志2017年第1期北京时间：

作者：李冲, 张安, 毕文豪

摘要：提出了一种新的单边矩形扩展A*（REA*）算法．新算法采用受迫扩展规则，在以矩形单元探索地图的过程中，用单条公共边取代相邻矩形的2条冗余独立边，从而提高了算法效率，简化了终止条件，优化了路径质量．在无需对地图进行预处理的情况下，算法速度比传统A*算法提高1个数量级以上．算法能够保证得到栅格最优的路径点序列，且最终路径（由路径点间直线组成）总是比栅格最优路径更短．典型地图集上的实验结果表明，相比于现有REA*算法，新算法提高了对复杂地图的处理能力和算法效率上限．新算法路径长度更短，路径转折次数更少，因此路径质量更优．除了在低复杂且不开阔的地图上外，新算法平均效率也高于REA*算法．

关键词：路径搜索, 启发式算法, 栅格图, A^*算法, 路径平衡性