状態空間とは状態をノードとする有向グラフのことであり，エッジはある状態から別の状態への遷移を表現します．状態はある時点での世界を表現する状態変数の集合です．アクションを適応することで，ある状態から別の状態への遷移が起こるとするわけですが，初期状態 s0 から出発して，ゴール状態 g に到達するアクションの列を，オペレータの集合 O から求めることをプラニングと言います．
状態空間プラニングは各種のプラニング手法の中でもっとも素朴かつ単純な手法で，まずこれからはじめます．
オペレータ集合 O，初期状態 s0，ゴール状態 g が与えられて，実際に初期状態 s0 から出発して探索を行う手法を前向き探索と言います．APTP の Figure 4.1 に与えられた Forward-search アルゴリズムを実際にプログラムすると，以下のようになります．
もし state のなかに goal 状態が見つかれば，探索終了で，答えとして plan を返します．plan にはそれまでの探索の結果が逆順に，すなわちゴールに近いものが先頭になって並んでいるものとしています．さもなければ探索する必要があるわけで，オペレータの中から現在の
state に対してインスタンス化できるものをインスタンス化して，それらの中から現在の state について applicable なものだけを取り出しておきます．もし
applicable なものがなければ，先に進めませんから，そこで (fail) と言います．applicable なものがあるときには，その中から任意の一つをとりだして
action とします．そしてこのアクションについて適応して状態を１ステップ進め，その結果である状態を新しい state としてさらに forward-search
で探索を進めます．このとき plan には探索経過である action を先頭に追加します．
ここでのポイントは，choose-bind において非決定的な選択が行われ，その決定のせいで探索に行き詰ったとき，(fail) と言うことで，自動的に探索経路をバックトラックしてくれて，異なる選択肢が選ばれるということです．AI においては探索は非常に重要な基礎技術ですが，通常のプログラムでこれを実装しようとすると，四苦八苦するわけです．ここではLisp における継続（continuation）を可能にしたPaul Graham のコードから，=defun，=values，choose-bind，および fail を借りてきて，APTP にあるアルゴリズムをほぼそのままコード化することに成功しました．
> (=defun forward-search (operators state goal plan)
(if (satisfy-p state goal) (=values (reverse plan))
(let ((applicable (remove-if-not #'(lambda (a) (applicable-action-p a state))
(mappend #'(lambda (o) (instantiate-fs o state)) operators))))
(cond ((null applicable) (fail))
(t (choose-bind action applicable
(forward-search operators (apply-action action state) goal
(cons action plan))))))))
forward-search
satisfy-p は簡単で，単にゴールのうち肯定的状態変数はすべて状態にあり，かつ関連する否定的状態変数は状態にはなく，ゴールのうち否定的状態変数は関連する肯定的状態変数が状態にあってはならない，とするものです．
> (defun satisfy-p (state goal)
(let ((state-positives (remove-if-not #'statevar-val state))
(state-negatives (remove-if #'statevar-val state))
(goal-positives (remove-if-not #'statevar-val goal))
(goal-negatives (remove-if #'statevar-val goal)))
(and (subsetp goal-positives state-positives :test #statevar-equalp)
(null (intersection goal-positives state-negatives :test #'pseudo-statevar-equalp))
(null (intersection goal-negatives state-positives :test #'pseudo-statevar-equalp)))))
satisfy-p
より難しいのは，instantiate-fs です．インスタンス化するとは，パラメータが変数であるオペレータという抽象的なものから，その時の状態にマッチしたアクションを生成する，すなわちグランドさせるということですが，具体的に言えば，パラメータの変数を，状態における状態変数においてマッチする定数に置き換えます．
> (defun instantiate-fs (operator state)
"returns substituted operator with precond unification against state.
This function returns nil if not unifiable."
(let ((result (operator-unify-in-forward-search operator state +no-bindings+)))
(when (car result)
result)))
instantiate-fs
operator-unify-in-forward-search はオペレータのすべてのパラメータについて，状態 state と bindings
を用いて変数の単一化を行います．やみくもに単一化するのではなく，オペレータの precond について単一化を行い，その結果のbindings
を用いてeffects を書き換えます．
> (defun operator-unify-in-forward-search (operator state bindings)
(let ((bindings-list
(precond-unify (operator-precond operator) state bindings)))
(loop for bindings in bindings-list
collect (make-action-from operator bindings))))
operator-unify-in-forward-search
precond の単一化では，複数の単一化の可能性がありますので，可能性をすべて組みつくすようにして，bindings のリストが返るように
precond-unify にてプログラムします．返された bindings のそれぞれについて，make-action-from を用いてアクションの生成を行います．
precond-unify では与えられた condition 中の各要素，すなわちstatevar について順番に statevar-unify で単一化を行いますが，このとき複数の単一化の可能性についていつも配慮すると同時に，各 bindings においては condition の各要素について単一化の効果を積み重ねます．statevar-unify が返すものは，単一化が成功すればその結果（複数）である bindings のリストであり，一つもなければ nil です．ある statevar についての複数の bindings に対する単一化の結果は append 操作でまとめられ，再び bindings のリストとなります．
> (defun precond-unify (condition state bindings)
(loop for svar in condition with bindings-list = (list bindings)
do (setq bindings-list
(mappend #'(lambda (bindings)
(statevar-unify svar state bindings))
bindings-list))
finally (return bindings-list)))
precond-unify
statevar-unify では与えられた statevar について状態 state との間で単一化を行います．unify で返される値は可能性を組みつくした単一化
binidngs のリストか，さもなければ失敗の値 +fail+ ですから，失敗した場合には nil を返すようにします．unify については後で説明します．
> (defun statevar-unify (statevar state bindings)
"returns a list of possible bindings of statevar against state."
(loop for st in state with result
unless (eq (setq result (unify statevar st bindings)) +fail+)
collect result))
statevar-unify
ではここで，APTP の Figure 2.3 の状態について，forward-search を実行してみよう．最初に初期状態とオペレータを定義します．
> (setq *state*
(make-state
'((attach(p1) = loc1) (in(c1) = p1) (top(c1) = p1) (on(c1) = pallet)
(attach(p2) = loc1) (in(c2) = p2) (top(c2) = p2) (on(c2) = pallet)
(belong(crane1) = loc1) (holding(crane1) = c3)
(adjacent(loc1 loc2)) (adjacent(loc2 loc1))
(loc(r1) = loc2) (occupied(loc2) = t) (load(r1) = nil))))
(#S(statevar :name attach :parms (p1 loc1) :val t) #S(statevar :name in :parms (c1 p1) :val t)
#S(statevar :name top :parms (c1 p1) :val t) ...)
> (defoperator load(?k ?l ?c ?r)
"crane k loads container c to robot r at location l"
:precond ((loc(?r) = ?l) (belong(?k) = ?l) (holding(?k) = ?c) (load(?r) = nil))
:effects ((load(?r) <- ?c) (holding(?k) <- nil)))
load
> (defoperator move(?r ?l ?m)
:precond ((loc(?r) = ?l) (adjacent(?l ?m)))
:effects ((loc(?r) <- ?m)))
move
さて，実際に実行してみると，答えが出ずに stack overflow になってしまう．原因は教科書にあるように，ロボットが loc2 と
loc1 の間をいったりきたりして，無限ループにはまってしまっていた．教科書にはどのようにしてこの状態から脱出するかは書いてないが，とりあえず，applicable
なアクションを求めたところで，過去に同じアクションを実行していないか，すなわち forward-search の引数 plan の中に同じアクションがないか調べることとします．まったく同じアクションは実行しないように
forward-search を書き換えます．
> (=defun forward-search (operators state goal plan)
(if (satisfy-p state goal) (=values (reverse plan))
(let ((applicable (remove-if-not #'(lambda (a) (applicable-action-p a state))
(mappend #'(lambda (o) (instantiate-fs o state)) operators))))
(setq applicable
(remove-if #'(lambda (action)
(some #'(lambda (occurence)
(same-action-p action occurence))
plan))
applicable))
(cond ((null applicable) (fail))
(t (choose-bind action applicable
(forward-search operators (apply-action action state) goal
(cons action plan))))))))
forward-search
> (defun same-action-p (action1 action2)
(equalp (action-name action1) (action-name action2)))
すると forward-search を実行できて次のようになります．
> (setq *goal*
(make-state '((loc(r1) = loc1) (load(r1) = c3))))
statevar-unify
(#S(statevar :name loc :parms (r1 loc1) :val t) #S(statevar :name load :parms (r1 c3) :val t))
> (forward-search *operators* *state* *goal* ())
(#S(action :name #S(action-name :symbol move :parms (r1 loc2 loc1))
:comment nil
:precond (#S(statevar :name loc :parms (r1 loc2) :val t)
#S(statevar :name adjacent :parms (loc2 loc1) :val t))
:effects (#S(statevar :name loc :parms (r1) :val loc1)))
#S(action :name #S(action-name :symbol load :parms (crane1 loc1 c3 r1))
:comment "crane k loads container c to robot r at location l"
:precond (#S(statevar :name loc :parms (r1 loc1) :val t)
#S(statevar :name belong :parms (crane1 loc1) :val t)
#S(statevar :name holding :parms (crane1 c3) :val t)
#S(statevar :name load :parms (r1) :val nil))
:effects (#S(statevar :name load :parms (r1) :val c3)
#S(statevar :name holding :parms (crane1) :val nil))))
後向き探索ではゴールから出発して，ゴールを達成するためのアクションとサブゴールを求めます．そしてサブゴールをゴールとして探索を継続し，サブゴールとして初期状態を含む状態が得られれば，探索成功となります．次のプログラムは APTP の Figure 4.2 に示されたアルゴリズムをコード化したものです．
> (=defun backward-search (operators state goal plan)
(if (satisfy-p state goal) (=values plan)
(let ((applicable (remove-if-not #'(lambda (a) (applicable-action-p a state))
(mappend #'(lambda (o) (instantiate-bs o state)) operators))))
(cond ((null applicable) (fail))
(t (choose-bind action applicable
(backward-search operators (regressive-action action state) goal
(cons action plan))))))))