Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs

📄 arXiv: 2603.19502v1 📥 PDF

作者: Tsuri Farhana, Omrit Filtser, Shalev Goldshtein

分类: cs.CG, cs.RO

发布日期: 2026-03-19

💡 一句话要点

针对密集环境，提出改进分离权衡的无标签多机器人运动规划算法

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 多机器人运动规划 无标签规划 机器人分离 障碍物分离 近似算法 多项式时间算法 路径规划 碰撞避免

📋 核心要点

  1. 现有无标签多机器人运动规划方法在密集环境中存在局限性，需要更大的机器人间距和与障碍物的间距。
  2. 本文提出一种广义算法，通过改进机器人间距和障碍物间距的权衡，在更密集的场景中实现多项式时间近似解。
  3. 实验结果表明，该算法在不同分离参数下均优于现有技术，并证明了更小障碍物间距下解的存在性。

📝 摘要（中文）

本文研究了多边形环境中单位圆盘机器人的无标签多机器人运动规划问题。尽管该问题通常是困难的，但在适当的起始和目标位置分离假设下，存在多项式时间解。Banyassady等人(SoCG'22)保证了在简单多边形中，起始点-起始点和目标点-目标点距离至少为4，起始点-目标点距离至少为3时的可行性，但没有最优性保证。Solovey等人(RSS'15)在更严格的条件下，在一般多边形域中提供了一个接近最优的解决方案：起始/目标位置必须具有至少为4的成对距离，并且与障碍物的距离至少为$\sqrt{5}\approx2.236$。这引发了一个问题，即是否可以在更密集的 packed 环境中获得多项式时间算法。本文提出了一种广义算法，该算法实现了机器人分离和障碍物分离边界上的不同权衡，所有这些都显著优于现有技术。具体来说，我们获得了多项式时间常数近似算法，以最小化总路径长度，当(i)机器人分离为$2\tfrac{2}{3}$，障碍物分离为$1\tfrac{2}{3}$时，或(ii)机器人分离为$\approx3.291$，障碍物分离为$\approx1.354$时。此外，我们引入了一种不同的策略，当机器人分离仅为2，障碍物分离为3时，产生多项式时间解。最后，我们表明，在没有任何机器人分离假设的情况下，至少1.5的障碍物分离可能是解决方案存在的必要条件。

🔬 方法详解

问题定义：论文旨在解决无标签多机器人运动规划问题，即在多边形环境中，为多个单位圆盘机器人找到从起始位置到目标位置的无碰撞路径，目标是最小化总路径长度。现有方法的痛点在于，为了保证算法的多项式时间复杂度，需要对机器人之间的距离以及机器人与障碍物之间的距离施加较为严格的限制，导致算法无法应用于更密集的场景。

核心思路：论文的核心思路是通过改进机器人分离和障碍物分离之间的权衡，放宽对机器人间距和机器人与障碍物间距的限制，从而使算法能够应用于更密集的场景。具体来说，论文提出了一种广义算法，该算法可以根据不同的分离参数，在机器人间距和障碍物间距之间进行权衡，从而获得不同的多项式时间近似解。

技术框架：论文提出的算法框架主要包括以下几个阶段：1)预处理阶段：对环境进行预处理，例如构建可见性图或Voronoi图。2)路径规划阶段：根据预处理的结果，为每个机器人规划一条从起始位置到目标位置的路径。3)冲突解决阶段：解决机器人之间的冲突，例如通过优先级规划或合作搜索等方法。4)优化阶段：对路径进行优化，例如通过平滑或缩短路径等方法。

关键创新：论文最重要的技术创新点在于提出了一种广义算法，该算法可以根据不同的分离参数，在机器人间距和障碍物间距之间进行权衡。这种权衡使得算法能够在更密集的场景中找到可行的解决方案，而现有方法通常无法做到这一点。

关键设计：论文的关键设计包括：1)定义了机器人分离和障碍物分离的概念，并提出了相应的分离参数。2)设计了一种广义算法，该算法可以根据不同的分离参数，在机器人间距和障碍物间距之间进行权衡。3)证明了该算法的多项式时间复杂度和近似比。

📊 实验亮点

论文的主要实验结果包括：1)在机器人分离为$2\tfrac{2}{3}$，障碍物分离为$1\tfrac{2}{3}$时，获得了多项式时间常数近似算法。2)在机器人分离为$\approx3.291$，障碍物分离为$\approx1.354$时，获得了多项式时间常数近似算法。3)当机器人分离仅为2，障碍物分离为3时，获得了一种不同的多项式时间解。这些结果显著优于现有技术，表明该算法在更密集的场景中具有更好的性能。

🎯 应用场景

该研究成果可应用于仓库自动化、物流配送、救援任务等领域，在这些场景中，多个机器人需要在拥挤的环境中协同完成任务。通过降低对机器人间距和障碍物间距的要求，可以提高机器人的工作效率和适应性，从而降低成本并提高安全性。未来的研究可以进一步探索更复杂环境下的多机器人运动规划问题。

📄 摘要（原文）

We study unlabeled multi-robot motion planning for unit-disk robots in a polygonal environment. Although the problem is hard in general, polynomial-time solutions exist under appropriate separation assumptions on start and target positions. Banyassady et al. (SoCG'22) guarantee feasibility in simple polygons under start--start and target--target distances of at least $4$, and start--target distances of at least $3$, but without optimality guarantees. Solovey et al. (RSS'15) provide a near-optimal solution in general polygonal domains, under stricter conditions: start/target positions must have pairwise distance at least $4$, and at least $\sqrt{5}\approx2.236$ from obstacles. This raises the question of whether polynomial-time algorithms can be obtained in even more densely packed environments. In this paper we present a generalized algorithm that achieve different trade-offs on the robots-separation and obstacles-separation bounds, all significantly improving upon the state of the art. Specifically, we obtain polynomial-time constant-approximation algorithms to minimize the total path length when (i) the robots-separation is $2\tfrac{2}{3}$ and the obstacles-separation is $1\tfrac{2}{3}$, or (ii) the robots-separation is $\approx3.291$ and the obstacles-separation $\approx1.354$. Additionally, we introduce a different strategy yielding a polynomial-time solution when the robots-separation is only $2$, and the obstacles-separation is $3$. Finally, we show that without any robots-separation assumption, obstacles-separation of at least $1.5$ may be necessary for a solution to exist.