WEKO3
アイテム
Semi-Uniform Deployment of Mobile Robots in Perfect ℓ-ary Trees
http://hdl.handle.net/10228/00008834
http://hdl.handle.net/10228/0000883495bc6534-d5f5-49f5-9ff8-4ca371dc5a07
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
RECN_2021-40.pdf (538.1 kB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-05-10 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Semi-Uniform Deployment of Mobile Robots in Perfect ℓ-ary Trees | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| 著者 |
柴田, 将拡
× 柴田, 将拡
WEKO
25091
× Tixeuil, Sébastien |
|||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | In this paper, we consider the problem of semi-uniform deployment for mobile robots in perfect ℓ-ary trees, where every intermediate node has ℓ children, and all leaf nodes have the same depth. This problem requires robots to spread in the tree so that, for some positive integer d and some fixed integer s(0≤s≤d−1), each node of depth s+dj (j≥0) is occupied by a robot. In other words, after semi-uniform deployment is achieved, nodes of depth s,s+d,s+2d,… are occupied by a robot. Robots have an infinite visibility range but are opaque, that is, robot ri cannot observe some robot rj if there exists another robot rk in the path between ri and rj. In addition, each robot can emit a light color visible to itself and other robots, taken from a set of κ colors, at each time step. Then, we clarify the relationship between the number of available light colors and the solvability of the semi-uniform deployment problem. First, we consider robots with the minimum number of available light colors, that is, robots with κ=1 (in this case, robots are oblivious). In this setting, we show that there is no collision-free algorithm to solve the semi-uniform deployment problem with explicit termination. Next, we relax the number of available light colors, that is, we consider robots with κ=2. In this setting, we propose a collision-free algorithm that can solve the problem with explicit termination. Thus, our algorithm is optimal with respect to the number of light colors. In addition, to the best of our knowledge, this paper is the first to report research considering (a variant of) uniform deployment in graphs other than rings or grids. | |||||||||||||
| 言語 | en | |||||||||||||
| 備考 | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | 2021 Ninth International Symposium on Computing and Networking, CANDAR 2021, 23-26 November, 2021, Virtual Conference | |||||||||||||
| 言語 | en | |||||||||||||
| 書誌情報 |
2021 Ninth International Symposium on Computing and Networking (CANDAR) p. 168-174, 発行日 2021-12-23 |
|||||||||||||
| 出版社 | ||||||||||||||
| 出版者 | IEEE | |||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | https://doi.org/10.1109/CANDAR53791.2021.00031 | |||||||||||||
| ISBN | ||||||||||||||
| 識別子タイプ | ISBN | |||||||||||||
| 関連識別子 | 978-1-6654-4246-6 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||
| 収録物識別子 | 2379-1896 | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | Copyright (c) 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | mobile robot | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | semi-uniform deployment | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | visible lights | |||||||||||||
| 会議記述 | ||||||||||||||
| 会議名 | 2021 Ninth International Symposium on Computing and Networking, CANDAR 2021 | |||||||||||||
| 言語 | en | |||||||||||||
| 回次 | 9 | |||||||||||||
| 開始年 | 2021 | |||||||||||||
| 開始月 | 11 | |||||||||||||
| 開始日 | 23 | |||||||||||||
| 終了年 | 2021 | |||||||||||||
| 終了月 | 11 | |||||||||||||
| 終了日 | 26 | |||||||||||||
| 開催会場 | Virtual Conference | |||||||||||||
| 言語 | en | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | AM | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||
| 査読の有無 | ||||||||||||||
| 値 | yes | |||||||||||||
| 連携ID | ||||||||||||||
| 値 | 10297 | |||||||||||||
