Some basic ideas to understand:

• Goal: planning a sequence of actions to achieve a given state.
• State: A complete description of the world for the purpose of problem-solving
• Operator: transforms one(complete) state of the world into another(complete) state
  A search problem is defined by a state space(i.e., an initial state or set of initial states and a set of operators) and a set of goal states.

Basically, forward planning is familiar(forward) search.

We start in the initial state, check which actions are applicable and what states they result in, check if resulting states are goals, repeat…

Check applicability of actions
Compute the result of action
For computing the result of actions, it is useful to split postcondition into add list of positive fluents and delete list of fluents occuring with negation. The state resulting from executing an action act in state s is computed as follows:

1

result(s, act) = (s U add-list(act)) \ delete-list(act)

AI planning systems solve a particular kind of reasoning problem by:

• changing the state representation from explicit to attribute-based allowing partial representations of states in operators
• changing the operator representation and inference procedure to avoid the need for explicit frame axioms.
• changing the space in which the search is carried out(from world space to plan space)
  To implement this planning in prolog, we have three predicates:

1. Block(x) x is a block
2. On(x, y) block x is on y (where y is a block or the table)
3. Clear(x) there is no block on top of x

Representing operators in Prolog

In STRIPS planning, states are conjunctions of fluents.

States(e.g., initial state, goal state) can then be represented by lists of terms, e.g. [clear(a), on(a,b), …] representing a conjunction of fluents.

STRIPS operators have three components: name, precondition and postcondition(effects).

Here we representing operators using a predicate, pop/4

• first argument is the name of the operator(a term)
• second argument is the precondition(a list of terms)
• third argument is the add list(a list of terms)
• fourth argument is the delete list(a list of terms)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

:- use_module(library(lists)).
% fp(+State,+Goals,-Plan): Plan is a sequence of operators that
% applied in State achieves Goals
fp(S,G,P) :-
    list_to_set(S,SS),
    list_to_set(G,GS),
    fp(SS,GS,[],R),
    reverse(R,P).
fp(S,G,P,P) :- holds(G,S).
fp(S,G,Os,P) :-
    pop(O,Pre,A,D),
    holds(Pre,S),
    \+ member(O,Os),
    apply(S,A,D,S1),
    fp(S1,G,[O|Os],P).
% holds(+Goals,+State): the goals (or preconditions) Goals hold in State
holds([],_).
holds([Pre|Ps],S) :- select(Pre,S,S1), holds(Ps,S1).
% apply(+State,+AddList,+DeleteList,-NewState): NewState is the result of updating State with AddList and DeleteList
apply(S,A,D,S1) :-
    subtract(S,D,S2),
    union(A,S2,S1).
pop(move(X,Y),
    [block(X),block(Y),on(X,Z),clear(X),clear(Y)],
    [on(X,Y),clear(Z)],
    [on(X,Z),clear(Y)]).
pop(move_to_table(X),
    [block(X),block(Y),on(X,Y),clear(X)],
    [on(X,table),clear(Y)],
    [on(X,Y)]).
% Testing
initial_state([block(a),block(b),block(c),
	       on(b,table),on(c,a),on(a,table),clear(b),clear(c)]).
goal_state([on(a,b),on(b,c),on(c,table)]).

For clear description:

list_to_set:
True when Set has the same elements as List in the same order. The left-most copy of duplicate elements is retained. List may contain variables. Elements E1 and E2 are considered duplicates iff E1 == E2 holds. The complexity of the implementation is N*log(N).-From the SWI-Prolog documentation
That is list_to_set([1,1,2,3],X) — X = [1,2,3], list_to_set([1,2,3,3],X) — X = [1,2,3] .

For
fp(S, G, Os, P), firstly, we will find a possible move, that operation should be O -> (pop(O, Pre, A, D)). Secondly, we need to check is the precondition included the Pre we want, if it is, that means this operation can be executed. \+member(O, Os) checks has this operation been executed or not. If it has not been executed, then it can be executed. Then we call the apply(S,A,D,S1) to get the new list of preconditions, and add the operation to [O|Os], and call fp(S1,G,[O|Os],P) again until, fp(S, G, P, P) :- holds(G, S). That means, G is included in the S. Then we can return the P(the solution path).

What we need to pay more attention is the P here is inverse, because, each time, we need our operation in front of the operation lists. So when we finally return our operations, we need to reverse P.

Another way which contains a cycle detection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

:- use_module(library(lists)).
:- use_module(library(ordsets)).
% fp(+State,+Goals,-Plan): Plan is a sequence of operators that
% applied in State achieves Goals
fp(S,G,P) :-
    list_to_ord_set(S,OS),
    list_to_set(G,GS),
    fp(OS,GS,[OS],P).
fp(S,G,_,[]) :- holds(G,S).
fp(S,G,C,[O|P]) :-
    pop(O,Pre,A,D),
    holds(Pre,S),
    apply(S,A,D,S1),
    \+ member(S1,C),
    fp(S1,G,[S1|C],P).
% holds(+Goals,+State): the goals (or preconditions) Goals hold in State
holds([],_).
holds([Pre|Ps],S) :- select(Pre,S,S1), holds(Ps,S1).
% apply(+State,+AddList,+DeleteList,-NewState): NewState is the result
% of updating State with AddList and DeleteList. Note that all
% parameters must be ordered.
apply(S,A,D,S1) :-
    ord_subtract(S,D,S2),
    ord_union(A,S2,S1).
% Note: requires conditions to be ordered.
pop(move(X,Y),
    [block(X),block(Y),clear(X),clear(Y),on(X,Z)],
    [clear(Z),on(X,Y)],
    [clear(Y),on(X,Z)]).
pop(move_to_table(X),
    [block(X),block(Y),clear(X),on(X,Y)],
    [clear(Y),on(X,table)],
    [on(X,Y)]).

To describe it clearly:
fp(OS, GS, [OS],P) the third argument will hold all the states that the planning has been gone through, so here we need to use list_to_ord_set rather than list_to_set When in the fp(S,G,C,[O|P]) each time, we need to check is the state has been reached or not. This improvement will work with cycle detection.

Comments: