エージェント型と探索アルゴリズムの設計原理

反応型エージェント
現在のセンサー入力に基づいて即座に行動を選択する。内部状態を持たず、ルールベースで動作する。
例：自動ドア（人を検知 → 開く）、煙感知器（煙検知 → 警報）
制限：部分観測や動的環境には対応不可。

モデル保持型エージェント
観測できない環境状態を推定するために内部モデルを維持する。
状態更新式：現在状態 = モデル更新(前状態, 行動, 観測)
例：SLAMによる地図構築ロボット、遮蔽物の予測を行う自動運転車
技術：カルマンフィルタ、ベイジアンネットワーク

目標指向型エージェント
明示的なゴールに向けて最適な行動シーケンスを計画する。
計画生成：プラン = 探索(現在状態, ゴール, 可能行動)
例：A*アルゴリズムによる経路探索、ルービックキューブの解法
アルゴリズム：Dijkstra、STRIPSプランニング

効用最大化型エージェント
複数の評価基準を統合した効用関数を最大化する行動を選択。
期待効用：Σ[結果確率 × 効用値] → 最大化行動を選択
例：安全性・燃費・時間のバランスを取る自動運転、リスク調整型投資AI
技術：マルコフ決定過程、パレート最適化

タイプ	判断基準	対応環境	代表的手法
反応型	現在の観測値	完全観測・静的	ルールエンジン
モデル保持型	推定状態	部分観測・動的	確率推論モデル
目標指向型	ゴール到達	多段階計画必要	A*、プランニング
効用最大化型	総合評価	多目的・不確実性	MDP、意思決定理論

幅優先探索（BFS）
FIFOキューを使用。浅いノードから順に展開。
用途：最短ステップ数の経路探索、階層的分析
空間計算量：O(最大幅) — 完全二分木ではO(n)

一様コスト探索（UCS）
最小ヒープによる優先度キュー。累積コスト最小のノードを展開。
用途：重み付きグラフでの最短経路（Dijkstra相当）
注意点：同一ノードへの低コスト経路発見時は優先度更新が必要

深さ優先探索（DFS）
LIFOスタックを使用。末端まで再帰的に探索後バックトラック。
用途：存在確認、メモリ制約下での探索
空間計算量：O(深さ) — 平衡木ではO(log n)

アルゴリズム	データ構造	展開順序	空間特性
BFS	キュー	レベル順	O(最大幅)
UCS	優先度キュー	コスト昇順	O(ノード数)
DFS	スタック	深さ優先	O(深さ)

        8
      /   \
    4       12
   / \     /  \
  2   6   10   14
 / \ / \ / \  / \
1  3 5 7 9 11 13 15

BFS訪問順: 8→4→12→2→6→10→14→1→3→5→7→9→11→13→15
DFS訪問順: 8→4→2→1→3→6→5→7→12→10→9→11→14→13→15

オーストラリア地図彩色問題において、中心ノードSAを赤固定することで星型構造を直線木に変換：

WA(青) → NT(緑) → Q(青) → NSW(緑) → V(青) → T(緑)

この変換により、元のNP困難問題が線形時間で解ける木構造CSPとなる。

構文（Syntax）: 記号列の形式的整合性
例: (P ∧ Q) → R（合法） vs P ∧ → Q（不合法）

意味（Semantics）: 真偽値に基づく解釈
例: KB ╞ α（KBが真ならαも必ず真） vs KB → α（論理式としての含意命題）

次元	構文	意味
焦点	記号の配置規則	真理値の関係
判断基準	形式的正当性	論理的必然性

リテラルの種類
- 正リテラル: P
- 負リテラル: ¬Q
- ホーン節: 最大1つの正リテラルを持つ節（例: ¬P ∨ ¬Q ∨ R）

分解アルゴリズム
- 単位分解: 1リテラル節との分解
- 一般分解: 互いに補完的なリテラルを持つ2節からの新節生成

一階述語論理の要素
- オブジェクト: 個体（例: Alice）
- 関数: オブジェクト間の写像（例: motherOf(x)）
- 述語: 真偽を返す関係（例: Loves(x,y)）
- 量化子: ∀x（全称）、∃y（存在）

∀x∃y P(x,y) と ∃x∀y P(x,y) の違い:
前者「各xに対してyが存在」、後者「あるxがすべてのyに対して成立」
例: P=「xがyを知っている」→ 前者は「誰もが知っている人がいる」、後者は「全員を知っている人がいる」

5月26日 20:39 投稿

異端開発室