智能机器人自适应巡检路径栅格地图邻域搜索算法

Adaptive inspection path grid map neighborhood search algorithm for intelligent robots

摘要

智能机器人巡检过程中的动态障碍物使巡检路径呈现非连续可访问性条件，导致路径可行域突变，难以获取重构路径的可行解，降低了巡检路径规划的转弯平滑度。为此，提出智能机器人自适应巡检路径栅格地图邻域搜索算法。采用栅格地图法对巡检环境建模，通过边界条件处理机制定义路径可行域。引入转弯代价函数改进A^*算法，以栅格地图可行域为巡检环境模型，生成初步转弯平滑巡检路径。针对动态环境下路径突变导致的失效问题，提出基于自适应大规模邻域搜索的巡检路径可行域动态重构方法，利用破坏算子移除部分巡检任务生成不完整路径，引入修复算子重新整合巡检任务，结合变邻域下降搜索策略深入探索解空间，通过自适应邻域算子评分与选择机制实现初步全局巡检路径的局部优化。实验结果表明：该算法可成功避开栅格地图中的动、静态障碍物，实现智能机器人巡检路径规划，巡检路径长度相对较短，路径优化度、转弯平滑度系数、全局搜索能力以及环境适应性评分分别为95.24%、0.917、0.764、91.45。

Abstract

The dynamic obstacles during the inspection process of intelligent robots result in discontinuous accessibility conditions for the inspection path， leading to abrupt changes in the feasible domain of the path and difficulty in obtaining feasible solutions for reconstructing the path， thereby reducing the smoothness of turning in the inspection path planning. To this end， an intelligent robot adaptive inspection path grid map neighborhood search algorithm is proposed. Adopting the grid map method to model the inspection environment， and defining the feasible path domain through the boundary condition processing mechanism. Introducing a turning cost function to improve the A^* algorithm， using a grid map feasible region as the inspection environment model， to generate a preliminary smooth inspection path for turns. Aiming at the failure problem caused by path mutations in dynamic environments， a feasible region dynamic reconstruction method for inspection paths based on adaptive large-scale neighborhood search is proposed. The destruction operator is used to remove some inspection tasks and generate incomplete paths， and the repair operator is introduced to reorganize inspection tasks. Combined with the variable neighborhood descent search strategy， the solution space is deeply explored. The local optimization of the preliminary global inspection path is achieved through the adaptive neighborhood operator scoring and selection mechanism. The experimental results show that the algorithm can successfully avoid dynamic and static obstacles in grid maps and achieve intelligent robot inspection path planning. The inspection path length is relatively short， and the path optimization degree， turning smoothness coefficient， global search ability， and environmental adaptability scores are 95.24%， 0.917， 0.764， and 91.45， respectively.

Graphical abstract

关键词

栅格地图 / 改进A^*算法 / 启发函数 / 转弯代价 / 邻域搜索 / 变邻域下降

Key words

raster map / improve the A^* algorithm / heuristic function / cost of turning / neighborhood search / variable neighborhood descent

0 引 言

在变电站等复杂环境中，智能巡检机器人需要自主导航并完成巡检任务^［1，2］。然而，这些环境往往存在大量的动态障碍物，如检修设备的工作人员、运输设备的车辆等。这些动态障碍物会临时出现在道路区域，造成局部道路堵塞现象，使巡检路径呈现非连续可访问性条件。由于动态障碍物的存在，巡检路径的可行域会随时发生变化^［3，4］。当机器人按照预规划的路径行驶时，会突然发现前方路径被障碍物阻挡，导致路径不可行。此时，机器人需要迅速自适应地重构路径，以找到一条新的可行路径^［5，6］。然而，这一过程往往面临诸多挑战，即如何评估新路径的可行性和优化性、如何在保证巡检效率的同时确保路径的转弯平滑度等。为应对上述挑战，本文提出了基于栅格地图的邻域搜索算法。

