Issue1011

Title Determine unsolvability based on landmark graph
Priority feature Status resolved
Superseder Nosy List clemens, jendrik, malte, remo, salome, silvan, thomas
Assigned To Keywords
Optional summary
related issues:
- issue467
- issue937
- issue998
(- issue247: This is about wrongly detecting tasks unsolvable)

Created on 2021-02-18.12:51:10 by thomas, last changed by salome.

Summary
related issues:
- issue467
- issue937
- issue998
(- issue247: This is about wrongly detecting tasks unsolvable)
Messages
msg10731 (view) Author: salome Date: 2022-06-01.16:36:28
Great! :) Marking this as resolved now.
msg10727 (view) Author: malte Date: 2022-05-30.11:28:59
Correction: from issue987.
msg10726 (view) Author: malte Date: 2022-05-30.11:28:39
Yes, if all the points mentioned in the discussion are addressed, we should set this one to resolved. There is no reason to keep it open just to have a pointer to issue247, especially since we already have such a pointer from issue986.
msg10725 (view) Author: salome Date: 2022-05-25.12:08:09
Should we set this issue to resolved? The only related issue we didn't resolve yet is issue247, which is less about how to relay unsolvability information and more about how to correctly deal with derived variables / axioms.

The main point of this issue was addressed: All methods for detecting unsolvability with landmarks now relay this information through an empty list of achievers.
msg10482 (view) Author: malte Date: 2022-02-02.13:08:51
We discussed msg10478 further outside the tracker and decided on landmarks with no achievers (or, where appropriate, no first achievers) as the only mechanism to use in all cases. If we know that a landmark needs to be made true in the future (required for the first time or required again) and the relevant set of achievers (first or all) is empty, the heuristics will return "unsolvable".

Case a) was already related to achievers.

Case b) implies that none of the landmarks involved in the cycle of natural orderings can ever be achieved (including the observation that none of them can be true in the initial state), and hence they are all initially unachieved and have an empty set of first achievers.

In case c) the method does a relaxed reachability analysis to detect unsolvability. If this detects unsolvability, there must be an initially unachieved goal with no first achievers in the delete relaxation and hence also no first achievers in the actual task.


One question that came up in the discussion is how we define "first achievers" for landmarks true in the initial state. This is not so strongly related to this issue except that it's hard to evaluate if something is correct without really knowing the semantics, so it would be great to clarify this in code comments and/or leave a note for the future.

I think a clean solution that would also help us with other things is to do a similar normal form as in our theoretical discussion (and I think also implementation, but not sure) of LM-Cut that "compiles the initial state and goal away" by introducing an artificial initial state and artificial goal within the heuristic.
msg10479 (view) Author: malte Date: 2022-02-01.12:27:33
You mention the existing check that a landmark is required again and has no achievers, in which case we return an infinite heuristic value.

If done a bit more generically, couldn't this also cover a)? In both cases we have a landmark that needs to be achieved (either for the first time or again, doesn't matter) but has no suitable achiever (either first achievers or all achievers depending on context, again this doesn't matter).

We don't need to specially flag a task as unsolvable if the heuristic already "naturally" returns an infinite value for the initial state.
msg10478 (view) Author: salome Date: 2022-02-01.12:18:15
Clemens, Remo and me discussed this and related issues today. As far as we can tell there are three mechanisms for detecting unsolvability (two of which Thomas mentioned below already):
a) A landmark with no first achievers that is false in the initial state (issue467)
b) Cycle with natural (or stronger) orderings (issue937)
c) lm_zg returns an empty graph when the task is not relaxed solvable (issue998)

We discussed two possible approaches to deal with this:

1. Add a flag in the landmark graph denoting that the task is unsolvable. The heuristic can then first of all check this flag and return infinity if the flag is set to true. For b) and c) this is straightforward. For a) we need to have access to the initial state during the graph construction, but we assume this should already be the case (or at the very least should be easy to add).

2. Encode the information in the "cost" attribute of Landmark Nodes and ensure that heuristics deal with it properly. However, the code is inconsistent in how it uses the cost attribute: it is by default set to one, only set explicitly by lm_rpg_sasp and only used in the inadmissible lm-count heuristic.
 - For a) we at first thought this is straightforward (if it has no achievers, cost is infinite). But there is a difference between "no achievers" and "no first achievers": If for example a landmark has achievers but no first achievers and is true in the initial state, then setting the cost to infinity would be wrong. So I think the only way to encode a) in the cost is to again have access to the initial state and only set the cost to infinite if the node either has no achievers, or has no first achievers and is false in the initial state. Or have different cost attributes for first/all achievers...
 - For b) we could set the cost of all  landmarks that are part of the cycle to infinity. This somewhat abuses the cost semantics.
 - For c) ther are no nodes to begin with. But we could either force the heuristic to return an infinite estimate if no landmarks are present (although this in my opinion is not really the intended semantics of an empty graph), or we could instead of an empty graph return a graph containing the goal landmarks that are relaxed unreachable, and assign infinite cost to them.

I initially though option 2 would be more elegant, but there are many issues: unclear semantics of "cost" attribute (first or all achievers), it is only used in one factory and for inadmissible heuristics, plus the suggested way to encode b) and c) feels hacky. Option 1 is definitively easier and also more straightforward, with it's main downside being that we need to check an additional (static after graph construction) flag every time we compute the heuristic. But given that we currently loop over all landmarks in every state for checking if the (first) achievers are empty I assume that it will not make a big dent in performance, especially if stuff like branch prediction might trigger here (I have no idea if this is the case; if someone has more insight on these types of optimization we'd greatly appreciate the input).

One last remark about the per-state checks: While we can move the check on whether the set of first achievers is empty into the factory, we should still do a per-state check whether the set of (all) achievers is empty and the landmark is false and needed again. We could however consider to store a list of all landmarks with no achievers in the landmark graph, and instead of iterating over all landmarks, we check for needed-again landmarks if they are in this list. Or, if we decide to properly use the cost attribute we could also encode it in there.
msg10089 (view) Author: thomas Date: 2021-02-18.12:51:09
The structure of the landmark graph can reveal that a planning task is unsolvable, e.g. if:

1. there is a landmark with an empty set of first achievers that is not satisfied in the initial state;
2. there is a cycle in the landmark graph that consists only of natural orderings.

The first of these is currently checked in every state, and the second is not checked at all. In this issue, we'd like to 

i. enhance landmark factories with a method that determines if a planning task is unsolvable;
ii. make sure that method is used correctly; and
iii. move the per-state check described in 1. into the factories

Further enhancements in this direction that could be part of this issue or not include:
iv. premature termination of the landmark creation because one component already shows unsolvability
v. methods like 2. described above
History
Date User Action Args
2022-06-01 16:36:28salomesetstatus: chatting -> resolved
messages: + msg10731
2022-05-30 11:28:59maltesetmessages: + msg10727
2022-05-30 11:28:39maltesetmessages: + msg10726
2022-05-25 12:08:09salomesetmessages: + msg10725
2022-02-02 13:08:51maltesetmessages: + msg10482
2022-02-01 12:27:33maltesetmessages: + msg10479
2022-02-01 12:18:15salomesetnosy: + remo
messages: + msg10478
summary: related issues: - issue467 - issue937 - issue998 (- issue247: This is about wrongly detecting tasks unsolvable)
2021-02-18 12:51:10thomascreate