综述：多机器人路径规划优化技术：连通性、效率与安全视角下的避碰与性能指标综述

《Technologies》：Optimisation Techniques for Multi-Robot Path Planning: A Review of Collision Avoidance and Performance Metrics in Connectivity, Efficiency and Safety

　　

路径规划是多机器人系统(Multi-Robot Systems, MRS)的核心问题，直接影响作业效率、执行时间与运营成本。尽管已有大量算法被提出并得到成功应用，但在杂乱或动态环境中实现全局最优解仍面临重大挑战。随着机器人数量增加，系统在可扩展性、计算效率、鲁棒性及协调复杂性等方面的问题持续推动着更可靠方法的发展。本研究基于广泛应用的路线图规划方法，综述了多机器人路径规划(Multi-Robot Path Planning, MRPP)的建模方法、优化准则及求解算法，重点关注三种图基算法：MRPP算法、中央算法(Central Algorithm, CA)和优化中央算法(Optimized Central Algorithm, OCA)。这些算法采用可见图(Visibility Graph, VG)进行环境表征，利用迪杰斯特拉(Dijkstra)算法计算最短路径，并通过引入代数连通性(Algebraic Connectivity, λ2)提升协调性、安全性与可扩展性。此外，本文从概念层面探讨了仿真环境、云机器人与人工智能框架等技术背景与实现平台，并强调了这些方法在辅助机器人领域的潜在应用，特别是在医疗与人本环境中支持安全可靠导航的价值。文章综合了理论与实践见解，指出现有局限与挑战，并为高效、可扩展且鲁棒的多机器人路径规划指明了未来研究方向。

1. 引言

多机器人系统凭借任务效率高、鲁棒性强、可扩展性好等优势，在工业、医疗、军事与环境监测等领域的应用日益广泛。然而，多机器人路径规划(MRPP)仍是核心挑战：需为共享环境中的多个机器人生成无碰撞、计算高效且协调一致的轨迹，且随机器人数量增加，规划的可扩展性、通信维护与鲁棒性问题愈发复杂。现有方法可分为栅格法、采样法与路线图法，其中路线图法因能将连续运动规划转化为带最优性保证的离散图搜索问题而备受关注。图基方法为建模机器人交互与环境约束提供了结构化且数学严谨的框架，其中可见图(VG)是代表性路线图方法，可在静态多边形环境中结合经典最短路径算法实现最优路径计算，并可通过引入代数连通性(λ₂)等图论度量增强多机器人系统的协调性与连通性保持能力。近年来，航天器轨道威胁规避等航空航天领域的任务规划进展，也为图基多机器人规划框架的鲁棒性与安全保证提供了跨域启示。本文聚焦MRPP、CA与OCA三种代表性图基算法，它们均以VG构建与Dijkstra算法为基础，但在规划架构、优化准则与安全机制上存在差异：MRPP强调协调与连通性保持，CA与OCA分别侧重计算效率与安全提升。本研究的主要贡献在于：系统综述图基运动规划方法及其在多机器人系统中的应用；提出融合VG规划与代数图论度量的分析视角，用于评估协调性与连通性；对比MRPP、CA与OCA在计算效率、路径最优性、鲁棒性与安全性能上的差异，旨在分析其建模方法、优化策略与性能权衡，并明确可扩展高效多机器人系统的未来研究方向。

2. 材料与方法

