基于A*算法的机器人路径规划与避障研究

张益辉 王长宁 孙玲

摘 要： 针对当前智能机器人应用中传统人工势场法路径规划存在的问题，对传统人工势场法进行改进，同时引入A*算法进行全局路径优化。具体则是在传统人工势场法中，对斥力函数进行改进，同时建立虚拟目标牵引点，以改进局部极小值和目标不可达的问题;在全局路径规划方面，引入A*算法，通过改进A*算法中的估计函数，以解决启发函数信息太弱或太强的问题。最后在Mat-lab2012b对上述混合算法进行编程，得到不同方法下的仿真结果。结果表明，本文构建的改机算法可有效到达终点，并且曲线光滑、平稳。

关键词： A*算法; 人工势场法; 路径规划; 避障; 仿真实验

中图分类号： TP311      文献标志码： A

Research on Robot Path Planning and Obstacle

Avoidance Based on A* Algorithms

Shi Yu， Li Chunkai

（）

Abstract： Aiming at the problems existing in the path planning of traditional artificial potential field method in the current application of intelligent robots， the A* algorithm is introduced to optimize the global path while improving the traditional artificial potential field method. Specifically， in the traditional artificial potential field method， the repulsion function is improved， and the virtual target traction point is established to improve the local minimum and target unreachability. In the aspect of global path planning， the A* algorithm is introduced to solve the problem that the information of heuristic function is too weak or too strong by improving the estimation function of A* algorithm. Finally， the hybrid algorithm is programmed in Matlab 2012 b， and the simulation results under different methods are obtained. The results show that the improved algorithm constructed in this paper can reach the end point effectively， and the curve is smooth and stable.

Key words： A* algorithm; Artificial potential field method; Path planning; Obstacle avoidance; Simulation experiment

0 引言

随着现代信息技术的进步，机器人开始逐步走向舞台，成为人们生活和工作中不可或缺的一部分。在机器人应用过程中，路径规划一直以来是研究的重点，也是机器人能够自主完成任务的基本保障。所谓的路径规划，其本质就是在众多的障碍物环境中找到一条无碰撞的路径。目前，学术上针对机器人路径的规划中，看可以分为局部路径规划和全局路径规划。其中人工势场法是常用的一种局部路径规划方法，但是人工势场法很容易陷入目标不可达和局部极小值的问题。由此，在人工势场法的基础上，人们主要从两方面进行改进：一是对人工势场法本身存在的缺陷进行改进，如在传统人工势场法的基础上，加入加速度场和速度场;二是引入全局路径规划算法，比较典型的就是A*算法、粒子群算法等。如许源（2014）在人工势场法的基础上，引入粒子群算法，最后通过实物仿真，验证上述方法的可行性。本文则在上述研究上，在传统人工势场法基础上，提出人工势场法与A*算法结合的机器人路径规划算法，并对其进行验证。

1 本文研究思路

结合机器人路径规划与避障相关理论，本文将研究的思路设计为如图1所示。

2 移动机器人栅格空间建模

2.1 栅格粒度的确定

在开展栅格建图工作时，单位栅格尺寸的划分将会对地图的精度值造成影响。单位栅格尺寸划分越细，地图的信息量也就越大，精确度也就越高，但这种划分方式会增加地图干扰项。单位栅格尺寸划分越大，系统实时性将会有所提高，地图干扰项也会随之减少，但这种划分方式的缺点在于存儲信息量较少，无法在障碍物密集环境下对有效路径进行规划。因此在研究中，引入栅格粒度来对障碍物的稀疏程度进行描述，具体数值需对障碍物区域面积以及环境计算而获取。但是在计算中，会面对不同类型的图形，如凸形、椭圆形等。若障碍物外形为凸型，可将该障碍物拆分为三角形进行计算;若障碍物为类似椭圆形，则按照矩形进行计算。在获取到栅格的粒度之后，需将各粒度与机器人自身尺寸进行对比，选取比机器人尺寸更大的粒度，目的是使机器人在运动过程中保持畅通。具体粒度获取步骤如下：

（1） 获取地图中的一个障碍物，并对该障碍物外形进行判断;

（2） 若障碍物外形为凸型，则从障碍物某顶点开始，将其拆分为多个不相交的三角形进行计算;

