two other heuristics (just the idea)
a technical note about merge and shrink
content-enhanced heuristics
assumption:
every action that affects x has some precondition x=value
the additive heuristics implicitely assume that variables can be changed
independently
but obtaining x=value may change y and z
first obtain x=value
then evaluate the cost of obtaining the other preconditions in that state
network flow heuristics
assumption:
every action that affects x has some precondition x=value
if x≠v in current state
but x=v in goal
then: actions x≠v⇒x=v are executed one time more than
actions x=v⇒x≠v
similar in the opposite case or when x=v is in both state and goal
variable = how many times an action is executed:
make a system of integer equations and disequations
minimize number of times actions are executed
solve (approximately: not integer) as linear programming
merge and shrink: technically
combine two abstract search spaces A and B
how: two states are together in C
only if they are together in A and are also together in B
done without looking at the original states
This is what happens when merging arbitrary abstractions: two states are in a
group in the output abstraction only if they are all in the same group in all
input abstractions.