Blocks World: the classical planning puzzle

Blocks world makes a good introductory puzzle since both Artificial Intelligence: A modern approach and Prolog: Programming for artificial intelligence use it as illustrations in their respective chapters on planning.

Handily, a version of the puzzle has been written in GDL, making this a good place to start showing how to apply this knowledge representation and reasoning language, called Knowledge Interchange Format (kif).

;;; Blocks World

  (role robot)


  (init (clear b))
  (init (clear c))

  (init (on c a))

  (init (table a))
  (init (table b))

  (init (step 1))


  (<= (next (on ?x ?y))
      (does robot (s ?x ?y)))

  (<= (next (on ?x ?y))
      (does robot (s ?u ?v))
      (true (on ?x ?y)))

  (<= (next (table ?x))
      (does robot (s ?u ?v))
      (true (table ?x))
      (distinct ?u ?x))

  (<= (next (clear ?y))
      (does robot (s ?u ?v))
      (true (clear ?y))
      (distinct ?v ?y))

  (<= (next (on ?x ?y))
      (does robot (u ?u ?v))
      (true (on ?x ?y))
      (distinct ?u ?x))

  (<= (next (table ?x))
      (does robot (u ?x ?y)))

  (<= (next (table ?x))
      (does robot (u ?u ?v))
      (true (table ?x)))

  (<= (next (clear ?y))
      (does robot (u ?x ?y)))

  (<= (next (clear ?x))
      (does robot (u ?u ?v))
      (true (clear ?x)))

  (<= (next (step ?y))
      (true (step ?x))
      (succ ?x ?y))

  (succ 1 2)
  (succ 2 3)
  (succ 3 4)


  (<= (legal robot (s ?x ?y))
      (true (clear ?x))
      (true (table ?x))
      (true (clear ?y))
       (distinct ?x ?y))

  (<= (legal robot (u ?x ?y))
      (true (clear ?x))
      (true (on ?x ?y)))


  (<= (goal robot 100)
      (true (on a b))
      (true (on b c)))

  (<= (goal robot 0)
      (not (true (on a b))))

  (<= (goal robot 0)
      (not (true (on b c))))


  (<= terminal
      (true (step 4)))

  (<= terminal
      (true (on a b))
      (true (on b c)))


This can easily be translated into Prolog, but note succ has been changed to successor to avoid a collision with SWI-Prolog's built in fuction succ(?Int1, ?Int2). Also note the variables which have been prefaced with underscores to avoid warnings about singleton variables.

init(on(c, a)).
next(on(X, Y)) :- does(robot, stack(X, Y)).
next(on(X, Y)) :- does(robot, stack(_U, _V)), true(on(X, Y)).
next(table(X)) :- does(robot, stack(U, _V)), true(table(X)), dif(U, X).
next(clear(Y)) :- does(robot, stack(_U, V)), true(clear(Y)), dif(V, Y).
next(on(X, Y)) :- does(robot, unstack(U, _V)), true(on(X, Y)), dif(U, X).
next(table(X)) :- does(robot, unstack(X, _Y)).
next(table(X)) :- does(robot, unstack(_U, _V)), true(table(X)).
next(clear(Y)) :- does(robot, unstack(_X, Y)).
next(clear(X)) :- does(robot, unstack(_U, _V)), true(clear(X)).
next(step(Y)) :- true(step(X)), successor(X, Y).
successor(1, 2).
successor(2, 3).
successor(3, 4).
legal(robot, stack(X, Y)) :- true(clear(X)), true(table(X)), true(clear(Y)), dif(X, Y).
legal(robot, unstack(X, Y)) :- true(clear(X)), true(on(X, Y)).
goal(robot, 100) :- true(on(a, b)), true(on(b, c)).
goal(robot, 0) :- \+true(on(a, b)).
goal(robot, 0) :- \+true(on(b, c)).
terminal :- true(step(4)).
terminal :- true(on(a, b)), true(on(b, c)).

In the Blocks World example, we have 27 lines of Prolog code which generate 15 ternary, "parent-node, edge, child-node", clauses which I have decided to name ply. Blocks World is literally a toy example by using more lines of code than the state space it describes, making it an exception to the rule that GDL is a compact way of describing state spaces which invariably suffer from combinatorial explosion.

