Making a STRIPS Planner using BFS in Prolog

Question

I have the following generic Breadth-first search code for Prolog and I would like to take the simple node representation s(a,b,go(a,b)) and change it to a predicate so that go(a,b) will represent a STRIPS operator say stack(A,B) so that I might have two predicates: s(S0,S,stack(A,B)) and s(S0,S,unstack(B,A)) (classic blocks world problem) which can be used by the breadth-first search below. I'm not sure if this is possible or how I would go about doing it. My first idea was to have a predicate as follows:

% S0 is the given state and S is the successor for the 'stack(A,B)' predicate if S0 
% A and B are not the same blocks, and we want the next state S to contain the 
% same state/preconditions information except we want to add 'on(A,B)'
% to S and we want to remove 'clear(B)' from S0

s(S0,S,stack(A,B)) :- 
 A \== B,
 % other predicates etc

The breadth-first search is given below.

:- use_module(library(lists)).

% bfs(?initial_state, ?goal_state, ?solution)
% does not include cycle detection
bfs(X,Y,P) :-
 bfs_a(Y,[n(X,[])],R),
 reverse(R,P).

bfs_a(Y,[n(Y,P)|_],P).
bfs_a(Y,[n(S,P1)|Ns],P) :-
 findall(n(S1,[A|P1]),s(S,S1,A),Es),
 append(Ns,Es,O),
 bfs_a(Y,O,P).

% s(?state, ?next_state, ?operator).
s(a,b,go(a,b)).
s(a,c,go(a,c)).

JTZ JTZ · Accepted Answer · 2015-03-31T12:35:41

bfs(S0,Goal,Plan) :-
    bfs_a(Goal1,[n(S0,[])],R),
    subset(Goal,Goal1),
    reverse(R,Plan).

bfs_a(Y,[n(Y,P)|_],P).
bfs_a(Y,[n(S,P1)|Ns],P) :-
    findall(n(S1,[A|P1]), s(S,S1,A), Es),
    append(Ns,Es,O),
    bfs_a(Y,O,P).

s(State,NextState,Operation) :-
    opn(Operation, PreList), subset(PreList, State),
    deletes(Operation, DelList), subtract(State, DelList, TmpState),               
    adds(Operation, AddList), union(AddList, TmpState, NextState).

subset([ ],_).
subset([H|T],List) :-
        member(H,List),
        subset(T,List).

opn(move(Block,X1,X2),[clear(Block),clear(X2),on(Block,X1)]) :-
    block(Block),object(X1),object(X2),
    Block \== X1, X2 \== Block, X1 \== X2.

adds(move(Block,X1,X2),[on(Block,X2),clear(X1)]).

deletes(move(Block,X1,X2),[on(Block,X1),clear(X2)]).

object(X) :- place(X) ; block(X).

block(a).
block(b).
block(c).
block(d).
place(x1).
place(x2).
place(x3).

Making a STRIPS Planner using BFS in Prolog

1 Answers