Issue207

Title revise search code
Priority meta Status chatting
Superseder Nosy List erez, florian, gabi, jendrik, malte, manuel, mkatz, salome
Assigned To Keywords 1.0
Optional summary
~~1. issue77: get rid of pathmax.~~

~~2. issue108: Heuristic values should be stored in the heuristic itself.~~

~~3. issue77: open list should not inherit from evaluator.~~

4. Make Evaluator and Heuristic into one class: issue716 and issue718.

5. support path dependence similar to multi-path dependence (especially
with path-dependent dead ends).

6. issue311: implement eager WA*.

7. issue505: More Aliases in driver instead of overfilling search class with
compositions: eg astar(lmcut)
-->eager(tiebreaking(sum_eval(g_eval,lmcut),lmcut))

8. Make sure that after dealing with the other points, issue182, issue339,
issue368 and msg2533 are addressed, and close the respective issues.

9. issue198: issues with multiple heuristics. In particular, all special-casing
of heuristics[0] in eager search should disappear.

10. issue407: g-bound should also work in corner cases.

11. issue407: initial nodes should go through the same tests as other nodes
when/before
being added to the open lists (e.g check for an infinite heuristic estimate).

12. Test that regular max and sum evaluators now always work as intended and
ensure they can be used on the top level. ~~Then get rid of 
ipc_max_heuristic.~~

13. Review and possibly improve the handling of search progress and search
statistics.

Created on 2011-01-16.18:42:34 by malte, last changed by manuel.

Summary
1. issue77: get rid of pathmax.

2. issue108: Heuristic values should be stored in the heuristic itself.

3. issue77: open list should not inherit from evaluator.

4. Make Evaluator and Heuristic into one class: issue716 and issue718.

5. support path dependence similar to multi-path dependence (especially
with path-dependent dead ends).

6. issue311: implement eager WA*.

7. issue505: More Aliases in driver instead of overfilling search class with
compositions: eg astar(lmcut)
-->eager(tiebreaking(sum_eval(g_eval,lmcut),lmcut))

8. Make sure that after dealing with the other points, issue182, issue339,
issue368 and msg2533 are addressed, and close the respective issues.

9. issue198: issues with multiple heuristics. In particular, all special-casing
of heuristics[0] in eager search should disappear.

10. issue407: g-bound should also work in corner cases.

11. issue407: initial nodes should go through the same tests as other nodes
when/before
being added to the open lists (e.g check for an infinite heuristic estimate).

12. Test that regular max and sum evaluators now always work as intended and
ensure they can be used on the top level. Then get rid of 
ipc_max_heuristic.

13. Review and possibly improve the handling of search progress and search
statistics.
Messages
msg5072 (view) Author: malte Date: 2016-01-09.19:06:48
> Since we now have a summary field, I tried to move and merge the summaries from
> the discussion there. I'm not quite sure which of the points are still up to date.

Regarding point 4: the last bit that isn't done there is merging Evaluator and
Heuristic.

Regarding points 12 and 13, the underlying bugs should have been resolved with
the evaluation context changes and the heuristic caching change, but there is
still more cleanup work to do, and these points do need some more thorough
investigation to see that everything is indeed done noe.

I've updated the summary on those points.
msg5068 (view) Author: florian Date: 2016-01-09.12:58:07
Since we now have a summary field, I tried to move and merge the summaries from
the discussion there. I'm not quite sure which of the points are still up to date.
msg4948 (view) Author: malte Date: 2015-12-10.17:09:35
Sounds good.
msg4945 (view) Author: gabi Date: 2015-12-10.15:09:46
In issue407 we discussed that the g-bound should also work in corner cases and
that initial nodes should go through the same tests as other nodes when/before
being added to the open lists (e.g check for an infinite heuristic estimate).
Maybe we can address this as part of this meta issue.
msg4043 (view) Author: malte Date: 2015-03-09.13:38:27
Points 1., 3. and 4. are addressed in the work in progress for issue77. (The
evaluator class hierarchy can be simplified further, but I think this will be
done as part of that issue, too.)
msg3963 (view) Author: jendrik Date: 2014-12-17.21:14:11
I created issue505 for point 7.
msg3948 (view) Author: erez Date: 2014-12-16.01:24:54
Let me know if I can help somehow.
msg3926 (view) Author: malte Date: 2014-12-13.18:13:40
I don't want to lose the references to old related issues, so let's add another
point (maybe later to be split into multiple points, but I hope some of these
will be resolved automatically after addressing 1.-7.):

8. Make sure that after dealing with the other points, issue182, issue339,
issue368 and msg2533 are addressed, and close the respective issues. I think
this covers all comments on this issue before 2014.
msg3924 (view) Author: salome Date: 2014-12-13.14:04:55
Changing this to a meta issue with the following list of issues:

1. get rid of pathmax.

2. Heuristic values should be stored in the heuristic itself (see issue108)

3. open list should not inherit from evaluator

4. Simplify evaluator class hierarchy

5. support path dependence similar to multi-path dependence

6. implement eager WA* (see issue311)

7. More Aliases in driver instead of overfilling search class with
compositions: eg astar(lmcut)
-->eager(tiebreaking(sum_eval(g_eval,lmcut),lmcut))
msg3423 (view) Author: gabi Date: 2014-09-17.13:54:26
We should have a closer look on multi-path dependence in general, especially
with path-dependent dead ends.
msg3421 (view) Author: malte Date: 2014-09-17.13:49:38
When fixing this one, we might want to look at issue468, too.
msg2533 (view) Author: gabi Date: 2013-07-01.12:03:48
In issue230 it was confusing that with lazy search the "best heuristic value"
output is not done for the goal state (which gives the impression that the
heuristic does not go down to 0 for goal states). This should be changed in the
revised code.
msg2507 (view) Author: gabi Date: 2013-06-25.14:51:09
See also issue182.
msg2372 (view) Author: mkatz Date: 2012-10-26.15:22:55
See also issue368.
msg2249 (view) Author: malte Date: 2012-06-01.11:34:26
See also issue339.
msg1192 (view) Author: malte Date: 2011-01-17.13:17:31
We've already had several releases like that in the past, e.g. the 2004 IPC
version, or the JAIR paper version. But giving it a label like 1.0 indicates
some degree of "ready-to-use"  that it doesn't have due to a few major bugs and
other issues. For comparison, Silvia was always emphatic that people should
*not* use the IPC version of LAMA for experiments due to its bugs. Calling it
LAMA 1.0 would have sent a wrong message there.
msg1191 (view) Author: erez Date: 2011-01-17.13:11:27
My point is that the IPC version is, for all intents and purposes, a release.
We might not call it 1.0, but it will be the reference version until we release a 
proper version, so we may as well call it 1.0.
However, I don't really mind what we call which release - as long as it works :-)
msg1190 (view) Author: gabi Date: 2011-01-17.12:59:49
Since we have code in the IPC version that is already marked to be replaced by a
proper implementation when we have time after the IPC, I vote for the IPC
version not being release 1.0.
msg1189 (view) Author: malte Date: 2011-01-16.23:19:24
Hmm, I think the IPC version has too many warts to call it 1.0.
But we can discuss this properly after the deadline.
msg1187 (view) Author: erez Date: 2011-01-16.23:15:51
I agree we should take care of this, and soon.
However, I think version 1.0 should be the IPC version, and this should be in 
version 1.1 or 2.0 or whatever.
msg1182 (view) Author: malte Date: 2011-01-16.18:42:34
I'm classifying this as a bug since there are several things that are wrong here
and only mostly work due to special cases, good luck, or limiting ourselves to
certain configurations.

The search code should be reviewed and revised, and the role of evaluators vs.
heuristics vs. search spaces in storing state information such as h values
reconsidered. The search progress statistics are a bit fragile, too; see e.g.
the comment in Heuristic::get_heuristic() in the latest code.

All special-casing of heuristics[0] in eager search should disappear, and there
currently is some confusion about heuristics vs. evaluators that keeps us from
correctly implementing max and sum evaluators (see issue198, which itself has
further references).

I know we shouldn't keep deferring our 1.0 release, but I think this one is
severe enough to be nominated for 1.0. For example, I'd really like to properly
support max and sum for 1.0. Thoughts?
History
Date User Action Args
2017-04-25 14:33:46manuelsetsummary: ~~1. issue77: get rid of pathmax.~~ ~~2. issue108: Heuristic values should be stored in the heuristic itself.~~ ~~3. issue77: open list should not inherit from evaluator.~~ 4. Make Evaluator and Heuristic into one class. 5. support path dependence similar to multi-path dependence (especially with path-dependent dead ends). 6. issue311: implement eager WA*. 7. issue505: More Aliases in driver instead of overfilling search class with compositions: eg astar(lmcut) -->eager(tiebreaking(sum_eval(g_eval,lmcut),lmcut)) 8. Make sure that after dealing with the other points, issue182, issue339, issue368 and msg2533 are addressed, and close the respective issues. 9. issue198: issues with multiple heuristics. In particular, all special-casing of heuristics[0] in eager search should disappear. 10. issue407: g-bound should also work in corner cases. 11. issue407: initial nodes should go through the same tests as other nodes when/before being added to the open lists (e.g check for an infinite heuristic estimate). 12. Test that regular max and sum evaluators now always work as intended and ensure they can be used on the top level. ~~Then get rid of ipc_max_heuristic.~~ 13. Review and possibly improve the handling of search progress and search statistics. -> ~~1. issue77: get rid of pathmax.~~ ~~2. issue108: Heuristic values should be stored in the heuristic itself.~~ ~~3. issue77: open list should not inherit from evaluator.~~ 4. Make Evaluator and Heuristic into one class: issue716 and issue718. 5. support path dependence similar to multi-path dependence (especially with path-dependent dead ends). 6. issue311: implement eager WA*. 7. issue505: More Aliases in driver instead of overfilling search class with compositions: eg astar(lmcut) -->eager(tiebreaking(sum_eval(g_eval,lmcut),lmcut)) 8. Make sure that after dealing with the other points, issue182, issue339, issue368 and msg2533 are addressed, and close the respective issues. 9. issue198: issues with multiple heuristics. In particular, all special-casing of heuristics[0] in eager search should disappear. 10. issue407: g-bound should also work in corner cases. 11. issue407: initial nodes should go through the same tests as other nodes when/before being added to the open lists (e.g check for an infinite heuristic estimate). 12. Test that regular max and sum evaluators now always work as intended and ensure they can be used on the top level. ~~Then get rid of ipc_max_heuristic.~~ 13. Review and possibly improve the handling of search progress and search statistics.
2016-07-12 01:00:27jendriksetsummary: ~~1. issue77: get rid of pathmax.~~ ~~2. issue108: Heuristic values should be stored in the heuristic itself.~~ ~~3. issue77: open list should not inherit from evaluator.~~ 4. Make Evaluator and Heuristic into one class. 5. support path dependence similar to multi-path dependence (especially with path-dependent dead ends). 6. issue311: implement eager WA*. 7. issue505: More Aliases in driver instead of overfilling search class with compositions: eg astar(lmcut) -->eager(tiebreaking(sum_eval(g_eval,lmcut),lmcut)) 8. Make sure that after dealing with the other points, issue182, issue339, issue368 and msg2533 are addressed, and close the respective issues. 9. issue198: issues with multiple heuristics. In particular, all special-casing of heuristics[0] in eager search should disappear. 10. issue407: g-bound should also work in corner cases. 11. issue407: initial nodes should go through the same tests as other nodes when/before being added to the open lists (e.g check for an infinite heuristic estimate). 12. Test that regular max and sum evaluators now always work as intended and ensure they can be used on the top level. Then get rid of ipc_max_heuristic. 13. Review and possibly improve the handling of search progress and search statistics. -> ~~1. issue77: get rid of pathmax.~~ ~~2. issue108: Heuristic values should be stored in the heuristic itself.~~ ~~3. issue77: open list should not inherit from evaluator.~~ 4. Make Evaluator and Heuristic into one class. 5. support path dependence similar to multi-path dependence (especially with path-dependent dead ends). 6. issue311: implement eager WA*. 7. issue505: More Aliases in driver instead of overfilling search class with compositions: eg astar(lmcut) -->eager(tiebreaking(sum_eval(g_eval,lmcut),lmcut)) 8. Make sure that after dealing with the other points, issue182, issue339, issue368 and msg2533 are addressed, and close the respective issues. 9. issue198: issues with multiple heuristics. In particular, all special-casing of heuristics[0] in eager search should disappear. 10. issue407: g-bound should also work in corner cases. 11. issue407: initial nodes should go through the same tests as other nodes when/before being added to the open lists (e.g check for an infinite heuristic estimate). 12. Test that regular max and sum evaluators now always work as intended and ensure they can be used on the top level. ~~Then get rid of ipc_max_heuristic.~~ 13. Review and possibly improve the handling of search progress and search statistics.
2016-01-09 19:06:48maltesetmessages: + msg5072
summary: ~~1. issue77: get rid of pathmax.~~ ~~2. issue108: Heuristic values should be stored in the heuristic itself.~~ ~~3. issue77: open list should not inherit from evaluator.~~ 4. Simplify evaluator class hierarchy. (See msg4043. Is this still current?) 5. support path dependence similar to multi-path dependence (especially with path-dependent dead ends). 6. issue311: implement eager WA*. 7. issue505: More Aliases in driver instead of overfilling search class with compositions: eg astar(lmcut) -->eager(tiebreaking(sum_eval(g_eval,lmcut),lmcut)) 8. Make sure that after dealing with the other points, issue182, issue339, issue368 and msg2533 are addressed, and close the respective issues. 9. issue198: issues with multiple heuristics. In particular, all special-casing of heuristics[0] in eager search should disappear. 10. issue407: g-bound should also work in corner cases. 11. issue407: initial nodes should go through the same tests as other nodes when/before being added to the open lists (e.g check for an infinite heuristic estimate). 12. Correctly implement max and sum evaluators. (See msg1182. Is this still current?) 13. The search progress statistics are fragile. (See msg1182. Is this still current?) -> ~~1. issue77: get rid of pathmax.~~ ~~2. issue108: Heuristic values should be stored in the heuristic itself.~~ ~~3. issue77: open list should not inherit from evaluator.~~ 4. Make Evaluator and Heuristic into one class. 5. support path dependence similar to multi-path dependence (especially with path-dependent dead ends). 6. issue311: implement eager WA*. 7. issue505: More Aliases in driver instead of overfilling search class with compositions: eg astar(lmcut) -->eager(tiebreaking(sum_eval(g_eval,lmcut),lmcut)) 8. Make sure that after dealing with the other points, issue182, issue339, issue368 and msg2533 are addressed, and close the respective issues. 9. issue198: issues with multiple heuristics. In particular, all special-casing of heuristics[0] in eager search should disappear. 10. issue407: g-bound should also work in corner cases. 11. issue407: initial nodes should go through the same tests as other nodes when/before being added to the open lists (e.g check for an infinite heuristic estimate). 12. Test that regular max and sum evaluators now always work as intended and ensure they can be used on the top level. Then get rid of ipc_max_heuristic. 13. Review and possibly improve the handling of search progress and search statistics.
2016-01-09 12:58:07floriansetnosy: + florian
messages: + msg5068
summary: ~~1. issue77: get rid of pathmax.~~ ~~2. issue108: Heuristic values should be stored in the heuristic itself.~~ ~~3. issue77: open list should not inherit from evaluator.~~ 4. Simplify evaluator class hierarchy. (See msg4043. Is this still current?) 5. support path dependence similar to multi-path dependence (especially with path-dependent dead ends). 6. issue311: implement eager WA*. 7. issue505: More Aliases in driver instead of overfilling search class with compositions: eg astar(lmcut) -->eager(tiebreaking(sum_eval(g_eval,lmcut),lmcut)) 8. Make sure that after dealing with the other points, issue182, issue339, issue368 and msg2533 are addressed, and close the respective issues. 9. issue198: issues with multiple heuristics. In particular, all special-casing of heuristics[0] in eager search should disappear. 10. issue407: g-bound should also work in corner cases. 11. issue407: initial nodes should go through the same tests as other nodes when/before being added to the open lists (e.g check for an infinite heuristic estimate). 12. Correctly implement max and sum evaluators. (See msg1182. Is this still current?) 13. The search progress statistics are fragile. (See msg1182. Is this still current?)
2015-12-10 17:09:35maltesetmessages: + msg4948
2015-12-10 15:09:46gabisetmessages: + msg4945
2015-03-09 13:38:27maltesetmessages: + msg4043
2014-12-17 21:14:11jendriksetmessages: + msg3963
2014-12-16 01:24:54erezsetmessages: + msg3948
2014-12-15 12:18:21jendriksetnosy: + jendrik
2014-12-15 09:56:02manuelsetnosy: + manuel
2014-12-13 18:13:40maltesetmessages: + msg3926
2014-12-13 14:04:55salomesetpriority: bug -> meta
nosy: + salome
messages: + msg3924
2014-09-17 13:54:26gabisetmessages: + msg3423
2014-09-17 13:49:38maltesetmessages: + msg3421
2013-07-01 12:03:48gabisetmessages: + msg2533
2013-06-25 14:51:09gabisetmessages: + msg2507
2012-10-26 15:22:55mkatzsetmessages: + msg2372
2012-10-26 15:22:41mkatzsetmessages: - msg2371
2012-10-26 15:20:49mkatzsetmessages: + msg2371
2012-10-26 15:18:12mkatzsetmessages: - msg2369
2012-10-26 15:17:04mkatzsetnosy: + mkatz
messages: + msg2369
2012-06-01 11:34:26maltesetmessages: + msg2249
2011-01-20 03:09:02maltesetkeyword: + 1.0
2011-01-17 13:17:31maltesetmessages: + msg1192
2011-01-17 13:11:27erezsetmessages: + msg1191
2011-01-17 12:59:50gabisetmessages: + msg1190
2011-01-16 23:19:24maltesetmessages: + msg1189
2011-01-16 23:15:51erezsetmessages: + msg1187
2011-01-16 18:42:34maltecreate