2

I recently had a look at automated planners and experimented a little bit with FastDownward. As I wanted to start a toy project, I created a PDDL model for the ordinary 3D Rubik's Cube (of course using a planner may not be the most efficient approach).

Although my model may not necessary be "totally correct" yet, so far it consists of 24 predicates, 12 actions for the respective moves (each with 8 typed parameters, 4 "edge subcubes" and 4 "corner subcubes"). For each of the movable subcubes I have a domain object whose position is basically determined by the respective predicate; overall, at first glance this seemed to me as a model of quite moderate size.

It was indeed not a very complex task to come up with this model and although it currently does not consider orientations of subcubes yet, I simply wanted to give it a try with an instance where only a single move (so application of one action) has to be conducted — I assumed that such a plangraph should level off quite soon, so basically after the first layer where a goal state can be reached.

However, as I started the planner, it soon run out of memory and started to page.

Previously, I only read something on PDDL and the respective sections of Russell & Norvig. I took a closer look at the planner itself and found that it transform the PDDL description into some intermediate description.

I tried to only execute the transformation and after cutting off a third of my Rubik's Cube it — at least — terminated. I investigated the transformed model file and found that the planner/solver actually instantiates (flattens) the actions with its parameters.

Since the Rubik's Cube has a quite unrestricted domain and each action has apparently 8 parameters (4 corners, 4 edges), this inherently results in a huge number of flattened actions. Even more, although I added precondition constraints to ensure distinctness of the parameters (so the very same subcube cannot be both edgecube $e_1$ and $e_2$), the flattened version still contains these invalid actions.

I have the following questions:

  • are state-of-the-art planners even suitable for such a problem or are they designed for problems where flattening the actions is of great advantage (e.g. few parameters, moderate number of objects per class, etc.). IMHO this would be a major limitation for their applicability in contrast to e.g. CP solvers.

  • can anyone recommend another planner that is more appropriate and that maybe does not perform the model transformation, which seems to be quite expensive for my PDDL spec (e.g. from this list, https://ipc2018-classical.bitbucket.io, i have chosen FastDownward since it seemed to be among the best...)

  • does PDDL or even FastDownward allow to specify that the parameters have to be distinct (i just found this: https://www.ida.liu.se/~TDDC17/info/labs/planning/writing.shtml — search for distinct — but this is more than vague), cause this may already lead to a significant reduction of flattened actions.

  • I'd also be happy for any other recommendations or remarks

Oliver Mason
  • 5,322
  • 12
  • 32
ttttttt1
  • 23
  • 2

1 Answers1

3

You have stumbled upon a common drawback of the vast majority of modern planning technology. The "flattening" you refer to is actually called "grounding" in the community. Indeed, grounding is the first step of almost every planner out there. Planners that don't do this grounding phase are typically referred to as "lifted planners", but their availability is far more limited (i.e., you'd likely need to reach out to an author of a paper to get access to their code).

That said, many of the planners, Fast Downward included, will try to be smart about the grounding phase. This includes simple things such as making sure that typing for the parameters (and the objects that instantiate them) is adhered to, but goes further with certain checks on reachability. The process isn't flawless, but it usually does a good job when the true number of ground actions is relatively small. If your model really does have an astronomical number of ground actions, then you're kind of out of luck here.

To your questions specifically:

  1. Yes, they are designed for problems where you can ground things. But the mark of suitability is the number of reachable ground actions. If this is small enough, then either
  • (1) the planners should be able to handle it or
  • (2) it presents a research opportunity for grounding things better.
  1. This is the most recent work that comes to mind, as well as the papers that cite it:

  1. They aren't assumed to be distinct. There are situations when you wouldn't want them to be, and so it is up to the designer to add the preconditions that ensure they are distinct (note that this is one excellent way to equip the grounder with extra information about what it should generate).

  2. Generally, having actions with many parameters is a recipe for problems that have too many ground actions. Either manually remodeling things yourself, or applying a technique like operator splitting is the approach most often taken.

Finally, if you'd like to have a more directed discussion, feel free to join us over on the slack channel. There may be more eyes on the questions you pose there.

Bilal
  • 105
  • 5
haz
  • 191
  • 2