众多科研机构和技术人员已经展开对机器人巡检路径搜索的研究。杨立炜等^［7］通过考虑路径长度、障碍物分布以及转弯平滑度等多个因素多蚁群算法进行改进，实现了对最优巡检路径的有效搜索和规划。蚁群算法容易陷入局部最优解，尤其是在动态环境中，当路径被障碍物阻断时，算法难以跳出当前的最优解区域，寻找新的可行路径。辛鹏等^［8］利用改进快速随机树快速生成可行路径，利用人工势场法的局部避障和平滑路径的优势，调整了生成的初步路径。改进快速随机树算法的随机性会导致生成的路径不够稳定，而障碍物的变化会使得原本可行的路径变得不可行。赵崇娟等^［9］通过优化A^*算法的启发式搜索策略、引入动态障碍物处理机制以及路径平滑技术，实现对变电站内复杂环境巡检路径规划。A^*算法本质上是一种静态规划方法，对动态环境的适应性较差。当障碍物位置发生变化时，算法需要重新规划路径，导致计算复杂度增加。许建民等^［10］在构建巡检环境栅格地图后，采用改进A^*算法进行初步全局路径规划，通过动态窗口法（Dynamic window approach，DWA）实现其局部优化。然而，在动态环境中，当全局路径被障碍物阻断时，DWA算法无法及时找到新的局部路径。

邻域搜索算法通过在当前解的邻域内搜索寻找改进解，逐步逼近全局最优解。将邻域搜索算法应用于智能机器人自适应巡检路径规划，可以在栅格地图中快速找到一条由初始位置至目标位置的最佳路径，同时能够动态适应环境的变化。因此，本文研究智能机器人自适应巡检路径栅格地图邻域搜索算法，提高对复杂巡检环境的动态适应能力以及路径规划效果。

1 机器人巡检路径栅格地图邻域搜索

1.1　巡检环境栅格地图边界界定

智能机器人在执行巡检任务时，通常将其巡检环境视作一个二维平面，环境中的静态、动态障碍物是影响路径规划的关键因子。然而，在动态环境下，由于障碍物的不断移动和变化，路径可行域会频繁突变。栅格地图将整个巡检区域视作规则矩形，通过细分内部以形成若干个小栅格单元。因此，通过界定栅格地图的边界，可以将路径搜索范围限制在已知且可控的区域内，避免机器人因搜索范围过大而陷入复杂的计算中，以及时获取可行的路径解。

对于智能机器人的巡检区域，依据设定的栅格边长N对该区域进行分割，形成若干个矩形栅格，将原始巡检地图转变为具有\mathrm{r}\mathrm{o}\mathrm{w}行\mathrm{c}\mathrm{o}\mathrm{l}列的栅格地图，其中的任意栅格单元都与一个节点相对应，并记录节点编号。通过下式描述位于i行j列的栅格s\left(i,j\right)：

s\left(i,j\right)=i+\left(j-\mathrm{1}\right)\times j,i\in \left[\mathrm{1},row\right],j\in \left[\mathrm{1},\mathrm{c}\mathrm{o}\mathrm{l}\right]（1）

定义权值矩阵\mathit{P}\left(m\right)，其值体现了编号为m的栅格单元被占用的可能性大小，地图中的栅格包含障碍栅格和无障碍通行栅格两类：

\mathit{P}\left(m\right)=\left\{\begin{array}{l}\mathrm{0},\mathrm{栅格}m\mathrm{有障}\mathrm{碍}\\ \mathrm{1},\mathrm{栅格}m\mathrm{可通}\mathrm{行}\end{array}\right.（2）

m栅格与之邻域栅格的关联紧密性通过\mathit{P}\left(m\right)值进行体现。当其取值较大时，说明m栅格与之邻域栅格紧密关联，m栅格被占用的可能性较高。

m栅格的邻域栅格编号表示为\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}\left(m\right)，可通过下式进行定义：

