arXiv:2602.11125cs.DCcs.RO2026-02

让一群机器人在直线或圆上均匀分布,最小化总移动距离。

Min-Sum Uniform Coverage Problem by Autonomous Mobile Robots

  • 设计分布式算法,使机器人在无记忆、无声通信下达成最优均匀布局。
  • 直线场景下算法可实现最小总移动距离,圆场景下有解条件被完全刻画。
  • 适用于自主移动机器人编队、分布式系统等场景,适合研究群智算法者阅读。

我们研究了在有限线段和给定正半径的圆上,由n个移动机器人组成的群体解决最小总移动距离的均匀覆盖问题。机器人需协调运动,达到均匀分布状态以最小化所有机器人总移动距离。机器人具有自治性、匿名性、同质性,采用非刚性运动的异步公平调度的看-计算-移动(LCM)模型,且无持久记忆与显式通信能力。在线段场景中,要求机器人在段上均匀分布以最小化总移动距离;在圆场景中,需形成正n边形,无固定方向或起始点,目标同样是极小化总移动距离。本文提出确定性分布式算法,在线段场景中实现最小移动成本。对圆场景,我们刻画了所有在此模型下无法确定求解的初始配置,并针对其余所有可解配置提供确定性算法,实现均匀覆盖并最小化总移动距离。这些结果完整刻画了无记忆机器人的最小和覆盖问题的确定性可解性,并在可解时达到最优代价。

原文摘要 · Abstract (English)

We study the \textit{min-sum uniform coverage} problem for a swarm of $n$ mobile robots on a given finite line segment and on a circle having finite positive radius, where the circle is given as an input. The robots must coordinate their movements to reach a uniformly spaced configuration that minimizes the total distance traveled by all robots. The robots are autonomous, anonymous, identical, and homogeneous, and operate under the \textit{Look-Compute-Move} (LCM) model with \textit{non-rigid} motion controlled by a fair asynchronous scheduler. They are oblivious and silent, possessing neither persistent memory nor a means of explicit communication. In the \textbf{line-segment setting}, the \textit{min-sum uniform coverage} problem requires placing the robots at uniformly spaced points along the segment so as to minimize the total distance traveled by all robots. In the \textbf{circle setting} for this problem, the robots have to arrange themselves uniformly around the given circle to form a regular $n$-gon. There is no fixed orientation or designated starting vertex, and the goal is to minimize the total distance traveled by all the robots. We present a deterministic distributed algorithm that achieves uniform coverage in the line-segment setting with minimum total movement cost. For the circle setting, we characterize all initial configurations for which the \textit{min-sum uniform coverage} problem is deterministically unsolvable under the considered robot model. For all the other remaining configurations, we provide a deterministic distributed algorithm that achieves uniform coverage while minimizing the total distance traveled. These results characterize the deterministic solvability of min-sum coverage for oblivious robots and achieve optimal cost whenever solvable.

机器人编队分布式算法优化覆盖群智系统

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。