本研究采用系统性图谱研究(Systematic Mapping Study, SMS)方法，遵循PRISMA（系统评价与荟萃分析首选报告项目）2020操作协议，对图基MRPP相关研究进行识别、筛选、图谱构建与分析，目标是对MRPP、CA与OCA算法进行结构化高层评估与主题分类。PRISMA框架虽源于临床证据合成，但其文献识别、筛选与资格评估的系统流程已被工程与计算机科学领域广泛采纳，可有效降低选择偏差并保证架构可追溯性；在本文的计算与理论导向语境中，该方法主要作为分类算法分类与结构边界映射的系统性图谱研究，而非统计荟萃分析，因此属于定性、结构化与分析性综述。文献检索覆盖IEEE Xplore、ScienceDirect、SpringerLink与Google Scholar等数据库，时间跨度为2012至2026年，关键词组合包括多机器人路径规划(MRPP)、避碰(CA)与优化中央算法(OCA)、图基方法与可见图(VG)、代数连通性(λ₂)与连通性维护、分布式通信与集群控制、人工智能框架（含强化学习RL与图神经网络GNN）、安全关键约束任务规划（含航天器自主导航与轨道避碰的SMT方法）。研究筛选遵循预定义纳入排除标准，区分核心研究（用于主要分析）与支持参考文献（提供理论背景与技术洞察），确保方法透明性与领域覆盖全面性。纳入标准为：聚焦MRPP、CA或OCA算法的原创研究或高质量综述；采用图论、Voronoi图或混合概率路线图等多机器人路径规划、协调或避碰方法且具备方法学严谨性；提供图基、路线图基或优化基解决方案以提升可扩展性、连通性或鲁棒性（如Dijkstra算法、冲突基搜索、安全状态估计）；涵盖行星探测、搜救、辅助机器人与医疗系统、航天器任务规划等代表性应用场景。排除标准为：仅聚焦单机器人、路径计算缺乏方法学或数学清晰度、非同行评审或技术细节不足。数据提取与合成阶段，初始检索得225篇文献，去重后剩185篇，经标题摘要筛选后102篇进入全文评审，最终41篇核心研究纳入主要图谱分析，另纳入54篇支持参考文献以提供代数连通性、ROS/Gazebo/Webots等技术基础。与传统临床系统综述不同，本研究未进行统计荟萃分析，而是对算法方法进行对比分析性合成，梳理不同环境下的性能权衡、设计原则与实践适用性，并结合航空航天安全关键任务规划的跨域洞见，支撑动态安全关键环境下地面与轨道MRPP方法的综合评估。

3. 多机器人系统

多机器人系统中多个机器人在共享环境中协作完成单机器人难以处理的复杂、大规模或危险任务，其核心优势在于可通过冗余流程与责任分担提升系统容错性，单个机器人故障不影响整体任务延续，从而增强系统弹性与鲁棒性。但该系统也存在局限性：动态不确定环境下的协调复杂性突出，通信约束可能降低系统性能，需鲁棒信息交换机制保障；单个机器人故障可能影响整体性能，需持续研究解决协调、路径规划、通信与现实约束下的自主性等挑战。多机器人系统可从组成、协调与通信三个维度分类：组成上分为同构系统（机器人相同，适合并行受限任务，设计部署简单、成本低）与异构系统（机器人能力多样，适合复杂任务，灵活性与适应性强但协调控制复杂度高）；协调上分为集中式（单一领导者掌握全局信息，规划效率高但通信故障敏感，适合小规模静态环境）与分布式（机器人自主决策，可扩展性与鲁棒性强，但易产生次优解，需复杂通信机制保障避碰与任务完成）；通信上分为显式通信（如Wi-Fi）、隐式通信（通过感知或环境交互推断信息）与网络化通信，需协同设计通信协议与控制策略以支持大规模团队。多机器人路径规划的动机在于生成无碰撞、最优且计算高效的轨迹，而多机器人场景还需额外考虑机器人间协调以避免互撞，面临可扩展性、通信约束与个体故障鲁棒性等挑战。图论为机器人运动规划提供了基础工具，可将工作空间抽象为图结构，顶点对应机器人位置、航点或障碍物顶点，边对应可行路径、可见关系或通信链路；加权图的边权可编码距离、能耗、通行成本或碰撞风险，支持精确优化决策。代数图论通过分析图的邻接矩阵与拉普拉斯矩阵的谱特性（特别是代数连通性λ₂），可量化与保持通信连通性与协调鲁棒性：λ₂越大表明图连通性越强、对链路故障的鲁棒性越高，在多机器人网络中可用于指导机器人优先级排序以维持通信连通性。图基运动规划技术主要包括单元分解法、路线图法与势场法，本文聚焦路线图法：可见图(VG)通过连接所有互见顶点生成多边形环境中的最短路径，但路径易贴近障碍物且可扩展性差；Voronoi图(VD)生成与最近障碍物等距的路径，安全性高但路径长度非最优；二者均适用于静态已知环境，路径计算常采用Dijkstra算法（离线静态规划保证最优性）或A/D（动态环境实时重规划）。图论规划的优势在于模块化（环境与机器人状态独立调整）、最优性保证（通过图搜索算法将连续规划转化为离散最短路径问题）与协调性支持（通过边权编码障碍物约束与机器人间距），结合λ₂可实现连通性保持的协调导航，为多机器人路径规划奠定核心基础。

