Title variable ordering in preprocessor differs from description in Fast Downward paper
Priority bug Status chatting
Superseder Nosy List malte, mikko
Assigned To malte Keywords
Optional summary

Created on 2012-06-05.14:18:25 by mikko, last changed by mikko.

File name Uploaded Type Edit Remove
hr-domain.pddl mikko, 2012-06-05.14:18:24 application/octet-stream
hr-problem1.pddl mikko, 2012-06-05.14:18:51 application/octet-stream
hr-problem2.pddl mikko, 2012-06-05.14:19:12 application/octet-stream
msg2269 (view) Author: mikko Date: 2012-06-18.10:32:56
Your welcome, let me know if I can do anything else to help.

I agree that it is sensible to not have non-goal variables at the highest level.
In fact, it does not make much sense to have non-goal leaf variables in the CG at 
all, and whenver possible, this should be avoided when pruning the CG.
msg2268 (view) Author: malte Date: 2012-06-18.10:07:33
Thanks, Mikko! I'm surprised to see that the special case for the goals is not
mentioned in the paper -- it is intentional, although maybe it goes too far.

The main reason why we have the special rule is that it never makes sense (in
the CG heuristic) to have a non-goal variable as the highest-level variable,
since all variables that occur after the last goal variable have no influence on
the heuristic value. But of course that doesn't mean that *all* goal variable
ought to occur right at the end.

I'll look into it, but it requires a lot of testing to make sure that
performance is not adversely affected in some configurations.
msg2267 (view) Author: mikko Date: 2012-06-18.09:13:15
Comparing to the description in the Fast Downward paper, 
the procedure does not work as advertised (at least not as I understand it).

I see how different formulations can influence the weight of arcs, 
but this is not directly related to the issue.
The attached problems have the exact same causal graphs (and arc weights)
except that the one with the quantified goal has an arc from one state-variable
to an axiom and from that axiom to another axiom. 
Thus the ordering should be identical up to ties in cumulated weights,
but it is not.

The reason for this is that goals are hardcoded to be the highest level
(see the code pasted in below). 

Example: Say we have a planning task with state-variables A and B and a goal 
defined for A. Furthermore A and B are strongly connected in the causal graph 
with B having higher cumulated weight than A.
According to the FastDownward paper B should then be the sink variable,
and as the goal is defined for A, B should be removed from the task.
However, what actually happens is that A becomes the sink variable with
B as an ancestor because this is "hardcoded" into the translator.
Yet, if we put a quantifier in the pddl goal description,
it is the axiom that gets to be the "hardcoded" sink variable.
Thus B is a predecessor of A and is thus removed from the task.

### from ###
if (goal_map.find(target) != goal_map.end()) {
     //TODO: soll das so bleiben? (Zahl taucht in max_dag auf)
     // target is goal
     subgraph_edges.push_back(make_pair(new_index, 100000 + cost));
msg2265 (view) Author: malte Date: 2012-06-16.23:57:58
If I understand the issue correctly, the problem is that the causal graph
ordering procedure gives logically different results for the two problem

As long as the procedure works as advertised (i.e. as described in the Fast
Downward paper) in all cases, I wouldn't classify this as a bug or as something
that ought to be changed. In general it cannot be avoided that heuristic
decisions are influenced by innocuous changes in the problem formulation.

For example, if you duplicate certain operators by introducting
identically-behaving operators with different names, this will change the weight
assigned to the induced arcs in the causal graph and hence affect the causal
graph sorting criterion. Similarly, breaking one logical operator with many
parameters into two parts with fewer parameters can dramatically reduce the
weight of a variable in the causal graph sorting.

For what it's worth, our handling of axioms is generally quite poor at the
moment, and if there's a way to avoid them, it's usually a good idea. (See issue98.)

I'll mark this as resolved, but if I'm misunderstanding something about the
nature of the issue, feel free to reopen.
msg2251 (view) Author: mikko Date: 2012-06-05.14:18:24
Attachments: problem1 and problem2 are logically equivalent. 
The only difference is that the goal is given as a ground atom
in problem1 and as a quantification in problem2. 
The causal graph heuristic gives different initial h values
for the two problems.

It seems like goals are hardcoded to be high(est)-level
in CausalGraph::calculate_topological_pseudo_sort 
( in preprocessor) when the causal graph is pruned.
This makes sense, but I think it should also be propagated 
to goal axiom's predecessors to be consistent over different
problem formulations.
This might influence other heuristics using the pruned CG as well.
Date User Action Args
2012-06-18 10:32:56mikkosetmessages: + msg2269
2012-06-18 10:07:34maltesetmessages: + msg2268
title: Bug in preprocessor pseudo sorting -> variable ordering in preprocessor differs from description in Fast Downward paper
2012-06-18 09:13:15mikkosetstatus: resolved -> chatting
messages: + msg2267
2012-06-16 23:57:58maltesetstatus: unread -> resolved
assignedto: malte
messages: + msg2265
2012-06-06 14:49:08maltesetnosy: + malte
2012-06-05 14:19:12mikkosetfiles: + hr-problem2.pddl
2012-06-05 14:18:51mikkosetfiles: + hr-problem1.pddl
2012-06-05 14:18:25mikkocreate