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

陈若男 文聪聪 彭玲 尤承增

摘 要：传统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算法、最佳优先算法、启发式搜索算法。Dijkstra算法是典型的广度优先算法，优点在于总是可以找到最优化路径;但搜索效率低，难以满足快速规划路径的需求。最佳优先算法BFS（Best-First-Search）与Dijkstra算法最大的差异是以与目标节点之间的距离作为评估，这种算法能够快速引导向目标节点搜索，大幅度提高算法搜索效率;但往往不能获取合理的最短路径。A*算法[8-10]是结合上述两种算法优势提出的一种启发式搜索算法。它利用启发信息来引导搜索方向，从而减小搜索范围，提高搜索效率。

继A*算法之后，还有诸多新算法的提出，如D*算法（又称动态A*算法）[11]，该算法遇到动态环境时无需重新规划，但是针对环境复杂的大区域地图，存储量会激增，且动态障碍频繁出现时仍要重新规划。还有诸多智能生物算法，如遗传算法模拟进化论观点，执行效率较高;缺点在于占用存储空间大，个体编码方式和初始种群的确定难度高[12-13]。

因此，A*作为经典算法，以其实用性至今被广泛应用，并且对不同场景具有很强的扩展性和适应性。研究学者们针对不同应用场景，作出不同改进。在移动机器人路径规划方面，王殿君[14]解决了传统A*算法路径包含过多冗余点的问题，并得到拐点处的最小转折角度，明确机器人转向;辛煜等[15]提出无限邻域的A*算法思想解决了运动方向被限定为π/4的倍数问题，但搜索速度会降低;顾辰[16]通過采用优先级的子节点生成策略来避免了生成穿过障碍物栅格顶点的路径，但路径依然存在较大安全问题;Botea等[17]提出了HPA*（Hierarchical Path-finding A*）算法，该算法通过减少搜索空间来提高速度，但往往不能获取最优路径;Goldberg等[18]通过提高启发函数的准确度来提高效率，但空间复杂度高;高民东等[19]提出了一种双向时效A*算法寻找路径，并采用多近邻栅格距离计算方案，以达到提高效率、平滑路径的效果，但不适合大尺寸复杂地图。

从以上分析可看出，虽然不少研究人员针对A*算法进行了改进，但仍未能很好地解决以下问题：忽略了机器人大小而造成的安全性问题;多U型障碍的室内环境中算法效率不高的问题。

为解决上述问题，本文主要对传统A*算法进行两方面的改进：1）采用邻域矩阵的方式来进行障碍搜索，以此达到通过选择矩阵大小来适应机器人实际大小的目的，解决传统A*算法规划路径过于紧贴障碍物的问题。

2）设计新启发函数，以分区加权方式来表达距离信息，以叉积距离来表达角度信息，提高大地图复杂环境下的算法效率，缩短遇到动态障碍再次规划耗费的时间。

1 环境模型

路径规划依赖地图，常见的地图构建方法有可视图法、拓扑图法、栅格法。其中栅格法简洁有效，易于维护，应用广泛[20-22]，所以，本文采用栅格法来建立移动机器人工作环境静态二维地图，以存储机器人工作环境的基本情况，并在此基础上进行全局路径规划工作。通常室内环境由于被分割成多个相邻空间，并散落分布家居等障碍物，存在多个U型类障碍。为保证本文算法的可靠性和稳定性，将多个U型障碍和简单矩形障碍拼接，构建了比真实室内场景复杂度更高的模拟环境，地图尺寸为600×600像素，如图1所示。图1中：深灰色区域为障碍，浅灰区域为自由可通行区域，黑色圆点为起点，白色原点为终点。

2 传统A*算法

A*算法是一种典型的启发式搜索算法，其结合了Dijkstra和BFS两种算法各自的优势，在保证搜索效率的同时，可以得到最优的路径规划[23]。传统A*算法的核心思想体现在综合考虑了起始点到当前节点的真实代價和当前节点到终点的估计代价，因此可以引导搜索方向。

