<div class="notebook">
<div class="nb-cell markdown" name="md1">
# STRIPS
This notebook explores [*STRIPS*](https://en.wikipedia.org/wiki/Stanford_Research_Institute_Problem_Solver); Stanford Research Institute Problem Solver.
STRIPS is
> an automated planner developed by Richard Fikes and Nils Nilsson
</div>
<div class="nb-cell markdown" name="md2">
## Blocks World
We will make plans in [blocks world](https://en.wikipedia.org/wiki/Blocks_world). Blocks world is
> one of the most famous planning domains in artificial intelligence. A set of wooden blocks of various shapes and colors sitting on a table. The goal is to build one or more vertical stacks of blocks. Only one block may be moved at a time: it may either be placed on the table or placed atop another block. Because of this, any blocks that are, at a given time, under another block cannot be moved. Moreover, some kinds of blocks cannot have other blocks stacked on top of them.
</div>
<div class="nb-cell html" name="htm1">
<svg width="480" height="480" viewBox="0 0 5 5" xmlns="http://www.w3.org/2000/svg">
<style>
.label { font-weight: normal; font-size: 0.8px; }
</style>
<g transform="scale(1 -1) translate(0 -5)" stroke="black" stroke-width="0.1" fill="none">
<g transform="translate(0, 1.5)">
<line x1="0" y1="0" x2="5" y2="0"></line>
<g name="b" transform="translate(0.5, 0)">
<rect x="0" y="0" width="1" height="1"></rect>
<text x="0.5" y="-0.5" transform="scale(1 -1) translate(-0.2, 0.3)" fill="black" class="label">b</text>
</g>
<g name="a" transform="translate(0.5, 1)">
<rect x="0" y="0" width="1" height="1"></rect>
<text x="0.5" y="-0.5" transform="scale(1 -1) translate(-0.2, 0.3)" fill="black" class="label">a</text>
</g>
<g name="c" transform="translate(3.5, 0)">
<rect x="0" y="0" width="1" height="1"></rect>
<text x="0.5" y="-0.5" transform="scale(1 -1) translate(-0.2, 0.3)" fill="black" class="label">c</text>
</g>
<g name="p" transform="translate(0.5, -1)">
<text x="0.5" y="-0.5" transform="scale(1 -1) translate(-0.2, 0.3)" fill="black" class="label">p</text>
</g>
<g name="q" transform="translate(2, -1)">
<text x="0.5" y="-0.5" transform="scale(1 -1) translate(-0.2, 0.3)" fill="black" class="label">q</text>
</g>
<g name="r" transform="translate(3.5, -1)">
<text x="0.5" y="-0.5" transform="scale(1 -1) translate(-0.2, 0.3)" fill="black" class="label">r</text>
</g>
</g>
</g>
</svg>
</div>
<div class="nb-cell markdown" name="md8">
Our world has three blocks: a, b, c, and three places on the table: p, q, r.
</div>
<div class="nb-cell program" data-background="true" name="p3">
block(a).
block(b).
block(c).
place(p).
place(q).
place(r).
</div>
<div class="nb-cell query" name="q2">
block(Block).
</div>
<div class="nb-cell query" name="q3">
place(Place).
</div>
<div class="nb-cell markdown" name="md3">
## State Representation
We will represent a state in the blocks world as a list of terms `on(X, Y)`. `X` can be a block, e.g. "a", "b", "c", and `Y` can either be a block or a place on the table, e.g. "p", "q", "r".
As an example the state above is represented as
```prolog
[on(a, b), on(b, p), on(c, r)].
```
</div>
<div class="nb-cell markdown" name="md4">
## `solve`
We will introduce a top-level term that allows us to come up with a plan to go from an `Initial` state to a `Final` state.
We delegate the actual solving to our implementation of STRIPS.
</div>
<div class="nb-cell program" data-background="true" name="p1">
solve(Initial, Final, Plan) :- strips(Initial, Final, Plan).
</div>
<div class="nb-cell query" name="q10">
solve([on(a, b), on(b, p), on(c, r)], [on(a, b), on(b, c), on(c,q)], Plan).
</div>
<div class="nb-cell markdown" name="md5">
## `strips`
The `strips/3` clause does the heavy lifting of coming up with a plan. There are two cases to consider.
1. We already reached the `Final` state. In this case our plan can be empty.
2. We haven't reached the `Final` state. In that case we perform any legal action to an intermediate state and try to reach the `Final` state from there.
### Optimalisation
#### Visited States
With the above considerations it is not garantueed that Prolog can find a solution. The reason for this is that Prolog would happily move a to b, and back again ad infinitum. In order to prevent the revisiting intermediate states, we keep track of the visited intermediate states.
#### Shorter Plan
In general we will favor shorter plans over longer plans. Since Prolog out of the box does a depth first search, we are not guaranteed to find the shortest plan first.
One way to remedy this is use [iterative deepening](https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search).
</div>
<div class="nb-cell program" data-background="true" name="p2">
strips(Initial, Final, Plan) :- strips(Initial, Final, [Initial], Plan).
strips(Initial, Final, Visited, Plan) :-
deepening_strips(1, Initial, Final, Visited, Plan).
deepening_strips(Bound, Initial, Final, Visited, Plan) :-
bounded_strips(Bound, Initial, Final, Visited, Plan).
deepening_strips(Bound, Initial, Final, Visited, Plan) :-
succ(Bound, Successor),
deepening_strips(Successor, Initial, Final, Visited, Plan).
bounded_strips(_, Final, Final, _, []).
bounded_strips(Bound, Initial, Final, Visited, [Action|Actions]) :-
succ(Predecessor, Bound),
action(Initial, Action),
perform(Initial, Action, Intermediate),
\+ member(Intermediate, Visited),
bounded_strips(Predecessor, Intermediate, Final, [Intermediate|Visited], Actions).
</div>
<div class="nb-cell markdown" name="md6">
## Definition
the `strips/4` clause is defined in terms of `action/2` and `perform/3`. In this section we will take a look at the definition of these clauses.
</div>
<div class="nb-cell markdown" name="md7">
### `action`
This clause is responsible for determining the legal actions in a state. All actions are of the form `move(Block, Destination)`.
A action `move(Block, Destination)` is legal if
1. `Block` is a block.
2. `Block` is not the `Destination`.
3. `Block` is free to move in this state. I.e. nothing is on `Block`.
4. `Destination` is free to move to in this state. I.e. nothing in on `Destination`.
</div>
<div class="nb-cell program" data-background="true" name="p4">
action(State, move(Block, Destination)) :-
block(Block),
\+ Block == Destination,
free(State, Block),
free(State, Destination).
free(State, Thing) :-
thing(Thing),
\+ member(on(_, Thing), State).
thing(Block) :- block(Block).
thing(Place) :- place(Place).
</div>
<div class="nb-cell query" name="q1">
free([on(a, b)], a).
</div>
<div class="nb-cell query" name="q4">
\+ free([on(a, b)], b).
</div>
<div class="nb-cell query" name="q5">
action([on(a, b), on(b, p), on(c, r)], move(a, q)).
</div>
<div class="nb-cell query" name="q11">
\+ action([on(a, b), on(b, p), on(c, r)], move(a, a)).
</div>
<div class="nb-cell query" name="q6">
action([on(a, b), on(b, p), on(c, r)], Action).
</div>
<div class="nb-cell markdown" name="md9">
### `perform`
This clause is responsible for changing the `Source` state into the `Target` state by performing an `Action`.
</div>
<div class="nb-cell program" data-background="true" name="p5">
perform(Source, move(Block, Destination), Target) :-
substitute(on(Block, _), Source, on(Block, Destination), Target).
</div>
<div class="nb-cell query" name="q7">
perform([on(a, b), on(b, p), on(c, r)],
move(a, c),
[on(a, c), on(b, p), on(c, r)]).
</div>
<div class="nb-cell markdown" name="md10">
## `substitute`
Given two lists `As` and `Bs`, `substitute/4` will substitute every term `A` in `As` with `B` to produce `Bs`.
</div>
<div class="nb-cell program" data-background="true" name="p6">
substitute(_, [], _, []).
substitute(A, [A|As], B, [B|Bs]) :-
substitute(A, As, B, Bs), !.
substitute(A, [X|As], B, [X|Bs]) :-
substitute(A, As, B, Bs).
</div>
<div class="nb-cell query" name="q8">
substitute(a, [a, b, c], x, [x, b, c]).
</div>
<div class="nb-cell query" name="q9">
substitute(X, [a, b, c], x, [a, x, c]).
</div>
</div>