基于改进A~*算法在AGV路径规划中的应用
|
摘要
为了解决复杂环境下A~*寻路算法存在搜索节点多,搜索时间长,路径曲折的问题,提出了一种改进的A~*算法。首先,在具有障碍物的栅格地图中引入象限的概念,通过限制当前节点只朝目标节点所处的一个象限进行节点扩展,有效降低了寻路过程中搜索的节点数量。其次,在估价函数中考虑了AGV行驶和转向时间消耗成本,从而有效的搜索最短时间路径。通过仿真实验分析比较了文中算法与A~*算法以及另一种改进A~*算法的搜索性能。仿真结果表明,文中算法能有效减少寻路过程中的搜索节点数和转向次数,提高了路径搜索效率和平滑度。
In order to solve the problems of A~* algorithm in complex environment, such as large number of search nodes, long search time, search path twist and turns etc, an improved A~* algorithm is presented. Firstly, the quadrant concept is introduced in a grid map with obstacles, and the number of searching nodes in the path finding process are effectively reduced by limiting the current node to expand only toward one quadrant where the target node is located. Secondly, the travelling and turning time costs are added into the evaluation function, so that the shortest-time path can be searched effectively. The analysis and comparison between the proposed algorithm, traditional A~* algorithm and another improved A~* method were then given in the simulation experiments. The experiment results show that the proposed algorithm effectively reduces the number of search nodes and turning times in the path planning, improves the path search efficiency and smoothness.
In order to solve the problems of A~* algorithm in complex environment, such as large number of search nodes, long search time, search path twist and turns etc, an improved A~* algorithm is presented. Firstly, the quadrant concept is introduced in a grid map with obstacles, and the number of searching nodes in the path finding process are effectively reduced by limiting the current node to expand only toward one quadrant where the target node is located. Secondly, the travelling and turning time costs are added into the evaluation function, so that the shortest-time path can be searched effectively. The analysis and comparison between the proposed algorithm, traditional A~* algorithm and another improved A~* method were then given in the simulation experiments. The experiment results show that the proposed algorithm effectively reduces the number of search nodes and turning times in the path planning, improves the path search efficiency and smoothness.
引文
[1] 汤红杰,王鼎,皇攀凌,等.优化Dijkstra算法在工厂内物流AGV路径规划的研究[J].机械设计与制造,2018(S):117-120.
[2] 刘二辉,姚锡凡,刘敏,等.基于改进灰狼优化算法的AGV路径规划及其实现原型平台[J/OL].计算机集成制造系统,http://kns.cnki.net/kcms/detail/11.5946.TP.20180122.1630.012.html,2018-07-30.
[3] 刘二辉,姚锡凡.基于改进遗传算法的自动导引小车路径规划及其实现平台[J].计算机集成制造系统,2017,23(3):465-472.
[4] Tang B,Zhu Z,Luo J.A convergence-guaranteed particle swarm optimization method for mobile robot global path planning[J].Assembly Automation,2017,37(1):114-129.
[5] Hart P E,Nilsson N J,Raphael B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics,1968,4(2):100-107.
[6] 王志中.复杂动态环境下自主机器人路径规划研究[J].组合机床与自动化加工技术,2018(1):64-68.
[7] 李伟光,苏霞.基于改进A*算法的AGV路径规划[J].现代制造工程,2015(10):33-36.
[8] Lin M,Yuan K,Shi C,et al.Path planning of mobile robot based on improved A* algorithm[C].Control and Decision Conference,IEEE,2017:3570-3576.
[9] 陈伟华,林颖,文宗明,等.基于双重A*算法的移动机器人动态环境路径规划[J].组合机床与自动化加工技术,2018(4):127-130.
[10] 赵晓,王铮,黄程侃,等.基于改进A*算法的移动机器人路径规划[J].机器人,2018,40(6):903-910.
[2] 刘二辉,姚锡凡,刘敏,等.基于改进灰狼优化算法的AGV路径规划及其实现原型平台[J/OL].计算机集成制造系统,http://kns.cnki.net/kcms/detail/11.5946.TP.20180122.1630.012.html,2018-07-30.
[3] 刘二辉,姚锡凡.基于改进遗传算法的自动导引小车路径规划及其实现平台[J].计算机集成制造系统,2017,23(3):465-472.
[4] Tang B,Zhu Z,Luo J.A convergence-guaranteed particle swarm optimization method for mobile robot global path planning[J].Assembly Automation,2017,37(1):114-129.
[5] Hart P E,Nilsson N J,Raphael B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics,1968,4(2):100-107.
[6] 王志中.复杂动态环境下自主机器人路径规划研究[J].组合机床与自动化加工技术,2018(1):64-68.
[7] 李伟光,苏霞.基于改进A*算法的AGV路径规划[J].现代制造工程,2015(10):33-36.
[8] Lin M,Yuan K,Shi C,et al.Path planning of mobile robot based on improved A* algorithm[C].Control and Decision Conference,IEEE,2017:3570-3576.
[9] 陈伟华,林颖,文宗明,等.基于双重A*算法的移动机器人动态环境路径规划[J].组合机床与自动化加工技术,2018(4):127-130.
[10] 赵晓,王铮,黄程侃,等.基于改进A*算法的移动机器人路径规划[J].机器人,2018,40(6):903-910.