問題解決とは，問題が現れた最初の状態（「初期状態」）から，最終的に目標とする状態（「目標状態」）に，状態を変化させてゆくことを言う。

そこでは，

• 状態
• オペレータ

状態とオペレータに関して，具体的に見てゆこう。 例題として，積み木の組み立て問題を考える。 初期状態から目標状態まで，クレーンを使ってブロックを積み替えてゆく問題である。

この問題解決の各「状態」は，On，Hold，Clearという 3 つの属性を用いて表される。(On x y) は，yの上にxがあるという状態を表し，(Hold x) は，xを掴んで持ち上げているという状態を表している。また，(Clear x)は，xというオブジェクトの上に何も置かれていない状況を示す。

(On ブロックう テーブル)
(On ブロックあ ブロックう)
(On ブロックい テーブル)
(Clear ブロックあ)
(Clear ブロックい)

(On ブロックう テーブル)
(On ブロックあ ブロックう)
(Clear ブロックあ)
(Hold ブロックい)

ではここで，上に示された「目標状態」をOnとClearという2つの属性を用いてリスト表現せよ。

「状態」に変化を与える作用を，オペレータ (operator) と呼ぶ。次に，以下のような2つのオペレータを定義する。

• Operator OP1：オブジェクトxを持ち上げる
• Operator OP2：オブジェクトxをオブジェクトyの上に置く

オペレータは，前提条件，削除リスト，追加リストによって具体的に定義される。

• 前提条件には，ある状態にそのオペレータを適用可能かどうかの判定が記述される。
• 削除リストとは，あるオペレータが適用されることによって，成立しなくなる状態を表す。
• 追加リストは，新たに成立する状態を表す。

Operator OP1：オブジェクトxを持ち上げる

• 前提条件
  

  (Clear x)
  (On x y)
  

• 削除リスト
  

  (On x y)
  (Clear x)
  

• 追加リスト
  

  (Hold x)
  (Clear y): ただし，yがテーブルの場合には追加しない
  

以下を参考にして，Operator OP2：オブジェクトxをオブジェクトyの上に置くを定義せよ。以下の(1)〜(3)にリストを指定せよ。

Operator OP2：オブジェクトxをオブジェクトyの上に置く

• 前提条件
  

  (Hold x)
  (Clear y)： ただし，yがテーブルの場合には必要ない
  

• 削除リスト
  

  (1)
  (Clear y)： ただし，yがテーブルならば削除しない
  

• 追加リスト
  

  (2)
  (3)
  

初期状態から目標状態へは，以下のような状態の系列を辿ることによって達成される。図で，OP1(ブロックあ）は，Operator OP1：ブロックあを持ち上げる，OP2(ブロックあ, テーブル)は，Operator OP2：ブロックあをテーブルの上に置くを示す。

上記の(1)にオペレータを，(2)に状態のリスト表現を示せ。

問題を解決するとは，オペレータを適用して，順次状態を変化させてゆき，初期状態から目標状態をつなぐオペレータの系列，すなわち状態の系列を発見することを意味する。
一般に，ある状態には，複数のオペレータが適用可能なので，状態とオペレータの組み合わせは，以下のような木を構成する。これを「問題空間」と呼ぶ。問題解決とは，このような木を探索して，初期状態から目標状態をつなぐ系列を発見することとして定式化される。