\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}\left(m\right)=\mathit{P}\left(m\right)\cdot s\left(i,j\right)（3）

栅格地图内部栅格编号可通过式（3）进行定义，位于地图边界处的栅格因其某些方向会延伸到地图范围之外，其编号无法通过式（3）精准确定。因此，通过式（4）定义栅格地图上下左右边界栅格判定条件，符合式（4）条件时，将其相应方向上的栅格编号设为0，由此辨别4个方向上是否存在栅格。

\left\{\begin{array}{l}\mathrm{m}\mathrm{o}\mathrm{d}\left(m,row\right)=\mathrm{1},\mathrm{上边}\mathrm{界栅}\mathrm{格判}\mathrm{定条}\mathrm{件}\\ \mathrm{m}\mathrm{o}\mathrm{d}\left(m,row\right)=\mathrm{0},\mathrm{下边}\mathrm{界栅}\mathrm{格判}\mathrm{定条}\mathrm{件}\\ \mathrm{1}\le m\le \mathrm{r}\mathrm{o}\mathrm{w},\mathrm{左边}\mathrm{界栅}\mathrm{格判}\mathrm{定条}\mathrm{件}\\ row\left(\mathrm{c}\mathrm{o}\mathrm{l}-\mathrm{1}\right)+\mathrm{1}\le m\le \mathrm{r}\mathrm{o}\mathrm{w}\times \mathrm{c}\mathrm{o}\mathrm{l},\\ \mathrm{右边}\mathrm{界栅}\mathrm{格判}\mathrm{定条}\mathrm{件}\end{array}\right.（4）

1.2　机器人全局巡检转弯平滑路径规划

构建的栅格地图虽然简化了机器人全局巡检的环境表示，但路径规划仍然需要处理大量的栅格信息。以转弯路径为例，如果转弯路径不平滑，将影响机器人巡检任务的完成质量。为此，引入A^*算法^［11］，A^*路径规划算法以栅格地图为巡检环境模型，以智能机器人的初始位置作为搜索的出发点，在路径搜索过程中，运用评价函数估计从当前节点到目标节点的代价，但由于该算法未充分利用已知搜索信息指导搜索过程，导致搜索效率较低。为此，引入转弯代价函数改进A^*算法，结合启发式信息指导搜索方向，设计出转弯环境中从初始位置到目标位置的最优路径。通过优化转弯路径，机器人可以更快地完成任务，减少不必要的停留和等待时间。

代价函数f\left(n\right)通过下式描述：

f\left(n\right)=g\left(n\right)+h\left(n\right)（5）

式中：g\left(n\right)为智能机器人由初始位置移动到当下所在位置所产生的累积代价；h\left(n\right)为由当下位置移动到目标位置的代价估计值表示。

启发函数根据欧几里得距离进行构造，计算公式为：

h\left(n\right)=\mathrm{s}\mathrm{q}\mathrm{r}\mathrm{t}\left[{\left(x_n-x_g\right)}^{\mathrm{2}}+{\left(y_n-y_g\right)}^{{}^{\mathrm{2}}}\right]（6）

式中：\left(x_n,y_n\right)为智能机器人的当前位置坐标；\left(x_g,y_g\right)为目标位置的坐标表示。

基于A*算法的智能机器人巡检路径规划步骤为：

（1）路径规划开始时，将栅格地图中智能机器人的初始位置节点作为唯一候选节点保存与OPEN表中，将栅格地图中的所有障碍点存放于CLOSE表中。

（2）将OPEN表中具有最低代价的节点n转移到CLOSE表中。

（3）验证节点n是否为智能机器人巡检的目标位置。当n对应于目标位置时，通过前向指针回溯，生成从初始位置到目标位置的巡检路径；反之，则进行节点扩展，得到可能的后继节点k。

（4）为节点k建立一条指向其父节点n的指针，通过f\left(k\right)=g\left(k\right)+h\left(k\right)求得节点k的综合代价值。

（5）检查OPEN表中是否存在节点k，当k不存在时，将其保存于OPEN表中；否则，将其与OPEN表中已存在的节点f\left(k\right)进行对比，若新节点的代价值更小，则更新OPEN表中该节点的信息。

（6）修正初始位置节点至当下节点k的累积代价g\left(k\right)，基于新的g\left(k\right)和原有的h\left(k\right)值，重新计算k节点的综合代价f\left(k\right)，并将其前向指针指向新的父节点，以反映到达k节点的最优路径。

（7）依据f\left(k\right)的高低对OPEN表中节点进行排序后，退回到第二步。

A*算法所用启发函数h\left(n\right)因未充分利用已知搜索信息指导搜索过程，导致搜索效率较低^{［12，13］}。为了增强A^*算法的导向性，在考虑父节点h\left(p\right)的情况下对启发函数进行优化设计，计算公式为：

h^{\text{'}}\left(n\right)=Z\left(a\right)\cdot \left[h\left(n\right)+h\left(p\right)\right]（7）

Z\left(a\right)=\mathrm{1}+\mathrm{e}\mathrm{x}\mathrm{p}\left(a/A\right)（8）

式中：Z\left(a\right)为巡检环境障碍率函数，其作用是对启发项\left[h\left(n\right)+h\left(p\right)\right]权重进行调节；A为栅格地图中障碍物总量；在以当下节点n与目标巡检位置节点作为对角线两个端点所构造出的矩形区域中，所含有的障碍物个数表示为a。

A^*算法采用8邻域搜索策略进行，父节点的8个子节点具有不变的移动代价，且不随着方向改变。这导致向任何方向进行节点扩展所产生的总代价相近，进而产生大量冗余节点，增加最优节点搜索难度。引入转弯代价，通过定义代价函数，完成机器人全局巡检转弯平滑路径规划。具体计算式如下：

f\left(n\right)=g\left(n\right)+h^{\text{'}}\left(n\right)-\omega \cdot D\cdot \mathrm{c}\mathrm{o}\mathrm{s}\theta（9）

式中：权重参数\omega在0至1区间上取值，用于对巡检路径规划中的转弯代价进行调节；\theta为目标位置以及父、子节点所形成的夹角；D为父节点与目标位置之间的距离。

1.3　自适应邻域搜索的巡检路径可行域重构

在机器人巡检路径栅格地图邻域搜索研究中，尽管已经完成了机器人全局巡检转弯平滑路径规划，但仍存在动态环境下路径可行域频繁突变导致原有路径失效的问题，以及因环境复杂性和不确定性带来的新障碍物或通行区域变化难以实时捕捉的挑战^{［14，15］}。这些问题使机器人难以仅凭规划后的路径完成巡检任务。因此，通过自适应大规模邻域搜索（Adaptive large neighborhood search， ALNS）技术在改进A^*算法的基础上，进一步进行智能机器人巡检路径的局部优化，引入破坏算子、修复算子、变邻域下降搜索算子以及自适应邻域算子评分与选择机制，进一步开展自适应邻域搜索的巡检路径可行域重构，以有效应对动态环境下巡检路径可行域的频繁突变，从而实时调整和优化路径，确保巡检任务的顺利进行。

1.3.1　个体表示和初始解

采用二维序列编码策略描述智能机器人巡检路径优化方案（即个体），每个优化方案由A^*算法规划的多条巡检路径构成，每条巡检路径记录了智能机器人完整的移动序列，路径的起止点标志着智能机器人巡检的起始位置和目标位置，中间节点列出了智能机器人按照预定顺序需要途径的各任务点，这种编码方式不仅直观地展现了智能机器人的巡检轨迹，还为后续的路径优化和调整提供了灵活的数据结构基础。

初始解通过改进A^*路径规划算法获得，即根据智能机器人的起始位置和预定任务点，利用改进A^*算法生成多条巡检路径。巡检路径充分考虑移动代价、转弯代价等因素，确保智能机器人能够遍历栅格地图中所有任务点。将这些基础路径组合成一个初始的巡检路径优化方案，作为后续路径优化过程的起点，为后续的迭代优化提供了可行的初始解。

1.3.2　破坏算子

破坏算子用于随机或策略性地移除路径中的部分节点，模拟路径因障碍物出现而失效的情况。破通过移除巡检路径优化方案中的部分任务，生成一条不完整路径，采取不同的移除策略能够形成不同的破坏算子，具体为：

（1）随机破坏策略。该算子通过从巡检路径优化方案中任意剔除\beta个任务点实现解的破坏。

（2）关键瓶颈任务剔除策略。智能机器人的移动时间与运行距离具有正相关性。在已知的巡检路径中，到前、后节点的总移动距离最大的关键瓶颈任务应予以删除，即智能机器人为访问该任务需移动更远的距离。

（3）最小效率比路径剔除策略。在巡检路径优化方案中，找出并剔除最小效率比路径。对于巡检路径R_{\mathrm{1}}，智能机器人巡检完该条路径的总移动时间表示为T\left(R_{\mathrm{1}}\right)，纯粹用于执行巡检任务的实际时间为t\left(R_{\mathrm{1}}\right)，通过下式计算效率比：

\alpha =t\left(R_{\mathrm{1}}\right)/T\left(R_{\mathrm{1}}\right)（10）

通过删除低效率巡检路径，可以达到整体巡检任务执行效率优化的目的。

1.3.3　修复算子

修复算子则尝试重新连接路径断点或寻找替代路径，以恢复路径的可行性。通过采用不同的修复策略，将先前被删除的任务重新整合到巡检路径优化方案（个体）中，构建出一个新的解决方案。

（1）随机嵌入策略，通过随机嵌入方式把已移除的任务重新整合到被破坏的解结构中，以提升解空间探索的多样性。

（2）最优嵌入策略，是把需添加的任务放置于绝对最优位置上，确保智能机器人的巡检代价最低。

（3）次优嵌入策略，并不总是追求将待添加任务放置在绝对最优（即代价最低）的位置。相反，它会选择一个在嵌入添加任务后，使得巡检代价增幅低于10%的相对较优位置进行嵌入，旨在保持路径规划的高效性，同时增加搜索解空间的多样性，以提高找到更优路径的可能性。

（4）最低效路径嵌入，针对每一个需要嵌入的任务，选取具有最低效率比的巡检路径，将其嵌入到巡检代价最低的位置上，反复循环执行此操作，直至所有任务均被整合到新的巡检路径规划方案中。

1.3.4　变邻域下降搜索算子

变邻域下降搜索策略通过不断变换邻域搜索结构进行解空间的深入探索，旨在发现更优的解，从而避免算法陷入局部最优困局，提高巡检路径优化效率和效果。本文设计的3种邻域搜索结构为：

（1）2-opt结构：通过反转巡检路径中某一段任务序列来寻求路径质量提升的邻域搜索结构。这意味着通过逐一审视每条巡检路径，检查是否存在通过反转i和j之间的任务序列降低路径代价的可能性。如果是，则采取反转操作。

（2）Swap结构：该策略分别对两条巡检路径中各自代价最高的任务进行识别并移除，然后将其交叉嵌入到对方路径中代价最低位置，达到优化巡检路径的目的。

（3）Migration结构，在存在两条或更多巡检路径的情况下，考虑将其中一条路径上的某个任务，在满足可行性的前提下，迁移到另一条巡检路径中，确保迁移后的巡检路径能满足整体最低代价要求。

1.3.5　自适应邻域算子评分与选择机制

自适应邻域算子评分与选择机制能根据当前环境信息和路径质量，动态调整搜索策略，选择最优的邻域算子进行路径重构。最终评分由两个核心要素决定：一是算子过往的性能表现\mathrm{h}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}；二是算子的利用频次c。通过对上述要素采取加权方式合并，共同构成算子的综合得分\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}。计算公式为：

\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}=\gamma \times \mathrm{h}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}+\frac{\mathrm{1}-\gamma }{\mathrm{1}+c}（11）

式中：\gamma为平衡系数。

\mathrm{h}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}通过式（12）（13）进行自适应修正：

\mathrm{h}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{r}{\mathrm{y}}^{\mathrm{n}\mathrm{e}\mathrm{w}}=\mathrm{h}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}+\delta（12）

（13）

式中：f\left(\mathrm{o}\mathrm{l}\mathrm{d}\right)为当前巡检路径规划方案（解）的综合代价；f\left(\mathrm{n}\mathrm{e}\mathrm{w}\right)为邻域搜索后的巡检路径优化方案的综合代价；q为衡量算子贡献的参数，反映了算子每次成功找到更优解时的正面贡献。

如果执行邻域搜索后，得到的巡检路径规划方案（解）综合代价没有降低，则\mathrm{h}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}的值为0，算子的历史表现不变；反之，如果巡检路径规划方案（解）的综合代价有所降低，则对\mathrm{h}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}进行修正。无论邻域搜索结果如何，c值都会增加1。

2 实验分析

选取某区域大型智能变电站为实验对象，该变电站长100 m、宽80 m，其内设有多个变压器区域、电力基础设施区域，还包括充电室、控制室、继电室等辅助设施。通过图1所示的平面效果图展示该变电站的实际布局情况以及巡检点分布。利用智能机器人执行变电站巡检任务，其性能参数如表1所示。智能机器人从充电室出发，对分布在变电站内的20个指定巡检点进行逐一检查。每个巡检点仅访问一次，完成所有巡检点的检查后返回充电室，准备下一次巡检任务。将研究算法应用到变电站巡检中，验证其路径规划效果。

对智能机器人巡检环境进行合理建模是实现巡检路径准确规划的关键步骤。利用本文算法进行栅格地图建模，通过对建模结果进行分析，验证其可行性和有效性，实验结果如图2所示（彩图见电子版，下同）。

分析图2可知，本文算法通过对智能变电站实际环境进行分析，实现了栅格地图的构建。其中黑色部分代表分布于智能变电站中的各类设施、设备以及不可通行区域，视作静态障碍物；绿色圆点为智能机器人的巡检点；红色圆点标注了智能机器人巡检的起止位置；余下区域代表变电站内的可通行区域。栅格地图呈现了变电站环境中的关键信息，为智能机器人的高效、安全巡检提供了有力的技术支持。

在只有静态障碍物的情况下，应用本文算法对智能机器人巡检路径进行规划，并与基于A^*算法以及改进A^*算法的路径规划结果进行对比，验证研究算法在巡检路径规划上的性能优势，实验结果如图3所示。

分析图3得出，本文算法能成功避开所有静态障碍物，实现对各巡检点的全面检查，其巡检路径长度相对较短，巡检轨迹曲线流畅无冗余；相比之下，改进A^*算法规划的巡检轨迹可能显得较为迂回曲折，这主要归因于该算法在搜索过程中缺少全局性指导，易于陷入局部最优困境；A^*算法规划的巡检路径虽然也能搜索到一条完整的巡检路径，但因其过于依赖启发式函数，导致路径在转弯处处理不够灵活。综合比较，本文算法规划出的巡检路径在路径长度、避障效果方面均展现出明显的优势，充分验证了其性能的优越性。