（3） 若障碍物外形非凸型，则对障碍物所有顶点中坐标系下最大值与最小值xmax、ymax、xmin、ymin，再以（xmin，ymin）以及（xmax，ymax）为对角定点，以此构建起一个矩形，再将矩形分割为两个不相交三角形进行计算;

（4） 通过公式s=12×a×b×sin α对各三角形面积进行计算。在该公式中，a，b为三角形定点的两个边;α为a，b的夹角;

（5） 观察地图上是否还存在其他障碍物，若存在则返回步骤（1）;

（6） 对上述障碍物面积的和进行计算，计算公式为Stotal=∑p∈ΩSp，Ω代表所有障碍物的集合;p代表Ω当中的某一障碍物元素;

（7） 对栅格粒度进行计算，计算式为式（1）。dt=StotalSenv×dmax

（1）  以此得到式（2）。d=dt，if dt>dmin

dmin，其他

（2）  在步骤（7）的公式中，senv代表环境面积;dmax代表被定义的栅格最大边长;dmin代表构造的栅格最小边长，dmin需大于机器人自身尺寸;d代表最终栅格边长。

2.2 栅格空间的表示

抛开机器人高度信息不计，仅对规划环境为平面情况进行考虑。若环境空间为W，W中的x轴位于水平方向向右位置;y轴为竖直方向向上位置，以此可构建起直角坐标系∑。假设X轴与Y轴的最大值分别为Xmax以及Ymax。假设栅格粒度为d，那么每行栅格数为Nx=Xmax/d;每列栅格数为Ny=Ymax/d。若地图中某栅格尺寸范围内并不具备任何障碍物，那么该栅格则为自由栅格，在地图中用白色进行表示;反之，该栅格则为障碍栅格，在地图中用黑色进行表示。当Xmax=Ymax=10，d=1时，机器人栅格工作空间如图2所示。

实际建模过程中，会碰到形状多样的障碍物。在此情况下，通常对栅格地图中不规则障碍物进行膨化处理，使原本占据不规则栅格的障碍物变为形状规矩的占据栅格。

2.3 栅格编码

栅格编码是路径搜索的重要部分，对路径搜索的效率有着直接的影响。传统的路径规划中，是通过行或者列进行搜索，最后连接确定的栅格，从而构成一条路径。但是这种搜索存在很大的弊端，一旦遇到复杂环境，则不能得到有效路径。因此，在本文中提出一种改进二维编码方法，主要思路是把障碍物的顶点信息作为关键点，然后将这些关键点按照一定的规则来进行编号，最后设计编码串。而编码串的长度是关键点的数量和。在编码串中，非0位不能复位，如图3所示。

如图3中的A障碍物为例，A的顶点坐标为（0，3）、（0，4）、（2，2）、（1，2）、（2，3）、（1，3）、（2，4）、（1，4）。去掉可能会引起碰撞的点，得到关键信息点为（1，2）、（2，2）、（1，3）、（2，4）四个点。以此类推，得到A、B、C三点的关键信息点。构建关键点的集合。同时假设编码串为[0，0，3，0，0，0，9，0，10，0，0，0，0，0]，那么机器人的通过坐标则为（2，2）、（4，4）、（4，5）。

3 机器人局部路径规划

3.1 传统人工势场法

传统人工势场法主要通过合力来实现对机器人前进方向的控制，具体如图4所示。

机器人在越靠近目标点时，其所受到的合力也将随之减小。当机器人到达目标点时，机器人所受的合力为最小。

但通过图4看出，机器人在运行至某一些点而并非目标点时，其所受的合力同样可以为零。当机器人受到的合力为零时，机器人将在该点上停留，不再向目标点进行移动。这些合力为零的点，被称为人工势场法的局部极小值点。同时，在机器人运行过程中，若目标点位于障碍物影响范围内，那么机器人在运行过程中的引力将减少、斥力将增大。当机器人到达某一点时，机器人将由于引力的减少而不再前进，而是以来回运动的方式在该点中进行移动。这种情况称作为人工势场法的目标不可达问题。

3.2 人工势场法改进