4. 基于可见图与代数连通性的规划

可见图(VG)为静态结构化环境中的多机器人路径规划提供了数学严谨的框架：顶点由障碍物顶点与机器人起终点构成，边为不穿越障碍物的直线视线连接，边权通常为欧几里得距离，将连续运动规划转化为无向加权图上的最短路径搜索，结合精确图搜索算法可保证路线图层面的最短路径最优性。在多机器人场景中，VG尤其适用于序贯规划架构：先规划机器人的路径会影响后续机器人的规划空间，提供确定性行为与可预测性能，便于分析协调策略与优化准则。MRPP、CA与OCA均以VG为核心路线图，通过融合VG几何与连通性感知协调机制，实现高效无碰撞的协同运动规划。VG构建中，顶点集包含障碍物角点与机器人起终点，边集为互见顶点间的直线连接；针对圆形等非多边形障碍物，可通过采样边界点或切线点适配VG构建，确保路径无碰撞。多机器人团队可建模为无向加权交互图，节点为机器人位置，边为有限通信或感知范围内的连接关系，结合VG路线图可统一集成运动规划、通信感知与协调约束。代数连通性(λ₂)通过量化机器人网络通信链路的鲁棒性，可指导协调与优先级排序，支持可靠信息交换；避碰可通过高维配置空间规划、优先级规划（先规划路径视为后规划机器人的动态障碍物）与λ₂引导的协调策略共同实现，MRPP明确将λ₂集成于规划过程以排序机器人并保持网络内聚性，CA与OCA虽不直接优化λ₂，但通过简化VG结构间接影响连通性。MRPP算法整合VG、Dijkstra算法与λ₂，采用序贯规划策略：按λ₂确定机器人优先级（对整体连通性更关键的机器人先规划），已规划路径视为动态障碍物，动态调整边权减少轨迹重叠，在保证最短可行路径的同时维持安全与协调，但存在路径贴近障碍物、计算成本随环境复杂度与机器人数量增加而上升、离线规划难以适应动态环境的局限，由此催生CA与OCA。CA通过引入中央基线(CB)简化VG：仅考虑与CB相交的障碍物，为每个相关障碍物生成有限个自由空间航点（通常4个），大幅减少顶点与边数，在保持近最优路径质量的同时显著提升计算效率，适合密集障碍物环境，但路径仍可能贴近障碍物边界，安全性不足。OCA在CA基础上显式引入安全距离D_s（机器人与障碍物的最小允许距离），通过预定义安全裕量δ膨胀障碍物以缩小自由配置空间，在膨胀障碍物边界周围生成航点，再采用Dijkstra算法计算最短可行路径，在保留CA计算优势的同时确保路径与真实障碍物的足够间隙，平衡了安全性、最优性与效率，适合静态已知环境中对安全裕量与执行鲁棒性要求高的场景。

5. 多机器人路径规划方法分类

