| 講演名 | 2021-12-17 ［ショートペーパー］Q学習を利用したグラフ上のランダムウォークの効率化に関する一検討 宮下 智行(関西学院大), 鈴木 泰誠(関西学院大), 松尾 涼太郎(関西学院大), 大崎 博之(関西学院大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 近年、グラフ上のランダムウォークに代表される、未知のグラフ上でのエージェントの移動モデルや、そのようなエージェントの移動モデルの数理的特性の研究が行われている。また、グラフ上のエージェントの移動モデルを、ネットワークの探査やネットワーク上での情報探索などへ応用する試みも始まっているグラフ上の移動モデルは、移動エージェントが利用できる情報が非常に限定的であるため、その特性を改善することは容易ではない。本稿では、エージェントが移動中に利用できる情報が非常に限定的な場合に、ランダムウォークの特性をどの程度改善できるかを検討する。特に、機械学習の一種である強化学習を用いることにより、ランダムウォークの特性をどの程度改善できるかを実験により調査する。具体的には、強化学習の一つであるQ学習によって学習したQ値を用いることにより、エージェントが移動先ノードを決定するランダムウォークである Q 学習に基づくランダムウォークを提案する。さらに、提案するQ学習に基づくランダムウォークの有効性を実験により調査する。その結果、QW-RW の移動エージェントはランダムウォークに基づく代表的な移動モデルの場合と比較して、同程度か、やや高速にグラフを被覆することなどがわかった。 |
| 抄録(英) | In recent years, modeling mobile agent on unknown graphs, such as random walks on graphs and understanding its mathematical properties have been studied. The mobility models of agents on graphs has also began to be applied to network exploration and information search on networks. It is not easy to improve the properties of the mobility models on graphs, because the information available to the mobile agents is very limited. In this paper, we investigate to what extent the properties of random walks can be improved when the mobile agents has access to very limited information. In particular, through experiments, we examine how much the properties of random walk can be improved using a kind of machine learning, reinforcement learning. Specifically, we propose a random walk based on Q-learning (QW-RW; Q-Weighted Random Walk), in which an agent decides a destination node using Q-values learned by Q-learning, one of the reinforcement learning techniques. Furthermore, through simulation experiments, we examine the effectiveness of the QW-RW. Our findings include that the QW-RW mobile agent covered the graph as fast as or slightly faster than the typical mobile model based on a random walk. |
| キーワード(和) | Q学習に基づくランダムウォーク / ランダムウォーク / Q-学習 / 移動モデル / 強化学習 |
| キーワード(英) | Q-Weighted Random Walk / Random Walk / Q-learning / Mobility Model / Reinforcement Learning |
| 資料番号 | IA2021-51 |
| 発行日 | 2021-12-09 (IA) |
| 研究会情報 | |
| 研究会 | IN / IA |
|---|---|
| 開催期間 | 2021/12/16(から2日開催) |
| 開催地（和） | 広島大学東千田キャンパス |
| 開催地（英） | Higashi-Senda campus, Hiroshima Univ. |
| テーマ（和） | 性能評価とシミュレーション、信頼性技術、スループットやトラヒックの計測、品質(QoS)制御、輻輳制御、トラヒック・フロー制御、オーバーレイネットワーク・P2P、IPv6 、マルチキャスト、ルーティング、DDoS及び一般※※※ 本研究会の2日目は情報指向ネットワーク技術特別研究会(ICN)とも併催です。※※※ |
| テーマ（英） | Performance Analysis and Simulation, Robustness, Traffic and Throughput Measurement, Quality of Service (QoS) Control, Congestion Control, Overlay Network/P2P, IPv6, Multicast, Routing, DDoS, etc. |
| 委員長氏名（和） | 石田 賢治(広島市大) / 義久 智樹(阪大) |
| 委員長氏名（英） | Kenji Ishida(Hiroshima City Univ.) / Tomoki Yoshihisa(Osaka Univ.) |
| 副委員長氏名（和） | 波戸 邦夫(インターネットマルチフィード) / 近堂 徹(広島大) / 屏 雄一郎(KDDI総合研究所) / 山本 寛(立命館大) |
| 副委員長氏名（英） | Kunio Hato(Internet Multifeed) / Toru Kondo(Hiroshima Univ.) / Yuichiro Hei(KDDI Research) / Hiroshi Yamamoto(Ritsumeikan Univ.) |
| 幹事氏名（和） | 谷口 展郎(NTT) / 星野 文学(長崎県立大) / 渡部 康平(長岡技科大) / 城 哲(KDDI総合研究所) / 大平 健司(阪大) / 坂野 遼平(工学院大) / 渡辺 俊貴(NEC) |
| 幹事氏名（英） | Noburo Taniguchi(NTT) / Fumitaka Hoshino(Univ. of Nagasaki) / Kouhei Watabei(Nagaoka Univ. of Tech.) / Tetsu Jyo(KDDI Research) / Kenji Ohira(Osaka Univ.) / Ryohei Banno(Kogakuin Univ.) / Toshiki Watanabe(NEC) |
| 幹事補佐氏名（和） | / 小谷 大祐(京大) / 中村 遼(福岡大) / 野林 大起(九工大) |
| 幹事補佐氏名（英） | / Daisuke Kotani(Kyoto Univ.) / Ryo Nakamurai(Fukuoka Univ.) / Daiki Nobayashi(Kyushu Inst. of Tech.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Networks / Technical Committee on Internet Architecture |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ［ショートペーパー］Q学習を利用したグラフ上のランダムウォークの効率化に関する一検討 |
| サブタイトル（和） | |
| タイトル（英） | [Short Paper] Study on Improving the Characteristics of Random Walk on Graph using Q-learning |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Q学習に基づくランダムウォーク / Q-Weighted Random Walk |
| キーワード(2)（和/英） | ランダムウォーク / Random Walk |
| キーワード(3)（和/英） | Q-学習 / Q-learning |
| キーワード(4)（和/英） | 移動モデル / Mobility Model |
| キーワード(5)（和/英） | 強化学習 / Reinforcement Learning |
| 第 1 著者 氏名（和/英） | 宮下 智行 / Tomoyuki Miyashita |
| 第 1 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 第 2 著者 氏名（和/英） | 鈴木 泰誠 / Taisei Suzuki |
| 第 2 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 第 3 著者 氏名（和/英） | 松尾 涼太郎 / Ryotaro Matsuo |
| 第 3 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 第 4 著者 氏名（和/英） | 大崎 博之 / Hiroyuki Ohsaki |
| 第 4 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 発表年月日 | 2021-12-17 |
| 資料番号 | IA2021-51 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | IA-300 |
| ページ範囲 | pp.100-103(IA), |
| ページ数 | 4 |
| 発行日 | 2021-12-09 (IA) |