基本规划路径思路是以起点为第一个计算点，计算其八邻域中每个节点的代价值f（n），若某个节点被占用即为障碍物则不入栈。然后取其中f（n）值最小的节点作为下一个计算点，并存储其父节点，直到搜索到终点，最后从终点追溯其父节点获取规划路径。图2为传统A*算法寻路的计算过程示例（此处假定障碍物顶点不可穿越）。

在上述计算路径过程中，忽略了机器人实际大小，将其看作质点，只有障碍物所占用的节点不可通行，其相邻节点均在可通行范围内，所以最终获取的路径将会如图2所示，紧贴障碍物，此类规划路径不适合机器人运动，容易发生碰撞。

另外，在评价函数中，启发函数h（n）对A*算法起主要影响作用：h（n）估值越小，A*算法需要计算的节点就越多，此时算法效率就会降低，逐步趋近Dijkstra算法;但如果h（n）估值很大，甚至远大于g（n），此时g（n）的作用便会失效，逐步趋于BFS算法，只追求速度无法获取合理路径。因此在设计启发函数时，h（n）和g（n）必须要单位相对一致，保证两者对f（n）的贡献相对平等。

本文针对传统A*算法忽略物体本身大小问题，提出一种面向机器人的障碍邻域搜索方法。同时，针对室内环境，构建新的启发函数，提高遇到动态障碍时再次规划的敏锐度。

3 本文算法

3.1 障碍搜索方式的改进

本文提出一种基于邻域矩阵的障碍搜索方式，在实际应用中，需要根据机器人自身尺寸及地图分辨率选择合适尺寸的搜索矩阵，来确定路径与障碍物的间距，保证机器人运行过程中的安全问题。

邻域矩阵搜索对路径规划的影响主要与类型和尺寸有关，本文将通过实验分析这两方面对路径产生的具体影响。

3.1.1 邻域矩阵类型选择

本文中邻域搜索矩阵是指以矩阵中1的个数命名的。以12邻域搜索矩阵（S12）为例，判断当前节点是否可通行的依据是：矩阵中心点（3，3）对应当前节点，此时标识为1的位置对应节点若均为自由节点（非障碍），则认为当前节点可通行;反之认为不可通行。根据邻域搜索方向分布可分为十字搜索和米字搜索两类。两者的区别是后者搜索矩阵四个顶点上值也为1。

基于前文构建的地图环境，分别对两类搜索矩阵进行测试，图3是两类方法规划路径的对比。表1是两类方法规划效率的对比，以搜索范围、搜索时间、路径长度为评价标准。其中搜索范围是指搜索过程中所涉及计算的节点栅格总数，搜索时间是指搜索总过程耗费的时长，路径长度是指从起点到终点规划路径的栅格节点总数。

图3表明在矩阵大小相同的情况下，两种搜索方式获取的路径与障碍物的最小间隔一致且不影响基本路径走势。从定性角度分析，两种方法的搜索范围（深灰色区域）差距不明显。

表1定量地对比了相同间隔时，不同搜索矩阵类型对算法效率和规划路径的影响。表1中间隔为路径与障碍物间的空闲节点数，根据实验对比可知：在三组实验中，从搜索效率分析只有间隔为1个节点时，米字搜索范围比十字搜索少42个节点，略占优势，但由于米字搜索中每一单元格都比十字多四个节点的计算量，因此即使搜索范围较小，耗费的总搜索时间却依然相对更长。且随着间隔的扩大，米字搜索对搜索范围的缩小能力逐渐弱于十字搜索。从路径角度分析，米字搜索法获取的路径始终比十字搜索要长。总的来看，十字障碍搜索法比米字效率更高，规划路径更优，因此采用十字障碍搜索邻域。

3.1.2 邻域矩阵大小的选择

