Add policy checker?

[ssardina]

I think a core and superb tool to add here is a policy checker/validator. I know you did one for PRP @haz but if I remember it was not efficient or generalizable? Maybe I am mixing things up...

In any case, a FOND validator is of course much more challenging than one for classical planning, but a much needed one when one does work in FOND. One of the things needed to do this is to standardize a policy output I guess?

anyway, before I forget I wanted to open this issue to discuss this desired feature in this repo. Seems to me it is the repo to host this tool.

[haz]

Great point...it's still in the PRP/PR2 repos, and I think the methodology used there is still the best we've got.

The core issue? There's no standard for a solution representation.

• PR2/FONDSAT/Grendel: Controller where nodes are actions and edges are outcomes.
• PRP: Weird partial-state action policy.
• MyND/Paladinus/?: Mapping from complete state to action

Mathematically, a solution is a mapping from states to actions, but practically, using that representation limits you to the types of problems you can solve. So with no settled representation, it's hard to have any single validator. The one I created ran validation by (1) assuming a state-to-action interface was implemented; (2) running a complete reachable state-space simulation with this implementation. This means validation can't be done for larger problems were some techniques represent things compactly. But it nonetheless lets you validate smaller instances.

Any more effective validation would need to be representation-specific. For example, given a controller, run the repeated regression to confirm the initial state entails the regressed condition (sound but incomplete). Partial state representation? Not sure what I'd do to validate.

[ssardina]

I hear you and I (with Nitin) have met the same issues and challenges. The very first is that there is no "standard" plan/solution representation, agree. But we have also never thought this carefully and deep, we just left it for "later".

I think it would be OK that we, via this repo, establish a common "sensible" representation, if possible at all, and let anyone developing a planner make sure they are able to somehow produce such representation (from their native one if anything). The question is whether that sensible representation exists at all! 😕

Now, wrt PRP validator, if I remember the discussion I had with Nitin, the output of PRP is a set of partial state - action pairs, not full states, which makes total sense of course and was one of the whole points of PRP... But this meant that PRP would sometime output solutions where two rules may apply, that is, non-deterministic policies. Is this correct? If so, then we have a bit of a problem because we need to assume a fair executor too. That's OK, but that's one of the (many) things to think about I suppose.

[haz]

But this meant that PRP would sometime output solutions where two rules may apply, that is, non-deterministic policies. Is this correct?

Not quite. If you treated the policy like that, it may not even be sound -- for certain it may not complete. When it's listed out, it's just that -- a list -- not a set. You're meant to read it from top-to-bottom, and then return the action on the first partial state that matches where you are.

Extremely non-standard, but needed for compactness (there's still the odd domain on the fringe of FOND planner where this seems to be outperforming controller-based representations!).

The reason I went with "give me your representation and small implementation on how to read it", is because I /did/ have a unified (simple) way of validating implemented -- state space enumeration. Regardless of the solution representation type, you should be able to enumerate the state space reachable by it. If you want any more sophisticated validation process (e.g., using regression), then that puts restrictions on the FOND solution form you have, I reckon.

[sasharubin]

Hi ! I see from the code [1] that PR2 has a policy validator. What other FOND planners have validators?

[1] https://mulab.ai/project/pr2/

[haz]

Hey @sasharubin . I'm not aware of any -- as mentioned above, it's really hard to imagine what form a single validator may take, since there are so many solution types floating around. The one you see with PRP/PR2 was an attempt to abstract away that representation, and there is an example of how it would work with both PRP/PR2 style plans, as well as Grendel. Shouldn't be too hard to extend to other FOND planners as well.

Caveat is that it operates by enumerating the entire reachable state space of the policy, and so runs into scaling issues very quickly with some of the more modern + compact solution representations.

[haz]

Oh, I should add, I imagine most FOND planners have some sort of internal validation/checks going on. The external one with PRP/PR2 was meant to be a clean separate codebase so that bugs in the parser (for example) wouldn't creep into both plan generation and validation.

[ssardina]

Oh, I should add, I imagine most FOND planners have some sort of internal validation/checks going on. The external one with PRP/PR2 was meant to be a clean separate codebase so that bugs in the parser (for example) wouldn't creep into both plan generation and validation.

That's correct. For example our CFOND-ASP has a verifier module/tool, but won't work for other planners.

In fact, this discussion is exactly what triggered this issue in GH: can we get a general planner-independent validator (as there is one for classical planning)?