三维时空网格驱动的协同路径规划：智能机器人系统导航层次策略

论文题目：Multi-robot collaborative obstacle avoidance based on hierarchical path planning methods

第一/通讯作者：吴艳娟 天津理工大学电气工程与自动化学院教授，研究方向为电力系统优化与控制、智能电网、智能制造、新能源应用、电力电子技术应用、人工智能和大数据分析在电力系统中的应用、综合能源等。

E-mail：wuyjtjut@email.tjut.edu.cn

三维时空网格驱动的协同路径规划：智能机器人系统导航层次策略

论文摘要

多机器人系统（Multi‑Robot System, MRS）已广泛应用于仓储物流、工业自动化和智能农业等场景。然而，多机器人路径规划既要兼顾全局路径的最优性，又要具备对动态障碍和同伴机器人实时冲突的响应能力，并保证系统的协同效率和安全性。针对传统算法在局部避障和多机器人协同上的不足，本文提出一种基于层次化路径规划的协同避障方法。框架包含全局规划、时空冲突检测和局部协调三个层次：在全局层面，作者改进了 Jump Point Search (JPS) 算法，在代价函数中引入安全距离项与角度优先策略，减少冗余节点扩展并提升路径安全性；在中间层，构建三维时空网格模型预测机器人与动态障碍或其他机器人之间的潜在碰撞，实现冲突的提前预警；在局部层面，集成 动态窗口法（DWA） 并设计优先级协调策略，实现动态避障和多机器人局部冲突的有序解决。仿真实验表明，改进的 JPS 相比传统 A* 和原始 JPS 在路径长度、转向次数及搜索节点数量上均明显优化；优先级协调策略则在保持系统稳定性的同时显著减少冲突处理开销。该研究为复杂动态场景中的多机器人协同导航提供了具有现实应用价值的解决方案。

一、研究背景与问题

1.1 多机器人应用与挑战

• 多机器人系统已应用于仓储分拣、工业加工、智能农业及城市交通等场景，其协作能力直接影响系统效率与安全。
• 路径规划通常分为全局规划与局部避障两阶段：全局规划追求路径最短、转弯少、平滑度高，局部规划负责实时避障和调整。
• 现有全局算法（如 A*、RRT、APF）能提供近似最优路径，但在动态场景下难以应对突发冲突；局部算法可快速避障，却易陷入局部最优甚至死锁；混合策略常缺乏各层协调。

1.2 本文关注的核心问题

• 如何在复杂动态环境中实现多机器人路径规划的全局优化、局部快速响应与协同避障的统一。
• 关键挑战包括：在全局层面减少搜索节点并保证安全距离、在时空层面精准预测潜在碰撞、在局部层面合理分配优先级以避免系统死锁。

二、改进的全局路径规划方法

2.1 JPS 算法简介与不足

Jump Point Search (JPS) 是一种基于 A* 的启发式搜索算法，通过跳跃搜索减少节点扩展，从而加速路径规划。然而在障碍物密集或动态场景中，JPS 可能产生靠近障碍的路径，难以保证安全，且简单的水平或垂直搜索可能遗漏最优路径。

2.2 引入安全距离的启发函数

为解决传统 JPS 搜索冗余节点并提升安全性，作者在 JPS 的代价函数中融入路径安全成本和动态加权项，构成新的综合启发函数：

其中  为当前路径代价， 为启发函数， 为动态权重系数并随环境调整， 提高远离障碍物的权重， 则根据信息点与起点或终点的距离动态调整搜索方向。该改进使算法既考虑路径长度，又保证离障碍保持安全距离。

2.3 角度优先搜索策略

在改进的 JPS 中，作者提出角度优先搜索策略：首先将理想路径连接起点和终点作为参考，计算当前节点至目标的方向角度 ，公式为：

并定义单位方向向量  与其垂直向量 。根据  的范围，将搜索方向划分为优先级，优先探索与理想路径夹角最小的三条方向，其他方向作为最低优先级。这种设计减少了无效扩展并引导搜索靠近直线，提高了计算效率和路径平滑度。

三、时空冲突建模与局部协调策略

3.1 时空冲突模型与碰撞类型

多机器人系统的潜在碰撞可分为机器人与静态障碍、机器人与动态障碍以及机器人之间的冲突。其中机器人间的冲突又分为迎面冲突和侧向冲突。传统二维栅格无法在时间维度准确表达这些冲突，因此本文通过引入时间轴，将机器人的轨迹映射到三维时空网格，将潜在碰撞抽象成时空交点，能提前预测并规避冲突。

3.2 动态窗口法与运动学模型

局部避障采用经典的 动态窗口法（DWA），其核心是在可行速度空间中采样速度、预测轨迹，并选择最优控制量。机器人运动学模型可表达为：

其中 、 分别是机器人线速度和角速度。在速度采样阶段，DWA 约束线速度  与角速度  的上下界、加速度限制及制动距离限制，并通过评价函数

