構造変化を伴う高品質グラフの発見手法

本年度は，平面上を移動できるロボット群の隊列形成問題について研究した．考察対象のロボットは，識別子を持ち，観察により他ロボットを認識でき，かつ自由な方向に移動できるものである．ただし，一時刻あたりに移動できる距離には上限がある．この問題においては，ロボットの初期位置は任意であり，その初期位置から移動することによって，目標の隊列を形成することがこの問題の目的である．平面上のロボットの位置の集まりを一つの状況と捉え，それをグラフ中の頂点に対応づける．目的とする隊列も一つの状況であるので，そのグラフ中の一つの頂点に対応する．そのためロボット群の移動に伴う状況の変化の列を，グラフ中の点列で表現できる道と捉えることができる．ロボットたちは毎時刻動けるわけではなく，ある種のスケジュールに従って，起動し移動を行う．そのため，ロボットが起動されるスケジュールによって，このグラフ上で頂点間の遷移が一部不可能になったりするという構造の変化が起こる．このような状況下で，全ロボットが毎時刻起動されるスケジュールと，各時刻では予測不可能な一部のロボットのみ（全部もあり得る）起動されるスケジュールを考慮した．そして，目標の隊列に確実に到達し，かつ，その途中段階の隊列の質が確実に改善する（途中で悪化することはない）ようなアルゴリズムを提案した．以上の研究成果を査読付き国際学術雑誌 Theoretical Computer Science 誌において発表した．さらに他の問題として，辺に向きの付いていないグラフにおいて，向き付けを行うことで，ある種の指標について最適化を行う問題について検討を行った．得られた研究成果は，査読付き国際会議に投稿中である．

本年度は，平面上を移動できるロボット群の隊列形成問題について研究した．考察対象のロボットは，識別子を持ち，観察により他ロボットを認識でき，かつ自由な方向に移動できるものである．ただし，一時刻あたりに移動できる距離には上限がある．この問題においては，ロボットの初期位置は任意であり，その初期位置から移動することによって，目標の隊列を形成することがこの問題の目的である．平面上のロボットの位置の集まりを一つの状況と捉え，それをグラフ中の頂点に対応づける．目的とする隊列も一つの状況であるので，そのグラフ中の一つの頂点に対応する．そのためロボット群の移動に伴う状況の変化の列を，グラフ中の点列で表現できる道と捉えることができる．ロボットたちは毎時刻動けるわけではなく，ある種のスケジュールに従って，起動し移動を行う．そのため，ロボットが起動されるスケジュールによって，このグラフ上で頂点間の遷移が一部不可能になったりするという構造の変化が起こる．このような状況下で，全ロボットが毎時刻起動されるスケジュールと，各時刻では予測不可能な一部のロボットのみ（全部もあり得る）起動されるスケジュールを考慮した．そして，目標の隊列に確実に到達し，かつ，その途中段階の隊列の質が確実に改善する（途中で悪化することはない）ようなアルゴリズムを提案した．以上の研究成果を査読付き国際学術雑誌 Theoretical Computer Science 誌において発表した．さらに他の問題として，辺に向きの付いていないグラフにおいて，向き付けを行うことで，ある種の指標について最適化を行う問題について検討を行った．得られた研究成果は，査読付き国際会議に投稿中である．