基于改进A^*的陆空两栖机器人路径规划

Path Planning for Ground-Aerial Amphibious Robot Based on an Improved A^* Algorithm

摘要: 针对传统A*算法搜索效率低、路径拐点多以及环境适应性差等问题，本文提出一种改进A*与蜣螂优化算法(DBO)相结合的跨域规划方法。首先采用基于环境障碍分类的智能分层跨域决策方法；同时，在A*算法中引入电池能耗和运行时间等代价，动态权重调整启发函数，提高搜索效率。最后，采用基于DBO的局部路径优化，利用其搜索能力对路径进行平滑处理与优化。仿真实验结果表明，本算法在路径长度、能量消耗和计算效率等方面均表现出显著优势，为陆空两栖机器人的实际应用提供了可靠的技术支撑。

Abstract: To address the issues of low search efficiency, numerous path inflection points, and poor environmental adaptability in traditional A^* algorithms, this paper proposes a cross-domain planning method combining an improved A^* algorithm with the dung beetle optimization (DBO) algorithm. First, an intelligent hierarchical cross-domain decision-making method based on environmental obstacle classification is adopted. Simultaneously, costs such as battery energy consumption and runtime are introduced into the A^* algorithm, dynamically adjusting the heuristic function weights to enhance search efficiency. Finally, DBO-based local path optimization is employed to leverage its search capabilities for path smoothing and refinement. Simulation results demonstrate that this algorithm exhibits significant advantages in path length, energy consumption, and runtime, providing reliable technical support for the practical application of ground-aerial amphibious robots.

1. 引言

随着城市化进程不断加快，各类灾害频发对救援工作提出严峻挑战，灾害现场复杂多变，传统救援设备难以有效开展工作[1]。陆空两栖机器人凭借其独特的跨域运动能力，在灾害救援中展现出巨大潜力，能够根据环境自主选择地面移动或空中飞行模式，适应复杂灾场环境[2]。

救援环境的特殊性对路径规划提出更高要求[3]，传统A^*算法在此场景下存在明显局限：状态空间定义单一，无法区分不同高度障碍物；代价函数简单；搜索效率有待提升等[4]。针对灾害救援的特殊需求，研究者提出了多种改进方法。文献[5]中，FAN等人使用A^*算法进行初始路径搜索，通过对空中节点增加额外能量成本来引导算法优先选择地面路径。由于缺乏轨迹后处理环节，该方法无法保证生成路径的光滑性和动态可行性。QI等[6]考虑到距离、能耗和模式切换成本，提出一种基于烟花算法的路径规划方法，但基于坐标旋转和平移的优化模型无法处理障碍物密集的复杂环境。GUO等[7]针对球形两栖机器人提出一种基于全局静态规划的多目标路径规划算法，采用A^*算法进行双向平滑优化并计算距离，采用蚁群寻找最优路径，但没有充分考虑两栖机器人的特点优化路径。

针对上述问题，本文提出面向灾害救援的改进A^*跨域路径规划算法，主要创新包括：基于障碍物分类的智能决策机制；构建多目标启发函数，综合考虑风险、能耗；引入DBO算法对路径进行优化处理。

2. 建立环境地图

2.1. 障碍物处理

实际使用场景的障碍物通常是不规则物体，为了确保机器人移动过程与障碍物保持一定安全距离，减少碰撞可能性，本研究对障碍物进行膨胀处理[8]：若障碍物完全占据栅格，则直接将当前栅格认定为障碍区域；若当前栅格存在障碍物，但未完全占据，将整个栅格进行膨胀，依旧认为该栅格全部为障碍物区域，见图1所示。

2.2. 构建环境地图

由于灾害现场无法满足滑行起飞条件，为了保障陆空机器人起飞、降落时的稳定性、安全性，要求在模式切换时进行垂直起降，本文采用在含有高度信息的2.5维地图中实现跨域规划。在判断搜索节点所在栅格是否存在障碍物时，根据栅格中Z值对目标区域障碍物进行分类：当Z = 0时，表示当前栅格无障碍物，机器人以能耗最低的地面模式进行移动；当Z > 0时，则表示当前区域存在障碍物。

