Match Tree for Action Applicability

[haz]

Any reason this shouldn't be pulled into tarski? It is well-known how much death there can be with the naive approach. We have a reference implementation both in FD and lapkt (see here and here), but I'm not sure this flavour is exactly something that "fits" with the tarski aim (hence a discussion and not an issue).

If not, then a match-tree implementation built on tarski is entirely possible too.

Thoughts?

[gfrances]

No particular reason, a python implementation of the match tree would definitely be a welcome addition!

[haz]

Interesting...so let us discuss ;).

A matchtree would require very strips-like precondition representation -- you could generalize with more expressive decision nodes, but that might be a grander task better suited to Scott or a student (👋 @ssanner ). Do you think there's merit in a strips-like match-tree for tarski? Or only the full-on expressive one that would handle the full breadth of tarski preconditions?

[gfrances]

No, I definitely think that something targeting STRIPS representations would be enough.
One thing to keep in mind though is that without going through a multivalued representation à la SAS+, the match tree will be way less compact and efficient than for instance the Fast Downward one. Actually if I remember correctly from some old conversarion with @maltehelmert (but I might be distorting his words...), the use of the match tree directly on a propositional representation was not that interesting, performance-wise. But of course that will depend pretty much on the benchmark at hand.
Porting the fast downward component that generates that multivalued representation (which is already in Python), then building the match tree based on that, could also be an interesting option.

[maltehelmert]

Hi Guillem and Christian, I don't remember such a discussion, but as we say in Germany, "I say many things when the day is long". The good news about the match tree representation is that it will never be asymptotically worse than a naive algorithm in runtime or memory. The question is how beneficial it is without the "switch-style" branching that the finite-domain representation enables. I wonder whether, for example, an algorithm based on marking or on watched-literal-style techniques wouldn't be preferable for a STRIPS representation. But answering this probably needs experimentation.

[haz]

Aye, I've some limited experience toying with this. Compared to the naive approach, it certainly helps a boat-load. As long as you're using a decent (dynamic) splitting procedure, it does fairly decent.

Watch-literal style might improve things, but my hunch is that it'd probably be domain-specific.

[gfrances]

The magic of Github, you write Malte's name and the real Malte appears, a true conjuration :-)

[gfrances]

The magic of Github, you write Malte's name and the real Malte appears, a true conjuration :-)

[haz]

Ok, so if you're in on a STRIPS-like action applicability, how would that be reflected in the tarski structure? Do we have that thin STRIPS shell over the fully expressive tarski data-structures (ala this discussion) for action preconds/effects? If you lay out the general process, I can get started on a PR...

[gfrances]

At the moment, the way to tell tell whether a problem is STRIPS like is by checking each of the requirements, i.e. going through all action preconditions + goal formula and checking they are conjunctions of atoms; going through the effects and checking they are add or delete effects, etc. This is implemented in tarski.fstrips.representation.is_strips_problem.

I've often thought on creating a particular Python subclass of Problem to represent STRIPS problems, but so far I don't think we have enough use cases to justify that - This would certainly be one important subcase though.

[haz]

Started work on this in #118 . Appears as though the tarski data structures are too slow to make the improvement meaningful (takes ages just to build the match tree). Will revise to convert everything to numbers for the match tree handling.