综合考虑方向偏差、障碍距离、速度大小和启发式距离，选择最优轨迹。

3.3 优先级协调策略

在多机器人场景中，仅依靠全局路径和局部避障难以解决机器人之间的运动冲突。作者设计了优先级协调策略：为每个机器人分配可动态调整的优先级，当低优先级机器人预测到与高优先级机器人存在冲突时，其主动减速或暂停，而高优先级机器人将其视为静态障碍继续前进。优先级根据任务紧急度、目标距离和冲突频率实时调整，从而避免固定优先级导致长时间阻塞。该策略在两种冲突类型中均能有效解决问题：迎面冲突时，高优先级机器人先通过，低优先级机器人等待；侧向冲突时，高优先级机器人保持原路径，低优先级机器人通过局部规划重新避让。

由于等待会带来延迟，作者用以下公式定义 协调延时：

其中  表示第  个机器人遭遇的冲突次数， 为高优先级机器人穿越冲突区所耗时间， 为低优先级机器人加速/减速造成的时间损失。尽管引入一定延时，但该机制换来了系统层面的稳定性和安全性。

3.4 方法流程

框架整体流程如下：首先使用改进的 JPS 为各机器人生成初始路径并去除冗余节点；然后利用角度优先策略进一步平滑路径；接着构建三维时空网格检测各机器人之间或与动态障碍之间的潜在冲突；若检测到冲突，则根据优先级策略在局部层面采用 DWA 进行重新规划；若无冲突，则机器人按原路径执行任务；当遇到未知动态障碍时，实时调用 DWA 进行局部重规划，否则继续行驶直至任务完成。

下图给出了层次化路径规划框架的流程图：

四、仿真与结果分析

4.1 单机器人路径规划实验

作者在随机生成障碍的 20×20 和 100×100 栅格地图上对改进 JPS 进行验证。结果表明，在 100×100 大尺度环境中，改进 JPS 相比 A* 算法路径长度减少约 13% 、转弯次数减少 50% 、搜索节点数量减少 74% 、计算时间减少 89% 。相较于原始 JPS，改进版在路径长度和计算时间上分别缩短 8% 和 49% 。在 20×20 中等规模环境中，改进 JPS 仍然取得最佳表现，显著优于仿生算法 DBO 与 SSA。

4.2 多机器人静态环境仿真

在 30×30 栅格静态环境中，设置三台机器人（AGV1～AGV3）的优先级依次降低。改进 JPS 为每个机器人生成全局路径，并在时空图中发现 AGV1 与 AGV2 在 42 s 时段会在同一位置相遇，属于迎面冲突；AGV2 与 AGV3 后续路径出现部分重叠，属于侧向冲突。通过优先级协调，AGV1 优先通过，其后 AGV2 与 AGV3 依次通过，最终所有机器人均安全到达目标。下图展示了静态环境时空冲突的三维示意：

4.3 多机器人动态环境仿真

在引入三台动态障碍和未知静态障碍的环境中，机器人起止点不同并重新随机设定优先级。三维时空图显示，AGV1 与动态障碍在 8.345 s 同时到达某位置，AGV3 与动态障碍在 24.038 s 时也存在碰撞风险。通过时空冲突检测及优先级策略，AGV1 和 AGV3 在本地规划阶段避让障碍，而 AGV2 因未与障碍产生实际交叉无需避让。最终三台机器人均成功抵达目标且无碰撞。以下分别给出多机器人全局路径规划结果和动态环境协同完成情况：

4.4 性能评价

综合实验结果表明，改进的 JPS 在保证全局最优性的同时显著提升了计算效率；时空网格模型能够提前预警并分类各类冲突；优先级协调策略通过少量延时换取了系统稳定性和安全性。该框架在静态和动态场景下均能保持 100% 的成功率，生成的路径更短、更平滑，且能实时应对动态障碍。

五、创新与展望

5.1 技术创新点

• 综合启发式函数：在 JPS 中引入安全距离、动态权重和危险节点评估，兼顾路径长度与安全性。
• 角度优先搜索：通过计算当前节点与目标之间的方向角，按优先级探索可能路径，大幅减少冗余节点并提高搜索效率。
• 三维时空网格建模：将时间作为第三维度，引入时空交点以预测潜在冲突，有效克服传统二维表示无法描述时间约束的缺陷。
• 优先级协同机制：针对多机器人冲突引入动态优先级和延时模型，实现去中心化的协同避障。

5.2 局限性与未来工作

虽然本文方法在仿真中表现优异，但仍存在以下不足：其一，优先级协调引入的等待时间会降低低优先级机器人的效率；其二，实验环境理想化，没有考虑传感器噪声和通信延迟；其三，算法尚未在真实机器人平台验证，工程适用性有待评估。未来研究可聚焦动态优先级分配机制、引入更智能的预测避障策略以及在真实工业场景的应用验证。

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。