Limitation on Number of Defined Types/Objects?

[David Paulius]

Greetings!

I am currently exploring PDDL and the use of FD for a planning problem using a directed graph representation, where a set of nodes are needed to "fire" actions or transitions that produce some new objects (much like a Petri net). I have been able to translate smaller versions of this graph to PDDL (around 90 defined types and objects) and I have been able to get results of the actions needed in a small problem space, but if I try to do path retrieval for a graph with >3K node types (and ~2K actions that uses small subsets of these objects to produce other objects), I always seem to get stuck at the "Parsing" phase and I cannot get to the search phase.

Now, I did not see if there was an explicit limit to the number of types or objects one can feature in a domain and/or problem. Is there such a limit, and if so, could it be bypassed so that I can get the search to work on a larger search space? The problem is that I currently have very precise definitions of objects, and thus I have many, many different types of them, which all need to be defined.

I could also provide some more elaborate examples if that would help. Thank you for your time!

[Florian Pommerening]

Dear David,

I'm not sure I completely understand your problem description but it
sounds like there is a combinatorial explosion during grounding. There
is no explicit limit on the number of types or objects but using too
many of them can lead to number of ground actions that is so high, that
it becomes problematic to even represent the problem. Have you computed
(on a theoretical level), how many possibilities there are to
instantiate an action? For example, if you have 2k action schemas, each
with 3 parameters and there are 20 possible choices for each parameter,
you'd get 2000 * 20^3 ground actions. A back-of-the-envelope computation
like this can probably give a hint whether the problem is still
realistically groundable.

If grounding is the problem but the actual search in the problem is
easy, a lifted planner might be an option. We are working on something
like this and could use additional benchmark domains. If you don't mind
sharing your domain, we could try running it in the lifted planner. If
that also doesn't help (for example, if both search and grounding are
difficult), then you might have to adapt the model.

Cheers
Florian

> --
> You received this message because you are subscribed to the Google
> Groups "Fast Downward" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to fast-downwar...@googlegroups.com
> <mailto:fast-downwar...@googlegroups.com>.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/fast-downward/91a2d342-23f3-4b22-8bb3-96026a9b7ee4n%40googlegroups.com
> <https://groups.google.com/d/msgid/fast-downward/91a2d342-23f3-4b22-8bb3-96026a9b7ee4n%40googlegroups.com?utm_medium=email&utm_source=footer>.

[David Paulius]

Greetings Florian,

Thank you for your reply. I think you have the gist of the problem. I have a large number of actions and object types and I could understand if there is an issue there. 

To give more explanation to my problem, I have been working on a representation coupling objects and actions for robot task planning (known as FOON). Here is a small example of such a network:

Here, you can think of there being 5 actions (reflected by red nodes), where each action is activated by incoming edges (i.e. the action is only executable when incoming edge nodes are available). However, in our case, these objects would be items that are needed for cooking (e.g. ingredients, such as pepper, eggs, etc., or tools, such as knife, spoon, etc.). In the current case, we have many, many of these actions, which we gathered from different recipes or cooking procedures. I was trying to investigate whether translating such a network to PDDL would work for finding a plan (i.e. a sequence of actions) that can reach to a goal. I have written my own code that operates on this structure, but I would like to take advantage of PDDL, since I have seen many works using it for similar robotics/AI problems.

Regarding your question about the grounding problem, yes, I would believe that the grounding part is the only difficulty. I have used smaller examples, and the search has worked. I believe the search itself is simple, as it merely requires searching for the subset of actions that need to be executed in sequence to arrive to a goal based on the current set of objects defined in the problem set. Could you tell me more about the lifted planner? And could you suggest any workarounds or solutions to this problem? I only thought of working on "chunks" of the graph, where each chunk is just a subset of the network that has the most relevance to the goal.

Thank you for your time and assistance!

David

[Florian Pommerening]

Hi David,

that sounds like an interesting domain. I still don't quite understand
where the combinatorial explosion comes from. In the example you sent,
it looks like there are 2 actions ("cut" and "pour") that both have a
single precondition and a single effect. This doesn't sound so bad, so
I'm probably missing something. Could you send a PDDL example of your
current encoding?

The lifted planner I was talking about avoids grounding before the
search and only grounds actions it wants to apply. This helps if the
search is very easy. You can hear Augusto's talk about it here:
https://www.youtube.com/watch?v=I7sqYCNOWcU

> I believe the search itself
> is simple, as it merely requires searching for the subset of actions
> that need to be executed in sequence to arrive to a goal based on the
> current set of objects defined in the problem set.

This applies to all planning problems, so the search could still be
difficult. As an example of what I mean with simple, the domain "organic
synthesis" that was used in the 2018 planning competition has a huge
number of actions once grounded (~10^13 actions if grounded naively) but
plans are super short (3 steps in one case), so the search is easy.


By the way, since this is getting a bit more general than just
concerning Fast Downward, you might reach a larger audience on
theplanningcommunity.slack.com

Cheers
Florian

On 30.11.20 12:48, David Paulius wrote:
> Greetings Florian,
>
> Thank you for your reply. I think you have the gist of the problem. I
> have a large number of actions and object types and I could understand
> if there is an issue there.
>
> To give more explanation to my problem, I have been working on a
> representation coupling objects and actions for robot task planning
> (known as FOON). Here is a small example of such a network:
>
>
>

> https://groups.google.com/d/msgid/fast-downward/4ea6723f-f4aa-47c7-813c-e51afa325c09n%40googlegroups.com
> <https://groups.google.com/d/msgid/fast-downward/4ea6723f-f4aa-47c7-813c-e51afa325c09n%40googlegroups.com?utm_medium=email&utm_source=footer>.

[Marcos Martín Pozo Delgado]

Hello David.

I have worked translating PDDL problems to Petri nets following the Hickmott et al. algorithm and I had similar problems in domains with many effects that do not appear in the preconditions, since the number of actions generated is exponential respect this number, generating thousands of actions in domains like agricola (and consuming high amounts of RAM). In the rest of domains the translation was successful.

You can check the code in https://github.com/Martin1887/downward/tree/petri.

Kind Regards,

Martín

[David Paulius]

Hi Florian,

Thank you for the response. I forgot to clarify that the graph I provided was just a simpler example of the network I am working with. Sorry for the misunderstanding. What I am currently working with is said domain and problem with >3K objects. I have these files in the following session: http://editor.planning.domains/#read_session=17IiQIzQC1. Just to explain a bit more: actions are referred to as functional units in the context of our representation, and they have inputs (preconditions) and outputs (effects). The planning is phrased as a problem of finding out how to make an object X using objects defined in the environment (init section of problem file).

From the knowledge side, I am trying to find out if there is a way that I could reduce the number of objects, as some of them could be simplified into archetypes (e.g. instead of separating types of cooking oil, I can represent it as just one label for the group of cooking oils), or I could try some other tricks to work on smaller portions of the network.

With regards to how simple the search is, I believe that the searching results can vary quite a bit, as it depends on how many objects are "available" for meal preparation. So if we have things in very basic states, then we will need to execute more actions to get them into their specific states. I think plans could be as long as

I will definitely take a look at the lifted grounding problem and I will see if I can incorporate some of those ideas. Thank you for the reference video. I sincerely appreciate your help with this matter, and I will look into the Planning Slack page for further assistance. I wanted to see if there was something inherent to FD or if it was just a general issue with what I am trying to achieve.

Thank you once again!

Sincerely,

David

[Malte Helmert]

On 01.12.20 13:50, David Paulius wrote:
> Hi Florian,
>
> Thank you for the response. I forgot to clarify that the graph I
> provided was just a simpler example of the network I am working with.
> Sorry for the misunderstanding. What I am currently working with is said
> domain and problem with >3K objects. I have these files in the following
> session: http://editor.planning.domains/#read_session=17IiQIzQC1. Just
> to explain a bit more: actions are referred to as functional units in
> the context of our representation, and they have inputs (preconditions)
> and outputs (effects). The planning is phrased as a problem of finding
> out how to make an object X using objects defined in the environment
> (init section of problem file).

