Precedence Constraints Contexts Heuristic

[Mikko Ettienne]

Hi,

I am writing my master's thesis on how to increase the efficiency and feasibility 

of automated planning through the specification of domain-dependent heuristic information.

Recently I have been looking at the context-enhanced additive heuristic 

and plan to investigate how much it can be improved by providing 

precedence constraints based on a non-automated "human" analysis of the domain.

The paper "Enhancing the Context-Enhanced Additive Heuristic with Precedence Constraints"

suggests that there is an implementation of an automated precedence constraint generator

and a precedence constraints contexts heuristic using it in FastDownard.

This would be a obvious place to start, but I haven't been able to locate the source code

in the public repo. Have I simply overlooked it or is possible to obtain the source code for

the pcc heuristic in some other way?

Cheers,

Mikko

[Malte Helmert]

[Moving the reply back to the group in case others are interested in
this -- Jörg, hope you don't mind.]

On 22.05.2012 16:28, Joerg Hoffmann wrote:
> Hi,
>
> the code was done by Dunbo Cai, and for all I know it hans't been
> integrated into the main FD repository. Malte will know exactly.

It's a discontinued branch in the old Subversion repository which we
used before we switched to Mercurial. Mikko, shall I give you access to
that SVN repository? It's in read-only mode and can be discontinued at
any time, but for now it's still available.

Be warned that this code branch is far behind the current code standard.
There are lots of old bugs that we have fixed in the meantime, action
costs are not supported there, etc. It would probably be better to
reimplement the feature in the new codebase rather than try to clean up
the old one.

> You research sounds interesting. I would say as a word of caution that
> our experiments -- refer to the section "Can we do better than this?" --
> don't suggest that different precedence constraints will result in
> fundamentally better heuristics. Although, of course, these are with
> randomly generated constraints, so it is possible that hand-made ones
> will work better. If they do, I'd be very interested to hear abhout it!

I agree with Jörg that it's not entirely clear how much further you can
push h^cea with manually specified precedence constraints, but I don't
want to put you off the idea, either. ;-)

Another possibility to make h^cea-style heuristics better is through
fluent merging (e.g.
http://ai.cs.unibas.ch/papers/seipp-helmert-icaps2011ws.pdf). With
domain-specific criteria on what to merge, I think there is some hope
that this can take you much further than what we managed in that paper.

Cheers,

Malte

[Mikko Berggren Ettienne]

Thanks for your prompt replies Jörg and Malte.

You might be right, that the possible improvements to h^cea by manually
ordering the precedence constraints is limited, as your paper suggests.
I just thought it would be relatively easy to test if most of the code was already there
and in case it gives better results, it seems like a simple way to specify domain-specific information.
I would like to check out the code, if its no hassle. At leas just for reference.

Another branch I am planning to investigate is how to relax the second assumption made in
the paper "Unifying the Causal Graph and Additive Heuristics".
Something along the lines of what you suggest in the discussion,
just manually choosing some core variables that should not loose their context value
when computing the estimates for preconditions.

I was also considering if the domain-specific info could be applied to
the lm-cut heuristic, maybe by providing some guidance on how to select landmarks,
but I haven't had time to look into this yet.

I will definitely also take a closer look at the Fluent Merging paper.
It seems like there is some potential and interestingly I am currently
working with a "Hospital Robots" domain that is very Sokoban like,
where your merging strategies seem to do good.

Initially I spent some time wondering if a more SAS+-like specification
would result in better performance. This is often a more natural way
to describe a domain and it would automatically disclose many multi-valued state variables.
However, my experiments showed that the translator part does a good job
discovering multi-valued state variables/mutex relations that are obvious.

I should also mention that I discovered some odd behaviour in the causal graph heuristic.
I found that using a quantifier rather than explicitly writing out a (grounded) goal formula,
leads to different heuristic estimates - even though it should be logically equivalent.
I know that quantifiers are handled by axioms,
and suspected that it might be because of the exclusion of non-parent variables
when solving suproblems starting from an axiom or maybe breaking
cycles in the causal graphs behaves differently on ties in the two cases.
I'm unsure whether this is intended or if it could be a bug.

Cheers,

Mikko

[Malte Helmert]

On 23.05.2012 12:54, Mikko Berggren Ettienne wrote:

> You might be right, that the possible improvements to h^cea by manually
> ordering the precedence constraints is limited, as your paper suggests.
> I just thought it would be relatively easy to test if most of the code
> was already there
> and in case it gives better results, it seems like a simple way to
> specify domain-specific information.
> I would like to check out the code, if its no hassle. At leas just for
> reference.

Another good way to tune the planner to specific domains could be to use
pattern database heuristics with a domain-specific pattern collection.
There are quite a few domains where PDBs, even with the automatically
generated pattern collections of ipdb, do very well. (Certainly if you
need optimal solutions -- we haven't tried out PDBs for satisficing
search yet.)

> Another branch I am planning to investigate is how to relax the second
> assumption made in
> the paper "Unifying the Causal Graph and Additive Heuristics".
> Something along the lines of what you suggest in the discussion,
> just manually choosing some core variables that should not loose their
> context value
> when computing the estimates for preconditions.

I think this is a very interesting idea in generally, as in a way it
provides an interesting bridge between delete relaxation and abstraction
heuristics, both of which are quite successful. But we don't have any
concrete plans in that direction yet. So many things to do, so little time.

> I will definitely also take a closer look at the Fluent Merging paper.
> It seems like there is some potential and interestingly I am currently
> working with a "Hospital Robots" domain that is very Sokoban like,
> where your merging strategies seem to do good.

Sounds very interesting -- we (not just the Fast Downward people, but a
more general we) are always curious about interesting new domains,
especially ones related to practical applications. If you can make
available this domain and a some example problems, I think many people
would be interested in it!

> I should also mention that I discovered some odd behaviour in the causal
> graph heuristic.
> I found that using a quantifier rather than explicitly writing out a
> (grounded) goal formula,
> leads to different heuristic estimates - even though it should be
> logically equivalent.
> I know that quantifiers are handled by axioms,
> and suspected that it might be because of the exclusion of non-parent
> variables
> when solving suproblems starting from an axiom or maybe breaking
> cycles in the causal graphs behaves differently on ties in the two cases.
> I'm unsure whether this is intended or if it could be a bug.

I faintly recall seeing something suspicious in the handling of axioms
in the CG heuristic, and they are definitely not handled well by the
delete relaxation heuristics at the moment. If you have a concrete
example that showcases this, it would be great it you could upload it at
http://issues.fast-downward.org/issue98. But be prepared that it can
take a long time for someone to look into this -- as you can see, the
last activity on that issue was about a year ago.

Cheers,

Malte

[Mikko Berggren Ettienne]

Hi, I will take a look at your paper as well,

I'm still in the beginning of my thesis work, 

so I'm very open to ideas and would of course

rather spend my time on areas where you think 

there is some hope for improvement than in areas

where you both indicate that there might not be hope:)

Cheers,

Mikko

On Wed, May 23, 2012 at 2:10 PM, Joerg Hoffmann <hoff...@cs.uni-saarland.de> wrote:

Hi,

just to note that you could also try to make domain-specific definitions of the set C in our ICAPS'12 paper "Semi-Relaxed Plan Heuristics". I for one would be quite interested to see whether, that way, you can get good results in domains that are currently not handled well. ... in some domains, the heuristic is dramatically better than hFF so this seems a promising line to look into.

cheers,
Joerg

[Mikko Ettienne]

Thanks for following up on my long post.

I will put PDBs on my list of things I should look into as well.

It's building up quickly already.

The "Hospital Robots" domain actually stems from a course I had at The Technical University of Denmark

and is not a "true" real world domain, even though it is motivated by the TUG hospital robots

and similar research project in Denmark.

It should not be a problem to make the domain and some example problems available if its still interesting.

Should I post it in a new thread or is there somewhere more suitable?

I have a very small concrete example of the CG heuristic problem

that I will upload to issue98, I might also try to look more into it.

Cheers, 

Mikko

[Carlos Linares Lopez]

Hi there,

In the page "Other contributions" of the last IPC (http://www.plg.inf.uc3m.es/ipc2011-deterministic/OtherContributions) we are maintaining a number of contributions from the research community. In case you want, I would not mind to post there the "Hospital Robots" domain so that other people could use it also for private experimentation. As a matter of fact, I would not mind even to run a competition with a selection of the entrants of the last competition on your domain.

Cheers,

--
Carlos Linares

[Mikko Ettienne]

Hi Carlos.

That sounds great - I will mail you the domain and some example problems later this week.

Cheers, Mikko

P.S.

I noticed that the "OtherContributions" link in the upper right wiki menu is not visible 

when I go to any of the other pages on http://www.plg.inf.uc3m.es/ipc2011-deterministic/.

[Mikko Ettienne]

Hi,

Carlos:

I have attached all the "full observability single agent" problems and the domain.

There is also a set of "multi-agent" and a set of "multi-agent partial observability" problems

which I have not considered. Let me know if you want them there as well.

If you have time for it at some point, it would be very nice to see how the entrants 

from the last competition do on this domain. Let me know if you need me to do anything.

Malte:

I have had very good results with the pdb heuristic for optimal planning in the

hospital robots domain and a few others. Manually selecting patterns based on a simple

domain analysis gives better results than using ipdbs, merge and shring and lm-cut.

I'm in the process of testing on more domains from the benchmark suite.

I have also looked at the fluent merging paper you suggested.

Is the implementation available?

It's a bit unclear to me how you can apply the "same object method" to the

sokoban domain. It seems like all state-variables will be associated 

with different objects in this domain and thus there will not be

any variables to merge by the "same object method".

Can you point me in the right direction.

Cheers, 

Mikko

[Jendrik Seipp]

Am 05.06.2012 17:08, schrieb Mikko Ettienne:
> I have also looked at the fluent merging paper you suggested.
> Is the implementation available?
> It's a bit unclear to me how you can apply the "same object method" to the
> sokoban domain. It seems like all state-variables will be associated
> with different objects in this domain and thus there will not be
> any variables to merge by the "same object method".
> Can you point me in the right direction.

Hi Mikko,
I will send you the relevant code bits in a separate mail. Concerning
the same-object-method: It is not guaranteed that it finds groups of
variables talking about the same object. If such groups cannot be found,
the method cannot be used.

Cheers,
Jendrik

[Carlos Linares Lopez]

Hi there Mikko,

I've been off the line for quite a bit but now I am back. I hope to upload your files before the week ends. Of course, if you have any other files that you think that might be interesting to the community, send them to me and I will happily upload them ---along with your name so that people know who to refer to in case they need additional information, if you agree.

We are currently re-arranging our cluster so that at this time I cannot run a competition with your files but be sure that I will do as soon as I have a chance!

- Carlos Linares

El 05/06/12 17:08, Mikko Ettienne escribió:

[Mikko Ettienne]

Hi Carlos.

I have attached a short description of the domain where theres also some background information of how it originated.

Fell free to edit or cut anything out if it's to long. I see you have already uploaded the domain and put my name there, great.

I'm looking forward to the results of your competition run.

Cheers,

Mikko

[Mikko Ettienne]

Hi Joerg.

I've read your paper on "Semi-Relaxed Plan Heuristics".

It gave me some interesting insights. The pi^C_ce compilation seems

to be related to the approach taken by Malte and Jendrik in "Fluent Merging for Classical Planning Problems"

which I am also currently looking into.

For startars, I would like to check whether the heuristic can be improved by making domain specific definitions of 

the C set as you suggested. Is it possible to check out your source code?

Cheers Mikko.

[emil keyder]

Hi Mikko,

The source code is still evolving, but I will make a usable version
and send you a .tgz. I think there is some connection between the
fluent merging approach and P^C(_ce) but I am still not exactly sure
what it is. For one, P^C is more fine grained in that it can represent
certain combinations of values while not taking the full Cartesian
product of two variables, but it's not clear what the implications of
that are (especially in the context of the delete relaxation).

Cheers,
Emil