在确定十字障碍搜索法后，需要选取合适邻域矩阵的大小，矩阵大小决定了障碍物与路径之间的间隔，对计算效率也有相应影响。图4为邻域变化与路径、障碍间隔大小间的关系。随着邻域的增大，规划路径与障碍物的最小间隔增大，如在传统A*算法中，规划路径紧贴障碍物，即忽略了机器人大小。而利用36邻域搜索障碍得到的路径与障碍物间保有明显的间隔，从而大幅降低了移动机器人在执行命令时的碰撞概率。

从另一方面考虑，随着邻域的增大，可达到与建图时“障碍膨胀”相同的效果，所以搜索邻域越大，认为是不可通行的节点数就会增加，相应地减少了需要计算的节点，总体上会提高规划速度。与此同时，为了远绕障碍，规划的路径长度会有所增加。图5量化了路径长度、搜索时间与邻域变化的关系，可看出邻域增大对算法确实有双向影响，一方面提高搜索效率，但另一方面却会使路径长度增加。

在应用中，需要结合机器人的尺寸以及室内地图的分辨率，计算出安全间隔对应的栅格数，然后选择一个能满足安全性前提且路径较短的邻域矩阵。

由于障碍搜索的改进方式侧重路径的安全性与最优性，效率的提升是下一步启发函数的侧重点，所以在选择矩阵时，路径长度短比搜索时间短优先级高。

3.2 启发函数的改进

结合距离信息和角度信息本文设计的新启发函数如下：

3.2.1 距离信息表达

常用的距离估算方式有曼哈顿距离、切比雪夫距离、欧几里得距离。曼哈顿距离是标准A*的启发函数，以X、Y方向上的距离差的绝对值之和作为估计距离，意味着只允许向上下左右四个格网运动;切比雪夫距离取X、Y方向距离差中较大的为距离估算值，即允许对角线运动，且对角线运动和水平垂直运动的代价一致;欧几里得距离则是最常见的两点一线距离计算方式，可用于沿任意角度移动的情况，其比前两种距离都短，在有障碍的情况下这种计算方式和实际距离会有较大差距。因为欧几里得距离和切比雪夫距离在障碍复杂环境下与真实代价的偏差较大，所以本文选择在多障碍环境下距离估计更准的曼哈顿距离更为合适。

为避免邻域中代价相同而造成的路径不确定性和抖动现象，将坐标差加权后再求和。通过设置十组权值比{1∶9， 2∶8，…，9∶1}进行路径搜索，最后确定权值比6∶10效率最高，即p=6，q=10。

而分区加权是为了起到一定的方向引导作用。分区加权对引导作用的体现如图6所示，以终点为坐标原点，以X=Y作为分割线，左下方区域中当前点到终点在X方向距离差大于在Y方向距离差，此时定义Y1的权重为大系数，由于在选择计算点时优先选择代价小的节点，故将会引导搜索方向朝Y1小的方向前进（箭头标识），同理分割線右上方的区域则会朝X1小的方向前进（箭头标识），从而引导搜索方向朝起止最短连线靠近。分析起止线左偏的情况同样适用。

3.2.2 角度信息表达

在式（3）中还加入了角度信息，它是两个向量叉积结果的模，这两个向量分别是起点到终点的向量和当前点到终点的向量。

其中：角度信息表达cross是依据叉积计算获取的;通常情况下起止点距离|AB|是常量;而|CD|是随着两向量夹角变化而变化的量，当两者平行时|CD|达最小值，当两者垂直时|CD|达最大值，它很好地以距离的形式反映了两者间的角度关系。

因此，在启发函数中加入角度信息变量cross可诱导A*算法偏向拓展分布在起始点到目标点连线附近的节点。

此外，因为cross的量纲是距离的平方，前文提及过，g（n）和h（n）必须要保持量纲平衡，不然可能会导致g（n）或h（n）的失效。本该对cross作开方然后叠加到h（n）中，考虑到开方对计算机而言是高复杂度的计算方式，所以选择乘上系数m来达到近似开方的效果。m*cross=cross，即m=1/cross 本文实验地图为600×600像素， 故本文实验crossmax=360000经计算预估m≈0.0017。由于m是递减函数，随着L增大而缩小。且cross最大值位于100000～1000000，根据单调递减函数特性，可知对应m阈值为[0.001，0.003]。