Hi David,

I looked at the larger task. It looks like a lot of time is spent
computing the subtype relationship, for which a transitive closure of
the direct subtype relation is computed.

The task has more than 3000 types. I think we never thought of this
subtype computation as a potential major bottleneck and didn't use very
efficient algorithms. An O(N^3) algorithm can be prohibitive if N is in
the several thousands.

We can probably address this, but no guarantees that there won't be
further bottlenecks further down the processing pipeline. :-)

One thing you could do is use fewer types. It seems to me that all these
types don't actually have to be different types. For example, if you use
static unary predicates instead of types, this particular problem should
not arise.

Best,
Malte

[Sergio Tessaris]

Hi David,

if I'm not mistaken it seems that most of the types (if not all)  are actually representing single objects, and all subclasses of the single object_node class. There doesn't seem to be any transitivity closure going on here.

If this is the case, most of the actions seem to be already ground since there's at most one object that can be assigned to each variable. Why don't you just put the constants directly in the pre and post conditions? I know that the spirit of domain/problem separation wouldn't encourage that, but I'm pretty sure that FD would be happy to eat that.

Given the structure of your problem I'd also consider writing directly the SAS file.

Cheers,

--sergio

--
You received this message because you are subscribed to the Google Groups "Fast Downward" group.

To unsubscribe from this group and stop receiving emails from it, send an email to fast-downwar...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/fast-downward/77502371-66ce-bcde-e1e9-cafc42193afe%40unibas.ch.

[Malte Helmert]

Hi all,

yes, I had the same impression, and I think using :constants instead of
:types should help here.

On the other hand, I'm also happy for us to look at the performance
bottleneck and try to address it. We currently use Warshall's algorithm
for computing the transitive closure, which is O(N^3) both in the best
and worst case. This is reasonable for dense graphs, but poor for sparse
graphs like this one. So a localized change to this part of the
translator might be good enough to address this issue, but as always, I
cannot promise that we can get to it quickly.

Best regards,
Malte

> <mailto:fast-downward%2Bunsu...@googlegroups.com>.

> To view this discussion on the web visit
> https://groups.google.com/d/msgid/fast-downward/77502371-66ce-bcde-e1e9-cafc42193afe%40unibas.ch.
>

> --
> You received this message because you are subscribed to the Google
> Groups "Fast Downward" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to fast-downwar...@googlegroups.com

> <mailto:fast-downwar...@googlegroups.com>.

> To view this discussion on the web visit

> https://groups.google.com/d/msgid/fast-downward/CAByenVEZYMMr2xbBRjYTFzwL1EkG2hSM_7rDZNy6Q7tME1GAnA%40mail.gmail.com
> <https://groups.google.com/d/msgid/fast-downward/CAByenVEZYMMr2xbBRjYTFzwL1EkG2hSM_7rDZNy6Q7tME1GAnA%40mail.gmail.com?utm_medium=email&utm_source=footer>.

[David Paulius]

Greetings,

To Malte and Sergio -- 

Thank you all for the suggestions. I can see there are a lot of things I did not consider before, as I am just introducing myself to PDDL. My setup was just going off of tutorial examples of domain/problem files, and I did not see any examples of files that used constants or exclusion of types. :) I thought the right way was to define everything that could possibly be used as types in the domain file. 

I went ahead and defined everything as constants, and it finished parsing and it executed the search! It makes sense now, because as mentioned, each object should only have at most 1 instance, so there's no need to define all those types. I thank you once again for the idea. 

I appreciate the explanation about the bottleneck with Warshall's algorithm and its complexity. I think that this problem was really more of a issue with the definition of the domain/problem. Now that this initial version has worked, I will work on cleaning up the graph and creating more feasible and scalable graphs for my current problem.

To Martín  -- Thank you for the reference with regards to Petri net translation. I will give it a closer look to see if this would also help with my current problem.

Thank you all once again for your help, especially since this is not a FD issue. 

Stay safe and take care,

David