Issue1009

Title Compute landmark costs in all landmark factories
Priority bug Status chatting
Superseder Nosy List clemens, jendrik, malte, remo, salome, silvan, thomas
Assigned To Keywords
Optional summary
This is part of meta issue987.

Created on 2021-02-11.13:26:16 by salome, last changed by clemens.

Summary
This is part of meta issue987.
Messages
msg10732 (view) Author: clemens Date: 2022-06-08.16:48:05
Remo and I started working on this today. We have so far removed the landmark cost attribute from the landmarks and compute the landmark costs in the setup of the heuristic as discussed in msg10723. The mentioned caveats remain open TODOs. Nevertheless, here's a link to a pull request draft for our code: https://github.com/aibasel/downward/pull/104. We do not require a code review yet, it's just so everybody can access our progress.
msg10728 (view) Author: malte Date: 2022-05-30.11:32:17
Sounds good. Having attributes that are only used in one setting of the heuristic but not another is a code smell, but it just contributes to an already existing divergence between the admissible and inadmissible case and therefore isn't an obstacle for this issue in my view. We can address this separately at a later point. 

Moving the cost into the heuristic is a step in the right direction.
msg10723 (view) Author: salome Date: 2022-05-25.12:04:12
In issue1025 (which is a duplicate of this issue) Thomas suggested to store the cost in the heuristic instead, which fits to option 3) from Malte here.

As far as we're aware lmcount is the only heuristic currently using this cost attribute, and it uses it only in the inadmissible setting. We thus suggest that lmcount should store two values for each landmark (and it should only store it in the inadmissible setting): 
1) the minimal cost over the *first* achievers, and 
2) the minimal cost over *all* achievers. 
These values can easily be computed for all factories by iterating over all/the first achievers of each landmark when initializing the heuristic.

Some caveats:
 - We are not sure yet whether all factories set the first/all achievers correctly (especially the hm factory). We will double check this.
 - As discussed in issue1011, we use empty achievers to signal that a landmark cannot be achieved. This is currently also the only way to detect dead-ends in lmcount. We could see if we can make the dead-end detection more elegant by using the stored cost (which would be infinity) instead.
msg10047 (view) Author: malte Date: 2021-02-11.21:38:06
I think option 3) is the clean one, don't store costs in the landmark nodes/landmark graph at all.

A landmark doesn't have a cost as part of its definition. The cost is a property that is externally associated with the landmark. Landmarks were used for a long time for things like goal ordering before people ever thought of associating costs with them; costs only became a thing when people started using landmarks for heuristics. I think it makes more semantic sense to handle the costs on the side of the heuristic.

It should also give us some nice efficiency gains because I think there are currently places inside the heuristic where we reach inside a landmark node only for the purpose of fetching its cost.
msg10031 (view) Author: salome Date: 2021-02-11.13:26:15
Each landmark node has a member cost (previously called min_cost), which is set differently depending on the factory: The lm_rhw factory sets cost to the minimum cost of all (first?) achievers, but all other factories just leave the cost at 1. We instead want that the landmark cost is set to the same value no matter which factory is used.

I see two ways to implement this:
1) Set the cost in the constructor of LandmarkNode. This is similar to the current behavior of lm_rhw, which sets the cost of each node right after creating it.
2) Let lmcount set the cost. This avoids computing costs for landmarks which are later discarded, but is not that nice from a design perspective since it changes the landmark graph after it has been created by the factory (something we were getting away from in issue988). We could also store the landmark cost in the heuristic instead, but this doesn't seem very clean to me either.

For either option we loose some synergy with lm_rhw since it uses the result of a previous computation, but this is unavoidable if we want to compute costs for other factories. But we might anyway need to rethink how to compute costs correctly and how to handle 0-cost actions.
History
Date User Action Args
2022-06-08 16:48:05clemenssetnosy: + remo
messages: + msg10732
2022-05-30 11:32:17maltesetmessages: + msg10728
2022-05-25 12:04:12salomesetmessages: + msg10723
2021-02-11 21:38:07maltesetmessages: + msg10047
2021-02-11 13:26:16salomecreate