| 講演名 | 2023-10-24 完全二部グラフにおけるモバイルロボット均一配置アルゴリズム 柴田 将拡(九工大), 北村 直輝(阪大), 江口 僚太(奈良先端大), 首藤 裕一(法政大), 中村 純哉(豊橋技科大), 金 鎔煥(名工大), 片山 喜章(名工大), 増澤 利光(阪大), セバスチャン ティクソイ(ソルボンヌ大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では，完全二部グラフ上のモバイルロボット均一配置問題を考察する. この問題は，n 台の左側ノード集合$V_L$ とn 台の右側ノード集合$V_R$ から成る完全二部グラフ$K_{n,n} 上で，n 台のモバイルロボットを$V_L$ 上に1 台ずつ，もしくは$V_R$上に1 台ずつ配置することを要求する問題である. 本稿ではロボットの可視領域と問題の可解性との間のトレードオフに着目し，ロボットの可視領域が1 ホップの場合は問題が解決不能であり，可視領域がn + 2 ホップの場合は問題が解決可能であることを示した. |
| 抄録(英) | In this paper, we consider the uniform deployment problem of mobile robots in perfect bipartite graphs. Intuitively, when n robots are placed in a perfect bipartite graph $K_{n,n}$ with an n-node set $V_L$ and another n-node set $V_R$, this problem requires robots to reach a configuration such that (a) there exists exactly one robot at every node in $V_L$ and no robot in $V_R$, or (b) there exists exactly one robot at every node in $V_R$ and no robot in $V_L$. In this paper, we consider the relationship between the visibility range for robots and solvability of the uniform deployment problem. As a result, we showed that the problem cannot be solved when robots have visibility range 1, and the problem can be solved when robots have visibility range n + 2. |
| キーワード(和) | 分散アルゴリズム / モバイルロボット / 均一配置問題 / 完全二部グラフ |
| キーワード(英) | Distributed algorithm / Mobile robots / Uniform deployment problem / Perfect bipartite graphs |
| 資料番号 | COMP2023-14 |
| 発行日 | 2023-10-17 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2023/10/24(から1日開催) |
| 開催地（和） | 名古屋大学 VBL |
| 開催地（英） | Nagoya Univ. Venture Business Lab. |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 委員長氏名（和） | 宇野 裕之(大阪公立大) |
| 委員長氏名（英） | Hiroyuki Uno(Osaka Metropolitan Univ.) |
| 副委員長氏名（和） | 来嶋 秀治(滋賀大) |
| 副委員長氏名（英） | Shuji Kijima(Shiga Univ.) |
| 幹事氏名（和） | 和佐 州洋(法政大) / 横井 優(東工大) |
| 幹事氏名（英） | Kunihiro Wasa(Hosei Univ.) / Yu Yokoi(Tokyo Inst. of Tech) |
| 幹事補佐氏名（和） | 安藤 映(専修大) |
| 幹事補佐氏名（英） | Ei Ando(Senshu Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 完全二部グラフにおけるモバイルロボット均一配置アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Algorithm of uniform deployment for mobile robots in perfect bipartite graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分散アルゴリズム / Distributed algorithm |
| キーワード(2)（和/英） | モバイルロボット / Mobile robots |
| キーワード(3)（和/英） | 均一配置問題 / Uniform deployment problem |
| キーワード(4)（和/英） | 完全二部グラフ / Perfect bipartite graphs |
| 第 1 著者 氏名（和/英） | 柴田 将拡 / Masahiro Shibata |
| 第 1 著者 所属（和/英） | 九州工業大学(略称：九工大) Kyushu Institute of Technology(略称：Kyutech) |
| 第 2 著者 氏名（和/英） | 北村 直輝 / Naoki Kitamura |
| 第 2 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 3 著者 氏名（和/英） | 江口 僚太 / Ryota Eguchi |
| 第 3 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara Institute of Science and Technology(略称：NAIST) |
| 第 4 著者 氏名（和/英） | 首藤 裕一 / Yuichi Sudo |
| 第 4 著者 所属（和/英） | 法政大学(略称：法政大) Hosei University(略称：Hosei Univ.) |
| 第 5 著者 氏名（和/英） | 中村 純哉 / Junya Nakamura |
| 第 5 著者 所属（和/英） | 豊橋技術科学大学(略称：豊橋技科大) Toyohashi University of Technology(略称：Toyohashi Tech.) |
| 第 6 著者 氏名（和/英） | 金 鎔煥 / Yonghwan Kim |
| 第 6 著者 所属（和/英） | 名古屋工業大学(略称：名工大) Nagoya Institute of Technology(略称：Nagoya Tech.) |
| 第 7 著者 氏名（和/英） | 片山 喜章 / Yoshiaki Katayama |
| 第 7 著者 所属（和/英） | 名古屋工業大学(略称：名工大) Nagoya Institute of Technology(略称：Nagoya Tech.) |
| 第 8 著者 氏名（和/英） | 増澤 利光 / Toshimitsu Masuzawa |
| 第 8 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 9 著者 氏名（和/英） | セバスチャン ティクソイ / Sebastien Tixeuil |
| 第 9 著者 所属（和/英） | ソルボンヌ大学(略称：ソルボンヌ大) Sorbonne Universite(略称：Sorbonne Univ.) |
| 発表年月日 | 2023-10-24 |
| 資料番号 | COMP2023-14 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | COMP-227 |
| ページ範囲 | pp.13-20(COMP), |
| ページ数 | 8 |
| 発行日 | 2023-10-17 (COMP) |