路径优化度指标用于衡量规划路径与最优路径之间的偏差率，其值越大，偏差率越低；转弯平滑度系数定义为路径中所有转弯角度的余弦值之和与转弯次数的比值，反映了路径在转弯处的平滑效果；全局搜索能力通过全局范围内搜索到的有效路径数量与总搜索次数的比值进行反映；环境适应性评分的高低反映了算法对复杂环境的适应能力。选取路径优化度、转弯平滑度系数、全局搜索能力、环境适应性评分这4个指标衡量3种算法在智能机器人巡检路径规划上的性能差异，实验结果如表2所示。

分析表2得出，应用研究算法对智能机器人巡检路径进行规划，路径优化度、转弯平滑度系数、全局搜索能力以及环境适应性评分4个指标值分别为95.24%、0.917、0.764、91.45，均高于对比算法，证明了本文算法在巡检路径规划上的显著优势，能够为智能机器人的高效、安全巡检提供了有力的技术支持。

以变电站中的检修人员作为动态障碍物，通过灰色矩形块呈现在栅格地图中。应用研究算法对静、动态障碍物环境下的巡检路径进行规划，实验结果如图4所示。

分析图4可知，本文算法能根据栅格地图中静态障碍物以及动态障碍物的实时分布，灵活地进行巡检路径的动态规划与调整，生成一条可行的巡检路径。该巡检路径不仅展现出突出的平滑度与转弯灵活性，还确保了智能机器人在复杂环境中安全、顺畅地完成巡检任务。

