Issue340

Title Using admissible heuristics for pruning in greedy search
Priority wish Status resolved
Superseder Nosy List jendrik, malte, patrik
Assigned To Keywords
Optional summary

Created on 2012-06-01.06:54:39 by patrik, last changed by malte.

Messages
msg11157 (view) Author: malte Date: 2023-07-24.14:40:07
This should now be easy to implement without changing any code with the https://www.fast-downward.org/Doc/PruningMethod interface. Closing due to lack of activity, following our policy not to keep wishes open unless there is a concrete plan to work on them. (But if someone feels this should be added to the base planner, feel free to lobby for it, for example on the Discord or mailing list.)
msg2247 (view) Author: patrik Date: 2012-06-01.06:54:39
This is a pure wish: I'd like to be able to run a greedy search (lazy or eager),
while using an admissible heuristic to prune nodes whose f-value exceeds a given
cost bound. (Most, if not all, search engines already have a "bound" parameter,
but it is only checked against the g-value.)

This is quite straightforward to add to the current eager_search: one just needs
to give a ScalarEvaluator to be used for pruning, make sure any heuristic in
that evaluator is added to the "heuristics" array (so that it gets computed on
new states), and add a bounds check for each successor generated in the step()
method (I put it just after the dead-end check). The search engine already has a
parameter for an f-evaluator, which, although seemingly intended for a different
purpose, can be used for pruning. But it might be nicer if the two functions are
separated into different parameters.
History
Date User Action Args
2023-07-24 14:40:07maltesetstatus: unread -> resolved
messages: + msg11157
2014-12-12 10:39:35jendriksetnosy: + jendrik
2012-06-01 06:54:39patrikcreate