分散型オンライングラフ探索問題

摘要

Parsons[3] はグラフ内を逃げ回る侵入者を複数の移動する探索者が発見する問題を考察した．この問題は探索者を石と見なして，グラフ上の石置きゲームでモデル化される[2]．このモデルでは，石置きゲームのプレイヤーが事前にグラフの形を知っているオフライン探索である．このような，移動する探索対象を発見する問題は，災害時に建物に取り残された人を探す救助ロボットや，海底や，地球以外の天体の探索などに応用できると考えられえる．しかし，このような応用を考える場合，探索者は常に事前に探索空間の形を知っているとは限らない．本稿ではグラフの形を知らない複数の探索者がグラフ内を移動し，協力して侵入者を発見するオンライングラフ探索問題を考える．