3 结束语

研究了智能机器人自适应巡检路径栅格地图邻域搜索算法，通过构建巡检环境栅格地图，实现了复杂变化环境的数字化表示，为智能机器人提供了精确的导航基础。通过优化启发函数和引入转弯代价对A^*算法进行改进，显著提升了路径规划的效率和准确性。利用自适应大规模邻域搜索算法通过动态调整搜索策略和算子评分机制，进一步增强了路径规划的全局优化能力和环境适应性，三者结合使得优化后的巡检路径更加高效且安全。未来，可进一步探索算法在更多复杂场景下的应用，以及与其他智能算法的融合，以持续提升智能机器人巡检的效率和智能化水平。

参考文献

[1] 金书奎, 寇子明, 吴娟. 煤矿水泵房巡检机器人路径规划与跟踪算法的研究[J].煤炭科学技术,2022,50(5): 253-262.

[2] Jin Shu-kui, Kou Zi-ming, Wu Juan. Research on path planning and tracking algorithm of inspection robot in coal mine water[J]. Coal Science and Technology, 2022,50(5): 253-262.

[3] 邢文芳,冯寄东,徐元,等.双程UFIR滤波算法及其在INS/双目视觉机器人组合导航的应用[J].传感技术学报,2023,36(7):1073-1078.

[4] Xing Wen-fang, Feng Ji-dong, Xu Yuan, et al. Double-Pass UFIR filtering and its application in ins/binocular vision robot integrated navigation[J]. Chinese Journal of Sensors and Actuators,2023,36(7):1073-1078.

[5] Jiang S H, Sun S J, Li C. Path planning for outdoor mobile robots based on IDDQN[J]. IEEE Access, 2024, 12:51012-51025.

[6] 李洁静,吴倩,耿轶钊,等.复杂环境下矿用巡检机器人的路径规划方法[J].煤炭技术,2023,42(10):236-239.

[7] Li Jie-jing, Wu Qian, Geng Yi-zhao, et al. Path Planning method for mining inspection robots in complex environments[J].Coal Technollgy, 2023,42(10):236-239.

[8] 岳程斐, 张枭, 王宏旭,等. 在轨操控机器人拓邻域搜索三维路径规划[J].宇航学报, 2022, 43(2): 206-213.

[9] Yue Cheng-fei, Zhang Xiao, Wang Hong-xu, et al. Three-dimensional path planning of on-orbit manipulation robot based on neighborhood continuation Search [J].Journal of Astronautics,2022,43(2):206-213.

[10] 李鹏, 闵小翠, 王建华. 基于改进蚁群算法的巡检机器人避障路径规划方法设计[J]. 机械与电子, 2022, 40(2): 71-74, 80.

