论文部分内容阅读
提出了一种新的单边矩形扩展A*(REA*)算法.新算法采用受迫扩展规则,在以矩形单元探索地图的过程中,用单条公共边取代相邻矩形的2条冗余独立边,从而提高了算法效率,简化了终止条件,优化了路径质量.在无需对地图进行预处理的情况下,算法速度比传统A*算法提高1个数量级以上.算法能够保证得到栅格最优的路径点序列,且最终路径(由路径点间直线组成)总是比栅格最优路径更短.典型地图集上的实验结果表明,相比于现有REA*算法,新算法提高了对复杂地图的处理能力和算法效率上限.新算法路径长度更短,路径转折次数更少,因此路径质量更优.除了在低复杂且不开阔的地图上外,新算法平均效率也高于REA*算法.
A new unilateral rectangle expansion A * (REA *) algorithm is proposed. The new algorithm uses the forced expansion rule to replace two redundant independent Which improves the efficiency of the algorithm, simplifies the termination condition and optimizes the path quality.When the map is not preprocessed, the speed of the algorithm is more than one order of magnitude higher than the traditional A * algorithm.The algorithm can ensure the optimal grid , And the final path (which consists of lines between path points) is always shorter than the optimal path of the grid.Experimental results on an atlas typically show that compared to the existing REA * algorithm, the new algorithm improves The processing power of complex maps and the upper limit of algorithm efficiency.The new algorithm has shorter path length and fewer path transitions, so the path quality is better.Except for low complex and not open map, the new algorithm also has higher average efficiency than REA * algorithm.