Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (4): 1006-1011.DOI: 10.11772/j.issn.1001-9081.2018091977

Previous Articles     Next Articles

Application of improved A* algorithm in indoor path planning for mobile robot

CHEN Ruonan1,2, WEN Congcong1,2, PENG Ling1, YOU Chengzeng1,2   

  1. 1. Institute of Remote Sensing and Digital Earth, Chinese Academy of Sciences, Beijing 100101, China;
    2. College of Resources and Environment, University of Chinese Academy of Sciences, Beijing 100049, China
  • Received:2018-09-25 Revised:2018-11-07 Online:2019-04-10 Published:2019-04-10

改进A*算法在机器人室内路径规划中的应用

陈若男1,2, 文聪聪1,2, 彭玲1, 尤承增1,2   

  1. 1. 中国科学院 遥感与数字地球研究所, 北京 100101;
    2. 中国科学院大学 资源与环境学院, 北京 100049
  • 通讯作者: 彭玲
  • 作者简介:陈若男(1996-),女,浙江温州人,硕士研究生,主要研究方向:人工智能、室内外定位导航;文聪聪(1994-),男,山西临汾人,博士研究生,主要研究方向:机器视觉、室内外定位导航;彭玲(1965-),女,湖北武汉人,研究员,博士,主要研究方向:遥感影像智能学习、智慧城市时空大数据脉动分析、室内外定位导航;尤承增(1993-),男,山东枣庄人,硕士研究生,主要研究方向:室内外定位导航、可见光定位。

Abstract: For indoor path planning for mobile robot in particular scenario with multiple U-shape obstacles, traditional A* algorithm has some problems such as ignoring the actual size of robot and long computational time. An improved A* algorithm was proposed to solve these problems. Firstly, a neighborhood matrix was introduced to perform obstacle search, improving path safety. Then, the effects of different types and sizes of neighborhood matrices on the performance of the algorithm were studied and summarized. Finally, heuristic function was improved by combining the angle information and the distance information (calculated in different expressions when situation changes) to improve the calculation efficiency. The experimental results show that the proposed algorithm can obtain different safety spacing by changing the size of obstacle search matrix to ensure the safety of different types of robots in different environments. Moreover, in the complex environment, compared with traditional A* algorithm, path planning speed is improved by 28.07%, and search range is narrowed by 66.55%, so as to improve the sensitivity of the secondary planning of robot when encountering dynamic obstacles.

Key words: A* algorithm, indoor path planning, mobile robot, heuristic function

摘要: 传统A*算法在面向机器人室内多U型障碍的特殊场景下规划路径时,容易忽略机器人实际大小,且计算时间较长。针对这个问题,提出一种改进A*算法。首先引入邻域矩阵进行障碍搜索以提升路径安全性,然后研究不同类型和尺寸的邻域矩阵对算法性能的影响,最后结合角度信息和分区自适应距离信息对启发函数进行改进以提高计算效率。实验结果表明,改进A*算法可以通过更改障碍搜索矩阵的尺寸来获得不同的安全间距,以保证不同机器人在不同地图环境下的安全性;而且在复杂大环境中与传统A*算法相比寻路速度提高了28.07%,搜索范围缩小了66.55%,提高了机器人在遇到动态障碍时二次规划的灵敏性。

关键词: A*算法, 室内路径规划, 移动机器人, 启发函数

CLC Number: