融合图神经网络的移动机器人集群轨迹规划算法

Trajectory planning algorithm for mobile robot clusters based on fused graph neural networks

摘要

针对移动机器人集群作业时，因存在路径冲突导致机器人易出现碰撞，研究了融合图神经网络的移动机器人集群轨迹规划算法。构建了移动机器人运动学模型，描述了机器人运动特性；运用基于融合图神经网络的移动机器人集群运行环境特征提取模型，提取移动机器人集群运行环境多维度特征，全面了解环境信息；结合人工势场法，依据所提取特征，将目的地设成引力源，吸引机器人的运动方向为目的地方向；将障碍物设为斥力源，控制机器人避开障碍物，每个机器人受合力决定运动方向与速度，规划移动机器人集群运行时防碰撞轨迹。实验显示：所提算法可有效提取移动机器人集群运行环境多维特征，为多个移动机器人规划无碰撞、风险指数低于0.1的运行轨迹。

Abstract

Aiming at the problem of path conflicts among multiple robots running in the same environment during mobile robot cluster operations， which can lead to collisions among robots， this paper studies a trajectory planning algorithm for mobile robot clusters that integrates graph neural networks. Construct a kinematic model of a mobile robot to describe its motion characteristics； Using a fusion graph neural network-based mobile robot cluster operating environment feature extraction model， multi-dimensional features of the mobile robot cluster operating environment are extracted to comprehensively understand environmental information； Combining the artificial potential field method， based on the extracted features， the destination is set as a gravitational source， and the direction of motion that attracts the robot is towards the destination； Set obstacles as repulsive sources， control robots to avoid obstacles， and determine the direction and speed of each robot's movement based on the resultant force. Plan collision avoidance trajectories for mobile robot clusters during operation. The experiment shows that the proposed algorithm can effectively extract multidimensional features of the operating environment of mobile robot clusters， and plan collision free and risk index less than 0.1 running trajectories for multiple mobile robots.

Graphical abstract

关键词

融合图神经网络 / 残差连接 / 移动机器人 / 集群轨迹规划 / 人工势场法 / 防碰撞

Key words

fusion graph neural network / residual connection / mobile robots / cluster trajectory planning / artificial potential field method / anti-collision

0 引 言

现代应用对移动机器人集群的任务要求越来越复杂，不再局限于简单的点到点移动，或单一任务的执行^［1］。例如，在仓储物流中，需要多个机器人协同完成货物的搬运、分拣和存储；在搜索救援中，机器人集群需要在复杂的废墟环境中搜索幸存者，并进行协同救援行动。这些复杂任务需要精确的轨迹规划，来确保每个机器人能准确地执行其任务^［2］，并且与其他机器人协同工作，以实现整体任务的目标^［3］。

杨振等^［4］将改进后的A^*算法和动态窗口法相融合，在融合算法中引入优先级避障策略，根据机器人的任务紧急程度、位置等因素为其分配优先级，使多机器人在动态环境中能更好地协调避障，避免冲突，实现高效的路径规划。但A^*算法改进侧重节点扩展与路径优化，对大规模环境突变适应性差；动态窗口法在局部避障时，面对环境骤变难以获取全局最优路径，导致多机器人在复杂动态环境中无法及时有效调整规划路径。

张凯翔等^［5］以 HCA^*算法为基础，将讨价还价博弈机制和熔断机制相互配合，前者通过机器人之间的协商来解决冲突，找到可行的路径方案，后者可以避免无效搜索，节省计算资源和时间。两者协同作用，提高路径求解的成功率，兼顾路径的代价，实现多机器人路径规划。而环境动态多变，诸如临时障碍物出现、机器人故障、任务变更等情况频发。该算法虽可借助讨价还价博弈与熔断机制处理部分冲突，但面对剧烈环境变化时，重新开展博弈与路径规划的进程较为迟缓，难以快速适应环境的快速转变。

