STRIPS Planner зацикливается бесконечно
В Прологе я определил Планировщик ПОЛОС для решения логических задач. После нескольких испытаний с другими более простыми проблемами я решил выяснить, может ли он решить более сложную проблему. Я дал ему СТРИПС определение пасьянса колышка, английскую версию и, учитывая, что мы не можем делать диагональные ходы, и последний шар окажется в центре доски и попробовал его, и программа перешла в петлю. Вот проблема: 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 ([ball (4,5), пустой (3,5), пустой (5,5), пустой (6,5)]).
Я пытался отследить и отладить, но, похоже, не могу найти проблему, хотя считаю, что она заключается в формулировке проблемы, а не в самом Планировщике. Есть идеи?
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
Мне пришлось прервать поиск в этой точке, он становится слишком медленным. Конечно, возможны и другие настройки, и я мог бы продолжать смотреть на это.