1. Semi‐uniform deployment of mobile robots in perfect ℓ$$ \ell $$‐ary trees.
- Author
-
Shibata, Masahiro and Tixeuil, Sébastien
- Subjects
MOBILE robots ,PROBLEM solving ,TREES ,VISIBLE spectra ,ROBOTS - Abstract
Summary: 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). [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF