[发明专利]快速规划最优路径方法及装置

摘要

一种快速规划最优路径方法及装置，其中方法包括如下步骤，将地图信息分为若干单元格，确定行驶路径的起点和终点；以单个单元格作为顶点，计算顶点的距离值；从终点开始通过相邻顶点搜索，当前距离为终点距离值减一；寻找距离值为当前距离的顶点，如果其中一个顶点为起点，则找到了最佳路径；区别于现有技术，上述技术方案通过计算顶点距离，寻找最佳路径，通过更新优先级队列的方法使得在环境变动的时候优先在最佳路径附近的顶点优先寻找重新规划路径，提高搜索效率。还通过计算本地距离值的方法优化环境变动后的距离计算，提高方法的可靠性，还通过增加启发式函数的算法节约计算步骤。

主权项

一种快速规划最优路径方法，其特征在于，包括如下步骤，将地图信息分为若干单元格，确定行驶路径的起点和终点；以单个单元格作为顶点，计算顶点的距离值；从终点开始通过相邻顶点搜索，当前距离为终点距离值减一；寻找距离值为当前距离的顶点，如果其中一个顶点为起点，则找到了最佳路径；如果未找到距离值为当前距离的顶点，则当前距离减一，重复上一步；不断更新一个优先级队列，所述优先级队列根据到最佳路径的远近对优先级队列中的顶点进行排序，当环境变动时重新计算顶点的距离值，根据优先级队列的顶点排序重新返回步骤“寻找距离值为当前距离的顶点”，直到重新规划出最佳路径；所述优先级队列通过顶点的本地到达值及启发式函数值确定，所述启发式函数为顶点到起点的横、纵距离中的最大值。