摘 要: A*( A-star) 算法是无人船全局路径规划中常用的算法之一，但是其规划的路径是不平滑、局部最优解的问题困扰着研究人员。针对该问题提出一种基于 A*算法改进的路径规划算法。该算法在栅格化的二维环境模型上扩大节点搜索邻域至 24 和 48 邻域，在更大的优化空间内得到全局最优解，且路径更加平滑。仿真实验结果表明，该算法在路径最短的基础上能够提高拐点的平滑度和路径的安全性。 引言
刮膜棒无人船( unmanned surface vessel，USV) 是一种无人操作的水面船。它凭借自主性、低风险性和环境适应能力强等特点，具有很高的军用和民用等应用前景，其主要功能是代替人执行一些特殊的、对人有危险的任务。
路径规划研究内容是在给定的环境下生成一条安全、合理的路径。根据给定场景的不同，可分为全局路径规划和局部路径规划。前者是从开始到一个完整的端到端路径，是这段路径中局部规划的总和; 而后者则是根据运动过程中实时变化的环境进行实时规划。这两者关系是可以相互转换的，如局部算法可以看做很短一段路径内的全局规划，同理，全局规划也是如此。现在常用的全局规划算法包括可栅格法和视图法等; 而局部路径规划算法包括人工势场
法和遗传算法等。上述这些都是启发式类算法，在目前的路径规划算法研究中，多数算法都是基于启发式思想实现的，包括蚁算法和粒子算法等。
遗传算法是利用迭代求解最优路径，但是实现较为复杂，且运算效率很低; 蚁算法是一种进化算法，优点是可以并行实现，但是在参数设置方面需要丰富的经验。人工势场法是一种基于长“场”的算法，当障碍物距离目标点太近时，易形成“死区”，在实际中难以应用。A*算法在 1969 年被提出，因其运算效率远高于当时主流的Dijkstra 算法而得到了广泛的关注。学者们将它应用于路径规划当中，发现其效率和结果完成度远高于其他算法，之后 A*算法便被使用在路径规划方面。而在之后的研究中，很多研究者都对其进行了改进，也取得了显著的成果。例如 Koenig 等人提出的 LPA*(long life planning A*) 算法在A*算法的基础上融入了人工智能领域“增量搜索”思想。但是 A*算法在实际应用场景中规划的路径是局部最优解，且路径不平滑，本文提出一种基于 A*算法的改进算法，在栅格图中扩大节点的搜索邻域至 24 和 48 邻域，得到全局最优路径且更加平滑的路径。
1 基于 A*算法的改进
1.1标准 A*算法区域能源管理
A*算法在静态环境下( 全局路径规划) 是最有效、最直接的一种搜索方法，表示为 f(n) = g(n) + h(n) 。其中: f(n) 是从初始节点( 位置) 到目标节点的成本估算，而在此过程中需要付出的实际代价用 g(n) 表示; h(n) 称为估算成本或启发信息，一般依据经验值选定。通常使用两者的曼哈顿距离来表示 h(n) ，即在栅格图中不考虑障碍物的情况下，初始节点到目标节点在标准坐标系的距离总和，表示为
hca2h( n) = | x1－ x2| + | y1－ y2| (1)
其中: (x1，y1) 表示起始节点; (x2，y2) 表示目标节点。
1.2 算法步骤和流程
A*算法是借助两个独立的列表完成对路径搜索的。在算法进行时，每搜索一个节点，算法就将这个节点进行分类放置。在所有节点完成搜索后应该得到一个放满的列表，这个列表中的元素按照放入的顺序输出就能得到 A*算法规划的最优路径。A*算法运行流程如下:
a) 新建 open 和 close 列表，在 open 列表中添加起始节点 S。
b) 按照算法遍历开发列表中的所有待搜索节点，直至所有待搜索节点遍历结束。若 open 列表为空，即不存在待搜索的节点，则算法结束。
c) 如果在步骤 b) 中遍历到了待搜索节点，则计算所有待搜索节点到当前节点的距离代价，即 f(n) 值。比较 open 列表中各个节点的 f 值，将最小值对应的节点作为下一步搜索节点，并移至 close列表。
d) 判断步骤 c) 新添加至 close 的节点是否为目标节点，若是算法结束; 否则进行下一步。
e) 重复以上步骤，直至步骤 d) 确定是需要的节点，计算f(m)并将值最小的节点作为下一步节点。
f) 确定节点 m 是否在开放列表和封闭列表中:
(a) 若 open 和 close 列表不包含节点 m，则将节点 m 添加至open 列表中，作为待搜索节点。然后用一个指针将 m 节点与上一节点链接，m 为起始。如果存在可行路径，则根据指针一路到起始节点，并更新最优路径。
一个度导航(b) 若节点 m 在开放列表中，则比较 f(m) 和之前储存的节点m0的价值 f(m0) 的大小。如果 f(m) 比之前节点的价值小，则代表到了更优的路径节点，之后使 m 放入封闭列表，并使 m0指向空集，同时，m0的下一节点变为 m 的父节点。
(c) 若节点 m 存在于闭合列表中，表示该节点已经在当前最优路径上，并返回上一步继续比较其他子节点。
g) 不断重复上述过程，直至到达目标节点(步骤 d) ) ，结束算法，输出规划完成的路径。
算法流程如图 1 所示。
1.3 改进的 A*算法
A*算法规划出路径的优劣与搜索空间有很大的关系。而在仿真中，A*算法只搜索了与当前节点相邻的八个节点，这与建模的方式不无关系。在将环境具体化后，一个节点所占的空间变为一个方块，每个相邻的移动方向的角度为 π/4。无人船的移动方向也被局限在 π/4 的整数倍。在这样的算法情况下，由标准 A*算法计划的最终路径的距离不是全局最优解，而且路径多拐弯不平滑。
解决 A*算法规划的路径不是全局最优、不够平滑的问题就要让算法遍历到更多的节点，增加算法的搜索空间。如图 2 所示，扩大当前节点的搜索邻域。在图 2(a) 中，由 A*算法进行扩展的节点数目是 24，此时当前节点可前进方向同样增加。如果想要更好的平滑效果，在图 2(b) 中，将图中最外围的点同样标记，并将其划分为当前节点可搜索范围之内。以此类推，A*算法的可搜索节点可以这样不断增加，直至前文介绍 A*算法时提到的 h(n) = d(n) 搜索范围和时间适中，搜索效率最高。
改进后的 A*算法流程与标准 A*算法流程大致相同，具体如下:
a) 同标准 A*算法步骤(a) 。
b) 遍历搜索 open 列表中需要扩展的节点。若 open 列表为空，则算法结束，表示无可行路径; 否则对待搜索节点扩展邻域，同时根据约束条件进行筛选。去除不符合约束条件的点，使用价值函数 f(n) 来计算和评估所有扩展节点的值，并且选择 f(n) 最小节点m 来作为下一个节点，将该节点移至 close 列表。
c) 判断由算法扩展的节点是否与 G 一致，如果一致则算法探索路径成功; 如果节点 n 不与目标节点 G 一致，则算法进行下一步。
d) 获取步骤 b) 得到的节点 m 邻域内所有满足条件的节点，比较成本函数 f( n) ，选择最小的节点 m 进行下一步。
e) 判断上述得到的节点 m 与已有的 open 和 close 列表元素的关系:
(a) 若 open 和 close 列表不包含节点 m，将其移至 open 列表，并新建指针变量指向父节点 n。于是，算法执行完成时，根据目标节点指向父节点的性质可以得到规划的路径。
(b) 若节点 m 在开放列表中，则比较 f(m) 和之前储存的节点m0的价值 f(m便携式高压氧舱0) 的大小。如果 f(m) 比之前节点的价值小，则代表到了更优的路径节点。之后使 m 放入封闭列表，并使 m0指向空集。最后将 m 节点的父节点指向 m0的下一节点。如果 f(m) 比之前节点的价值大，则保持节点储存信息。
(c) 若节点 m 存在于闭合列表中，表示该节点已经在当前最优路径上，并返回上一步继续比较其他子节点; 如果节点 m 的封闭列表已经存在，则表明该节点已经是在目前的最佳路径上，并返回到步骤 d) ，继续进行比较和判断，以扩展其他子节点。铝制工艺品
f) 循环步骤 b) e) ，当该算法的下一个节点是目标节点 G 或开放列表是一个空表时，则算
法结束退出。此时，可以得到规划的路径或者没有可行路径。改进的 A*算法主要是在节点的搜索空间上，将原有的搜索邻域由 8 邻域扩展到 24 邻域或者 48 邻域，增大了搜索空间。
2 仿真验证
2．1 环境建模
环境建模的目的是将各种环境、地图等因素抽象为计算机所能理解的计算机模型，采用常用的栅格法进行建模。首先需要进行信息预处理，即对得到的地图进行预处理，主要步骤是二值化和图像膨胀处理。二值化的目的是根据地图生成二值化图，使得黑部分表示障碍物( 无法航行区域) ，白部分表示可航行区域。图像膨胀主要是对障碍物进行膨胀处理，给路径规划留下一定的阈值( 与船舶尺寸有关) ，使得规划的路径是有效的。预处理效果如图 3 所示。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议