但由于式（3）中距离信息中进行了加权操作，为了保持角度信息和距离信息贡献量一致，取距离权值6，10的平均值8对角度信息进行操作，即w=8*m。故w预估值为0.0136，阈值为[0.008，0.024]。通过二分法，进行实验，最终确定w为0.014，与预估值相近。

4 实验与结果分析

为了验证本文算法的可行性和有效性，基于Matlab2017a环境进行仿真实验。将本文算法与传统A*算法、双向时效A*算法[19]以及提升安全性的文献[16]算法进行对比，分析定性和定量结果。实验中本文算法的障碍搜索方式采用12邻域十字搜索矩阵（S12）。

图8是本文算法与传统A*算法路径效果的定性对比：传统A*算法路径紧贴障碍物，规划搜索范围大;改进其障碍搜索方式后，路径与障碍物间有了安全间隔（浅灰色区域），且搜索范围（深灰色区域）有所缩减，主要缩减量体现在靠近障碍物的区域。在此基础上，进一步改良启发函数后获取的路径，在无障时基本走两点间最短直线，在遇障时以小短折线形式绕过障碍，与原先随机转向相比，更加契合人类思维。与此同时，发现搜索范围明显缩小了，表明新启发函数的导向能力更强。

表2是算法改进前后规划效率的定量对比。与传统A*算法相比，本文路径长度增加了6.63%，这主要消耗在保证路径安全性上（增加了6.16%），是为了避开障碍物才产生的路径长度增加效应。除此项性能降低外，搜索栅格范围缩小66.55%，体现了本文算法搜索方向聚拢效果增强;操作总次数减少了37.93%，体现出搜索方向的引导效果好，减少了需要比较计算的节点数;搜索耗费时间降低了28.07%。

本文算法最大的特点是保证了路径安全性，目前A*优化算法中少有研究考虑路径安全性问题，而这对机器人导航来说这至关重要。

文献[16]提出了一种采用优先级的子节点生成策略来避免路径穿过障碍物栅格顶点，效果如图9（b）所示。该算法得到的路径所在栅格依然与障碍物为相邻单元格，并无间隔。

在实际应用中，真实地图的分辨率往往远小于机器人的实际体积，因此依然存在很大的安全隐患。且文献[16]提出的优先级策略从一定程度上加大了一些计算量：当前点N的上下左右为一级节点，对角线为二级节点。二级节点是否扩展除了要判断其自身是否为障碍物外，还需要考虑相邻一级节点是否为障碍物。

而本文算法不仅能够保证路径整体与障碍物间有空闲单元格（如图9（c）），还减少了算法的扩展节点。此外，间格的多少可以通过改变障碍邻域搜索矩阵大小来控制。因此可以满足不同机器人尺寸和不同栅格地图分辨率的应用需求。

此外，本文算法的效率在复杂大地图环境下有一定的优势。文献[19]提出了一种双向时效A*算法，并采用多近邻栅格距离计算方案，以达到提高效率、平滑路径的效果。表3是双向时效A*算法和本文算法分别与传统A*算法效率对比的结果。文献[19]中设立了5个实验场景（表3中的实验1～5），分析表3可知该算法相对传统A*算法，计算效率显著提高，但也有一定的局限性。首先对比实验1～3，发现该算法对椭圆障碍的搜索效率远大于对矩形障碍。对比实验3和4，发现随着地图尺寸增大，算法效率提升效果降低。说明该算法的高效率特性需要建立在一定的前提下，对障碍类型和地图尺寸有一定的要求。

在实验5中，以大地图和中等复杂程度的障碍物为实验环境，文献[19]算法计算速度比传统A*算法提高36.11%。

