Overly complicated unification for planning algorithm?

[jjtolton]

I'm trying to implement a planning algorithm from video game literature and I am surprised about how gnarly the unification part is turning out to be:

Now, my current implementation seems to match what is in the literature:

?- F+\(state_action(state([at_c(loc1, c1), at_c(loc1, c2),
                           at_c(loc2,c3), at_c(loc3,c4),
                           at_o(loc1,o1), at_o(loc1,o3),
                           at_o(loc3,o4),at_o(loc5,o2),
                           at_o(loc5,o5)]),
                    action(Name, parameters(Params), _, _)),
       F=..[Name|Params]
      ).  
   F = take(location(loc1),creature(c1),object(o1)), dif:dif(at_c(_A,_B),at_c(loc1,c2)), dif:dif(at_c(_C,_D),at_c(loc2,c3)), dif:dif(at_c(_E,_F),at_c(loc3,c4)), dif:dif(at_o(_G,_H),at_o(loc1,o3)), dif:dif(at_o(_I,_J),at_o(loc3,o4)), dif:dif(at_o(_K,_L),at_o(loc5,o2)), dif:dif(at_o(_M,_N),at_o(loc5,o5))
;  F = take(location(loc1),creature(c1),object(o3)), dif:dif(at_c(_A,_B),at_c(loc1,c2)), dif:dif(at_c(_C,_D),at_c(loc2,c3)), dif:dif(at_c(_E,_F),at_c(loc3,c4)), dif:dif(at_o(_G,_H),at_o(loc1,o1)), dif:dif(at_o(_I,_J),at_o(loc3,o4)), dif:dif(at_o(_K,_L),at_o(loc5,o2)), dif:dif(at_o(_M,_N),at_o(loc5,o5))
;  F = take(location(loc1),creature(c2),object(o1)), dif:dif(at_c(_A,_B),at_c(loc1,c1)), dif:dif(at_c(_C,_D),at_c(loc2,c3)), dif:dif(at_c(_E,_F),at_c(loc3,c4)), dif:dif(at_o(_G,_H),at_o(loc1,o3)), dif:dif(at_o(_I,_J),at_o(loc3,o4)), dif:dif(at_o(_K,_L),at_o(loc5,o2)), dif:dif(at_o(_M,_N),at_o(loc5,o5))
;  F = take(location(loc1),creature(c2),object(o3)), dif:dif(at_c(_A,_B),at_c(loc1,c1)), dif:dif(at_c(_C,_D),at_c(loc2,c3)), dif:dif(at_c(_E,_F),at_c(loc3,c4)), dif:dif(at_o(_G,_H),at_o(loc1,o1)), dif:dif(at_o(_I,_J),at_o(loc3,o4)), dif:dif(at_o(_K,_L),at_o(loc5,o2)), dif:dif(at_o(_M,_N),at_o(loc5,o5))
;  F = take(location(loc3),creature(c4),object(o4)), dif:dif(at_c(_A,_B),at_c(loc1,c1)), dif:dif(at_c(_C,_D),at_c(loc1,c2)), dif:dif(at_c(_E,_F),at_c(loc2,c3)), dif:dif(at_o(_G,_H),at_o(loc1,o1)), dif:dif(at_o(_I,_J),at_o(loc1,o3)), dif:dif(at_o(_K,_L),at_o(loc5,o2)), dif:dif(at_o(_M,_N),at_o(loc5,o5))
;  false.

(Should I be concerned about all these difs??)

However, I was surprised how much work I had to do to unify this, so I'm wondering if anyone has any suggestions.

This was my approach:

1. Model as they do in the book

action(take,
       parameters([location(L),
                   creature(C),
                   object(O)]),
       preconditions([not(hold(O,C)),
                      at_c(L,C),
                      at_o(L,O)]),
       effects([not(at_o(L,O)),
                hold(O,C)])).

2. An action is valid for a state if the preconditions of the action are valid for the state

state_action(state(State),
             action(Name,
                    parameters(Params),
                    preconditions(Pre),
                    effects(Fx))
             ) :-
        action(Name,
               parameters(Params),
               preconditions(Pre),
               effects(Fx)),
        state_goals_satisfied(State,Pre).

3. The preconditions are valid for the state if:
   a. All positive preconditions are present in the state
   b. There are no negated precondition terms which contradict terms in the state, i.e., not(a) contradicts a.

state_goals_satisfied(State,Goals) :-
        all_positives_there(State,Goals),
        no_negatives_there(State,Goals).

So far so good... this is where it starts to get hairy.

The Rest of the Owl

all_positives_there(State,Goals) :-
        positives(State, PositiveState),
        positives(Goals, PositiveGoals),
        all_positive_goals_present(PositiveGoals, PositiveState).

all_positive_goals_present(PositiveGoals, PositiveState) :-
        tfilter(\G^T^(memberd_t(G, PositiveGoals, T)), PositiveState, PositiveBindings),
        PositiveBindings=PositiveGoals.

no_negatives_there(State,Goals) :-
        negatives(Goals,NegativeGoals),
        negatives(State,NegativeState),
        neg__state_goals_unbound(NegativeState, NegativeGoals, RemainingNegativeGoals),
        no_contradictions(State, RemainingNegativeGoals).

neg__state_goals_unbound(NegativeState, NegativeGoals, RemainingNegativeGoals) :-
        tpartition(\G^T^(memberd_t(G, NegativeState, T)), NegativeGoals, _NegativeBindings, RemainingNegativeGoals).

no_contradictions(State, RemainingNegativeGoals) :-
        state_negated(State,FlippedState),
        tfilter(\G^T^(memberd_t(G, RemainingNegativeGoals, T)), FlippedState, []) .


positive(Elem, T) :-
        (   var(Elem)
        ->  T=true % allow for general query
        ;   Elem =.. [F|_],
            if_(dif(F,not),
                T=true,
                T=false
               )
        ).
        

positives(Goals, PositiveGoals) :-
        tfilter(positive, Goals, PositiveGoals).

negatives(Goals,NegativeGoals) :-
        tpartition(positive,Goals,_,NegativeGoals).

normal_negated(X, not(X)).

state_negated(State,FlippedState) :-
        positives(State,PosState),
        maplist(normal_negated,PosState,FlippedState).

So, it seems to be working, but I feel like there's probably a more elegant way to do it. That being said, reif came in very handy here, but I feel like the pattern of

   tfilter(\G^T^(memberd_t(G, Xs, T)), Ys, Intersection)

is probably a solved problem that I don't have a better way to do. Would appreciate any thoughts/critiques!

Full Code:

:- use_module(library(lists)).
:- use_module(library(debug)).
:- use_module(library(lambda)).
:- use_module(library(reif)).
:- use_module(library(queues)).
:- use_module(library(clpz)).
:- use_module(library(debug)).
:- use_module(library(dcgs)).
:- use_module(library(dif)).


action(take,
       parameters([location(L),
                   creature(C),
                   object(O)]),
       preconditions([not(hold(O,C)),
                      at_c(L,C),
                      at_o(L,O)]),
       effects([not(at_o(L,O)),
                hold(O,C)])).


state_action(state(State),
             action(Name,
                    parameters(Params),
                    preconditions(Pre),
                    effects(Fx))
             ) :-
        action(Name,
               parameters(Params),
               preconditions(Pre),
               effects(Fx)),
        state_goals_satisfied(State,Pre).
        

state_goals_satisfied(State,Goals) :-
        all_positives_there(State,Goals),
        no_negatives_there(State,Goals).


all_positives_there(State,Goals) :-
        positives(State, PositiveState),
        positives(Goals, PositiveGoals),
        all_positive_goals_present(PositiveGoals, PositiveState).

all_positive_goals_present(PositiveGoals, PositiveState) :-
        tfilter(\G^T^(memberd_t(G, PositiveGoals, T)), PositiveState, PositiveBindings),
        PositiveBindings=PositiveGoals.

no_negatives_there(State,Goals) :-
        negatives(Goals,NegativeGoals),
        negatives(State,NegativeState),
        neg__state_goals_unbound(NegativeState, NegativeGoals, RemainingNegativeGoals),
        no_contradictions(State, RemainingNegativeGoals).

neg__state_goals_unbound(NegativeState, NegativeGoals, RemainingNegativeGoals) :-
        tpartition(\G^T^(memberd_t(G, NegativeState, T)), NegativeGoals, _NegativeBindings, RemainingNegativeGoals).

no_contradictions(State, RemainingNegativeGoals) :-
        state_negated(State,FlippedState),
        tfilter(\G^T^(memberd_t(G, RemainingNegativeGoals, T)), FlippedState, []) .


positive(Elem, T) :-
        (   var(Elem)
        ->  T=true % allow for general query
        ;   Elem =.. [F|_],
            if_(dif(F,not),
                T=true,
                T=false
               )
        ).
        

positives(Goals, PositiveGoals) :-
        tfilter(positive, Goals, PositiveGoals).

negatives(Goals,NegativeGoals) :-
        tpartition(positive,Goals,_,NegativeGoals).

normal_negated(X, not(X)).

state_negated(State,FlippedState) :-
        positives(State,PosState),
        maplist(normal_negated,PosState,FlippedState).

        

?- state_action(state([at_c(store,bob),
                       at_o(store,gun),
                       not(hold(gun,bob))
                      ]),
                action(Name,
                       parameters(Params),
                       preconditions(Pre),
                       effects(Fx)
                      )
               ).
   Name = take, Params = [location(store),creature(bob),object(gun)], Pre = [not(hold(gun,bob)),at_c(store,bob),at_o(store,gun)], Fx = [not(at_o(store,gun)),hold(gun,bob)]
;  false.


?- state_action(state([at_c(store,bob),
                       at_o(store,gun),
                       hold(gun,bob)
                      ]),
                action(Name,
                       parameters(Params),
                       preconditions(Pre),
                       effects(Fx)
                      )
               ).
   false.


?- state_action(state([at_c(store,bob),
                       at_o(store,gun),
                       not(wrong)
                      ]),
                action(Name,
                       parameters(Params),
                       preconditions(Pre),
                       effects(Fx)
                      )
               ).
   Name = take, Params = [location(store),creature(bob),object(gun)], Pre = [not(hold(gun,bob)),at_c(store,bob),at_o(store,gun)], Fx = [not(at_o(store,gun)),hold(gun,bob)]
;  false.




?- F+\(state_action(state([at_c(loc1, c1), at_c(loc1, c2),
                           at_c(loc2,c3), at_c(loc3,c4),
                           at_o(loc1,o1), at_o(loc1,o3),
                           at_o(loc3,o4),at_o(loc5,o2),
                           at_o(loc5,o5)]),
                    action(Name, parameters(Params), _, _)),
       F=..[Name|Params]
      ).  
   F = take(location(loc1),creature(c1),object(o1)), dif:dif(at_c(_A,_B),at_c(loc1,c2)), dif:dif(at_c(_C,_D),at_c(loc2,c3)), dif:dif(at_c(_E,_F),at_c(loc3,c4)), dif:dif(at_o(_G,_H),at_o(loc1,o3)), dif:dif(at_o(_I,_J),at_o(loc3,o4)), dif:dif(at_o(_K,_L),at_o(loc5,o2)), dif:dif(at_o(_M,_N),at_o(loc5,o5))
;  F = take(location(loc1),creature(c1),object(o3)), dif:dif(at_c(_A,_B),at_c(loc1,c2)), dif:dif(at_c(_C,_D),at_c(loc2,c3)), dif:dif(at_c(_E,_F),at_c(loc3,c4)), dif:dif(at_o(_G,_H),at_o(loc1,o1)), dif:dif(at_o(_I,_J),at_o(loc3,o4)), dif:dif(at_o(_K,_L),at_o(loc5,o2)), dif:dif(at_o(_M,_N),at_o(loc5,o5))
;  F = take(location(loc1),creature(c2),object(o1)), dif:dif(at_c(_A,_B),at_c(loc1,c1)), dif:dif(at_c(_C,_D),at_c(loc2,c3)), dif:dif(at_c(_E,_F),at_c(loc3,c4)), dif:dif(at_o(_G,_H),at_o(loc1,o3)), dif:dif(at_o(_I,_J),at_o(loc3,o4)), dif:dif(at_o(_K,_L),at_o(loc5,o2)), dif:dif(at_o(_M,_N),at_o(loc5,o5))
;  F = take(location(loc1),creature(c2),object(o3)), dif:dif(at_c(_A,_B),at_c(loc1,c1)), dif:dif(at_c(_C,_D),at_c(loc2,c3)), dif:dif(at_c(_E,_F),at_c(loc3,c4)), dif:dif(at_o(_G,_H),at_o(loc1,o1)), dif:dif(at_o(_I,_J),at_o(loc3,o4)), dif:dif(at_o(_K,_L),at_o(loc5,o2)), dif:dif(at_o(_M,_N),at_o(loc5,o5))
;  F = take(location(loc3),creature(c4),object(o4)), dif:dif(at_c(_A,_B),at_c(loc1,c1)), dif:dif(at_c(_C,_D),at_c(loc1,c2)), dif:dif(at_c(_E,_F),at_c(loc2,c3)), dif:dif(at_o(_G,_H),at_o(loc1,o1)), dif:dif(at_o(_I,_J),at_o(loc1,o3)), dif:dif(at_o(_K,_L),at_o(loc5,o2)), dif:dif(at_o(_M,_N),at_o(loc5,o5))
;  false.

[hurufu]

For an unfinished project of mine, I used standard PDDL for planning and have used Prolog to convert program data to PDDL format and then parse solver's output. It proved to be unimpressive. Performance was bad and I was starting to have more problems than I hoped that approach would solve.

Maybe your approach trying to implement everything in Prolog will turn out better, but I can't comment on the implementation – I don't have much experience with this sort of things.

[jjtolton]

😬 Yikes, thanks for the experience report. I have heard that not a lot of people use Prolog for planners these days, which I find surprising!

I am parsing C# data and returning data to C# so I hope I don't run into the same problem 😅

Btw are you coming to the meetup @hurufu ??

[hurufu]

I don't remember what was the show-stopper for me, around the same time I wrote my silly program LLMs started to be very good at similar tasks, so it kinda made my work immediately obsolete.

P.S. I don't know if I will come to the meetup, we'll see.

[triska]

The data structure in the screenshot is a list with uniform elements (property-value pairs) and would for example correspond to:

[action-take,
 parameters-[location-L,creature-C,object-O],
 preconditions-[not(hold(Object,C)),'at-c'(L,C),'at-o'(L,O)],
 effects-[not('at-o'(L,O)),hold(Object,C)]
]

This may simplify reasoning about it.

The remaining dif/2 constraints may indicate that "too much" is taken into account, values that do not matter for the distinction but are now nevertheless constrained. If you find a smaller example that exhibits the issue then we may understand it better.

[jjtolton]

Oh interesting I had no considered that it might be over constrained, will have to investigate.

[jjtolton]

The remaining dif/2 constraints may indicate that "too much" is taken into account, values that do not matter for the distinction but are now nevertheless constrained. If you find a smaller example that exhibits the issue then we may understand it better.

Huzzah! Great suggestion. After simplifying the problem I realized what the issue was, and now I have a very clean and correct solution -- although it is not yet optimal, but that will come next!

?- Action+\(State=state([at_c(loc1, c1),
                         at_c(loc1, c2),
                         at_c(loc2,c3),
                         at_c(loc3,c4),
                         at_o(loc1,o1),
                         at_o(loc1,o3),
                         at_o(loc3,o4),
                         at_o(loc5,o2),
                         at_o(loc5,o5)]),
            Depth=5,
            slurp(ActionFileName, Actions),
            Goals=[hold(A,B)],
            plan(Depth,State,Goals,Actions,action(Name,parameters(Params),_,_)),
            Action=..[Name|Params]).
%@   Action = take(location(loc1),creature(c1),object(o1))
%@;  Action = take(location(loc1),creature(c1),object(o3))
%@;  Action = take(location(loc1),creature(c2),object(o1))
%@;  Action = take(location(loc1),creature(c2),object(o3))
%@;  Action = take(location(loc3),creature(c4),object(o4))
%@;  false.

The solution was to take everywhere I was doing:

tfilter(\G^T^memberd_t(G,Xs,Y), Something, Res)

and replace it with:

member_of_t(Xs,G,T) :-
        memberd_t(G, Xs, T).

tfilter(member_of_t(XS), Something, Res)