Issue285

Title evalute/improve A* tie-breaking w.r.t. goal states
Priority feature Status chatting
Superseder Nosy List malte, manuel
Assigned To Keywords
Optional summary

Created on 2011-10-14.17:22:57 by malte, last changed by manuel.

Messages
msg1806 (view) Author: malte Date: 2011-10-14.17:22:56
If a goal state becomes eligible for expansions (i.e. is among the states with
minimal f value), A* should select it immediately to complete the search. For
tasks and heuristics where h=0 is only true for goal states, this happens
automatically due to the tie-breaking preferring low h values.

However, with 0-cost actions, it is quite possible even for decent heuristics to
report h=0 for non-goal states. So we should check if we can improve performance
in domains with 0-cost actions by explicitly taking goal states into account.
One possibility to do this would be to incorporate goal-ness directly into the
tie-breaking decisions. Another would be to take note when a goal state is
generated (not chosen for expansion) and updating an upper bound on the best
known solution so far in this case, and then introducing special handling to
extract the solution as soon as the f value climbs to that upper bound. This
latter solution would have the advantage that we could also use the upper bound
on the solution for pruning generated states.
History
Date User Action Args
2017-07-05 12:42:35manuelsetnosy: + manuel
2011-10-14 17:22:57maltecreate