而本文以600×600的大地图和高复杂程度的障碍为实验环境（图8），较传统A*算法，效率提高28.07%。因此，而文献[19]算法在简单小地图环境里表现突出，而本文算法更合适复杂大地图的应用场景。

综合评价，本文算法虽然在路径长度上有所牺牲，但保证了路径的安全性，能够在一定程度上避免机器人运行过程中发生碰撞;与此同时，算法的效率得到了提升，适用于室内多U型障碍的应用场景，使得机器人在遇到动态障碍时再次规划实时性更好。

5 结语

本文针对传统A*算法在室内机器人路径规划应用中的问题进行改进：首先，采用十字多邻域矩阵搜索障碍解决原先忽略机器人大小造成的安全性问题;然后，设计新启发函数，引入分区加权距离信息和角度信息，提高复杂多U型障碍的室内环境下的搜索效率，以缩短遇到动态障碍再次规划所耗费的时间。

仿真实验结果表明：本文算法可通过选择不同尺寸的搜索矩阵来自定义路径与障碍物的间距，方便地解决了不同尺寸机器人安全路径的问题;且在复杂大环境下计算效率得到提高，使得遇到动态障碍时再次规划的灵敏度提升。下一步工作将会考虑删除路径中的冗余节点，以进一步提高机器人运行效率。

参考文献（References）

[1] 王丽苹. 机器人技术变迁及产业发展战略研究[D]. 天津， 天津大学， 2016： 1. （WANG L P. The study of development strategy and technological change of robot industry [D]. Tianjin： Tianjin University， 2016： 1.）

[2] 康凯. 基于机器视觉的移动机器人定位与三维地图重建方法研究[D]. 哈尔滨： 哈尔滨工业大学， 2017： 1-2. （KANG K. Research on localization and mapping of mobile robot based on machine vision [D]. Harbin： Harbin Institute of Technology， 2017： 1-2.）

[3] JEDDISARAVI K， ALOTAPPEH R J， PIMEMTA L C A， et al. Multi-objective approach for robot motion planning in search tasks [J]. Applied Intelligence， 2016， 45（2）： 305-321.

[4] 彭利民. 基于广度优先搜索的虚拟网络映射算法[J]. 四川大学学报（工程科学版）， 2015， 47（2）： 117-122. （PENG L M. Virtual network embedding algorithm based on breadth-first search [J]. Journal of Sichuan University （Engineering Science Edition）， 2015， 47（2）： 117-122.）

[5] 劉艳丽， 樊晓平， 张恒. 基于启发式搜索的移动机器人主动定位[J]. 机器人， 2012， 34（5）： 590-595. （LIU Y L， FAN X P， ZHANG H. Heuristic search assisted active localization for mobile robot [J]. Robot， 2012， 34（5）： 590-595.）

[6] 房佳， 杜震洪， 张丰， 等. 应用于城市道路网的启发式深度优先有向搜索算法[J]. 浙江大学学报（理学版）， 2013， 40（4）： 469-474. （FANG J， DU Z H， ZHANG F， et al. Heuristic depth-first directional algorithm for shortest path searching in traffic networks[J]. Journal of Zhejiang University （Science Edition）， 2013， 40（4）： 469-474.）

[7] BURNS E， LEMONS S， ZHOU R， et al. Best-first heuristic search for multi-core machines [J]. Journal of Artificial Intelligence Research， 2010， 39（1）： 689-743.

[8] FRANTISEK D， ANDREJ B. Path planning with modified a star algorithm for a mobile robot [J]. Procardia Engineering， 2014， 96（1）： 59-69.

[9] UTTENDORF S， EILERT B， OVERMEYER L. Combining a fuzzy inference system with an A* algorithm for the automated generation of roadmaps for automated guided vehicles [J]. at-Automatisierungstechnik， 2017， 65（3）： 189-197.

[10] WODZINSKI M， KRZYZANOWSKA A. Sequential classification of palm gestures based on A* algorithm and MLP neural network for quadrocopter control [J]. Metrology and Measurement Systems， 2017， 24（2）： 265-276.

