英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
基于改进A*算法的智能移动机器人的路径规划
摘要
针对自主阅兵机器人在室内环境下的路径规划算法问题，本文提出了一种新的路径规划算法，基于Dijkstra算法和A*算法，介绍了当前节点的父节点对A*算法中启发式函数的影响，并寻找最优权重的启发式函数来优化路径规划算法。在MATLAB环境下，对不同的场景进行了仿真，并与未改进的情况进行了搜索消耗时间、路径代价和遍历网格数等指标的比较。在使用更合理的启发式函数和适当地改变权值之后，改进了A*算法在一条小路的花费实时性差的缺点。
关键词：移动机器人；路径规划；A*算法；启发式函数；父节点
1ˊ介绍
自主移动机器人是一种在无人工控制的情况下能够通过传感器移动并执行任务的机器人。它可以代替处于危险环境中的人类去工作。
路径规划是自主移动机器人的基础，这意味着机器人根据特定的索引寻找从起点到目的地的路径。有很多种公有的道路规划方法。传统的方法是基于 在网格或人工势场上，而新的方法是基于模糊逻辑或神经网络。
最经典的路径规划算法是Dijkstra算法，属于遍历搜索型算法。它易于使用，并且能够得到最短的路径。但是，当网络中的节点数量较大时，算法的效率将会很低。因此，人们提出了一些启发式搜索算法，如局部最优搜索法、最优优先搜索法、A*算法等。 A*算法是近年来比较常用的一种启发式路径规划算法，由Nilsson于1980年提出。它是一种基于区域的全局规划算法，属于启发式搜索的最佳搜索方法。但是A*算法在路径规划方面的计算效率较低，所选路径与最优路径有偏差。
本文通过介绍当前节点的父节点效应对A*算法进行优化，寻找启发式函数的最佳最优权重并对A*算法在速度和遍历节点数方面的性能进行了评价。
2.算法描述
最常用的路径规划的算法有Dijkstra算法和A*算法，其中Dijkstra算法是A*算法的基础。本文的改进A*算法是在原有的A*算法的基础上提出的，为了改进A*算法，我们要先了解Dijkstra算法和A*算法的原理。
2.1Dijkstra算法
作为A*算法的基础，Dijkstra算法使用贪婪算法求解单个源点到有向图中某一点的最短路径问题，它的主要特点是选择的下一个顶点是除了规范点之外的距离源点最近的顶点。
考虑到Dijkstra算法计算的是从源点到目标点的最短路径，以牺牲计算速度为代价，可以达到很高的精度和综合性。
图1 Dijkstra算法的基本思想
Dijkstra算法的基本思想如图1所示，假设问题是找到从源点v0到目标点V9的最短路径。箭头表示最短路径，圆圈中的数字表示从源点到采取此节点的最短路径的最佳路径的成本，箭头上的数字表示从起点到终点的成本。 该算法计算所有路径的代价，并通过比较选择最短路径代价。 在最优路径的选择方法中，算法的关键部分是从未标记的节点中找出距离源点最近的节点，并将其加入到未标记的节点集合中，同时更新其余未标记节点到起点的最短距离。 经过多次更新，将得到全面的数据。最后，得到全局最优解，并求出剩余节点到起点的最短距离。
2.2A*算法
作为另一种图搜索算法，A*具有搜索地图的大部分区域的潜力。它是一种基于Dijkstra算法和BFS算法的启发式搜索算法。A*可用于搜索最短路径，这是因为A*的组成包括Dijkstra算法。A*可以通过启发式函数引导自己寻找路径，因为它还包括BFS算法，这是BFS的核心功能。简单来说，它和BFS一样快。在路径搜索过程中，使用代价函数来评估节点的质量，该算法选择下一步费用最小的节点作为代价节点。然后它将继续从下一个节点搜索，直到到达目标点。像BFS一样，A*可以使用启发式函数来引导自己。A*算法的代价函数如下：
f(n)=g(n) h(n) (1)
式（1）中，n是路径上的最后一个节点，g（n）是从起点到n的路径代价，h（n）是估计n到目标的路径代价的启发式函数，一般g（n）是固定值，h（n）根据路径选择而变化。 只有选择合适的h（n）值，才能得到最优路径。目前还没有一个选择h（n）的固定标准。如果功能h（n）改变，计划的路径可能改变。我们可以根据需要设置h（n）。在选择最合适的h（n）类型时，频率最高的启发式函数是曼哈顿距离。它考虑了从一个位置移动到下一个位置的最小成本D。因此，启发式函数可以设置为曼哈顿距离的D倍。曼哈顿距离公式如下:
(2)
我们也可以使用简化的曼哈顿距离，也就是切比雪夫距离,此函数选择水平和垂直坐标差中较大的一个作为距离。切比雪夫距离公式如下：
(3)
然而，曼哈顿距离和切比雪夫距离不能直接反映两点之间的距离。欧几里德距离更为实用，因此本文选择了欧几里德距离,以两点之间的距离作为启发式量。欧氏距离公式如下：
(4)
A*算法主要使用两个列表：Open列表和Close列表来存储相关的节点信息。Open队列主要保存已生成但尚未访问的节点信息，Close队列主要保存已访问的节点信息。可以通过在当前节点周围的4或8个方向上遍历子节点来选择节点。可以通过以下规则选择子节点：
- 如果子节点是障碍，则忽略此节点。
- 如果节点在Open列表中，则需要对其进行判断。如果A*算法选择的当前代码到子节点的路径成本小于覆盖父代码的路径成本，则将当前节点设置为子节点的父节点。然后修改子节点的g（n）和h（n）值。否则将忽略子节点。
- 如果不满足上述情况，则会找到一个新生成的节点，并将其插入打开的列表中。
3.算法改进
A*算法只引入当前临时标记节点到目标节点的距离作为算法的启发式代价，这使得在规划路径时不太合理。但如果增加启发式代价对A*算法评价函数的影响，则该算法在路径规划中的搜索方向更倾向于有目的地接近终点，因此该算法效率更高。
另一方面，A*算法的成本评估功能只是直接将实际成本和启发式成本相加。事实上，在最优成本评价函数中，实际成本和启发式成本的权重往往不相等。因此，对不同环境下的启发式成本设置一定的权重，可以提高a*算法的成本评估功能。
3.1引入父节点的A*算法
基于A*算法评估当前节点的思想，将当前节点的父节点加入到改进的A*算法中，计算节点到端点的距离。公式如下：
（5）
其伪码如下：
Procedure Modified_Astar
initialize open list and closed list;
add the starting point into open list;
while open list not empty
choose a node from open list;
delete the node;
if it is the terminal point then
get the path;
for each child point Y
if Y is not in either list then
find the value of Y;
add Y into open list;
else if Y is in open list then
compare the value of Y;
update open list;
else if less than value of closed list then
update the value of closed list;
remove Y to open list;
end if
end if
end if
end for
add X to closed list;
rank the nodes in open list;
end while
该算法的核心思想是将当前临时标记节点到搜索起点的最短距离、当前临时标记节点到目标节点的距离和当前临时标记节点的父节点到目标节点的距离的计算值之和作为评估节点在最佳路由上的可能性的度量。假设当前临时标记节点为n，且该节点的父节点设置为p，则改进后的求值函数可以写成公式（6）：
(6)
其中，g（n）和h（n）具有与A*算法相同的含义，h（p）是当前临时标记节点的父节点到目标节点的距离。
改进后的估计函数使A*算法的搜索方向在算法搜索中更有针对性地向终点逼近，从而减少了算法中的遍历点数，提高了算法的速度。如果需要，甚至可以引入当前节点的父节点的父节点。需要注意的是，并不是评价点越多，算法的效率就越高。 虽然算法中涉及的节点数量随着评价点数的增加而减少，但是存储容量和评价值的数量都会增加，这意味着算法的负担会更重。
对于最一般的路径规划问题，本文模拟了一般的A*算法和引入父节点的A*算法
图2 A*算法的搜索结果
图3 引入父节点的A*算法的搜索结果
在MATLAB中。本文建立了50times;50栅格栅格地图，随机放置了不同大小和形状的障碍物作为仿真场景。
在MATLAB中，A*算法和改进的A*算法的仿真结果如图2和图3所示。暗块是一个障碍物，虚线是路径规划的路径。折线的两点是路径规划的起点和终点，较暗的背景是光栅地图中的单位。从路径规划的结果可以清楚地看出，改进的A*算法比A*算法的遍历单元明显少，说明改进的A*算法在路径规划方面远比A*算法强大。在路径规划时间上，改进的A*算法耗时4.1559秒，而A*算法耗时13.9603秒，改进效果非常明显。但是，由于改进的A*算法比A*算法具有更大的启发式量，因此路径搜索不够全面，改进的A*算法在规划路径中的总代价分别大于A*算法65.3102和56.2260个单位。
3.2引入权重的启发式函数
对于A*算法，g（n）和h（n）的系数也非常重要。从公式（1）可以看出，为了将这两个值相加，测量单位必须相同。否则，A*将认为g（n）或f（n）太大或太小，然后无法找到正确的路径，并对操作速度产生不良影响。
在极端情况下，如果h（n）为0，则只有g（n）有效，A*演化为Dijkstra算法，从而确保能够找到最短路径。函数h（n）使用更大的启发式，估计从n到目标的最便宜路径的代价，以限制与路径方向的引导的某些偏差。如果h（n）通常小于（或等于）从n移动到目标的实际成本，那么A*保证可以找到最短路径。h（n）越小，A*扩展的节点越多，运行越慢。如果h（n）正好等于从n移动到目标的代价，那么A*将只寻找最佳路径而不扩展任何其他节点，这将大大减少计算量，并且A*将非常快地运行。虽然很难实现，但只要你能提供完美的信息，在某些特殊情况下，他们完全可以平等。在另一个极端情况下，如果h（n）大得多，则只有h（n）有效，A*算法将演变为BFS算法。
考虑父节点的A*算法也会出现同样的问题。启发式代价h（n） h（p）与实际代价g（n）之间的关系也会影响路径的选择和算法的速度。
针对上述问题，引入了启发式函数的权重。非最优路径规划的原因是考虑父节点的A*算法的启发式代价与实际代价相比太高。 因此，本文提出通过增加一个适当的系数来减少启发式的作用，从而提高A*算法的启发式数量。进一步改进的评价函数可以写成公式（7）：
（7）
一般来说，启发式算法的权重和实际成本不能太大。如果启发式代价太大，则规划路径陷入局部最优解的概率就非常大，这使得规划路径和最优路径变化很大。因此，启发式函数的权重一般设置在1左右。本文将A*算法和考虑父节点的算法分别设为0.5和0.5。MATLAB仿真结果如图4和图5所示：
图4 带父节点和启发式函数权重的A*算法的搜索结果
图5 启发式函数权重A*算法的搜索结果
从图中可以清楚地看到，穿越的网格数从593和212个节点分别增加到923和338个节点，路径规划时间从13.9603秒和4.1559秒分别增加到24.1771秒和7.2228秒。然而，路径的代价分别从56.2260和65.3102降低到55.9091和58.4023，几乎等同于A*算法。 可以看出，牺牲路径选择的效率可以提高规划路径的质量。
4.模拟与分析
针对移动服务机器人的典型场景，选择了典型的室内环境，构建了室内地图。同时，本文还考虑了房间大小和室内装修等因素，使地图更符合室内实际情况。在这种环境下，本文对上述算法进行了仿真，并对仿真结果进行了分析和比较。光栅地图设置为50*80网格。
4.1.Dijkstra算法和A*算法
首先，对Dijkstra算法和A*算法进行了仿真，仿真结果如图6和图7所示。
从图6和图7可以看出，两种常用的路径规划算法都穿越了大量的网格。Dijkstra算法遍历了所有的网格，在耗费大量时间和计算量的前提下找到了最优路径。A*算法的实时性稍强。
图6 Dijkstra算法在室内环境中的搜索结果
图7 A*算法在室内环境中的搜索结果
4.2引入父节点的A*算法
从图8可以清楚地看出，考虑父节点的A*算法显著减少了遍历的网格数。从实验结果看，两种情况下的时间分别为10.1362秒和63.7900秒，但路径成本分别为126.1070和121.9172。
lt;
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[239633]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
