优化了欧几里得冻结标签问题的唤醒时间上限，二维降至4.31，三维显著提升效率。
Improved Wake-Up Time For Euclidean Freeze-Tag Problem
- 提出新策略，基于几何分布优化机器人唤醒路径。
- 二维平面中唤醒比降至4.31（原4.62），三维中分别达12和12.76。
- 适用于多机器人协同调度与路径规划场景。
冻结标签问题（FTP）旨在从单个活跃机器人出发，以最短时间激活所有初始休眠的机器人。激活后的机器人可协助唤醒其他机器人，所有活跃机器人以单位速度移动。目标是最小化完工时间（即激活最后一个机器人的时刻）。关键性能指标为唤醒比，定义为在任意初始位置下激活任意数量机器人所需的最大时间。本文研究$ℝ^d$空间中$ℓ_p$范数下的欧几里得版本FTP，其中每个休眠机器人与初始活跃机器人之间的距离不超过1。在$(\mathbb{R}^2, \ell_2)$中，将先前上界4.62（[7], CCCG 2024）改进至4.31；已知3.82为该问题的下界。在$\mathbb{R}^3$中，提出新策略，获得$(\mathbb{R}^3, \ell_1)$下唤醒比12、$(\mathbb{R}^3, \ell_2)$下12.76，优于此前13和$13\sqrt{3}$的上界（[2]）。
原文摘要 · Abstract (English)
The Freeze-Tag Problem (FTP) involves activating a set of initially asleep robots as quickly as possible, starting from a single awake robot. Once activated, a robot can assist in waking up other robots. Each active robot moves at unit speed. The objective is to minimize the makespan, i.e., the time required to activate the last robot. A key performance measure is the wake-up ratio, defined as the maximum time needed to activate any number of robots in any primary positions. This work focuses on the geometric (Euclidean) version of FTP in $\mathbb{R}^d$ under the $\ell_p$ norm, where the initial distance between each asleep robot and the single active robot is at most 1. For $(\mathbb{R}^2, \ell_2)$, we improve the previous upper bound of 4.62 ([7], CCCG 2024) to 4.31. Note that it is known that 3.82 is a lower bound for the wake-up ratio. In $\mathbb{R}^3$, we propose a new strategy that achieves a wake-up ratio of 12 for $(\mathbb{R}^3, \ell_1)$ and 12.76 for $(\mathbb{R}^3, \ell_2)$, improving upon the previous bounds of 13 and $13\sqrt{3}$, respectively, reported in [2].
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。