STRIPS Planner loops indefinitely

Question

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?

Answer 1

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 plan P = [move(3, 5, 5, 5), move(6, 5, 4, 5)]. But the second of these moves is not legal with your definition of restricoes: For this move you have Xi = 6, Xf = 4, and conditions requiring that 6 =< Xm and Xm <= 4, but this is impossible. The idea of these constraints is to ensure that ball(Xm,Ym) is between the other two balls in the move. Here is an alternative formulation that ensures this:

restricoes : [abs(Xf-Xi)+abs(Yf-Yi) =:= 2,
              abs(Xf-Xi)*abs(Yf-Yi) =:= 0,
              abs(Xf-Xm)+abs(Yf-Ym) =:= 1,
              abs(Xi-Xm)+abs(Yi-Ym) =:= 1]

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) and restriction(R) in the definition of createPlan/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 and createPlan/4 to:

 plano(P) :-
     length(P, PlanLength),
     createPlan(P, _, 0, PlanLength).

 createPlan(Plan,[I|Exec],N,Max) :- inicial(I),
                               N =< Max,
                               createPlan(Plan,I,Exec,Fn,N,Max),
                               satisfiedGoal(Fn).

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:

?- P = [_,_], plano(P).
P = [move(3, 5, 5, 5), move(6, 5, 4, 5)] ;
false.  % no more solutions

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):

?- length(P, N), format('searching for solutions of length ~w~n', [N]), time(plano(P)).
searching for solutions of length 0
% 58 inferences, 0.000 CPU in 0.000 seconds (71% CPU, 2171959 Lips)
searching for solutions of length 1
% 9,709 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 9123980 Lips)
searching for solutions of length 2
% 79,789 inferences, 0.009 CPU in 0.009 seconds (100% CPU, 8778416 Lips)
searching for solutions of length 3
% 477,230 inferences, 0.051 CPU in 0.051 seconds (100% CPU, 9409315 Lips)
searching for solutions of length 4
% 3,412,088 inferences, 0.361 CPU in 0.361 seconds (100% CPU, 9453315 Lips)
searching for solutions of length 5
% 30,967,699 inferences, 3.503 CPU in 3.503 seconds (100% CPU, 8840598 Lips)
searching for solutions of length 6

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.