Figure 1. Obstacle puffing treatment

图1. 障碍物膨化处理

依据障碍物高度与机器人运动能力，将灾场障碍划分为三个类别：高度低于1.0 m的低障碍物(碎石堆)、高度在1.0至2.5 m之间的中等障碍物(破损墙体)以及高度超过2.5 m的高障碍物(未完全倒塌的楼板)，三种障碍物分别对应Z = 1、2、3的栅格编码。分别用绿色、橙色、灰色三种颜色进行表征。根据上述方法，对30 × 30边长的环境进行2.5维栅格地图的建立，如图2所示。

Figure 2. 30 × 30 environmental map

图2. 30 × 30环境地图

3. 基于跨域场景的改进A^*算法

3.1. 自适应跨域决策

在路径规划领域，A^*算法采用8节点搜索策略，即在每个节点处均匀地向八个方向进行扩展搜索。这种搜索方式在均匀环境中表现稳定，但在灾害救援这类复杂异构环境中暴露出明显局限性，无法区分不同方向上的障碍物特征差异。本研究通过扩展搜索邻域，将搜索节点从8个增加为16个，避免了在相同方向重复搜索节点的问题。改进了A^*在复杂障碍分布环境中冗余检查和路径转折点大的问题，具体扩展过程如图3所示。

(a) 8邻域搜索 (b) 扩展邻域搜索

Figure 3. Schematic diagram of the expanded search neighborhood principle

图3. 扩展搜索邻域原理图

本研究针对不同障碍实施差异化策略。对低障碍物采用地面绕行，通过计算绕行代价决定最优路径；中等高度障碍物则通过比较绕行和飞行之间的代价，选择出代价更低的路径；考虑到灾害现场较高障碍物存在二次事故风险，规定只能采用飞行路径，这种分类决策机制使机器人能够根据环境特征自适应选择最优运动模式。

3.2. 启发函数优化

A^*算法作为广泛应用于路径规划的启发式算法，结合了Dijkstra算法的完备性和贪婪最佳优先搜索的效率，通过建立代价函数F(n)进行路径搜索，如式(1)所示：

$F\left(n\right)=G\left(n\right)+H\left(n\right)$ (1)

其中G(n)为从起始节点到当前节点n的实际代价；H(n)为从当前节点n到目标节点的估计代价。H(n)通常只考虑距离这一个维度，无法处理陆空两栖机器人面临的多模态运动和异构环境的复杂决策问题。因此，本研究在传统欧几里得距离的基础上，增加对目标区域附近障碍物复杂程度的感知，采用高程方差与障碍物密度复合指标评估环境复杂度，如式(2)所示：由高程标准差σ_h和障碍物密度ρ共同表征，其中α和β为权重系数，避免了在障碍密集区域陷入局部最优，提升路径搜索效率与质量。

$T_c=\alpha \cdot {\sigma }_h+\beta \cdot \rho$ (2)

同时，考虑到飞行过程的不确定性和危险性以及模式切换造成的能耗，引入飞行风险系数P和切换成本e_f。设定机器人处于飞行模式时，P取值为1.2~1.5的惩罚因子，本文取1.3，意在引导算法在非必须情况下通过增加代价值来抑制频繁的低效飞行；当地面移动时，P = 1.0。切换成本e_f则为机器人执行起飞或降落动作时的固定能耗代价。

