基于A~*改进算法的四向移动机器人路径搜索研究  

Research of four-way mobile robot path search based on improved A~* algorithm

作　　者：田华亭[1] 李涛[1] 秦颖[1] TIAN Hua-ting LI Tao QIN Ying(School of Mechanical and Electrical Engineering, Kunming University of Sscience and Technology, Kunming 650500, Chin)

机构地区：[1]昆明理工大学机电工程学院,昆明650500

出　　处：《控制与决策》2017年第6期1007-1012,共6页Control and Decision

基　　金：国家自然科学基金项目(51567012);国家科技支撑计划项目(2013BAF02B02)

摘　　要：在由栅格法构建的环境地图中,利用A~*算法进行路径搜索时存在搜索范围广、搜索速度慢、路径曲折等问题.针对栅格地图及具有四向移动机器人的特点,从搜索方向、启发函数构建、机器人加减速以及转向成本等几个方面对A~*算法进行研究和改进,提出一种基于启发信息的扩展节点算法,降低偏离最佳路径节点的扩展数量.改进后的A~*算法平均可降低67.1%的搜索面积、49.2%的计算时长、24.9%的路径成本及减少51.1%的转向次数,提高了路径的搜索速度和平滑度.There are some problems in the use of the A＊ algorithm for path-search of the mobile robot based on a grid map, such as wide search range, calculation slow, search path twists and turns etc. For the characteristics of the four-way mobile robot which moves on the grid map, from the search range, heuristic function constructed, robot acceleration-deceleration and steering costs and other factors on the A＊ algorithm research and improvement, an extended node algorithm is propose. based on heuristic information, and the number of extensions nodes that deviate from the optimum path is reduced. The results show that the improved A＊ algorithm can reduce 67.1% of the search area, 49.2% of the computing time in average and reduce 24.9% of the average path cost, as well as decrease 51.1% steering times, and the speed and smoothness of the path-search are improved.

关 键 词：A＊改进算法 启发函数 移动机器人 路径搜索 配送中心 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]