取档机器人路径规划的改进Dijkstra算法
|
摘要
档案库取档机器人在使用传统Dijkstra算法进行路径规划时,存在无法筛选出拐弯数最少、经过节点数最少的最短路径等缺点,提出了一种改进型的Dijkstra算法。首先针对档案库平面布局建立基于拓扑法的电子地图;然后根据任务需求,建立最短路径搜索数学模型;采用Dijkstra算法并结合深度优先遍历算法筛选出任意2个节点间的所有最短路径,并找出花费代价最小的路径。最后对改进的算法进行仿真实验,结果表明,改进后的Dijkstra算法可以有效地提高取档机器人的运行效率,可以用最小的行驶代价到达目标点。
An improved Dijkstra algorithm was proposed to overcome the shortcomings of path planning for archives accessing robot,such as the inability to select the shortest path with the least number of turns and the least number of nodes when using the general Dijkstra algorithm. First,the electronic map based on topological method was established according to the layout of archives. second,the shortest path search mathematical model was established according to the mission requirements. Dijkstra algorithm combined with depth-first traversal algorithm was used to select all the shortest paths between two locations and find the path with the least cost. Finally,the improved algorithm was simulated. The results show that the improved Dijkstra algorithm can effectively improve the efficiency of the robot and can reach the target point with the lowest cost.
An improved Dijkstra algorithm was proposed to overcome the shortcomings of path planning for archives accessing robot,such as the inability to select the shortest path with the least number of turns and the least number of nodes when using the general Dijkstra algorithm. First,the electronic map based on topological method was established according to the layout of archives. second,the shortest path search mathematical model was established according to the mission requirements. Dijkstra algorithm combined with depth-first traversal algorithm was used to select all the shortest paths between two locations and find the path with the least cost. Finally,the improved algorithm was simulated. The results show that the improved Dijkstra algorithm can effectively improve the efficiency of the robot and can reach the target point with the lowest cost.
引文
[1]金婷,方欢,方贤文.改进型Dijkstra算法的最短路径求解[J].软件导刊,2016,15(2):129-131.
[2]王树西,李安渝. Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机学,2014,41(6):217-224.
[3]孙强,沈建华,顾君忠. Dijkstra的一种改进算法[J].计算机工程与应用,2002,38(3):99-101.
[4]施剑烽,杨勇生.基于改进的Dijkstra算法AGV路径规划研究[J].科技视界,2016(20):111-112.
[5]刘维民. AGV路径规划与调度系统研究[D].广州:华南理工大学,2016:7.
[6]毛洋洋,赵欢,韩世博,等.面向复杂曲面的机器人砂带磨抛路径规划及后处理研究[J].机电工程,2017,34(8):829-834.
[7]郭丽晓.基于拓扑地图的AGV智能路径规划技术研究[D].杭州:浙江大学,2013:18.
[8]王玉林,魏国亮,鲍海锋.基于Dijkstra算法的磁带导引AGV路径规划[J].农业装备与车辆工程,2018,56(3):51-54.
[9]张默. Dijkstra最短路径算法的研究[J].数学学习与研究,2018(16):152.
[10]严蔚敏,吴伟民.数据结构[M]. 2版.北京:清华大学出版社,1992:167-168.
[2]王树西,李安渝. Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机学,2014,41(6):217-224.
[3]孙强,沈建华,顾君忠. Dijkstra的一种改进算法[J].计算机工程与应用,2002,38(3):99-101.
[4]施剑烽,杨勇生.基于改进的Dijkstra算法AGV路径规划研究[J].科技视界,2016(20):111-112.
[5]刘维民. AGV路径规划与调度系统研究[D].广州:华南理工大学,2016:7.
[6]毛洋洋,赵欢,韩世博,等.面向复杂曲面的机器人砂带磨抛路径规划及后处理研究[J].机电工程,2017,34(8):829-834.
[7]郭丽晓.基于拓扑地图的AGV智能路径规划技术研究[D].杭州:浙江大学,2013:18.
[8]王玉林,魏国亮,鲍海锋.基于Dijkstra算法的磁带导引AGV路径规划[J].农业装备与车辆工程,2018,56(3):51-54.
[9]张默. Dijkstra最短路径算法的研究[J].数学学习与研究,2018(16):152.
[10]严蔚敏,吴伟民.数据结构[M]. 2版.北京:清华大学出版社,1992:167-168.