-
|
I am struggling to get I am working on a monotonic rewrite of I am sharing a little extra code so you can see the larger context, plan( State, Goals, [ ]) :-
satisfied( State, Goals).
plan( State, Goals, Plan) :-
conc( PrePlan, [Action], Plan), % conc/3 is append/3
select( State, Goals, Goal), % NOT select from scryer, actually defined as member/2
achieves( Action, Goal),
can( Action, Condition),
preserves( Action, Goals),
regress( Goals, Action, RegressedGoals), % Regress Goals through Action
plan( State, RegressedGoals, PrePlan).I am currently working on getting The definition of satisfied( State, Goals) :-
delete_all( Goals, State, [ ]).
select( State, Goals, Goal) :-
member( Goal, Goals).
achieves( Action, Goal) :-
adds( Action, Goals),
member( Goal, Goals).
preserves( Action, Goals) :-
deletes( Action, Relations),
\+ ( member( Goal, Relations),
member( Goal, Goals)).
regress( Goals, Action, RegressedGoals) :-
adds( Action, NewRelations),
delete_all( Goals, NewRelations, RestGoals), % we rewrote this to be monotic yesterday
can( Action, Condition),
addnew( Condition, RestGoals, RegressedGoals).
addnew( [ ], L, L).
addnew( [Goal | _ ], Goals, _ ) :-
impossible( Goal, Goals), !
fail.
addnew( [X | LI], L2, L3) :-
member( X, L2),!,
addnew( LI, L2, L3).
addnew( [X | LI], L2, [X | L3]) :-
addnew( LI, L2, L3).
delete_all( [],_,[ ]). %% we rewrote this https://github.com/mthom/scryer-prolog/discussions/2507
delete_all( [X | LI], L2, Diff) :-
member( X, L2),!,
delete_all( LI, L2, Diff).
delete_all( [X | LI], L2, [X | Diff]) :-
delete_all( LI, L2, Diff).We cut out the This time, It was easy enough to adapt the xs_ys_setunion([], L, L).
xs_ys_setunion([X|Xs], Ys, Union0) :-
if_(memberd_t(X, Ys),
Union0=Union,
Union0=[X|Union]
),
xs_ys_setunion(Xs, Ys, Union).but I am struggling to incorporate it into This is my current implementation of i_impossible_t(Goal, Goals, true) :-
impossible(Goal, Goals).
?- i_impossible_t(Goal, Goals, T).
%@ Goal = on(_A,_A), T = true
%@ ; Goal = on(_A,_B), Goals = [clear(_B)|_C], T = true
%@ ; Goal = on(_A,_B), Goals = [_C,clear(_B)|_D], T = true
%@ ; ... .
impossible_t(Goal, Goals, T) :-
if_(i_impossible_t(Goal, Goals),
T=true,
T=false
).
?- impossible_t(Goal, Goals, T).
%@ Goal = on(_A,_A), T = true
%@ ; Goal = on(_A,_B), Goals = [clear(_B)|_C], T = true
%@ ; Goal = on(_A,_B), Goals = [_C,clear(_B)|_D], T = true
%@ ; ... .
any_impossible_t([], [_|_], false).
any_impossible_t([Goal|Goals0], Goals, T0) :-
if_(impossible_t(Goal, Goals),
T0=true,
T0=T
),
any_impossible_t(Goals0, Goals, T).
?- any_impossible_t(G, G1, T).
%@ G = [], G1 = [_A|_B], T = false
%@ ; G = [on(_A,_A)], G1 = [_B|_C], T = true
%@ ; G = [on(_A,_A),on(_B,_B)], G1 = [_C|_D], T = true
%@ ; ... .
xs_ys_setunion([], L, L).
xs_ys_setunion([X|Xs], Ys, Union0) :-
if_(memberd_t(X, Ys),
Union0=Union,
Union0=[X|Union]
),
xs_ys_setunion(Xs, Ys, Union).
?- xs_ys_setunion("abc", "bcd", Union).
%@ Union = "abcd".
addnew(Goals0, Goals1, AllGoals) :-
if_(any_impossible_t(Goals0, Goals1),
fail,
xs_ys_setunion(Goals0, Goals1, AllGoals)).
?- addnew(Goals0, Goals1, AllGoals).
%@ Goals0 = [], Goals1 = [_A|_B], AllGoals = [_A|_B]
%@ ; nonterminationSo, I'm struggling with the Ultimately, I'd like to rewrite If anyone has any thoughts on the best approach to achieve |
Beta Was this translation helpful? Give feedback.
Replies: 5 comments 4 replies
-
|
What is |
Beta Was this translation helpful? Give feedback.
-
|
Ad |
Beta Was this translation helpful? Give feedback.
-
I wasn't sure how much detail to include-- I will type this up when I get back to my bench.
|
Beta Was this translation helpful? Give feedback.
-
|
Unfortunately, |
Beta Was this translation helpful? Give feedback.
-
If that's the only issue, I was able to rewrite that portion with Does that help anything? |
Beta Was this translation helpful? Give feedback.
-
|
Potentially? I don’t have a great sense of what is “required” for good |
Beta Was this translation helpful? Give feedback.
-
I suspected as much. So more likely the entire path search algorithm needs to be rewritten in a more monotonic fashion, there is perhaps no surgical solution to this one! |
Beta Was this translation helpful? Give feedback.
-
|
Hey, I actually got it ... kinda sorta maybe!!! Could anyone verify if this is ACTUALLY a monotonic rewrite? I think I'll make a separate discussion to critique/roast the code to a) verify correctness b) use proper terminology and style and c) rewrite it using DCGs or some other preferred method. As you can see, there are TONs of redundant choice points so I think there are a lot of possible savings with efficiency.
Source Code:- use_module(library(dif)).
:- use_module(library(charsio)).
:- use_module(library(debug)).
:- use_module(library(reif)).
:- use_module(library(lists)).
%% https://github.com/mthom/scryer-prolog/discussions/2507#discussioncomment-10471435
xs_ys_setdiff([], _, []).
xs_ys_setdiff([X|Xs], Ys, Diff0) :-
if_(memberd_t(X, Ys),
Diff0=Diff,
Diff0=[X|Diff]
),
xs_ys_setdiff(Xs, Ys, Diff).
?- xs_ys_setdiff("abcd", "be", Diff).
%@ Diff = "acd".
xs_ys_setunion([], L, L).
xs_ys_setunion([X|Xs], Ys, Union0) :-
if_(memberd_t(X, Ys),
Union0=Union,
Union0=[X|Union]
),
xs_ys_setunion(Xs, Ys, Union).
?- xs_ys_setunion("abc", "bcd", Union).
%@ Union = "abcd".
%% can(Action, Preconditions)
can(move(Block, From, To), [clear(Block), clear(To), on(Block,From)]) :-
block(Block),
object(To),
dif(To, Block),
object(From),
dif(Block, From).
?- can(Action, Preconditions).
%@ Action = move(a,1,1), Preconditions = [clear(a),clear(1),on(a,1)]
%@ ; Action = move(a,2,1), Preconditions = [clear(a),clear(1),on(a,2)]
%@ ; Action = move(a,3,1), Preconditions = [clear(a),clear(1),on(a,3)]
%@ ; Action = move(a,4,1), Preconditions = [clear(a),clear(1),on(a,4)]
%@ ; ... .
adds(move(X, From, To), [on(X,To), clear(From)]).
?- adds(Move, Conditions).
%@ Move = move(_A,_B,_C), Conditions = [on(_A,_C),clear(_B)].
deletes(move(X,From,To), [on(X,From),clear(To)]).
?- deletes(Move, Conditions).
%@ Move = move(_A,_B,_C), Conditions = [on(_A,_B),clear(_C)].
object(X) :-
( place(X)
; block(X)
).
?- object(X).
%@ X = 1
%@ ; X = 2
%@ ; X = 3
%@ ; X = 4
%@ ; ... .
block(a).
block(b).
block(c).
place(1).
place(2).
place(3).
place(4).
% plan(State, Goals, Plan).
plan(State, Goals, []) :-
satisfied(State, Goals).
plan(State, Goals, Plan) :-
append(PrePlan, [Action], Plan),
member(Goal, Goals),
achieves(Action, Goal),
can(Action, Condition),
preserves(Action, Goals),
regress(Goals, Action, RegressedGoals),
plan(State, RegressedGoals, PrePlan).
/** monotic rewrite of
satisfied( State, Goals) :-
delete_all( Goals, State, [ ]).
**/
satisfied(State, Goals) :-
xs_ys_setdiff(Goals, State, []).
?- satisfied(State, Goals).
%@ Goals = []
%@ ; State = [_A|_B], Goals = [_A]
%@ ; State = [_A|_B], Goals = [_A,_A]
%@ ; State = [_A|_B], Goals = [_A,_A,_A]
%@ ; ... .
achieves(Action, Goal) :-
adds(Action, Goals),
member(Goal, Goals).
?- achieves(Action, Goal).
%@ Action = move(_A,_B,_C), Goal = on(_A,_C)
%@ ; Action = move(_A,_B,_C), Goal = clear(_B).
/** Non monotic, rewrite below
preserves(Action, Goals) :-
deletes(Actions, Relations),
\+ ( member(Goal, Relations),
member(Goal, Goals)).
**/
%% monotonic rewrite. I think?
preserves(Action, Goals) :-
deletes(Action, Relations),
memberd_t(Goal, Relations, T1),
memberd_t(Goal, Goals, T2),
( dif(T1, true) ; dif(T2, true) ).
?- preserves(Action, Goals).
regress(Goals, Action, RegressedGoals) :-
adds(Action, NewRelations),
xs_ys_setdiff(Goals, NewRelations, RestGoals),
can(Action, Condition),
addnew(Condition, RestGoals, RegressedGoals).
?- regress(Goals, Action, RegressedGoals).
%@ Goals = [], Action = move(a,1,1), RegressedGoals = [clear(a),clear(1),on(a,1)]
%@ ; Goals = [], Action = move(a,2,1), RegressedGoals = [clear(a),clear(1),on(a,2)]
%@ ; Goals = [], Action = move(a,3,1), RegressedGoals = [clear(a),clear(1),on(a,3)]
%@ ; Goals = [], Action = move(a,4,1), RegressedGoals = [clear(a),clear(1),on(a,4)]
%@ ; ... .
i_impossible_t(on(X,X), _, true).
i_impossible_t(on(X,Y), Goals, true) :-
( member(clear(Y), Goals)
; member(on(X,Y1),Goals), dif(Y1, Y)
; member(on(X1,Y), Goals), dif(X1,X)
).
i_impossible_t(clear(X), Goals, true) :-
member(on(_,X), Goals).
i_impossible_t(_, _, false).
?- length(Goals, _), i_impossible_t(Action, Goals, T).
%@ Goals = [], Action = on(_A,_A), T = true
%@ ; Goals = [], T = false
%@ ; Goals = [_A], Action = on(_B,_B), T = true
%@ ; ... .
impossible_t(Goal, Goals, T) :-
length(Goals, _),
i_impossible_t(Goal, Goals, T).
?- impossible_t(Goal, Goals, false).
%@ Goals = []
%@ ; Goals = [_A]
%@ ; Goals = [_A,_B]
%@ ; Goals = [_A,_B,_C]
%@ ; ... .
any_impossible_t([], _, false).
any_impossible_t([Goal|Goals0], Goals, T0) :-
if_(impossible_t(Goal, Goals),
T0=true,
( T0=T,
any_impossible_t(Goals0, Goals, T)
)
).
?- any_impossible_t(Goal, Goals, T).
%@ Goal = [], T = false
%@ ; Goal = [on(_A,_A)|_B], Goals = [], T = true
%@ ; Goal = [_A], Goals = [], T = false
%@ ; Goal = [_A,on(_B,_B)|_C], Goals = [], T = true
%@ ; ... .
%% addnew(OldGoals, NewGoals, AllGoals): set union of goals if no conflicts
addnew(Goals0, Goals1, AllGoals) :-
if_(any_impossible_t(Goals0, Goals1),
fail,
xs_ys_setunion(Goals0, Goals1, AllGoals)).
?- can(_, Actions), addnew(Goals, Actions, AllGoals).
%@ Actions = [clear(a),clear(1),on(a,1)], Goals = [], AllGoals = [clear(a),clear(1),on(a,1)]
%@ ; Actions = [clear(a),clear(1),on(a,1)], Goals = [clear(a)], AllGoals = [clear(a),clear(1),on(a,1)]
%@ ; Actions = [clear(a),clear(1),on(a,1)], Goals = [clear(1)], AllGoals = [clear(a),clear(1),on(a,1)]
%@ ; Actions = [clear(a),clear(1),on(a,1)], Goals = [on(a,1)], AllGoals = [clear(a),clear(1),on(a,1)]
%@ ; ... .
% A state in the blocks world
%
% c
% a b
% = = = =
% place 1 2 3 4
state1([clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)]).
?- state1(Start), plan(Start, [on(a,b)], Plan).
%@ Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ; Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ; Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ; Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ; Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ; Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)], dif:dif(clear(2),_A), dif:dif(clear(a),_A), dif:dif(clear(b),_A), dif:dif(on(a,1),_A), dif:dif(on(c,a),_A)
%@ ; Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)], dif:dif(clear(2),_A), dif:dif(clear(a),_A), dif:dif(clear(b),_A), dif:dif(on(a,1),_A), dif:dif(on(c,a),_A)
%@ ; Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,4),move(a,1,b)]
%@ ; Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,4),move(a,1,b)]
%@ ; Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,4),move(a,1,b)]
%@ ; ... .But at least on initial inspection, |
Beta Was this translation helpful? Give feedback.
-
|
Moved code roast to: #2513 |
Beta Was this translation helpful? Give feedback.
Hey, I actually got it ... kinda sorta maybe!!! Could anyone verify if this is ACTUALLY a monotonic rewrite? I think I'll make a separate discussion to critique/roast the code to a) verify correctness b) use proper terminology and style and c) rewrite it using DCGs or some other preferred method. As you can see, there are TONs of redundant choice points so I think there are a lot of possible savings with efficiency.
Or if everyone prefers we could just roast the code here!Here!Source Code