エージェント間通信による情報からの 局所時刻の前後関係に関する推論問題

村上 哲也 (9651110)


内容梗概

本論文では,2体のエージェントa0, a1から成る環境を考える. 各エージェントはローカルな時刻をも ち, いくつかの命題の真偽値を観測した結果を自分のローカルな時刻とともに 記録する. エージェントa1が自分の観測結果をエージェント間通 信によりエージェントa0に伝えたとすると, a0は通信 により得られた情報と自分の観測結果を用いて,a0のローカルな 時刻とa1のローカルな時刻の相互関係を表す制約式を構成できる. a0のある時刻tとa1のある時刻sの前後関係を表す式 (例えばs≦t)が, この制約式のもとで成り立つか否かを判定する問題を推論問 題と呼ぶ.本論文では, 推論問題を解く効率の良いアルゴリズムを提案する.

発表の概要

  1. 背景
  2. 本研究の目標
  3. 推論問題の例
  4. 推論問題の定義
  5. 本研究の結果
  6. アルゴリズムの概要
  7. 制約式の変形その1
  8. 制約式の変形その2
  9. 配列上の経路
  10. 判定方法
  11. 時間計算量
  12. 推論問題の拡張
  13. まとめと今後の課題