arXiv:2412.19706cs.DCcs.RO2024-12被引 3

提出三维空间中机器人唤醒问题的新最优时间上限,显著提升效率。

Geometric Freeze-Tag Problem

  • 设计几何启发式策略,通过优化路径减少唤醒延迟。
  • 在二维欧氏空间中将最晚唤醒时间降至5.4162倍最大距离,优于此前7.07倍。
  • 首次给出三维空间下 $l_1$ 和 $l_2$ 范数的理论上限,适用于实际部署场景。

我们研究由 Arkin 等人(SODA'02)提出的冻结标签问题(FTP),目标是从一个活跃机器人开始唤醒 $n$ 个机器人。聚焦于几何版本,即机器人位于 $/mathbb{R}^d$ 空间中,激活后可恒速移动唤醒其他机器人。目标是最小化最后一个机器人被激活的时间(即完工时间)。本文针对 $(/mathbb{R}^2, l_2)$ 提出至多 $5.4162r$ 的完工时间上界,优于先前 $7.07r$。在 $(/mathbb{R}^3, l_1)$ 中建立 $13r$ 上界,进而推得 $(/mathbb{R}^3, l_2)$ 的 $22.52r$。其中 $r$ 为任意机器人到初始活跃机器人的最大距离(按对应范数计算)。据我们所知,这是首次针对 $/mathbb{R}^3$ 下这两种范数的完工时间上界。还分析了机器人位于边界上的特定实例,为实际应用提供洞见。

原文摘要 · Abstract (English)

We study the Freeze-Tag Problem (FTP), introduced by Arkin et al. (SODA'02), where the goal is to wake up a group of $n$ robots, starting from a single active robot. Our focus is on the geometric version of the problem, where robots are positioned in $\mathbb{R}^d$, and once activated, a robot can move at a constant speed to wake up others. The objective is to minimize the time it takes to activate the last robot, also known as the makespan. We present new upper bounds for the $l_1$ and $l_2$ norms in $\mathbb{R}^2$ and $\mathbb{R}^3$. For $(\mathbb{R}^2, l_2)$, we achieve a makespan of at most $5.4162r$, improving on the previous bound of $7.07r$ by Bonichon et al. (DISC'24). In $(\mathbb{R}^3, l_1)$, we establish an upper bound of $13r$, which leads to a bound of $22.52r$ for $(\mathbb{R}^3, l_2)$. Here, $r$ denotes the maximum distance of a robot from the initially active robot under the given norm. To the best of our knowledge, these are the first known bounds for the makespan in $\mathbb{R}^3$ under these norms. We also explore the FTP in $(\mathbb{R}^3, l_2)$ for specific instances where robots are positioned on a boundary, providing further insights into practical scenarios.

几何优化机器人调度算法复杂度

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