KCL-Planning / VAL

The plan validation system.
BSD 3-Clause "New" or "Revised" License
107 stars 48 forks source link

TIM returns nothing #58

Open aymeric75 opened 1 year ago

aymeric75 commented 1 year ago

domainPlusproblem.zip

Hello,

When using:

./TIMdomain.pddl problem.pddl

it outputs absolutly nothing. Is there something wrong with the pddls ? (here attached).

Thanks a lot

Aymeroc

DerekLong101 commented 1 year ago

You have a domain without objects. That's fine, but TIM is concerned with properties that are invariants of the objects in the domain. No objects, no invariants. Now, it is certainly true that there are still invariants in there. One of the ways that we looked at developing TIM is with what we called "zero-analysis". This refers to the way that TIM performed its analysis by considering arguments of predicates at different positions - the first, the second and so on. The "zeroth" would be the predicate itself. There are situations in which it is helpful to suppose that there is an implicit object, "the Actor" or whatever, that is assumed to be present and never explicitly named in the model. In this case, the predicates can be considered to have an implicit reference to this actor and the invariants are the invariant properties of that actor. In an earlier implementation of TIM, this was present, but it is not present in the implementation in the VAL codebase.

There is a problem with your problem file: initial states are built with the closed world assumption, so negative facts are never placed in there. The absence of a fact is treated as the assertion of the negation. That will break the parser.

Also, TIM (again, in this implementation) doesn't handle negative preconditions.

Is your domain a real representation of something meaningful, or a randomly generated structure? 6000 actions that switch 50 predicates in different subsets in different directions seems like quite a specific shape, but the shape doesn't seem meaningful.

I just cut the negative conditions out of the initial state and ran a planner on it and got a plan - not sure if that is what you were hoping for.

;;;; Solution Found ; States evaluated: 469 ; Cost: 0.010 0.00000: (a812) 0.00100: (a3810plus9) 0.00200: (a1390) 0.00300: (a2087) 0.00400: (a3846) 0.00500: (a152) 0.00600: (a5974) 0.00700: (a3028) 0.00800: (a5982) 0.00900: (a3144) 0.01000: (a3727)


From: aymeric75 @.> Sent: 21 October 2022 10:56 To: KCL-Planning/VAL @.> Cc: Subscribed @.***> Subject: [KCL-Planning/VAL] TIM returns nothing (Issue #58)

domainPlusproblem.ziphttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2FKCL-Planning%2FVAL%2Ffiles%2F9837926%2FdomainPlusproblem.zip&data=05%7C01%7Cderek.long%40kcl.ac.uk%7Ca9dbb4ed0a4d46a7fd9e08dab34a845c%7C8370cf1416f34c16b83c724071654356%7C0%7C0%7C638019430597584007%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=F4%2FZPA7hfH5W6YJeu9RUx1sCilNGoqm7EiNNYldQiMc%3D&reserved=0

Hello,

When using:

./TIM domain.pddl problem.pddl

it outputs absolutly nothing. Is there something wrong with the pddls ? (here attached).

Thanks a lot

Aymeroc

— Reply to this email directly, view it on GitHubhttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2FKCL-Planning%2FVAL%2Fissues%2F58&data=05%7C01%7Cderek.long%40kcl.ac.uk%7Ca9dbb4ed0a4d46a7fd9e08dab34a845c%7C8370cf1416f34c16b83c724071654356%7C0%7C0%7C638019430597740244%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=E1wzHIYsnkJPnypUvJ8upBEU%2BFrH5KHQZvUzujnDW8w%3D&reserved=0, or unsubscribehttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FAB2KOVEMOM7AQ7GBK5EAQ53WEJSERANCNFSM6AAAAAARLAEEQI&data=05%7C01%7Cderek.long%40kcl.ac.uk%7Ca9dbb4ed0a4d46a7fd9e08dab34a845c%7C8370cf1416f34c16b83c724071654356%7C0%7C0%7C638019430597740244%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=mt1V%2BM8FKX6PRDzRLXWYMscW6R08UkdxIfnEdZBMbFs%3D&reserved=0. You are receiving this because you are subscribed to this thread.Message ID: @.***>

aymeric75 commented 1 year ago

Thanks a lot for this detailed answer.

Is your domain a real representation of something meaningful, or a randomly generated structure?

These PDDL was generated by Lat Plan ( repo here ). In short, it's a neural network that generates it.

There is a problem with your problem file: initial states are built with the closed world assumption, so negative facts are never placed in there.

In the problem file, the initial state is specified with a value of truth for all 50 variables, some of true, some are false, but I don't see how it can break the parser honestly...

DerekLong101 commented 1 year ago

It breaks the parser because the parser does not expect tokens of the form (not (...)) in the initial state and treats them as errors (the BNF does not allow them, so that is correct). The parser is not particularly well instrumented (in VAL/TIM) for error cases - it often simply crashes.

I don't think any of the invariant finders work on pure propositional variables, but I might be wrong. TIM in this implementation is probably not going to do what you want, because it doesn't output invariants in an obvious way.

No invariant finder will find all the invariants in the problems. This is because I could always modify a planning problem by adding a new proposition, dummy1, to the initial state and an action to the domain with precondition equal to the goal and effect (and (dummy2) (not dummy1)). Then, if (dummy1) is invariant, I know there is no plan, while if it is not invariant then I know there is a plan. So plan existence and plan-non-existence both become solvable using the invariant tester. Plan existence (for this language, anyway) is PSPACE-complete and plan-non-existence is not, in general, known to have any short certificates.

I don't believe that there is a signal in the domain structure that correlates with invariants in a way that could be learned by a neural network. And note that the invariants change depending on the initial state, so the signal would have to include that is input (eg the invariant that a block can only be on one surface at a time is an invariant in blocks world encodings only if it is true in the initial state​). Invariant finders are all versions of inductive proof generators - they identify an initial hypothesis that is true in the initial state and then "prove" by some means that the invariant condition hypothesised is maintained by all actions in the domain.


From: aymeric75 @.> Sent: 21 October 2022 12:59 To: KCL-Planning/VAL @.> Cc: Long, Derek @.>; Comment @.> Subject: Re: [KCL-Planning/VAL] TIM returns nothing (Issue #58)

Thanks a lot for this detailed answer.

These PDDL was generated by Lat Plan ( repo here https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fguicho271828%2Flatplan&data=05%7C01%7Cderek.long%40kcl.ac.uk%7C7c3fb446d45641f55ce208dab35bafd8%7C8370cf1416f34c16b83c724071654356%7C0%7C0%7C638019503612897535%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=XR5YJNDjblA4dipiDDtA9qEfHlumKkf4GdzIwZnG8BE%3D&reserved=0 ). In short, it's a neural network that generates it. My work is to use an automatic invariant finder, to take the invariants found and to test them by re-training and re-evaluating the network.

In the problem file, the initial state is specified with a value of truth for all 50 variables, some of true, some are false, but I don't see how it can break the parser honestly...

— Reply to this email directly, view it on GitHubhttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2FKCL-Planning%2FVAL%2Fissues%2F58%23issuecomment-1286863353&data=05%7C01%7Cderek.long%40kcl.ac.uk%7C7c3fb446d45641f55ce208dab35bafd8%7C8370cf1416f34c16b83c724071654356%7C0%7C0%7C638019503612897535%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=Ei1y5LvLQnbSz1%2B7O%2BXaTbJXBMyblNQHNJ4p56WdcrI%3D&reserved=0, or unsubscribehttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FAB2KOVE66ZTCHRI6VK3YYU3WEKARNANCNFSM6AAAAAARLAEEQI&data=05%7C01%7Cderek.long%40kcl.ac.uk%7C7c3fb446d45641f55ce208dab35bafd8%7C8370cf1416f34c16b83c724071654356%7C0%7C0%7C638019503612897535%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=WykWFfuAwP7ZnYGqWWXHbhBfI2zkV45n4gWgo6tHO50%3D&reserved=0. You are receiving this because you commented.Message ID: @.***>

maltehelmert commented 1 year ago

Regarding invariant finders that work on pure propositional variables, the h^2-based mutex analysis does that. Jussi Rintanen's invariant synthesis algorithm is equivalent. (Jussi also has a lifted algorithm, but it doesn't find more invariants, but rather exists for efficiency reasons.) But from other discussions I think Aymeric is already aware of this (specifically, Alvaro Torralba's implementation), so I'm just mentioning it here more for the benefit of others that might follow the discussion.

alfonsogerevini commented 1 year ago

Hello everyone! :-) Regarding invariant finders that work on pure propositional variables, Discoplan does support them.

Best, Alfonso

aymeric75 commented 1 year ago

Indeed, I found invariants with both h2 preprocessor (mutex for now) and Discoplan (equivalences for now)

aymeric75 commented 1 year ago

It breaks the parser because the parser does not expect tokens of the form (not (...)) in the initial state and treats them as errors (the BNF does not allow them, so that is correct). The parser is not particularly well instrumented (in VAL/TIM) for error cases - it often simply crashes. I don't think any of the invariant finders work on pure propositional variables, but I might be wrong. TIM in this implementation is probably not going to do what you want, because it doesn't output invariants in an obvious way.............

I will remove the not variables from the initial state and keep you updated. Thanks

aymeric75 commented 1 year ago

Hello, I removed the "not" variables from the initial state, still nothing, maybe as you said, no invariants can be found with TIM on this domain. problem.txt domain.txt

DerekLong101 commented 1 year ago

No, as I said, TIM only finds invariants for object properties - this domain has no objects. It is possible to implement 0-analysis, but it is not implemented in this version of TIM.


From: aymeric75 @.> Sent: 28 October 2022 12:43 To: KCL-Planning/VAL @.> Cc: Long, Derek @.>; Comment @.> Subject: Re: [KCL-Planning/VAL] TIM returns nothing (Issue #58)

Hello, I removed the "not" variables from the initial state, still nothing, maybe as you said, no invariants can be found with TIM on this domain. problem.txthttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2FKCL-Planning%2FVAL%2Ffiles%2F9888058%2Fproblem.txt&data=05%7C01%7Cderek.long%40kcl.ac.uk%7C90d755efde7e4f4a588b08dab8d99b2c%7C8370cf1416f34c16b83c724071654356%7C0%7C0%7C638025541988818202%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=ZjgvYVtQaZ8lQPW50oAg94uR6nmtbQMjTUfUrTJyDK4%3D&reserved=0 domain.txthttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2FKCL-Planning%2FVAL%2Ffiles%2F9888059%2Fdomain.txt&data=05%7C01%7Cderek.long%40kcl.ac.uk%7C90d755efde7e4f4a588b08dab8d99b2c%7C8370cf1416f34c16b83c724071654356%7C0%7C0%7C638025541988818202%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=jsdm5DruAfxHZJRO4HH8B26jMPH6u9mgeALdSeyAAiI%3D&reserved=0

— Reply to this email directly, view it on GitHubhttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2FKCL-Planning%2FVAL%2Fissues%2F58%23issuecomment-1294895348&data=05%7C01%7Cderek.long%40kcl.ac.uk%7C90d755efde7e4f4a588b08dab8d99b2c%7C8370cf1416f34c16b83c724071654356%7C0%7C0%7C638025541988818202%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=CJ%2B3c7E2%2BXeAqzYBqsdT2DuGeNYLd9Umxsj6rebFmTU%3D&reserved=0, or unsubscribehttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FAB2KOVDVRTZN5D3JUCNES23WFO35JANCNFSM6AAAAAARLAEEQI&data=05%7C01%7Cderek.long%40kcl.ac.uk%7C90d755efde7e4f4a588b08dab8d99b2c%7C8370cf1416f34c16b83c724071654356%7C0%7C0%7C638025541988818202%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=M4lF9AV2jJkqxDza%2BOgNm9DWBEwsGEzsFy%2BHqpku5t0%3D&reserved=0. You are receiving this because you commented.Message ID: @.***>

aymeric75 commented 1 year ago

ok thanks, but is there a version of TIM with this feature ? If yes, I could try

DerekLong101 commented 1 year ago

Hmm. I don't think that I can be sure of finding a copy - I will have a look. It was implemented to work with a type-free PDDL subset, so it got discarded a long time ago.


From: aymeric75 @.> Sent: 28 October 2022 12:58 To: KCL-Planning/VAL @.> Cc: Long, Derek @.>; Comment @.> Subject: Re: [KCL-Planning/VAL] TIM returns nothing (Issue #58)

ok thanks, but is there a version of TIM with this feature ? If yes, I could try

— Reply to this email directly, view it on GitHubhttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2FKCL-Planning%2FVAL%2Fissues%2F58%23issuecomment-1294908941&data=05%7C01%7Cderek.long%40kcl.ac.uk%7C078b0052107e46a694d708dab8dbadb8%7C8370cf1416f34c16b83c724071654356%7C0%7C0%7C638025550891626209%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=NkzCWAB92QS8WdpEbo5SwQz2Pf52DGt4EBbEfWOZHgQ%3D&reserved=0, or unsubscribehttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FAB2KOVFRKMAZB6XAK4T4PKLWFO5U5ANCNFSM6AAAAAARLAEEQI&data=05%7C01%7Cderek.long%40kcl.ac.uk%7C078b0052107e46a694d708dab8dbadb8%7C8370cf1416f34c16b83c724071654356%7C0%7C0%7C638025550891626209%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=xmlKJEeJrggjUj4czYIMCncp%2F%2BstN2V490dAxSyFyok%3D&reserved=0. You are receiving this because you commented.Message ID: @.***>

aymeric75 commented 1 year ago

Hello Derek,

Were you able to find the "0-analysis" version of TIM ?

Best regards