I defined in Prolog a STRIPS Planner to solve logic problems. After a few tryouts with other simpler problems I set out to see if it could solve a more complex one. I gave him a STRIPS definition of the peg solitaire, the english version and considering we cant do diagonal moves and the last ball will end up in the center of the board and tried it, to which the program broke into a loop. Here's the problem: https://en.wikipedia.org/wiki/Peg_solitaire
Here's my solution:
%%%%%%%%%%%%%%%%%%%%%% PLAN %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
accao(nome : move(Xi,Yi,Xf,Yf),
condicoes : [empty(Xf,Yf),ball(Xi,Yi), ball(Xm,Ym)],
efeitos : [ball(Xf,Yf), -ball(Xm,Ym),-ball(Xi,Yi), empty(Xi,Yi), empty(Xm,Ym), -empty(Xf,Yf)],
restricoes : [abs(Xf-Xi)+abs(Yf-Yi)=:=2, abs(Xf-Xi)*abs(Yf-Yi)=:=0, Xi=<Xm, Xm=<Xf, Yi=<Ym, Ym=<Yf]).
inicial([empty(5,5), ball(1,4), ball(1,5), ball(1,6),
ball(2,4), ball(2,5), ball(2,6),
ball(3,4), ball(3,5), ball(3,6),
ball(4,1), ball(4,2), ball(4,3),ball(4,4), ball(4,5), ball(4,6),ball(4,7), ball(4,8), ball(4,9),
ball(5,1), ball(5,2), ball(5,3),ball(5,4), ball(5,6),ball(5,7), ball(5,8), ball(5,9),
ball(6,1), ball(6,2), ball(6,3),ball(6,4), ball(6,5), ball(6,6),ball(6,7), ball(6,8), ball(6,9),
ball(7,4), ball(7,5), ball(7,6),
ball(8,4), ball(8,5), ball(8,6),
ball(9,4), ball(9,5), ball(9,6)]).
objectivos([ball(5,5), empty(1,4), empty(1,5), empty(1,6),
empty(2,4), empty(2,5), empty(2,6),
empty(3,4), empty(3,5), empty(3,6),
empty(4,1), empty(4,2), empty(4,3),empty(4,4), empty(4,5), empty(4,6),empty(4,7), empty(4,8), empty(4,9),
empty(5,1), empty(5,2), empty(5,3),empty(5,4), empty(5,6),empty(5,7), empty(5,8), empty(5,9),
empty(6,1), empty(6,2), empty(6,3),empty(6,4), empty(6,5), empty(6,6),empty(6,7), empty(6,8), empty(6,9),
empty(7,4), empty(7,5), empty(7,6),
empty(8,4), empty(8,5), empty(8,6),
empty(9,4), empty(9,5), empty(9,6)]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%% PRINT FUNCTION %%%%%%%%%%%%%%%%%%%%%%%%%%%
printExec([]).
printExec([A,E|T]) :- write("Action performed: "),
write(A),nl,
write("Situation: "),
write(E),nl,
printExec(T).
writeExec([I|T]):- write("Initial Situation"),
write(I),nl,
printExec(T),
write("Goal: "),
objectivos(G),
write(G),
write(" satisfied."),nl.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%% AUXILIAR FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%
member(E,[E|_]).
member(E,[_|T]):-member(E,T).
sub([],_).
sub([H|T],L):- member(H,L),
sub(T,L).
remove(_,[],[]):-!.
remove(E1, [E2|T], T):- E1 == E2, !.
remove(E,[H|T1],[H|T2]):- remove(E,T1,T2).
add(E,[],[E]):-!.
add(E1,[E2|T],[E1,E2|T]):- E1 \== E2, !.
add(E,[H|T1],[H|T2]):-add(E,T1,T2).
effects([],S,S).
effects([-H|Fx],S,N) :-!,
remove(H,S,NS),
effects(Fx,NS,N).
effects([H|Fx],S,N) :- !,
add(H,S,NS),
effects(Fx,NS,N).
restriction([]).
restriction([R|T]) :- R,
restriction(T).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%% PLAN EXECUTE %%%%%%%%%%%%%%%%%%%%%%%%%%%
planExecute(P):-testPlan(P,E),writeExec(E),!.
satisfiedGoal(E):- objectivos(Fn),!,
sub(Fn,E).
testPlan(Plan,[I|Exec]) :- inicial(I),
testPlan(Plan,I,Exec,Fn),
satisfiedGoal(Fn).
testPlan([],Fn,[],Fn).
testPlan([H|T],S,[H,N|Exec],Fn) :- accao(nome:H, condicoes:C,efeitos:E, restricoes:R),
sub(C,S),
effects(E,S,N),
restriction(R),
testPlan(T,N,Exec,Fn).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%% FIND PLAN %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
plano(P) :- progressivePlan(P, 0).
progressivePlan(P, N) :- createPlan(P,_,0,N).
progressivePlan(P, N) :- \+ createPlan(P,_,0,N),
NewN is N + 1,
progressivePlan(P, NewN).
createPlan(Plan,[I|Exec],N,Max) :- inicial(I),
createPlan(Plan,I,Exec,Fn,N,Max),
satisfiedGoal(Fn).
createPlan([],Fn,[],Fn,Max,Max):- !.
createPlan([H|T],S,[H,N|Exec],Fn,Acc, Max) :- accao(nome:H, condicoes:C, efeitos:E, restricoes:R),
sub(C,S),
effects(E,S,N),
restriction(R),
NewAcc is Acc+1,
createPlan(T,N,Exec,Fn,NewAcc, Max).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%`
I've tried simplifying the goal by just doing one or two moves, which works for the one and when the two moves don't contradict each other, like moving a marble on through one that was already moved, entering the loop with two moves when they do, like with said objective:
objectivos([ball(4,5), empty(3,5), empty(5,5), empty(6,5)]).
I've tried tracing and debugging but I cant seem to find the issue, although I believe it to be located in the formulation of the problem as opposed to the Planner itself. Any Ideas?
There is at least one logical error in your code, and some simple performance tweaks are possible. This gives a partial solution to your problem.
First, for the logical error: The intended solution for the goal
objectivos([ball(4,5), empty(3,5), empty(5,5), empty(6,5)])
seems to be the planP = [move(3, 5, 5, 5), move(6, 5, 4, 5)]
. But the second of these moves is not legal with your definition ofrestricoes
: For this move you haveXi = 6
,Xf = 4
, and conditions requiring that6 =< Xm
andXm <= 4
, but this is impossible. The idea of these constraints is to ensure thatball(Xm,Ym)
is between the other two balls in the move. Here is an alternative formulation that ensures this:This also excludes a case that confused me before, when tracing the code: Previously it was legal to have
ball(Xi,Yi) = ball(Xm,Ym)
.Second, to improve performance, exchange the goals
effects(E,S,N)
andrestriction(R)
in the definition ofcreatePlan/6
. Previously you computed the effects of moves before checking their legality! Because most moves proposed by the planner are illegal, this wastes a lot of time.Then, to make the whole thing nicer to use, you can change the definitions of
plano/1
andcreatePlan/4
to:This is simpler than the definition you had before, and it also behaves more nicely. We can pass in a complete plan to check whether it is legal, or just pass in a list of fixed length to ask what plans of that length exist:
With your definition, this would go on looping and counting up the
Max
counter, searching for further solutions that cannot exist.With this formulation we can switch to your big goal and try to search for a solution (this is partly specific to SWI-Prolog):
I had to interrupt the search at this point, it becomes too slow. More tweaks are certainly possible, and I might keep looking at this.