三次元グリッド空間における自律分散ロボット群の緩集合問題について

摘要

共通座標系をもたない三次元グリッド空間内での自律分散ロボットの緩集合問題を扱う．緩集合問題とは全ロボットをあらかじめ与えられた範囲内に停止させる問題である．本研究ではロボットは三次元グリッド空間の格子点にのみ存在可能であり，座標系に関し，ては原点およびZ軸の向きと方向，またXY 軸に関してはキラリティのみが合意されているものとし，自身が存在する格子点を中心としてXY平面上の周囲8点および上下2点に移動可能とする．また，自身よりマンハッタン距離2の格子点に存在するロボットを観測可能とし，半同期（SSYNC）で動作する．以上のモデルでロボットの台数が未知の場合に原点を中心とした最小包含正八両体内にロボットを集合させる，緩集合問題を解くアルゴリズムを提案する．