$H^{\prime }\left(n\right)=\{\begin{array}{ll}{w}_g\cdot d\left(n,goal\right)\hfill & Z=0\hfill \\ w_g\cdot d\left(n,goal\right)\cdot T_c\hfill & Z=1\hfill \\ w_g\cdot d\left(n,goal\right)\cdot T_c+w_f\cdot d\left(n,goal\right)\cdot P+e_f\hfill & Z=2\hfill \\ w_f\cdot d\left(n,goal\right)\cdot P+e_f\hfill & Z=3\hfill \end{array}$ (3)

式中，$d\left(n,goal\right)$ 为当前节点到目标的欧氏距离；w_g、w_f分别为地面基础能耗系数与飞行基础能耗系数。改进A^*算法通过环境障碍物分析和多代价因子融合，实现了从几何距离估计到环境代价估计，大幅提高在复杂环境下的搜索效率，满足灾害救援的时效性要求。

4. 基于DBO算法的路径优化

灾害救援场景下，路径的质量直接关系到救援效率和机器人的续航能力。为此，本文引入蜣螂优化算法(Dung Beetle Optimizer, DBO)作为路径优化器，对改进A^*算法生成的初始路径进行路径优化处理。

4.1. 增加运动模式切换点

考虑到机器人搭载的电池容量有限，可用能量受到严格约束。飞行模式会显著耗能，因此在满足无障碍通行条件下，优先采用能耗较低的地面移动模式，最大限度延长续航能力。为保障无人机在跨越障碍物时的飞行安全，需明确定义垂直起飞与降落的模式切换节点，并在空中加入额外路径点，如图4所示。当遇到需要飞行才能越过的障碍物时，机器人在运动模式切换点，进行从地面绕行状态切换到预备起飞状态，完成准备动作后飞升至空中路径点，然后再转换为降落模式，实现无碰撞、能耗低的三维跨域任务。

注：f₁~f₃为运动模式切换点；g₁、g₂为二维路径点。

Figure 4. Adding mode switching nodes

图4. 增加模式切换节点

4.2. DBO算法路径优化

陆空两栖机器人的局部路径优化属于典型的多约束、非线性强耦合问题。以DWA为例的传统梯度类算法的实时性强，但灾害环境下易陷入局部极值，机器人震荡从而影响模式切换。PSO、SSA等元启发式算法虽具全局寻优能力，但存在早熟收敛或迭代后期种群多样性下降问题，难以满足高维约束下关键位置的微调精度。为此，本文选用蜣螂算法(DBO)作为局部优化算法，其生物行为机制与陆空跨域规划需求高度契合。

DBO算法是一种新型的元启发式优化算法，其灵感来源于蜣螂的滚球、繁殖、觅食和偷窃等自然行为[9]，这种生物学机制为算法提供了精细的搜索策略。该算法具有收敛速度快、参数设置简单、全局搜索能力强等特点，非常适合解决路径优化这类非线性问题。

以改进A^*初始路径作为DBO初始种群，将初始路径进行编码处理，将每条路径表示为一个包含序列化路径点的向量$S=\left[s_1,s_2,\cdots ,s_k\right]$ ，每个向量中包含位置坐标及运动模式。适应度函数以最小化整体路径代价为目标：

$F\left(s\right)={\displaystyle \sum }_{i=1}^k{C}_s\left(s_i,s_{i+1}\right)+\lambda \cdot N_s$ (4)

其中，C_s表示段路径代价，N_s为模态切换次数，λ为权重系数，用于平衡路径成本与切换代价。经过DBO优化后的路径在平滑度、能量效率和安全性方面均有显著提升，特别适合对路径质量要求较高的灾害救援应用场景。

4.3. 算法对比分析

为验证本文引入的DBO优化算法在局部路径规划中的有效性与优越性，基于Matlab实验平台构建15 × 15栅格环境，选取目前常见的元启发函数：麻雀搜索算法(SSA)、常春藤算法(IVY)、鹅群算法(GOOSE)与DBO算法进行对比实验。图5(a)显示，GOOSE与IVY算法规划路径虽避障成功，但曲折且存在无效绕路；SSA算法表现更优，但狭窄通道处平滑度不足。DBO算法规划路径总程最短、密集障碍区平滑性极佳，符合两栖机器人运动学约束，利于稳定跟踪。

图5(b)的300次迭代适应度收敛曲线表明，IVY与GOOSE算法初期就陷入局部最优，SSA算法虽然部分跳出，但迭代次数与适应度值均高于DBO算法。

(a) 路径规划对比图 (b) 适应度函数收敛曲线

Figure 5. DBO algorithm comparison experiment

图5. DBO算法对比实验

5. 算法仿真及实验结果分析

本文实验在MatlabR2022a平台上进行。为了确保算法在不同场景下的鲁棒性，文中所涉及的关键控制参数经多次经验调试，具体参数设定如下：设定高程标准差权重α = 2.0，障碍物密度权重β = 1.5。通过测试发现，较高的α值能更有效地引导机器人避开地形起伏剧烈的区域，降低翻越风险。适应度函数中，权重系数λ取值为5。较大的λ值意味着算法更倾向于减少频繁的起降操作，以保护机身结构和节省能耗。

5.1. 简单环境下的算法仿真结果

低复杂度环境主要表现为平坦地形与稀疏障碍物分布。在该环境下，算法优先采用地面移动模式以降低能耗。实验表明，本文算法在此类场景中能够快速收敛，路径总代价主要来源于地面行驶能耗，且运行稳定，拐点数量减少(图6)。

(a) A^*算法 (b) 本文算法

Figure 6. Simple environmental simulation experiment

图6. 简单环境仿真实验

5.2. 中复杂度环境下的算法仿真结果

中复杂度环境引入高程变化与局部障碍群，地形连续性降低。算法在该环境中能够依据局部地形特征动态调整行进策略，算法在综合考虑能耗、起飞降落成本后选择出最佳路径(图7和图8)。

(a) 路径规划对比图 (b) 适应度函数收敛曲线

Figure 7. Simulation experiments in complex environments

图7. 中复杂度环境仿真实验

Figure 8. Three-dimensional path

图8. 三维路径

5.3. 复杂环境下的算法仿真结果

高复杂度环境模拟具有密集障碍的极端灾害场景。在此类环境中，算法可以规避连续地形障碍与复杂地面条件，展现出优异的全局优化能力，通过DBO算法高效搜索高性能的模态切换序列，显著降低整体路径代价。尽管计算开销略有增加，但所规划路径在安全性与可行性方面显著优于经典A^*算法，验证了方法在复杂场景中的有效性与鲁棒性(图9和图10)。

(a) 路径规划对比图 (b) 适应度函数收敛曲线

Figure 9. Simulation experiment in a highly complex environment

图9. 高复杂度环境仿真实验

Figure 10. Three-dimensional path

图10. 三维路径

5.4. 改进算法比较分析

为定量评估算法在不同环境下的性能，本节对三类复杂度场景下的关键指标进行了系统统计与对比分析。所有数据为20次独立实验的平均值，结果如表1所示，表中综合代价为包含能耗、时间与风险的无量纲加权数值；路径长度单位为米(m)。

Table 1. Algorithm performance comparison across different environments

表1. 不同环境下算法性能对比

环境类型	使用算法	拐点个数	综合代价	路径长度
简单环境	A^*算法	10	40.63	34
	改进算法	7	40.03	35
中复杂度环境	A^*算法	6	47.66	47
	改进算法	3	45.31	43
复杂环境	A^*算法	12	74.14	71
	改进算法	10	57.15	40

改进算法在不同复杂度环境中展现出良好的适应性，特别是在中高复杂度环境中表现优异。其核心优势在于能够根据障碍物类型智能选择地面绕行或空中飞越策略，实现路径长度、运动平稳性和能源消耗的多目标优化。随着环境复杂度的增加，本文算法相对于经典A^*算法的优势愈加明显，这使其特别适合应用于实际机器人导航任务中遇到的复杂、动态环境。这种基于环境复杂度的自适应算法选择策略，能够在保证导航效果的同时优化计算资源的利用效率。

6. 结论

本文针对陆空两栖机器人跨域路径规划问题，提出了一种融合改进A^*算法与DBO优化器的规划框架，通过改进A^*算法实现初始路径搜索，结合DBO优化模态切换序列，有效解决了多模态自适应与全局优化问题，确保规划出一条综合代价最小的跨域路径。仿真结果表明，该算法在路径质量、规划效率和决策合理性方面均有显著提升。未来研究可围绕动态环境适应以及多目标优化等方向展开，进一步提升算法的实用性与推广性。

NOTES

^*通讯作者。