张凯翔等^［6］还以调度次序优化为核心，构建分层算法。优化遗传算法，迭代生成机器人调度序列，规划层采用改进的IHCA^*算法依序求解路径，实现多机器人路径高度耦合规划。但遗传算法用于优化层调度序列时，随着机器人数量增多，其搜索空间呈指数级膨胀，每次迭代需评估筛选海量序列，无法适应对响应速度要求高的场景。

褚晶等^［7］构建 Petri 网模型描述多机器人运动状态与行为，用线性时序逻辑（LTL）语言精确表述月球基地建设等任务的逻辑和时序要求，结合二者协同运算分析，求解多机器人路径规划结果。而在一些需要机器人进行灵活决策和自适应调整的任务中，LTL 语言的精确性和固定的逻辑结构可能无法充分涵盖所有情况，导致任务描述不完整，进而影响路径规划的准确性。

本文提出融合图神经网络的移动机器人集群轨迹规划算法，此算法能利用图神经网络中，融合残差连接的图卷积神经网络，提取移动机器人集群运行环境的多维度特征作为移动机器人集群轨迹规划的基础数据，结合人工势场法，为移动机器人集群规划防碰撞运行轨迹。

1 移动机器人集群轨迹规划算法

1.1　移动机器人运动学方程

移动机器人集群作业时，向目标点O运动，运动信息主要包含线速度v_{\mathrm{s}}与角速度\varpi，其运动学方程是：

\varphi =v_{\mathrm{s}}\mathrm{c}\mathrm{o}\mathrm{s}{P}_{\mathrm{a}}（1）

\phi =v_{\mathrm{s}}\mathrm{s}\mathrm{i}\mathrm{n}{P}_{\mathrm{a}}（2）

P_{\mathrm{a}}=\varpi（3）

式中：\varphi、\phi分别为集群中某移动机器人在横轴方向上投影的速度分量、纵轴方向上投影的速度分量；P_{\mathrm{a}}为移动机器人运行方向角度。

移动机器人集群轨迹规划时，主要通过调节各移动机器人的v_{\mathrm{s}}、P_{\mathrm{a}}，保证集群运行环境中在不出现碰撞的情况下抵达目的地^［8，9］。

1.2　基于融合图神经网络的移动机器人集群运行环境特征提取模型

1.2.1　移动机器人集群运行环境特征类型

融合图神经网络进行移动机器人集群运行环境特征提取时，主要涉及从环境的空间、拓扑以及动态变化多个维度进行信息挖掘。

空间维度上，利用激光雷达、摄像头等外部传感器^［10］，将障碍物与机器人分别抽象为图节点，通过图神经网络提取障碍物的位置、机器人的坐标；拓扑维度中，通过分析环境地图图结构特征，识别区域连通性与关键节点、边，生成的栅格地图特征信息；动态维度下，一方面持续感知人员移动、物体变动等环境变化，实时更新环境特征以优化轨迹规划，另一方面捕捉机器人集群内各成员的相对位置特征。

1.2.2　用于机器人集群运行环境特征提取的融合图神经网络设计

本文所用的融合图神经网络为融合残差连接的图卷积神经网络，此网络结构分为输入层、图卷积层、图池化层、图全连接层以及输出层^［11-13］。

输入层的主要任务是将原始的环境数据转化为适合网络处理的图结构数据。在移动机器人集群运行环境中，传感器会采集到大量的环境信息，包括障碍物的位置、形状，机器人的位置、姿态等。输入层会将这些信息抽象为图的节点和边，例如将障碍物和机器人分别表示为图中的节点，节点之间的连接关系（如相邻关系、可达关系等）表示为边。同时，为每个节点和边赋予相应的特征向量，这些特征向量将作为网络的输入。

设置图结构是F=\left(U,F,\mathit{B}\right)，U、F、\mathit{B}依次代表节点、边以及邻接矩阵。图结构采用无向图模式构建，在移动机器人集群运行环境特征提取中，设置图中边为f_{ij}，顶点分别为u_i、u_j，邻接矩阵为：

{\mathit{B}}_{ij}=\left\{\begin{array}{l}{f}_{ij},f_{ij}\in F\\ \mathrm{0},\mathrm{其他}\end{array}\right.（4）

在移动机器人集群运行环境特征提取中，图卷积神经网络将环境中的障碍物、机器人个体等，抽象为图中的节点。每个节点初始包含如障碍物的位置、形状，机器人的坐标、姿态等自身特征信息。通过图卷积运算，节点会将自身特征与邻居节点的特征进行聚合。例如，机器人节点会聚合周围障碍物节点的位置、大小特征，以及相邻机器人节点的坐标、速度等信息，从而生成新的节点表示。

图卷积神经网络中聚合邻居节点的详细运算方法如下：

K^{\left(q+\mathrm{1}\right)}=\alpha \left(\widehat{\mathit{B}}{K}^{\left(q\right)}{\omega }^{\left(q\right)}\right)（5）

式中：K^{\left(q+\mathrm{1}\right)}、K^{\left(q\right)}分别为层q+\mathrm{1}、层q的隐藏状态，即各层的特征表示；{\omega }^{\left(q\right)}、\alpha分别为层q的权重参数、激活函数；\widehat{\mathit{B}}为归一化后拉普拉斯矩阵，在图卷积过程中起到特征平滑与聚合作用。

从图卷积本质来看，式（5）是在图结构上对节点特征进行聚合与变换。\widehat{\mathit{B}}{K}^{\left(q\right)}相当于在图结构中，结合节点之间连接关系，将邻居节点的特征聚合^［14］，则类似于在传统图像卷积中通过卷积核在图像上滑动聚合周边信息，只不过这里是在图的拓扑结构上对节点特征操作，其次与{\omega }^{\left(q\right)}相乘，即可筛选重要特征。

\widehat{\mathit{B}}={\tilde{\mathit{E}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\tilde{\mathit{B}}{\tilde{\mathit{Z}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}（6）

\tilde{\mathit{B}}=\mathit{B}+\mathit{L}（7）

式中：\mathit{B}、\mathit{L}分别为可描述节点连接关系的矩阵、单位矩阵；\tilde{\mathit{B}}为B、L之和；\tilde{\mathit{Z}}为\tilde{\mathit{B}}的对角矩阵。

将式（6）、式（7）与式（5）融合，则图神经网络提取的移动机器人集群运行环境特征为：

K^{\left(q+\mathrm{1}\right)}=\alpha \left({\tilde{\mathit{E}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\widehat{\mathit{B}}{\tilde{\mathit{Z}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}{K}^{\left(q\right)}{\omega }^{\left(q\right)}\right)（8）

而传统的图卷积神经网络，随着层数增加，数据经过层层变换，最初输入的信息可能会逐渐被 “稀释” 或改变，为此，在此网络中引入残差连接，残差连接引入 “快捷连接”（也叫跳跃连接），每一层都能保留一部分未经过复杂变换的原始输入信息。则融合残差连接的图卷积更新结果为：

K^{\left(q+\mathrm{1}\right)}=\alpha \left({\tilde{\mathit{E}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\widehat{\mathit{B}}{\tilde{\mathit{Z}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}{K}^{\left(q\right)}{\omega }^{\left(q\right)}\right)+K^{\left(q\right)}（9）

图池化层压缩图卷积特征提取结果，则输出的移动机器人集群运行环境特征矩阵为：

{\mathit{K}}^{\text{'}}=\left(\mathit{K}\mathrm{*}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{h}\left(x\right)\right)（10）

式中：x为特征重要度。

图全连接层将K^{\text{'}}进行关键特征整合^［15］。输出结果为：

{\mathit{K}}^{″}=\alpha \left({\mathit{K}}^{\text{'}}{\omega }^{\mathrm{T}}+c\right)（11）

式中：c为偏置项；\omega为此层权重。

输出层输出多维度移动机器人集群运行环境特征提取结果如下：

\widehat{\mathit{K}}=\mathrm{s}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{x}\left(\widehat{\mathit{B}}{\mathit{K}}^{″}\mathit{\omega }\right)（12）

1.3　基于人工势场法的防碰撞动态轨迹规划方法

结合1.2.2节提取的多维度运行环境特征\widehat{\mathit{K}}，使用基于人工势场法的防碰撞动态轨迹规划方法规划防碰撞运行轨迹。此方法将环境中目的地设成引力源，吸引机器人的运动方向为目的地方向；将障碍物设为斥力源，控制机器人避开障碍物。合力决定集群中每个机器人运动方向与速度，规划防碰撞轨迹。

引力势场函数设成：

{\Omega }_y\left(e\right)=\frac{\mathrm{1}}{\mathrm{2}}\delta d^{\mathrm{2}}\left(e,e_{\mathrm{g}}\right)（13）

式中：e、\delta分别为集群中某移动机器人位置、引力场增益系数；d\left(e,e_{\mathrm{g}}\right)为机器人与目的地位置e_{\mathrm{g}}的距离，此距离特征由1.2小节方法提取，d\left(e,e_{\mathrm{g}}\right)\in \widehat{K}。

引力计算如下：

W_y\left(e\right)=-\nabla {\Omega }_y\left(e\right)（14）

斥力势场函数为：

{\Omega }_x\left(e\right)=\left\{\begin{array}{l}\frac{\gamma }{\mathrm{2}}\left(\frac{\mathrm{1}}{d\left(e,e_{\mathrm{u}}\right)}-\frac{\mathrm{1}}{d_{\mathrm{m}}}\right),d\left(e,e_{\mathrm{u}}\right)\le d_{\mathrm{m}}\\ \mathrm{0},d\left(e,e_{\mathrm{u}}\right)>d_{\mathrm{m}}\end{array}\right.（15）

式中：\gamma、e_{\mathrm{u}}、d_{\mathrm{m}}依次代表斥力势场常量、障碍物位置、障碍物影响范围；d\left(e,e_{\mathrm{u}}\right)代表与机器人距离最短的障碍物位置，d\left(e,e_{\mathrm{u}}\right)\in \widehat{\mathit{K}}。

斥力计算如下：

W_x\left(e\right)=-\nabla {\Omega }_x\left(e\right)（16）

机器人依据合力确定运动方向与速度，合力方向决定运动方向，合力大小结合动力学特性确定速度，其运动轨迹即为防碰撞运行轨迹。

合力计算如下：

W_{\theta }=W_y\left(e\right)+W_x\left(e\right)（17）

在移动中，机器人随位置变化实时重新计算引力和斥力，调整v_{\mathrm{s}}、P_{\mathrm{a}}以适应环境和避障。对于移动机器人集群，把其他机器人也当作斥力源，调节各移动机器人的v_{\mathrm{s}}、P_{\mathrm{a}}，保证集群运行环境中在不出现碰撞的情况下抵达目的地。

2 实验分析

2.1　实验环境

图1是使用本文算法作为移动机器人集群轨迹规划技术的智能仓储管理系统拓扑图，在此系统管理下，图2是此仓储环境中机器人运行场景图。

在智能仓储管理系统中，上位机经以太网与下层设备交互数据。交换机作为网络关键节点，负责数据转发分配，连接移动机器人，搭建上位机与机器人通信链路。移动机器人承担货物搬运等具体任务，此拓扑结构通过合理层级与网络连接，为移动机器人集群轨迹规划等功能奠定硬件基础。表1是移动机器人参数信息。

在实验环境中，4个移动机器人负责货物分拣，并运送至仓库。

2.2　移动机器人集群轨迹规划效果分析

智能仓储管理系统使用本文算法后，本文算法利用基于融合图神经网络的移动机器人集群运行环境特征提取模型，提取移动机器人集群运行环境的空间维度特征、拓扑维度特征、动态维度特征。提取结果可视化信息如图3所示。

分析图3可知：本文算法在空间维度特征提取方面表现优异，可精准确定移动机器人（①~④）在空间中的坐标位置，同时能明确货架等障碍物的位置。这充分表明算法能借助激光雷达等外部传感器，有效地将障碍物与机器人抽象为图节点，并准确获取其位置信息。

在拓扑维度特征提取上，货架在图3中的分布呈现出特定结构特征，本文算法能敏锐识别此类区域布局，反映出其具备对环境地图图结构特征的深度分析能力。

针对动态维度特征提取而言，图3中所呈现的工作人员移动位置特征，凸显本文算法对环境中动态变化因素（如人员移动）的持续感知能力，为移动机器人轨迹规划的优化奠定坚实基础。

结合所提取的多维度特征基础之上，本文算法对移动机器人集群移动轨迹规划结果如图4所示（彩图参见电子版），其中，红色虚线表示机器人集群运行轨迹。

分析图4可知：多个移动机器人移动轨迹没有出现碰撞情况，在仓储环境中稳定运行，有效完成各自货架物品运输任务，本文算法的轨迹规划效果理想。

最后，引入风险指数作为轨迹规划效果测试指标，测试本文算法与基于改进A^*算法和动态窗口法的机器人轨迹规划算法、基于HCA^*算法的机器人轨迹规划算法，在仓储移动机器人集群轨迹规划问题中使用后机器人运行的风险指数，风险指数越小，表明机器人运行过程中碰撞事故的风险也就越低。3种算法的风险指数对比结果如图5所示。

分析图5可知：3种算法中，本文算法所规划的轨迹风险指数最低，随着障碍物数量增多，风险指数数值控制在0.1之内，表明机器人运行过程中碰撞事故的风险较小，机器人集群的碰撞风险最低。

4 结束语

从理论层面分析，本文提出的融合图神经网络的移动机器人集群轨迹规划算法充分利用融合图神经网络强大的特征提取能力，提取移动机器人集群运行环境空间、拓扑和动态变化多维度特征，为后续轨迹规划提供更加全面且准确的输入信息。从实验效果方面分析，本文算法使用下，多个移动机器人在仓储环境中运行轨迹无碰撞，能稳定、低风险地完成物品运输任务。

参考文献

[1] 武星, 汤凯, 李兴达, 等. 多视角雷达点云融合的移动机器人集群跟踪[J]. 仪器仪表学报, 2023, 44(12): 175-186.

[2] Wu Xing, Tang Kai, Li Xing-da, et al. Mobile robot cluster tracking based on multi-perspective Lidar point cloud fusion[J]. Chinese Journal of Scientific Instrument, 2023,44(12):175-186.

[3] 陈晨, 殷诗雨, 邱星星, 等. 采样数据交互的异构非完整轮式机器人集群连通保持切换编队控制[J]. 南京理工大学学报: 自然科学版,2024,48(5):615-625, 634.

[4] Chen Chen, Yin Shi-yu, Qiu Xing-xing, et al. Connectivity-preserving switching formation control of heterogeneous nonholonomic wheeled robots with sampled-data interaction[J]. Journal of Nanjing University of Science and Technology, 2024, 48(5):615-625, 634.

[5] 郭万金, 李儒, 郝钦磊, 等. 农业物料移运机器人协同作业时间最优轨迹规划方法[J]. 农业机械学报,2024, 55(1): 22-38.

[6] Guo Wan-jin, Li Ru, Hao qin-lei, et al. Time-optimal trajectory planning method for cooperative working of agriculture material handling robot[J]. Transactions of the Chinese Society for Agricultural Machinery, 2024,55(1):22-38.

[7] 杨振, 李俊丽, 杨立炜, 等. 安全性A^*融合DWA的分布式多移动机器人路径规划方法[J]. 控制工程,2024, 31(12): 2284-2295.

[8] Yang Zhen, Li Jun-li, Yang Li-wei, et al. Distributed multi-mobile robots path planning method based on safe A^*fused with dynamic window approach[J]. Control Engineering of China, 2024,31(12):2284-2295.

[9] 张凯翔, 毛剑琳, 向凤红, 等. 基于讨价还价博弈机制的B-IHCA*多机器人路径规划算法[J]. 自动化学报, 2023, 49(7): 1483-1497.

[10] Zhang Kai-xiang, Mao Jian-lin, Xiang Feng-xiang, et al. B-IHCA*,a bargaining game based multi-agent path finding algorithm[J]. Acta Automatica Sinica, 2023,49(7):1483-1497.

[11] 张凯翔, 毛剑琳, 宣志玮, 等. 面向关隘地形的分层调度多机器人路径规划[J]. 计算机集成制造系统,2024, 30(1): 172-183.

[12] Zhang Kai-xiang, Mao Jian-lin, Xuan Zhi-wei, et al. Hierarchical scheduling based multi-robot path planning for pass terrain[J]. Computer Integrated Manufacturing Systems, 2024,30(1):172-183.

[13] 褚晶, 周力, 岳颀, 等. 一种基于Petri网的多机器人路径规划建模方法[J]. 西北工业大学学报, 2024, 42(4): 716-725.

[14] Chu Jing, Zhou Li, Yue Qi, et al. A Petri nets-based modeling method for multi robot path planning[J]. Journal of Northwestern Polytechnical University, 2024,42(4):716-725.

[15] 毛剑琳, 贺志刚, 张书凡, 等. 面向多到一任务交接的多机器人协作路径规划算法[J]. 仪器仪表学报,2024, 45(9): 237-248.

[16] Mao Jian-lin, He Zhi-gang, Zhang Shu-fan, et al. Multi-robot collaborative path planning algorithm for many-to-one task handover[J]. Chinese Journal of Scientific Instrument, 2024,45(9):237-248.

[17] 程晓明, 刘银华, 赵文政. 面向大型三维结构检测的多机器人覆盖路径规划方法[J]. 计算机集成制造系统, 2023, 29(1): 246-253.

[18] Cheng Xiao-ming, Liu Yin-hua, Zhao Wen-zheng. Multi-robot coverage path planning for large 3D structure inspection[J]. Computer Integrated Manufacturing Systems, 2023,29(1):246-253.

[19] Lewke M, Wu H J, List A, et al.Automated trajectory planning and analytical improvement for automated repair by robot-guided cold spray[J].Journal of Thermal Spray Technology,2024,33(2/3):515-529.

[20] 陈金杰, 王一蕾, 傅仰耿. 注意力融合机制和拓扑关系挖掘的异构图神经网络[J]. 福州大学学报: 自然科学版, 2025, 53(1): 1-9.

[21] Chen Jin-jie, Wang Yi-lei, Fu Yang-geng. Heterogeneous graph neural network based on attention fused mechanisms and topology relation mining[J]. Journal of Fuzhou University (Natural Science Edition), 2025,53(1):1-9.

[22] 秦志龙, 朱一峰, 邓琨, 等. 融合路径优化的异构图神经网络算法[J]. 小型微型计算机系统, 2025, 46(3): 627-635.

[23] Qin Zhi-long, Zhu Yi-feng, Deng Kun, et al. Path Optimization based heterogeneous graph neural network algorithm[J]. Journal of Chinese Computer Systems, 2025, 46(3): 627-635.

[24] 刘冠麟, 赵志耘, 曾文. 一种基于图神经网络的技术融合预测方法[J]. 情报杂志, 2024, 43(12): 117-124, 185.

[25] Liu Guan-lin, Zhao Zhi-yun, Zeng Wen. A technology convergence prediction method based on graph neural networks[J]. Journal of Intelligence, 2024, 43(12):117-124, 185.

[26] 江昌旭, 卢玥君, 邵振国, 等. 基于图神经网络多智能体强化学习的电力-交通融合网协同优化运行[J]. 高电压技术, 2023, 49(11): 4622-4631.

[27] Jiang Chang-xu, Lu Yue-jun, Shao Zhen-guo, et al. Collaborative optimization operation of integrated electric power and traffic network based on graph neural network multi-agent reinforcement learning[J]. High Voltage Engineering, 2023, 49(11): 4622-4631.

[28] 旺扎拉, 戴景民. 无冲突协调自动联控集群机器人方法与仿真[J]. 计算机仿真, 2024, 41(4): 451-455.

[29] Wang Zha-la, Dai Jing-min. Simulation of conflict free coordination and automatic joint control method for cluster robots[J]. Computer Simulation, 2024, 41(4): 451-455.

基金资助

国家自然科学基金项目(61871444)