ply([clear(b),clear(c),step(1),table(a),table(b),on(c,a)], does(robot, stack(b,c)), [clear(b),step(2),table(a),on(b,c),on(c,a)]).
ply([clear(b),clear(c),step(1),table(a),table(b),on(c,a)], does(robot, unstack(c,a)), [clear(a),clear(b),clear(c),step(2),table(a),table(b),table(c)]).
ply([clear(a),clear(b),clear(c),step(2),table(a),table(b),table(c)], does(robot, stack(a,b)), [clear(a),clear(c),step(3),table(b),table(c),on(a,b)]).
ply([clear(a),clear(b),clear(c),step(2),table(a),table(b),table(c)], does(robot, stack(a,c)), [clear(a),clear(b),step(3),table(b),table(c),on(a,c)]).
ply([clear(a),clear(b),clear(c),step(2),table(a),table(b),table(c)], does(robot, stack(b,a)), [clear(b),clear(c),step(3),table(a),table(c),on(b,a)]).
ply([clear(a),clear(b),clear(c),step(2),table(a),table(b),table(c)], does(robot, stack(b,c)), [clear(a),clear(b),step(3),table(a),table(c),on(b,c)]).
ply([clear(a),clear(b),clear(c),step(2),table(a),table(b),table(c)], does(robot, stack(c,a)), [clear(b),clear(c),step(3),table(a),table(b),on(c,a)]).
ply([clear(a),clear(b),clear(c),step(2),table(a),table(b),table(c)], does(robot, stack(c,b)), [clear(a),clear(c),step(3),table(a),table(b),on(c,b)]).
ply([clear(b),step(2),table(a),on(b,c),on(c,a)], does(robot, unstack(b,c)), [clear(b),clear(c),step(3),table(a),table(b),on(c,a)]).
ply([clear(b),clear(c),step(3),table(a),table(c),on(b,a)], does(robot, stack(c,b)), [clear(c),step(4),table(a),on(b,a),on(c,b)]).
ply([clear(b),clear(c),step(3),table(a),table(b),on(c,a)], does(robot, stack(b,c)), [clear(b),step(4),table(a),on(b,c),on(c,a)]).
ply([clear(a),clear(b),step(3),table(b),table(c),on(a,c)], does(robot, stack(b,a)), [clear(b),step(4),table(c),on(a,c),on(b,a)]).
ply([clear(a),clear(b),step(3),table(a),table(c),on(b,c)], does(robot, stack(a,b)), [clear(a),step(4),table(c),on(a,b),on(b,c)]).
ply([clear(a),clear(c),step(3),table(a),table(b),on(c,b)], does(robot, stack(a,c)), [clear(a),step(4),table(b),on(a,c),on(c,b)]).
ply([clear(a),clear(c),step(3),table(b),table(c),on(a,b)], does(robot, stack(c,a)), [clear(c),step(4),table(b),on(a,b),on(c,a)]).

Blocks World can be drawn as a game tree akin to the family trees commonly used as introductory Prolog examples.

Block World Tree


solve(Path) :-
  search(Start, Path).

search(State, [Move]) :-
  ply(State, Move, End),

search(State0, [Move | Path]) :-
  ply(State0, Move, State1),
  search(State1, Path).
?- solve(Path).
Path = [does(robot, unstack(c, a)), does(robot, stack(b, c)), does(robot, stack(a, b))] ;

Where to start?

Getting the representatio of the start space involves gathering a list of propositions init(P). I use setof(+Template, +Goal, -Set) because it removes duplicates and sorts the propositions alphanumerically.

Here is the first clause in the file I'll develop to solve this puzzle.

start(Start) :-
  setof(Init, init(Init), Start).

This can be run from within swipl as follows:

?- consult('').

?- consult('').

?- start(Start).
Start = [clear(b), clear(c), step(1), table(a), table(b), on(c, a)].

Including the step(1) proposition in the state representation converts a directed cyclic graph into a subcategory of directed acyclid graph called a tree.

I'm not sure at this stage if all GDL puzzles and games avoid cycles, but for this starting example, there is no need to worry about cycles in our search algorithm.

Where to end?

Typically, the goal of the puzzle is a terminal state worth 100 points, which we get from a state the terminal condition in the game description is true and goal(robot, 100) is true.

Looking at the rules for goal(Player, Value) and terminal, note the GDL clauses search for true(P).

This involves placing the propositions for whatever state in Prolog's clausal store using this unfortunate clause:

update_state(State) :-
  forall(member(X, State), assertz(true(X))).   

Using retractall(+Head) and assertz(+Term) to change the clausal store is considered bad practice for the same reason using global variables (in contrast to global constants) is considered a recipe for hard to trace bugs.

Furthermore, besides potentially confusing other parts of the programme referencing global variables, in Prolog constantly changing the clausal state is also considered harmful because it slows performance. But since setting true(P) is intrinsic to GDL, I don't see any easy alternative.

Using true/1 will also infuriate Prolog purists because true/0 is a builtin. But since the two have different arities, I'm not bothered rewriting true(P) as currentstate(P)_ or whatever since it does not create any problems for computers, only pedants.

For the rule to get the Player (role in this example), I'm jumping ahead to handle multiplayer games later.

end(End) :-
  (true(control(Player)) ; role(Player)),
  goal(Player, 100).

Knight's Tour is an example of a game which makes it dangerous to assume that there is an end goal valued at 100, but we'll worry about that later.

In swipl after consult(''). and updating consult('')..

?- end([on(a, b), on(b, c)]).
true ;

How to get from start to end?

Prolog has a cardinal, recursive state space search example which looks something like this:

search(End) :-

search(State0) :-
  ply(State0, _Move, State1),

solve :-

Besides init(Proposition) to tell us the initial state, puzzles and games written in GLD also provide next(Proposition) which are dependent on does(Role, Action). We get the available does(Role, Action) from GDL's legal(Role, Action) for whatever state is defined by true(Proposition).

For puzzles, Role is found from role(Role). But for games, the role is found from what control(Role) proposition is currently true.

Even though it is not needed for puzzles, I've included the line line (true(control(Player)) ; role(Player)) to get the current player even though it is not necessary until we get to more than single player games. Simultanious move games will require more thought, but I'll cross that bridge when we get to it.

ply(State0, does(Player, Move), State1) :-
  (true(control(Player)) ; role(Player)),
  legal(Player, Move),
  assertz(does(Player, Move)),
  setof(Next, next(Next), State1).