陈若男 文聪聪 彭玲 尤承增

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

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

中图分类号：TP242.6

文献标志码：A

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

0 引言

这些年，受机器人带来的影响，人们的生活生产方式发生了革命性的转变。机器人产业在市场需求以及国家政策扶持下，得到了迅速发展[1]，被广泛应用到工业、服务业、安防，甚至医疗等领域中，对机器人要求也从原来的单一化和机械化向智能化和人性化的需求转变[2]，激发了社会各界人士对机器人的研究兴趣。其中，路径规划是机器人智能化的关键技术，是指移动机器人按照某一性能指标搜索一条从起始状态到目标状态的最优或次最优的无碰撞路径[3]。

基于栅格法地图，常用的路径规划算法[4-7]有Dijkstra算法、最佳优先算法、启发式搜索算法。……