AND-ORツリー（アンド・オア・ツリー）は、人工知能（AI）およびコンピュータサイエンスにおいて、問題解決プロセスや意思決定構造を表現するために用いられるグラフィカルな形式主義である。これは、各ノードがANDノードまたはORノードのいずれかとしてラベル付けされるツリーデータ構造の一種である。ANDノードでは、親ゴールを満たすためにすべての子サブ問題を解決しなければならず、ORノードでは、いずれか1つの子サブ問題を解決すれば十分である。この区別により、AND-ORツリーは連言的および選言的なサブタスクに分解される複雑な問題をモデル化でき、自動プランニング、ゲームプレイ、論理プログラミングなどの分野における基本的なツールとなっている。
この概念は、問題解決と探索アルゴリズムに関する初期のAI研究から生まれた。これはゲームツリーや決定木と密接に関連するが、AND関係を明示的に扱う点で異なる。AND-ORツリーは、深さ優先探索、幅優先探索、ヒューリスティック探索などの探索戦略と組み合わせて使用されることが多く、AO*（AND-ORグラフのための最良優先探索）のようなアルゴリズムの基礎を形成している。
構造と意味論
AND-ORツリーは、各内部ノードが次の2つのタイプのいずれかを持つ根付きツリーである：
- ANDノード：ノードは、そのすべての子が満たされた場合にのみ満たされる。これはサブゴールの連言を表す。例えば、家を建てるには、基礎、壁、屋根をすべて完成させなければならない（すべて必須）。
- ORノード：ノードは、その子の少なくとも1つが満たされた場合に満たされる。これは代替案の選言を表す。例えば、都市へ移動するには、電車、バス、車のいずれかを利用すればよい（どれか1つで十分）。
葉は通常、真または偽のいずれかである原始的なゴールまたは終端状態である。ルートノードは全体的な問題またはゴールを表す。問題の解は、ルートを満たすサブツリーに対応し、サブツリー内のすべてのANDノードについてすべての子が含まれ、すべてのORノードについて正確に1つの子が含まれることを意味する。
歴史的背景
AND-ORツリーの形式主義は、1960年代から1970年代にかけて人工知能の分野で重要性を増した。アレン・ニューウェルとハーバート・A・サイモンによって開発された一般問題解決器（GPS）などの初期のAIシステムは、手段-目標分析を使用しており、これは暗黙的にAND-OR分解を含んでいた。しかし、AND-ORツリーの明示的な表現は、問題解決に関する教科書や研究において標準となった。特に、1970年代に導入されたAOアルゴリズムは、A探索アルゴリズムをAND-ORグラフに拡張し、連言的なサブゴールを持つ問題で最適解を見つけることを可能にした。
人工知能における応用
AND-ORツリーは、AIにおいて広く使用されている：
- 自動プランニング：タスクの階層的分解としてプランを表現する。例えば、ロボットのナビゲーションプランでは、ある場所への移動（AND：障害物を回避、目標に到達）や、複数の経路からの選択（OR）が必要になる場合がある。
- ゲームプレイ：プレイヤーが手を打つ（OR）局面と、対戦相手の応答（AND）を考慮するゲーム状態をモデル化する。チェスなどで使用されるミニマックスアルゴリズムは、AND-OR探索の特殊なケースと見なすことができる。
- 論理プログラミング：Prologでは、解決プロセスをAND-ORツリーとして視覚化でき、ゴールはANDで結合され、節はORの代替を提供する。
- エキスパートシステム：ルールベースの推論は、前提から結論を推論するためにAND-OR構造を使用することが多い。
AND-ORツリーのための探索アルゴリズム
解を見つけるために、いくつかのアルゴリズムがAND-ORツリー上で動作する：
- 深さ優先探索（DFS）：バックトラックする前に、1つのブランチを可能な限り探索する。ANDノードではすべての子を探索する必要があり、ORノードでは最初に成功した子で十分な場合がある。
- 幅優先探索（BFS）：ノードをレベルごとに探索し、最も浅い解が見つかることを保証する。
- AO*：コスト推定に基づいてノードを展開する最良優先探索アルゴリズムで、ANDブランチとORブランチの両方を考慮する。解グラフを維持し、コストを再帰的に更新する。
- アルファベータ枝刈りを用いたミニマックス：ゲームツリーで使用される。これはAND-ORツリーのサブセットであり、プレイヤーと対戦相手が交互に手を打つ。
これらのアルゴリズムはAIコースの基本であり、多くのAIシステムに実装されている。
他の形式主義との関係
AND-ORツリーは、他の構造と密接に関連している：
- 決定木：決定木では、各内部ノードは属性のテストを表し、ブランチは結果を表す。これらは分類や回帰に使用されるが、通常ANDノードを持たず、単一のパスがたどられるという意味で純粋にOR的である。
- ゲームツリー：ゲームツリーは、すべての可能な手と応答を表す。これは、プレイヤーの手がORノード（手を選ぶ）であり、対戦相手の手がANDノード（すべての応答を考慮する必要がある）であるAND-ORツリーと見なすことができる。
- AND-ORグラフ：ツリーとは異なり、グラフは共有サブ問題を許可し、重複を回避する。AND-ORグラフはより一般的であり、問題の縮約に使用される。
拡張と変種
基本的なAND-ORツリーのいくつかの拡張が開発されている：
- 重み付きAND-ORツリー：ノードまたはエッジにコストを割り当て、コストベースの最適化を可能にする。
- 確率的AND-ORツリー：不確実な結果の確率を組み込み、意思決定分析やゲーム理論で使用される。
- 制約付きAND-ORツリー：サブツリー全体で満たさなければならない制約を追加し、制約充足問題で一般的である。
これらの変種は、実世界のアプリケーションに対する形式主義の表現力を強化する。
現在の関連性と研究
現代のAIはMachine learningやDeep learningのアプローチにシフトしているが、AND-ORツリーはシンボリックAIやハイブリッドシステムにおいて依然として関連性がある。これらは、透明な推論構造を提供する説明可能なAIや、構造化表現を組み込んだNeural networkアーキテクチャで使用されている。ニューロシンボリックAIの研究では、一般化と解釈可能性を向上させるために、ニューラルネットワークとAND-ORツリー推論を組み合わせることが多い。さらに、AND-ORツリーは、自然言語理解における文の階層構造への解析や、コンピュータビジョンにおけるシーン理解にも使用されている。
関連項目
参考文献
- Nilsson, N. J. (1980). Principles of Artificial Intelligence. Tioga Publishing.
- Rich, E., & Knight, K. (1991). Artificial Intelligence. McGraw-Hill.
- Russell, S., & Norvig, P. (2021). Artificial Intelligence: A Modern Approach. Pearson.