search

drexlerd / Loki

GNU General Public License v3.0
4 stars 2 forks source link

Detecting duplicate tasks #5

Closed jendrikseipp closed 9 months ago

jendrikseipp commented 9 months ago

I like the idea of using Loki for detecting duplicate planning tasks! Can you add a short guide to the README that shows how to do this?

Maybe this should be a separate discussion, but have you thought about canonicalizing PDDL files, i.e., sorting everything in them, to detect more duplicates? And possibly even canonicalizing all (object, action, etc.) names?

drexlerd commented 9 months ago

The API is not stable yet but this is already implemented and working! I will link to the examples in this issue once I have them. You would simply parse two problems and if the resulting pointer is equal, then both problems are structurally equivalent up to reordering.

jendrikseipp commented 9 months ago

Great, thanks!

drexlerd commented 9 months ago

There you go :)

https://github.com/drexlerd/Loki/blob/main/examples/multiple_problems.cpp

I also added two other examples.

jendrikseipp commented 9 months ago

Thanks! Shall we leave this issue open for the canonicalization, or do you consider this out of scope?

drexlerd commented 9 months ago

I explicitly avoided canonicalization to preserve the user defined structure and do a sort in the equality testing, which is only executed when inserting into the factory. The sorting does not use lexicographic but uses the unique identifiers which is more efficient.

drexlerd commented 9 months ago

What canonicalization do you have in mind? Is it lexicographically?

jendrikseipp commented 9 months ago

I think canonicalizing PDDL is actually beyond what Loki should be doing. Such things should probably be left to an implementation that computes the planning graphs for two problems and tests whether they're isomorphic.