Semi‐uniform deployment of mobile robots in perfect $\ell$‐ary trees
Semi‐uniform deployment of mobile robots in perfect $\ell$‐ary trees
复制标题
移动机器人在完美 $ell$-ary 树中的半均匀部署
DOI：
10.1002/cpe.7432
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Sebastien Tixeuil
中科院分区：
文献类型：
--
作者：
Masahiro Shibata;Sebastien Tixeuil
本文研究了移动的机器人在完美二叉树中的半均匀部署问题。这个问题要求机器人在树中扩散，使得对于某个正整数d$$ d $$和某个固定整数s（0≤s≤d−1）$$ s\left（0\le s\le d-1\right）$$，深度为s+dj（j≥0）$$ s+ dj\left（j\ge 0\right）$$的每个节点都被机器人占据。机器人具有无限的可见度范围，但不透明，每个机器人可以在每个时间步发射一种对自己和其他机器人可见的光颜色，从一组κ$$ \kappa $$颜色中提取。然后，我们澄清了半均匀部署问题的可解性，重点是可用的光颜色的数量。首先，我们考虑κ=1$ \kappa =1 $的机器人。在这种情况下，我们表明没有无碰撞算法来解决这个问题。接下来，放松可用光色的数量，即我们考虑κ=2$$ \kappa =2 $$的机器人。在这种情况下，我们提出了一个无冲突算法，可以解决这个问题。从这些结果中，我们可以表明，当κ≥2$$ \kappa \ge 2 $$时，可以解决半均匀部署问题，并且我们提出的算法在所使用的浅色数量方面是最优的（即，2）。
In this paper, we consider the problem of semi‐uniform deployment for mobile robots in perfect ℓ$$ \ell $$‐ary trees. This problem requires robots to spread in the tree so that, for some positive integer d$$ d $$ and some fixed integer s(0≤s≤d−1)$$ s\left(0\le s\le d-1\right) $$, each node of depth s+dj(j≥0)$$ s+ dj\left(j\ge 0\right) $$ is occupied by a robot. Robots have an infinite visibility range but are opaque, and each robot can emit a light color visible to itself and other robots, taken from a set of κ$$ \kappa $$ colors, at each time step. Then, we clarify the solvability of the semi‐uniform deployment problem, focusing on the number of available light colors. First, we consider robots with κ=1$$ \kappa =1 $$. In this setting, we show that there is no collision‐free algorithm to solve the problem. Next, relax the number of available light colors, that is, we consider robots with κ=2$$ \kappa =2 $$. In this setting, we propose a collision‐free algorithm that can solve the problem. From these results, we can show that the semi‐uniform deployment problem can be solved when κ≥2$$ \kappa \ge 2 $$, and our proposed algorithm is optimal with respect to the number of used light colors (i.e., 2).