AI-Planning / pddl

Unquestionable PDDL 3.1 parser
https://ai-planning.github.io/pddl/
MIT License
85 stars 27 forks source link

Non-deterministic string representations #107

Closed ssardina closed 8 months ago

ssardina commented 8 months ago

Subject of the issue

I get different strings of PDDL domains in different runs (see effects):

     (:action t_n0_n1
        :parameters ()
        :precondition (and (q_n0) (next_q_n1) (in crate0 depot0))
        :effect (and (not (q_n0)) (not (next_q_n1)) (q_n1) (oneof (goal_app) (next_q_n4) (next_q_n2)))
    )
   (:action t_n0_n1
        :parameters ()
        :precondition (and (q_n0) (next_q_n1) (in crate0 depot0))
        :effect (and (not (q_n0)) (not (next_q_n1)) (q_n1) (oneof (goal_app) (next_q_n2) (next_q_n4)))
    )

Your environment

Expected behaviour

I would claim that we should always produce the same string.

Actual behaviour

See above.

Possible fix/improvement

I am not an expert of the project but I think we could fix this issue by SORTING the operands:

https://github.com/ssardina-research/pddl/commit/7cf81b19fb4d8d5c0fee0e8a0fa94400c20bd59d

I post this as an issue and not a PR as I am not sure this is the best way of doing this and whether you agree the PDDL string rep should be unique.

francescofuggitti commented 8 months ago

Hi @ssardina !

Thanks for raising the issue. Given the small PDDL snippet you posted, I'm assuming you're generating the PDDL programmatically. Looking at pddl/logic/base.py code, the operands in a BinaryOp are always initialized as a list, which should actually preserve the order.

Given that, are you sure your input operands are always ordered in the same way when passed to the effect formula?

ssardina commented 8 months ago

@francescofuggitti , thanks for the prompt reply. Indeed, I was very suspicious and after some further investigation we were issuing different orderings to pddl and it seems the non-det came from Python list() function. All good and no need to change pddl.

Nonetheless, this brings the question if pddl should provide a "canonical" output representation of a PDDL that is not sensitive to the ordering that data structures are created? (e.g., alphabetical). I suspect this may be useful to have. :thinking:

francescofuggitti commented 8 months ago

Great to hear that you solved your issue, @ssardina!

Indeed, providing a canonical representation could be highly beneficial to the end users. On the other hand, there are cons to it, such as it will require changes over almost the entire code base or it will make the library less efficient.

We can use this issue to start talking about it and see whether we want to put it on our TODO list. @haz, @marcofavorito?

haz commented 8 months ago

It certainly is compelling...kind of gives a canonical representation of the PDDL objects we have. Can you comment on this statement?

...or it will make the library less efficient.

ssardina commented 8 months ago

It certainly is compelling...kind of gives a canonical representation of the PDDL objects we have. Can you comment on this statement?

...or it will make the library less efficient.

I am not following why it would be less efficient; but I am sure I must be missing something as you know pddl way better than me.

In principle, my proposal was related to the string output of a domain/problem. I was not thinking manipulating the underlying data structures, objects in a "canonical" manner, that could indeed impact efficiency. But it would be good to be able to get a canonical string representation of a domain; for example alphabetical (predicates, objects, actions, formulas).

francescofuggitti commented 7 months ago

Sorry for the late reply...I guess I was just wondering whether introducing all the sorted(...) calls could slow down the library when using the __str__ method. Sometimes it's preferable to have a canonical representation, sometimes not. One way to handle it at best would be to have a flag to produce the canonical repr. only if explicitly requested.

ssardina commented 7 months ago

You are right @francescofuggitti , we probably wouldn't do it in __str__. It is a bit messy to implement that flag, you would have to set it before using __str__ I guess?

What about if we just provide a specialized method that needs to be called explicitly, like domain_to_string but with an optional flag cannonical=False ?

francescofuggitti commented 7 months ago

What about if we just provide a specialized method that needs to be called explicitly, like domain_to_string but with an optional flag cannonical=False ?

Yes, that's exactly what I was thinking of.

ssardina commented 7 months ago

What about if we just provide a specialized method that needs to be called explicitly, like domain_to_string but with an optional flag cannonical=False ?

Yes, that's exactly what I was thinking of.

OK but that would not be via the __str__ method (see PR #109), that will stay as is and "fast". :+1: