Required vs Suggested Landmarks

[Daniel Bryce]

Hi,

Has anyone had experience with forcing LAMA to satisfy landmarks (or particular disjuncts of a landmark)?  As far as I understand it, the landmark count heuristic "suggests" that the search satisfy landmarks, but there is no facility to prune plans that fail to satisfy a landmark. 

Thanks in advance!

Dan

[Malte Helmert]

Hi Dan,

all the landmarks that the planner generates natively are necessary in
the sense that there all solutions must reach all of them. So in that
sense plans that fail to satisfy a landmark are never generated. Are you
thinking of landmarks that have been added through some other facility?

Or are you thinking of some kind of facility that detects that a certain
landmark that hasn't been reached can no longer be reached in the future
and then prunes the state? I think there was/is something like that in
the landmark code (maybe you have to enable preferred operators to get
it), but I'm not sure. Silvia or Erez might know more about this. In any
case, if there is something like this in the planner, it's pruning power
is no higher than the following algorithm:

1) Compute all landmarks that still need to be achieved (like the LM
heuristics do anyway).

2) Check if all these landmarks are reachable in the delete relaxation.
If not, prune.

In other words, the pruning power of such an approach is no better than
using a delete relaxation heuristic on a problem where unreached
landmarks are treated as goals. You can probably get the same effect by
combining the compilation from the "When Abstractions Met Landmarks"
paper with any delete relaxation heuristic.

Or are you thinking of something else?

Cheers,
Malte

[Daniel Bryce]

Hi Malte,

Thanks for the response.  Yes, I'm thinking of something different.

I'm doing surgery on the landmark graph without changing the planning
problem.  This means that all of the original landmarks will be reachable
in the delete relaxation, and LAMA can choose to ignore the new landmark
graph.

I could arrive at the same altered landmark graph by changing the planning
problem, which would also effect the delete relaxation and give me what I
want.  Unfortunately, its much easier to modify the landmark graph than
the domain description (or at least I haven't fully thought through how to
change the domain to reliably get the landmarks that I want). 

Thanks,

Dan

[Malte Helmert]

On 04.01.2013 23:56, Daniel Bryce wrote:
> Hi Malte,
>
> Thanks for the response. Yes, I'm thinking of something different.
>
> I'm doing surgery on the landmark graph without changing the planning
> problem. This means that all of the original landmarks will be reachable
> in the delete relaxation, and LAMA can choose to ignore the new landmark
> graph.

OK, that much is clear now. And by "forcing LAMA to satisfy landmarks"
in your original message, you mean that you want to make sure that no
plan is reported as a solution that fails to achieve all the (new)
landmarks? Or is it something else or something more?

If that's what you want, and if you know that landmarks cannot be
achieved for free (e.g. because the problem has no 0-cost actions or
because action costs are ignored within the heuristic), the easiest
thing to do would be to modify the search code so that the goal test is
only performed on states with h=0. In such a setting h=0 should be
necessary and sufficient for "all landmarks have been reached". Some of
the search algorithms might already do this to save time on the goal test.

If h=0 is possible even for states with unreached landmarks, things get
more complicated, though.

Cheers,
Malte

[Daniel Bryce]

Hi Malte,

My main purpose is to remove landmark disjuncts to disallow certain plans.  Yes, I was thinking something similar about changing the goal test and this seems to be the easiest approach. 

Yet, I am concerned that this will cause some thrashing because the relaxation heuristic will continue push search to find plans that may not satisfy the landmarks.  The only solution to this that I can think of is to remove the operators that gave rise to the landmark disjuncts that I removed. However, I'm not sure if this is a sound strategy.

Thanks,

Dan

 

[Malte Helmert]

On 05.01.2013 17:51, Daniel Bryce wrote:

> Yet, I am concerned that this will cause some thrashing because the
> relaxation heuristic will continue push search to find plans that may
> not satisfy the landmarks.

Indeed it likely will.

> The only solution to this that I can think
> of is to remove the operators that gave rise to the landmark disjuncts
> that I removed. However, I'm not sure if this is a sound strategy.

Unless there are strong restrictions, it won't be.

In general, we (= in planning in general) don't have a good grasp on
control information of the kind "I'd like to avoid X, Y or Z". This is a
topic that Héctor Geffner has been talking about a lot in recent years;
he might be a good person to get in touch with if you want to take this
further. At this point, I would see this as a pretty open research problem.

Cheers,
Malte