STRIPS Planer Loops unbegrenzt

Question

Ich definierte in Prolog einen STRIPS-Planer, um logische Probleme zu lösen. Nach ein paar Versuchen mit anderen einfacheren Problemen machte ich mich auf, um zu sehen, ob es ein komplexeres Problem lösen könnte. Ich gab ihm eine STRIPS-Definition des Peg Solitaire, der englischen Version und bedenkt, dass wir keine diagonalen Züge machen können und der letzte Ball wird in der Mitte des Bretts enden und es versuchen, zu dem das Programm in eine Schleife einbrach. Hier ist das Problem: https://en.wikipedia.org/wiki/Peg_solitaire

Hier ist meine Lösung:

%%%%%%%%%%%%%%%%%%%%%% 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). 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%` 

Ich habe versucht, die Vereinfachung der das Tor nur tun, ein oder zwei Züge, die für die man arbeitet, und wenn die beiden bewegt sich nicht widersprechen andere, wie das Bewegen eines Marmors durch einen, der bereits bewegt wurde, und das Betreten der Schleife mit zwei Bewegungen, wie mit besagtem Objektiv:

objectivos ([ball (4,5), leer (3,5), leer (5,5), leer (6,5)]).

Ich habe versucht, zu verfolgen und zu debuggen, aber ich kann nicht scheinen, das Problem zu finden, obwohl ich glaube, dass es in der Formulierung des Problems im Gegensatz zum Planer selbst zu finden ist. Irgendwelche Ideen?

Answer 1

Es gibt mindestens einen logischen Fehler in Ihrem Code und einige einfache Leistungsoptimierungen sind möglich. Dies gibt eine teilweise Lösung für Ihr Problem.

Zuerst für den logischen Fehler: Die beabsichtigte Lösung für das Ziel objectivos([ball(4,5), empty(3,5), empty(5,5), empty(6,5)]) scheint der Plan zu sein P = [move(3, 5, 5, 5), move(6, 5, 4, 5)]. Aber die zweite dieser Bewegungen ist nicht legal mit Ihrer Definition von restricoes: Für diesen Schritt haben Sie Xi = 6, Xf = 4, und Bedingungen, die 6 =< Xm und Xm <= 4 erfordern, aber das ist unmöglich. Die Idee dieser Einschränkungen ist es, sicherzustellen, dass ball(Xm,Ym) zwischen den anderen zwei Kugeln in der Bewegung ist. Hier ist eine alternative Formulierung, die dies gewährleistet:

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] 

Dies auch einen Fall ausschließt, die mich vor verwirrt, wenn Sie den Code Tracing: Früher war es legal ball(Xi,Yi) = ball(Xm,Ym) zu haben.

Zweitens, um die Leistung zu verbessern, tauschen Sie die Ziele effects(E,S,N) und restriction(R) in der Definition von createPlan/6. Zuvor haben Sie die Auswirkungen von Zügen berechnet, bevor Sie ihre Rechtmäßigkeit überprüfen! Da die meisten vom Planer vorgeschlagenen Bewegungen illegal sind, verschwendet dies viel Zeit.

Dann das Ganze schöner zu machen, verwenden Sie die Definitionen von plano/1 und createPlan/4 ändern:

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

als die Definition, bevor Sie hatte Das ist einfacher, und es verhält sich auch schön. Wir können in einem vollständigen Plan passieren zu prüfen, ob es legal ist oder in einer Liste mit fester Länge passieren nur zu fragen, was diesen Länge Pläne existieren:

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

Mit Ihrer Definition, dies auf Looping und Zählen geht bis der Max Zähler, auf der Suche nach weiteren Lösungen, die nicht existieren können.

Mit dieser Formulierung wir zu Ihrem großen Ziel wechseln und versuchen, nach einer Lösung suchen (dies SWI-Prolog zum Teil spezifisch ist):

?- 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 

Ich hatte die Suche an dieser Stelle zu unterbrechen, es wird zu langsam. Weitere Verbesserungen sind sicherlich möglich, und ich könnte das weiter beobachten.