以上分析看出，传统人工势场法存在局部极小点与目标不可达两大问题。对此，本文根据传统人工势场法的特性，采用改进斥力函数对传统人工势场法目标不可达问题进行改进。具体改进后的斥力势场函数表达式为式（3）U2（x）=12m（1ρ-1ρ0）2（x-xg）n，ρ≤ρ0

0，ρ>ρ0

（3）  在公式（1）中，m代表大于零的斥力场系数常量;ρ0代表障碍物最大影响范围;ρ代表机器人与障碍物的最短距离;x代表机器人当前位置坐标;xg代表目标点位置坐标，则斥力表达式为式（4）～式（6）。F2（x）=- Δ （U2（x））=F11+F12，ρ≤ρ0

0，ρ>ρ0

（4）其中，F11=m（1ρ-1ρ0）1ρ2·（x-xg）nρx

（5）

F12=12mn（1ρ-1ρ0）2·（x-xg）n-1·（x-xg）x

（6）  经过改进之后，斥力函数将机器人受到的障碍物斥力划分为两部分：一部分斥力主要通过障碍物连线向机器人发起影響，如公式（3）所示;另一部分斥力主要通过机器人与目标点之间的连线，由机器人指向目标点，如公式（4）所示。在实际应用过程中，主要采用公式（3）与公式（4）的简化形式，具体为式（7）F11=m（1ρ-1ρ0）2·（x-xg）n

F12=12mn（1ρ-1ρ0）2·（x-xg）n-1

（7）  而对于人工势场法局部极小点问题，本文通过在极小点附近建立虚拟目标牵引点的方式，来对传统人工势场法局部极小点问题进行改进。改进后分为两个部分：极小值点的检测以及自主虚拟目标牵引点的建立、对原有目标点的隔离。

虚拟目标牵引点设置方法为：

假设（x1，y1）为机器人当前位置坐标;（c1，c2）为机器人受最大斥力的障碍物位置坐标;（x，y）为设置的虚拟目标牵引点位置坐标;d为可选常数，由此构建方程为式（8）、式（9）。y-y1=-c1-x1c2-y1（x-x1）

（8）

（x-x1）2+（y-y1）2=d2

（9）  联立公式（6）与公式（7）可得出解为式（10）。x=x1±d（c2-y1）（c1-x1）2+（c2-y1）2

y=y1±d（c1-x1）（c1-x1）2+（c2-y1）2

（10）4 基于人工势场法的机器人避障改进

在采用人工势场法对局部路径进行改进时，要想得到最优的路径，还需要对路径进行全局规划。传统的全局算法中，包括粒子群算法、A*算法等。本文则采用A*算法对机器人全局路径进行优化改进。

4.1 A*算法原理

A*算法属于启发式搜索算法的一种，在应用过程中主要通过启发函数来对平面上任意位置与目标位置之间的距离进行评价，再借助启发函数对最优方向开始搜索，以此找出最优方向。A*算法凭借自己具备的函数表达简单、编程易实现等优势，使其成为当前人工智能领域中广泛使用的算法之一。A*算法基本启发函数表达公式为：f（n）=g（n）+h（n）

（11）  在公式（9）中，f（n）代表地图中节点n的总代价函数;g（n）主要是对机器人由最初状态节点至节点n之间实际代价值大小进行表示;h（n）代表机器人由节点n到最终目标点对应节点最小估计代价值大小。

4.2 A*算法改进

在实际应用中发现，A*算法虽然能够有效降低节点拓展范围，以及整体计算难度，但启发信息的增加程度给搜索结果造成很大的影响。若搜索过程的启发信息增加过强，将会使搜索路径的最优性无法得以保障;若启发信息太弱，又会给路径搜索工作量造成影响，使工作量在原基础上得以增长，计算的复杂度也将提高。对此，在本文中引入权重的方式，来弥补启发信息过强或过弱带来的影响。具体则是对（9）进行改进，利用加权思想改进估价函数，具体数学表达式为：f（n）=（1-w）g（n）+wh（n）

（12）5 混合算法流程设计

结合上述的改进，提出基于全局路径规划与局部路径规划的避障算法，具体避障流程如图5所示。

6 仿真实验验证

