面向工厂环境中障碍物与环境变化的鲁棒多智能体路径规划（MAPF）方法

《Sensors》：Robust Multi-Agent Path Finding Method for Obstacles and Environmental Changes in Factory Environments

　　

多智能体路径规划（MAPF）是工厂与仓储物流自动化的核心技术。为兼顾计算效率与执行可行性，能够反映工厂环境结构特性的基于引导策略（guidance-based）方法已得到广泛应用。然而，此类方法通常假设环境为静态，预定义的引导策略始终有效。因此，突发障碍物可能导致机器人间碰撞或死锁。为使标称MAPF计划对执行不确定性具备鲁棒性，已有研究将界定的执行延迟纳入MAPF。一种代表性方法为k鲁棒多智能体路径规划（kR-MAPF），其利用全局鲁棒性参数k对允许执行延迟进行建模。然而，当由障碍物引发的大延迟由单一全局鲁棒性参数表示时，kR-MAPF会引入不必要的保守性并扩大搜索空间。搜索空间的扩大会增加规划运行时间，并降低大规模机器人集群运行中的路径效率。本文提出一种多机器人路径规划框架，该框架根据实时障碍物信息对每个路段的引导策略进行更新。所提框架识别受障碍物影响的机器人并选择性地对其路径进行重规划，从而在保持路径规划成功率与路径效率的同时减少不必要的计算。在包含多达100台机器人的工厂环境中进行的仿真结果表明，所提框架在所有测试条件下均保持100%成功率。与取不同k值的kR-MAPF相比，所提框架的规划运行时间降低约35%–79%，工作完成时间（flowtime）降低约7%–24%。这些结果表明，障碍物感知选择性重规划能够改善动态工厂环境中的实时性能与路径效率。所提框架为结构化工业环境中稳定的大规模多机器人运行提供了技术基础。

研究背景与问题

多智能体路径规划（MAPF）用于在图上为多个智能体计算无碰撞路径，是现代多机器人协调（multi-robot coordination）的基础。在智慧工厂与自动化仓储等结构化环境中，路径规划必须在上百台自主移动机器人实时运行的同时避免碰撞。由于寻找最优解是NP-hard问题，实际系统常采用基于引导策略的方法，将工厂抽象为由走廊（corridor）与交叉口（junction）组成的拓扑图，并预先生成符合机器人运动学特性的分段运动引导策略。该方法通过反映环境结构特性来缩小搜索空间，因而具备较好的计算效率与执行可行性。然而，此类方法通常假设环境是静态的，预定义引导策略始终有效；一旦环境中出现突发障碍物或动态变化，局部避障导致的执行延迟会使全局计划失效，引发机器人间碰撞或死锁。为应对此类不确定性，现有方法如kR-MAPF通过引入全局鲁棒性参数k，在所有机器人的整条路径上分配统一的时间裕量，以保证有界延迟下的安全性。但该方式将局部障碍物造成的大延迟用单一全局参数建模，会对未受影响路段施加不必要的保守约束，不仅降低路径效率，还因在基于冲突搜索（Conflict-Based Search，CBS）框架中冲突树（conflict tree）分支大量增多而扩大搜索空间，影响大规模机器人集群的实时性。

研究内容、结论与意义

针对上述问题，研究人员提出了一种面向动态工厂环境的多机器人路径规划框架。该框架在现有基于引导策略的环境表示基础上，新增障碍物感知规划层：由中心服务器实时聚合各机器人的观测信息，维护分段全局障碍物图；战略计划器根据障碍物类型为各路段分别更新引导策略；仅在检测到受影响机器人时触发选择性重规划。仿真结果表明：在100 m×100 m工厂环境中，机器人数量从10台增至100台时，该方法路径规划成功率均保持100%；与不同k值下的kR-MAPF相比，规划运行时间降低约35%–79%，工作完成时间（flowtime）降低约7%–24%，且1 s内完成规划的比例达到50%，接近无障碍物条件下的55%。这些结果说明，该方法在保障安全性的同时兼顾了路径效率与实时性，为结构化工业环境中的大规模多机器人稳定运行提供了算法基础。该论文发表于《Sensors》。

关键技术方法

该框架的核心机制包括三项：事件驱动的分段障碍物图管理、面向路段的战略引导策略更新，以及基于20 s时间窗的受扰机器人识别与选择性重规划。中心服务器将机器人感知的障碍物信息汇总为全局分段障碍物集合，并区分静态障碍与动态障碍；战略计划器据此更新运动引导、计算安全间隔（Safe Interval，SI），用于静态障碍的双向走廊防死锁；以及可变交通调节裕量（Traffic Regulation Margin，TRM），用于动态障碍的入段时间间隔约束；随后仅对预计在20 s内经过含障路段的机器人集合R_affected启动CBS重规划，未受影响机器人保持原路径。这种设计将不确定性约束限定在局部路段和相关机器人，抑制了冲突树分支。

研究结果

成功率：无障碍物最优CBS基线在所有条件下均保持100%成功率；kR-MAPF随k增大及机器人数量增加成功率下降；而所提方法在10至100台机器人条件下均保持100%成功率，显示出良好的规划完备性。

工作完成时间：在100台机器人场景中，所提方法的flowtime为4580.5 s，比kR-MAPF（k=5 s）降低约24%，且仅比无障碍物CBS结果4466.3 s高约2.5%，说明其在应对障碍的同时维持了路径效率。

路径规划运行时间：所提方法在100台机器人时的平均重规划运行时间约为3417.6 ms，相比kR-MAPF（k=5 s时约15942.8 ms）降低约79%；即使在机器人密集场景下也能避免搜索空间过度膨胀。

路径规划实时性能：在100台机器人场景下，所提方法在1 s内完成规划的比例为50%，仅比无障碍物条件下的55%低5个百分点，而kR-MAPF各k值均低于5%。这表明选择性约束显著降低了障碍物带来的计算复杂度。

讨论与结论

讨论指出，kR-MAPF将统一时间裕量作用于所有机器人及所有路段，导致CBS冲突树深度和宽度均增加；而所提方法通过分段障碍物图管理和受扰机器人选择性重规划，仅在实际受影响路段上生成约束，避免不必要分支和冗余等待，从而在运行时间与flowtime上均取得优势。其技术贡献可概括为：提出了分段障碍物图的在线维护、静态与动态障碍物的差异化引导策略，以及基于CBS的选择性重规划框架。

研究结论可概括为：研究人员提出了一种利用障碍物信息提升动态工厂环境下多机器人路径规划鲁棒性并保持实时性能的多机器人路径规划框架。实验结果表明，在多达100台机器人的环境中该方法成功率达100%，相比kR-MAPF运行时间最多降低约79%，flowtime最多降低约24%，且1 s内完成规划比例与无障碍物条件相当。未来研究将进一步结合障碍物状态预测模型，并在更多样化的工厂布局中验证该框架的实用性。