計算場上の自律移動ロボット

- 自律移動ロボットのための計算モデル CABOT を提案する論文。 - ロボットが動く離散平面を、受動的な舞台ではなく能動的な計算媒体とみなす。 - 各セルが有限状態集合 Q の状態を持ち、一様な局所規則で同期更新される（床が cellular automaton）。 - Look 操作は可視ロボット位置に加え可視セルの状態も返す。 - ロボットは oblivious, silent, lightless, visibility range 1, multiplicity detection 不可、床への書き込み不可と極めて弱い。 - 資源の尺度はロボット能力ではなく場の状態数 |Q| となる。

- 古典的 Look-Compute-Move (LCM) モデルでは、計算能力の向上は lights, memory, 広い visibility などロボット側の強化で達成され、コストはロボットごとに支払う。 - CABOT は環境側を強化する点が根本的に異なる。 - ロボットを可能な限り弱くしたまま、場の状態数 |Q| を資源尺度にする新しい枠組みを提示。 - 不活性な床（|Q| = 1）では line formation, gathering, grid exploration が不可能であることを示し、少数状態で可能になることを示した。

- 離散平面上の各セルが有限状態集合 Q の状態を持ち、ロボット在否も感知する一様局所規則で同期更新される cellular automaton として床を定式化。 - Look は可視セル状態と可視ロボット位置を返す。 - ロボットは oblivious, silent, lightless, visibility range 1, multiplicity detection 不可、書き込み不可。 - 資源尺度は |Q|。 - 具体的状態数での可解性: Line Formation from connected configurations は 4 状態、field-silently は 5 状態、Gathering from arbitrary configurations は 3 状態、Line Formation from arbitrary configurations は 6 状態。 - 単一ロボットによる全 finite grid の永久探索は 4 状態、全 torus は 2 状態（最適）。

- 構成可能性・不可能性の理論的証明により検証。 - |Q| = 1 の不活性床では line formation, gathering, grid exploration が不可能であることを示す。 - 各状態数での可解性を証明し、field-silent では任意状態数でも解けないことを証明。 - torus 探索の 2 状態が最適であることを示す。 - 追加の規則集合（行上のロボット間隔均等化、床に描かれたパターンの充填、迷路誘導）は simulation のみで検証。

- 床を計算媒体とすることで、ロボット側の能力強化とは異なる資源配分の可能性を示す。 - field-silently（床も固定点に達する）で解ける問題と解けない問題の境界があることを証明。 - simulation のみで検証された規則集合はモデルの適用範囲の広さを示唆するが、理論的保証は別途必要。 - 要旨からは、ロボット数や障害物、非同期性などへの拡張に関する議論は不明。

- 古典的 Look-Compute-Move (LCM) モデルに関する研究。 - lights, memory, visibility などロボット能力を強化する既存研究。 - cellular automaton と mobile robot の交差研究。 - gathering, line formation, exploration の分散ロボットアルゴリズムに関する定番研究。