Design and Analysis of Algorithms for Graph Exploration and Resource Allocation Problems and Their Application to Energy Management

 エネルギーの効率的な活用は様々な分野において重要な研究テーマである．特に近年，いわゆる「スマートグリッド」に代表されるように，情報通信技術を用いた電力受給の効率化に対して活発に研究開発が行われている．本研究では，効率の良いグラフ探索アルゴリズム，利用者の生活の利便性をできるだけ高めるように電力を消費機器に割り当てるアルゴリズム，電力測定や通信および制御を行うデバイス，そしてそれらの組合せによる電力割当制御システムについて考察した．

 本研究の1つめのトピックは，グラフ探索問題に対する効率の良いアルゴリズムの設計と解析である．この問題はネットワーク上の資源探索やロボットによる未知環境の情報収集等を念頭にしたものである．アルゴリズムは限られた情報のみを利用して，できるだけ短い総移動距離でグラフ上のすべての頂点を訪問することが求められる．本研究では，グラフに制限を付した2つのモデル（サイクルグラフと枝コスト一定のグラフ）を考察し，それぞれ理論的に最適なオンラインアルゴリズムを得た．

 2つめのトピックは，電力割当アルゴリズムの理論的設計と解析である．利便性を高めるように消費機器への電力割当を決定する問題はいわゆる「ナップザック問題」として解釈できる．ナップザック問題は，実用的な所要時間で最適解を求めることが困難な問題（NP困難問題）であるため，近似的な解を効率的に求める「近似アルゴリズム」の追究が1つのアプローチとなる．本研究では，実際の電力網を念頭に，機器の消費電力に比べて電源の容量が一定割合以上大きいと想定するモデルと，対照的に分散型電源のように比較的小さな容量の電源を想定するモデルとを考察し，それぞれ近似アルゴリズムと近似の困難性を示した．

 3つめのトピックは，電力割当制御デバイスの設計と実装である．開発したデバイスは「スマートタップ」および一種の「電力ルータ」であり，電力消費状態を把握するための電力センサ，他機器との通信機能，電力供給の制御機能を持つ．スマートタップは実生活環境に設置して継続的な運用を行うとともに，測定した消費電力情報や環境情報を用いた自動制御ポリシーを実装評価してその有用性を検証した．電力ルータについては，2種類の電源を条件に基づき自律的に切り替える機能の実装評価を行った．

 4つめのトピックは，電力割当アルゴリズムとデバイスの組合せによる電力割当制御システムの構築である．本システムは，スマートタップで測定した消費電力情報を利用して，ナップザック問題に対するアルゴリズムにより最適な電力割当を決定する．そして，スマートタップの電力供給制御機能を用いて，アルゴリズムにより決定した電力割当を実際の機器の状態に反映させる．実験では，最適割当の計算や制御に要する処理時間等の評価を行っている．