RFC: tarski just says no to stack(a, a)

[miquelramirez]

As the title implies, I think we're now in a good place to start considering what kind of constraints we would like to enforce in the grounding algorithms that we have in tarski. Enforcing such constraints would be an optional feature which is not enabled by default.

From the point of view of grounding as an auxiliary problem to automated planning, there are several possible ways to go about it. I will soon commit to devel a very straightforward mechanism for the naive module, but indeed, the end game would be to have these constraints (if possible) passed along to an efficient grounding algorithm.

Please share any comments or thoughts on this topic. Most welcome are suggestions on what kind of constraints folks think would be interesting to consider (beyond alldifferent etc.).

[JoanEspasa]

If I understand you correctly, the idea here is to be able to let a user specify additional constraints to a tarksi problem, with the objective to manually prune the space of possible grounded actions, right?

The elements where constraints can be applied upon are only the parameters of the actions, or are you thinking about something else?

[miquelramirez]

Hello Joan, 1. they would indeed be additional constraints, defined over the action schemas parameters (which are f.o. variable symbols) 2. they could be "blanket" constraints for instance to "project away" grounded actions involving domain objects the modeller knows are irrelevant to the optimal solutions of a given problem Salutacions des de Melbourne, Miquel

…

On Thu, 20 May 2021, 16:53 Joan Espasa, ***@***.***> wrote: If I understand you correctly, the idea here is to be able to let a user specify additional constraints to a tarksi problem, with the objective to manually prune the space of possible grounded actions, right? The elements where constraints can be applied upon are only the parameters of the actions, or are you thinking about something else? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#105 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AADMQKMFXKV7DZCX2NHMKMDTOSWYDANCNFSM45GDETJA> .

[miquelramirez]

the modeller knows

Or an NP Oracle, of course :)

…

On Thu, 20 May 2021, 17:02 Miquel Ramírez, ***@***.***> wrote: Hello Joan, 1. they would indeed be additional constraints, defined over the action schemas parameters (which are f.o. variable symbols) 2. they could be "blanket" constraints for instance to "project away" grounded actions involving domain objects the modeller knows are irrelevant to the optimal solutions of a given problem Salutacions des de Melbourne, Miquel On Thu, 20 May 2021, 16:53 Joan Espasa, ***@***.***> wrote: > If I understand you correctly, the idea here is to be able to let a user > specify additional constraints to a tarksi problem, with the objective to > manually prune the space of possible grounded actions, right? > > The elements where constraints can be applied upon are only the > parameters of the actions, or are you thinking about something else? > > — > You are receiving this because you authored the thread. > Reply to this email directly, view it on GitHub > <#105 (comment)>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AADMQKMFXKV7DZCX2NHMKMDTOSWYDANCNFSM45GDETJA> > . >

[haz]

Constraints over the valid states would be natural.

But do you mean to forbid actions that are naturally never executable, or allow for actions to be forbidden? Subtle difference...

[miquelramirez]

No, I can't agree with state constraints being "natural" because before the grounding there is no state transition model, and there are no states to be "constrained".

This would be a step beyond/generalisation of the : equality PDDL feature and the use of equality predicates in preconditions of actions.

They would be actions that would not even register, effectively being projected away.

[JoanEspasa]

In my limited experience, when I modelled PDDL I typically used the type system to try to approximate the parameters that are sensible for the actions. That lead at some point to things like (:types A B - A_or_B).

I guess it is something that can be more useful when you can be expressive (like with FSTRIPS) where you could plug in something like an equality graph (E-graph) from SMT solvers?

[miquelramirez]

In my limited experience, when I modelled PDDL I typically used the type system to try to approximate the parameters that are sensible for the actions. That lead at some point to things like (:types A B - A_or_B).

I guess it is something that can be more useful when you can be expressive (like with FSTRIPS) where you could plug in something like an equality graph (E-graph) from SMT solvers?

Using typing is essentially imposing domain constraints on the operator schema variables. I think there's not so much you can do with such constraints alone.

That type construct is interesting, Joan. Could you share the domain (or an analogue if the one you were working on is confidential?).

I didn't know about E-graphs @JoanEspasa, checking one of the papers from the yices guys.

[haz]

I can't agree with state constraints being "natural" because before the grounding there is no state transition model, and there are no states to be "constrained".

I guess "natural" is subjective, but I absolutely think it's fair game for the modeller to want to specify invariants about the allowable state space (again, separating entailed invariants that come from the actions, fluents, init, and goal -vs- the invariants that further filter things).

(forall ?b - block (not (on ?b ?b)): Sure, we typically do this with a precondition on the move operators, but what if there are two or three or a growing number of move operators? You can stop having to model it repeatedly and just model it once.

(forall ?b1 ?b2 - block (not (and (heavy ?b1) (not (heavy ?b2)) (on ?b1 ?b2)))): Don't put heavy blocks on other non-heavy blocks. Again, you could probably finesse this through the right action preconditions, but it's cleaner (yes, subjective, I suppose) at the domain level.

(forall ?rm - room (exists ?rb - robot (in ?rb ?rm))): Never leave a room unattended. Again, you could throw this into action theory, but I hope you start to see where the complexity starts bumping higher and higher, despite the state constraints being relatively simple.

And I know you know we know our way around an LTL spec -- this is the argument pulled to the limit. Yes, technically we can slam it down to automata and cross-product'ize our transition semantics, but the fact remains that specifying constraints over the states we'd like to see -- which can/should in turn influence the grounding -- seems very natural to me ;).

[JoanEspasa]

Although it is nothing fancy (the location type), I'm always happy to share @miquelramirez :)
domain + instances. The e-graph is what came to my mind when visualising when reading about the generalisation of the equality constraints.

Regarding state constraints, I've been always quite vocal on those. It is something natural to be expressed when you are modelling, of course. An example of how those are useful can be seen in Guillem's work with fs, which I enjoyed quite a bit. To keep everything nice and tidy, maybe we can open a new discussion about those @haz ?

[gfrances]

Quick consideration: there's a conceptual difference between constraints involving only action parameter "names", and more general constraints involving function and predicate names of the domain vocabulary. The former (which maybe are the ones Miquel had in mind?) can be resolved while grounding, and are "constraints about what groundings of a certain action schema are acceptable".
The latter are much more general and can encompass state constraints, etc.; they cannot be "dealt with" only at preprocessing (e.g. in a grounding statge).
Both have their usefulness, of course, but looks to me like separate discussions?

[gfrances]

Yes, including those in the theory would make sense, then allowing each planner to deal with them as it prefers. (One obvious possibility if you don't have the time of being smarter: compile them to action preconditions.). Another possibility: if you deem they are simple enough to fall in the "preprocessing" category in the post before: just use them for grounding. And so on.

Now, about the question of what to do with these constraints for the grounding. The ASP grounding strategy (borrowed from Malte's FD strategy) that we use at the moment is pretty powerful, and would allow us to incorporate a fair amount of interesting constraints into the logic program we build to get (an overapproximation of) the reachable ground actions. But whether we could easily incorporate arbitrary (s, s, s'), logical formulas, I'm more skeptical. Perhaps you had some idea in mind about how to do this, Chris? Definitely and interesting research direction to me.

[haz]

Ah, well I haven't thought deeply into the implication on the LP front. My perspective is from uambat -- a project I've never fully spun up yet to logically model action transition semantics with the purpose of converting between action theories.

Can totally understand that there may need to by syntactic restrictions on the "constraints" given for the grounding process. Is this characterized anywhere? Maybe in the original FD writeup on things?

[gfrances]

Interesting project, Christian - and great name! :-)

Well, one thing is that you don't really need to aim at dealing with all of this at grounding time. Even with the current reachability analysis, the set of ground actions you get is still only an overapproximation. But then of course you need to take into account the constraints during planning, which will likely be unavoidable as soon as these are not of the form that Miquel mentioned at the very beginning of the discussion (e.g. constraints defined only on the variable names representing the action parameters).
But no, I wouldn't expect to find this on Malte's FD JAIR/AIJ papers...

[haz]

Heh, thanks. It was originally envisioned while in Australia, so Wombat's were on my mind ;).

We still have the finicky distinction to make on invariant -vs- control. If you consider the stack(a, a) example, this is a pre-existing invariant if that action will never actually be executable (e.g., preconditions never allowing it in the reachable state space). It's control if it filters what would otherwise be grounded.

In other worlds, control will filter the resulting state space while invariants won't. Both have their place. Do we care to distinguish between the two?

[JoanEspasa]

IMO it feels like a BMC-style query. If you want to consider state constraints to limit the groundings, a way of doing that (similar to my ICAPS16 paper) is by using an oracle. You basically have to ask:

• Given an action and a state constraint, consider its parameters.
• There exists state where, after applying the action effects, turns the state constraint not true?

This would give you either:

• UNSAT, meaning that the action can never falsify the the state constraint and you cannot prune actions
• SAT and a model, giving you the parameters for which the action can falsify the state constraint

What I'm not sure how to deal with is to check if that state is reachable from the initial state. I assume that is still P-SPACE, and I'm not that knoweledgeable about how to do an overapproximation of that.

Would that make sense or am I far off?

Edit: woops, started writing before you guys continued the conversation :)