問題解決は、状態空間を探索することに帰着される。探索では状態空間を木というデータ構造で表現する。木の各節点が状態に、各枝が作用素(状態に対する操作)に相当する。前向き推論においては木の根は初期状態である。初期状態に適用可能な作用素を適用した結果が根のすぐ下の節点である。そのそれぞれの状態に適用可能な作用素を適用した結果の状態がそのまた下の節点である、というように続く。この木の枝の先のどこかの節点にあるはずの目標状態を探索するのが問題解決である。体系的な探索の方法としては、縦型探索と横型探索が基本になる。状態空間が有限で、その中に初期状態と目標状態が存在すれば、これらの探索によって必ず初期状態から目標状態へ到達する道筋を見いだせる。