多机器人路径规划方法可按环境知识、环境表征、规划架构与优化准则系统分类，以明确MRPP、CA与OCA的定位。环境知识分为离线（全局）与在线（局部）：离线规划假设环境完全已知，适合静态环境，可采用Dijkstra等精确图算法保证最优性；在线规划应对部分已知或动态环境，需实时更新路径，常牺牲全局最优性。环境表征包括栅格法（规则网格，实现简单但大环境计算成本高）、采样法（随机采样，适合高维空间，如PRM与RRT）与图基（路线图）法（顶点为关键配置，边为可行路径，如VG与VD）。规划架构分为集中式（单一全局规划器计算所有路径，保证协调与全局最优，但计算成本高、可扩展性差）与分布式（各机器人独立规划，可扩展性与鲁棒性强，但易产生冲突与次优解）。优化准则包括路径最优性（最小化路径长度、时间或能耗）、计算效率（降低运行时与内存占用）、安全与避碰（保持与障碍物及其他机器人的安全距离）、连通性保持（通过图论度量维持通信链路）。MRPP、CA与OCA均属于离线规划（依赖完整环境先验知识，适合静态环境）、集中式架构（全局可用环境与机器人状态，保证协调一致性）、VG表征（MRPP用完整VG保证全局最优但计算成本高，CA用中央基线简化VG提升效率，OCA膨胀障碍物增强安全）、Dijkstra算法（保证确定性最优路径，与λ₂等协调机制的分离清晰），优化目标上均最小化路径长度，但各有侧重：MRPP优先保持λ₂连通性，CA优先提升计算效率，OCA平衡安全与效率。定量评估显示：CA平均路径长度比MRPP短约12.5%，OCA比MRPP短约15.1%、比CA短约2.9%；CA平均到达时间比MRPP少约12.5%，OCA比MRPP少约15.1%、比CA少约2.9%；MRPP计算时间最高，CA比MRPP低约30.2%，OCA比MRPP低约38.7%、比CA低约12.1%。算法权衡体现为：MRPP优先协调鲁棒性与连通性保持，CA通过集中优化提升计算效率，OCA在安全、协调与任务完成速度上达到最佳平衡，适合复杂密集环境。

6. MRPP、CA与OCA的回顾与分析

三种算法均为结构化环境中渐进优化的图基方法，以VG与Dijkstra算法为基础，但在规划架构、优化策略与性能上存在差异：MRPP采用集中式序贯规划，以λ₂为协调度量保持通信与网络连通性，适合通信关键应用，但完整VG导致密集环境下计算开销较高；CA通过中央基线构建简化VG，降低搜索空间与处理复杂度，保持近最优路径质量，路径更短、执行更快，但障碍物间隙较小、连通性感知较弱；OCA在CA基础上引入配置空间障碍物膨胀的安全距离约束，保持预设安全裕量，提升密集环境下的导航鲁棒性与操作安全性，同时保留高计算效率。三者反映了图基多机器人路径规划在协调鲁棒性、计算开销、可扩展性与安全性之间的基本权衡，无通用最优方案，需根据应用需求与环境约束选择。当前局限主要在于离线或半静态规划假设：VG预计算导致对移动障碍物敏感，环境变化需重建图；动态场景下λ₂需实时重评估通信图，计算强度大；CA的中央基线与OCA的障碍物膨胀在快速变化环境中易失效，频繁更新抵消效率增益。与冲突基搜索(CBS)、优先级规划(PBP)、采样法(PRM、RRT)、学习法(MARL、GNN)相比，图基路线图法虽动态适应性较弱，但提供结构化确定性框架，保证全局最优路径计算与清晰协调机制，适合对最优性、计算可处理性与协调精度要求高的场景。技术实现上，MRPP适合ROS、Gazebo、Webots等仿真平台验证；CA适合云机器人或数字孪生平台，支撑智能工厂、物流仓储等应用；OCA适合大规模自主车队在动态密集环境运行，需结合仿真环境、云机器人、数字孪生与AI平台，对齐算法设计与部署场景需求。在辅助机器人等新兴应用中，三类算法可扩展支持医院协作机器人助手、智能家居分布式服务机器人等场景，需满足人存在、不可预测障碍物与严格安全约束的要求，凸显了安全、自适应与人感知导航的重要性。

7. 结论与未来研究方向

本文系统分析了MRPP、CA与OCA三类图基多机器人路径规划方法，展示了VG表征、经典图搜索技术与连通性感知度量在结构化环境中实现协调、计算效率与避碰的有效性。未来需重点突破大规模系统的可扩展性与动态不确定环境的适应性，发展低计算开销的近最优规划框架，结合全局路径规划与局部反应控制以提升动态障碍物响应能力，融合学习与分布式优化提升适应性、可扩展性与通信效率，并集成云机器人、数字孪生与先进仿真平台推动实际部署。实现可靠可扩展的多机器人路径规划需统筹算法设计、使能技术与应用场景需求，以支撑多机器人系统在复杂操作域的实际落地。