STRIPS Planner петли неопределенно

Question

Я определил в Прологе a Планировщик STRIPS для решения логических задач. После нескольких попыток с другими более простыми проблемами я решил посмотреть, может ли он решить более сложную задачу. Я дал ему определение STRIPS пасьянса peg, английскую версию и учитывая, что мы не можем делать диагональные ходы, и последний мяч попадает в центр доски и пробовал его, к чему программа ворвалась в цикл. Вот проблема: https://en.wikipedia.org/wiki/Peg_solitaire

Вот мое решение:

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

Я попытался упростить задачу, просто делая один или два хода, который работает на одном и когда два движения не противоречат друг другие, например, перемещение мрамора по тому, что уже было перемещено, вхождение в петлю с двумя ходами, когда они это делают, например, с указанной целью:

objectivos ([шар (4,5), пустой (3,5), пустой (5,5), пустой (6,5)]).

Я пробовал отслеживать и отлаживать, но я не могу найти проблему, хотя я считаю, что она находится в формулировке проблемы в отличие от самого Планировщика. Есть идеи?

Answer 1

В коде есть как минимум одна логическая ошибка, и возможны некоторые простые настройки производительности. Это дает частичное решение вашей проблемы.

Во-первых, для логической ошибки: Предполагаемое решение для цели objectivos([ball(4,5), empty(3,5), empty(5,5), empty(6,5)]) похоже на план P = [move(3, 5, 5, 5), move(6, 5, 4, 5)]. Но второй из этих шагов не является законным с вашим определением restricoes: для этого хода у вас есть Xi = 6, Xf = 4 и условия, требующие, чтобы 6 =< Xm и Xm <= 4, но это невозможно. Идея этих ограничений заключается в обеспечении того, чтобы ball(Xm,Ym) находился между двумя другими шарами в движении. Вот альтернативная формулировка, которая обеспечивает это:

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] 

Это также исключает случай, который перепутал меня раньше, когда трассировка кода: Раньше это было законно иметь ball(Xi,Yi) = ball(Xm,Ym).

Во-вторых, чтобы улучшить производительность, обменивайте цели effects(E,S,N) и restriction(R) в определении createPlan/6. Раньше вы вычисляли эффекты ходов перед проверкой их законности! Поскольку большинство шагов, предложенных планировщиком, являются незаконными, это отнимает много времени.

Затем, чтобы сделать все это лучше использовать, вы можете изменить определения plano/1 и createPlan/4 к:

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

Это проще, чем определение вы были раньше, и это также ведет себя более красиво. Мы можем пройти в полном плане, чтобы проверить, является ли это законным, или просто передать список фиксированной длиной, чтобы спросить, что планы этой длиной существует:

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

С вашим определением, это будет идти на перекручивании и подсчете вверх счетчик Max, ища дальнейшие решения, которые не могут существовать.

С этой формулировкой мы можем перейти к вашей большой цели и попытаться найти решение (это отчасти специфично для 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 

мне пришлось прервать поиск в данный момент, это становится слишком медленным. Возможно, возможны дополнительные настройки, и я могу продолжать смотреть на это.