一种机器人路径规划算法的研究

景晓琦，吕艳辉，李发伯

(沈阳理工大学 信息科学与工程学院，沈阳110159)

随着人工智能的迅速发展，室内移动机器人已进入人们的生活，移动机器人给人们带来了很多便利[1]。路径规划是移动机器人不可缺少的一项技术[2]，该技术是在已知机器人的环境地图和当前姿态的情况下，规划出一条从指定起点到指定目标点的无碰撞路径。

A*算法是移动机器人路径规划中的一种重要算法[3]，凭借启发式函数可以获得一条最优路径。A*算法便于运用到其他算法中，并有较强的塑造性，但在应用过程中，A*算法存在着冗余点过多、计算量大等问题，为此采用删除冗余点的方法以减少计算量。但仅凭借A*算法无法完成遇到动态障碍物时的路径规划，所以要采用局部路径规划算法来实时避障。本文将改进后的A*算法与时间弹性带[4](Timed Elastic Band，TEB)局部路径规划算法相结合，形成新的路径规划算法。

1 全局路径规划

1.1 A*算法介绍

A*算法的思想是依靠全局地图信息，使用启发式搜索法来选择下一个节点[5]。A*算法的启发式函数可以描述为

f(n)=g(n)+h(n)

(1)

式中：g(n)为起始点到当前点的代价；h(n)为当前点到目标点的代价。

A*算法搜索过程可分为以下几个步骤。

(1)开始搜索：首先将起始点放到open 队列中，向周围八向查找能够通过的方格并且将其加入到open队列中；然后设置起始点为新加入方格的父节点并用箭头标注；最后把起始点从open队列中移入到close队列中(close队列中存放的是所有不用再次查看的方格)。

(2)继续搜索：选择open队列中具有最小f(n)值的节点n，并将其放入close队列中。……