[11] 张晓冉， 居鹤华. 采用改进D*Lite算法的自主移动机器人路径规划[J]. 计算机测量与控制， 2011， 19（1）： 155-157. （ZHANG X R， JU H H. Developed D* Lite algorithm for path planning of autonomous mobile robots [J]. Computer Measurement & Control， 2011， 19（1）： 155-157.）

[12] 徐美清， 孙晨亮. 基于栅格地图的遗传算法路径规划[J]. 科技信息， 2011（31）： 76-77. （XU M Q， SUN C L. The occupancy grid map-building with neural network [J]. Science & Technology Information， 2011（31）： 76-77.）

[13] 李天旭， 陈广大.基于改进遗传算法的室内移动机器人路径规划[J]. 制造业自动化， 2015， 37（20）： 31-35. （LI T X， CHEN G D. Indoor mobile robot path planning based on improved genetic algorithm [J]. Manufacturing Automation， 2015， 37（20）： 31-35.）

[14] 王殿君. 基于改进A*算法的室内移动机器人路径规划[J]. 清华大学学报（自然科学版）， 2012， 52（8）： 1085-1089. （WANG D J. Indoor mobile-robot path planning based on an improved A* algorithm [J]. Journal of Tsinghua University （Science and Technology）， 2012， 52（8）： 1085-1089.）

[15] 辛煜， 梁华为， 杜明博， 等. 一种可搜索无限个邻域的改进A*算法 [J]. 机器人， 2014， 36（5）： 627-633. （XIN Y， LIANG H W， DU M B， et al. An improved A* algorithm for searching infinite neighborhoods [J]. Robot， 2014， 36（5）： 627-633.）

[16] 顾辰.改进的A*算法在机器人路径规划中的应用[J]. 电子设计工程， 2014， 22（19）： 96-98， 102. （GU C. Application of improved A* algorithm in robot path planning [J]. Electronic Design Engineering， 2014， 22（19）： 96-98， 102.）

[17] BOTEA A， MULLER M， SCHAEFFER J. Near optimal hierarchical path-finding [J]. Journal of Game Development， 2004， 1（1）： 7-28.

[18] GOLDBERG A V， HARRELSON C. Computing the shortest path： A*search meets graph theory[C]// Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. New York： ACM， 2005： 156-165.

[19] 高民东， 张雅妮， 朱凌云. 应用于机器人路径规划的双向时效A*算法[J]. 计算机应用研究， 2019， 36（3）： 792-795，800. （GAO M D， ZHANG Y N， ZHU L Y. Bidirectional time-efficient A* algorithm for robot path planning [J]. Application Research of Computers， 2019， 36（3）： 792-795，800.）

[20] 余翀， 邱其文. 基于栅格地图的分层式机器人路径规划算法[J]. 中国科学院大学学报， 2013， 30（4）： 528-538， 546. （YU C， QIU Q W. Hierarchical robot path planning algorithm based on grid map [J]. Journal of University of Chinese Academy of Sciences， 2013， 30（4）： 528-538， 546.）

[21] 程向红， 祁艺. 基于栅格法的室内指示路径规划算法[J]. 中国惯性技术学报， 2018， 26（2）： 236-240， 267. （CHENG X H， QI Y. Indoor indicator path planning algorithm based on grid method[J]. Journal of Chinese Inertial Technology， 2018， 26（2）： 236-240， 267.）

[22] 朱愛斌， 刘洋洋， 何大勇， 等. 解决路径规划局部极小问题的势场栅格法[J]. 机械设计与研究， 2017， 33（5）： 46-50. （ZHU A B， LIU Y Y， HE D Y， et al. An improved potential field-grid method for local minimization problem in path planning [J]. Machine Design and Research， 2017， 33（5）： 46-50.）

[23] PETER E， NILSSON J， RAHEAL B. A formal basis for the heuristic determination of minimum cost paths [J]. ACM SIGART Bulletin， 1972， 4（37）： 28-29.