考虑到改进算法的有效性，本文将在Mat-lab2012b平台上对该算法开展仿真实验。在开展仿真实验过程中，本文将采用栅格法来对静态室内环境模型进行构建，以二维平面来表示室内环境，通过直角坐标法对地图进行表示，以此构成其整个相对应的仿真路径规划环境。通过仿真，得到图6和图7的结果。

通过观察图6及图7显示内容可知，在单独使用人工势场法的情况下，存在无法有效绕开U型障碍物这一问题，并且在机器人在运行过程中在通过走廊时的轨迹较为曲折，此情况从图5中的AB段可以看出。然而，通过对本文混合路径规划算法的使用，能够借助全局路径规划找出子目标点，并以此对机器人进行引导，使机器人具备绕过U型障碍物的能力，从而顺利到达目标点。同时，通过双层路径规划算法的应用，还能够使机器人在行走至狭窄的走廊路径时，保持平滑、笔直的运行轨迹，说明本文构建的算法具有一定的可行性。

7 总结

通过上述的改进可以看出，在对移动机器人进行路径规划中，采用单一的路径规划方法往往得不到最佳路径，同时也起不到有效避障的效果。因此，在实际应用中，往往采用混合算法，从全局和局部的角度进行综合路径规划，以此改变以往路径规划的弊端。

参考文献

[1] 李阳，卢健，何耀帧. 基于ROS系统自主路径规划与避障小车的研究[J]. 科技风，2018（4）：248.

[2] 陈峰，赵萍. 休闲园林割草机器人设计及性能测试[J]. 农机化研究，2018，40（10）：82-85.

[3] 张晓玲，王正存，吴作君. 基于改进蚁群算法的机器人路径规划[J]. 中国石油大学胜利学院学报，2018，32（2）：44-47.

[4] 晋晓飞，王浩，宗卫佳，等. 自主移动机器人避障技术研究现状[J]. 传感器与微系统，2018，37（5）：5-9.

[5] 秦承志，呼雪梅. 栅格数字地形分析中的尺度问题研究方法[J]. 地理研究，2014，33（2）：270-283.

[6] 方啸，郑德忠. 移动机器人自主寻路避障启发式动态规划算法[J]. 农业机械学报，2014，45（7）：73-78.

[7] 王哲，孙树栋，曹飞祥. 动态环境下移动机器人路径规划的改进蚁群算法[J]. 机械科学与技术，2013，32（1）：42-46.

[8] 邹益民，高阳，高碧悦. 一种基于Dijkstra算法的机器人避障问题路径规划[J]. 数学的实践与认识，2013，43（10）：111-118.

[9] 余翀，邱其文. 基于柵格地图的分层式机器人路径规划算法[J]. 中国科学院大学学报，2013，30（4）：528-538.

[10] 翟红生，王佳欣. 基于人工势场的机器人动态路径规划新方法[J]. 重庆邮电大学学报（自然科学版），2015，27（6）：814-818.

[11] 余勇. 基于改进蚁群算法的移动机器人路径规划研究[J]. 机械传动，2016，40（7）：58-61.

[12] 贾庆轩，陈钢，孙汉旭，等. 基于A～*算法的空间机械臂避障路径规划[J]. 机械工程学报，2010，46（13）：109-115.

[13] 陈雄，赵一路，韩建达. 一种改进的机器人路径规划的蚁群算法[J]. 控制理论与应用，2010，27（6）：821-825.

[14] 张紫辉，熊岳山. 未知环境下基于A～*的机器人路径规划算法[J]. 计算机工程与科学，2012，34（11）：141-147.

[15] 左大利，聂清彬，张莉萍，等. 移动机器人路径规划中的蚁群优化算法研究[J]. 现代制造工程，2017（5）：44-48.

[16] 张彪，曹其新，王雯珊. 使用三维栅格地图的移动机器人路径规划[J]. 西安交通大学学报，2013，47（10）：57-61.

（收稿日期： 2018.12.10）

作者简介：张益辉（1972-），男，本科，高级工程师，研究方向：智能巡检机器人、电力信息化。

王长宁（1982-），男，硕士，工程师，研究方向：智能巡检机器人、电力信息化。

孙玲（1977-），女，硕士，高级工程师，研究方向：智能巡检机器人、电力信息化。文章编号：1007-757X（2020）02-0120-04