[11] Li Peng, Min Xiao-cui, Wang Jian-hua. Design of obstacle avoidance path planning method for inspection robot based on improved ant colony algorithm[J].Machinery & Electronics, 2022, 40(2): 71-74, 80.

[12] 杨立炜, 付丽霞, 郭宁, 等.多因素改进蚁群算法的路径规划[J].计算机集成制造系统,2023,29(8):2537-2549.

[13] Yang Li-wei, Fu Li-xia, Guo Ning, et al. Path planning with multi-factor improved ant colony algorithm [J].Computer Integrated Manufacturing Systems,2023,29(8):2537-2549.

[14] 辛鹏, 王艳辉, 刘晓立, 等. 优化改进RRT和人工势场法的路径规划算法[J]. 计算机集成制造系统,2023, 29(9): 2899-2907.

[15] Xin Peng, Wang Yan-hui, Liu Xiao-li, et al. Path planning algorithm based on optimize and improve RRT and artificial potential field[J].Computer Integrated Manufacturing Systems, 2023,29(9):2899-2907.

[16] 赵崇娟, 朱奕弢, 胡钰莹, 等.基于改进A^*算法的变电站自动巡检路径规划研究[J].机械设计, 2024,41(): 153-158.

[17] Zhao Chong-juan, Zhu Yi-tao, Hu Yu-ying, et al. research on automatic inspection path planning for substations based on improved A algorithm[J]. Machine Design, 2024,41(Sup.1):153-158.

[18] 许建民, 宋雷, 邓冬冬, 等. 基于多尺度A^*与优化DWA算法融合的移动机器人路径规划[J].系统仿真学报, 2025, 37(1): 257-270.

[19] Xu Jian-min, Song Lei, Deng Dong-dong, et al. Path planning of mobile robot based on the integration of multi-scale A^* and optimized DWA algorithm[J].Journal of System Simulation, 2025, 37(1): 257-270.

[20] 边艳华, 解路, 苗超. 基于深度强化学习和大邻域搜索的矿山巡检机器人路径规划算法[J]. 金属矿山, 2024, 41(2): 212-218.

[21] Bian Yan-hua, Xie Lu, Miao Chao. Path planning algorithm of mine inspection robot based on deep reinforcement learning and large neighborhood search[J].Metal Mine, 2024, 41(2): 212-218.

[22] 姜媛媛, 张阳阳.改进8邻域节点搜索策略A^*算法的路径规划[J]. 电子测量与仪器学报, 2022, 36(5): 234-241.

[23] Jiang Yuan-yuan, Zhang Yang-yang. Improved path planning of A^* algorithm of domain node search strategy 8[J].Journal of Electronic Measurement and Instrumentation, 2022, 36(5): 234-241.

[24] 王硕, 周海波, 张建军, 等. 拓展A^*算法的机器人室内三维地图路径规划[J]. 计算机仿真, 2022, 39(2): 394-398.

[25] Wang Shuo, Zhou Hai-bo, Zhang Jian-jun, et al. Extended A* algorithm for indoor 3D map path planning of robots[J].Computer Simulation,2022,39(2): 394-398.

[26] 吕文艳. 金属弧焊机器人加工轨迹智能规划研究[J].模具技术, 2024(2): 26-34.

[27] Lv Wen-yan. Research on intelligent planning of machining trajectory for metal arc welding robot[J]. Die and Mould Technology,2024(2):26-34.

[28] 吕东许, 李少梅, 周炤, 等.基于改进变邻域搜索算法的多批次协同任务规划[J].包装工程, 2023, 44(5): 222-229.

[29] Lv Dong-xu, Li Shao-mei, Zhou Zhao, et al. Multi-batch collaborative task planning based on improved variable neighborhood search algorithm[J].Packaging Engineering,2023, 44(5): 222-229.

基金资助

国家级大学生创新创业训练项目(202310120006)

大同市应用基础研究项目(2025081)