critical path heuristics

another way of viewing the maximal heuristics h^max

extend it

maximal heuristics, in retrospect

e and f both make x₈ true
alternative actions: cheapest

x₃ and x₄ both needed to execute c
preconditions: maximal cost only

cheapest way to go the goal
with the additional simplification of a single precondition per action

no way to do it better: critical path
minimal absolute possible cost of reaching the goal

critical path: extension

instead of "single precondition per action"

use: "two preconditions per actions"

Switching from one to two creates an additional complication, since a pair of variables may be made true by the same action or by two different ones.

But delete effects can be taken into account somehow.

maximal of two

base of h^max:

obtaining all three of x₁, x₂ and x₃
cannot be easier than obtaining x₁ alone,
or x₂ alone
or x₃ alone

safe choice: obtaining three is the maximal cost of obtaining each

also safe is the maximal cost of obtaining each pair:

obtaining all three of x₁, x₂ and x₃
cannot be easier than obtaining x₁ and x₂,
cannot be easier than obtaining x₁ and x₃
and cannot be easier than obtaining x₂ and x₃

preconditions and effects of action

example: action a
preconditions x₁ x₂ x₃
effects x₄ x₅

pairs of precondition

before: cost is maximal of obtaining x₁ alone, x₂ alone or x₃ alone

now: maximal of obtaining the pairs

not so easy…

needed pairs

no action has x₅x₆ in a precondition
⇒ do not calculate the cost of this pair, pointless

an action has x₃x₆ in a precondition
⇒ calculate the cost of this pair

other pairs

if some other action has x₄x₆ as a precondition
⇒ calculate the cost of this pair
⇒ how is this pair obtained?

x₄x₆ made true by a if x₆ is already true!

requires: preconditions of a and x₆
so: x₁ x₂ x₃ x₆

pairs, again

to make x₁ x₂ x₃ x₆ true:
maximal cost of making a pair true

multiple actions

example: action b
precondition x₇
effects x₄x₆

x₄x₆ can be obtained both by a and b
alternative: minimal cost of the two

single variables

if some action has one precondition only
⇒ calculate its cost

in the example: a also makes x₄ alone true

delete effects

if a does not delete x₆
⇒ makes x₄x₆ true if x₆ was true before

if a deletes x₆
⇒ does not make x₄x₆ true even if x₆ was true before

Incorporating delete effects this way allows excluding a as a possible way for obtaining x₄x₆.

Since it only applies to pairs of variables, it cannot be applied to the maximal heuristics h^max, which only consider single variables.

triples, etc.

heuristics using subsets of at most m variables: h^m

polynomial for every fixed m

only h¹ (=max heuristics) and h² used in practice

mathematical formalization

example: maximal heuristics

start with cost(x_i) = 0 if x_i initially true
otherwise cost(x_i) = ∞
cost(a) = cost of executing a alone

keep updating costs until they do not change

cost(x_i) = min(cost(x_i), P_i)

where P_i is: P_i = min_{a . x_i ∈ add(a)}(cost(a) + max_{x_j ∈ pre(a)}(cost(x_j))) and pre(a) = preconditions of a
and add(a) = positive effects of a

The cost of obtaining a variable x_i is the minimal overall cost of the actions that have x_i as an effect. The overall cost is the cost of the action plus its preconditions. So far, this is an exact calulation.

The approximation enter the scent at this point: instead of computing the cost of the preconditions, their maximum individual cost is considered. In the case of h², the maximal cost of pairs of preconditions is used instead.

critical path

max heuristics = generating a variable is the same as generating is hardest-to-obtain precondition

go back from the goal to the initial state

cost of the critical path of actions
from initial state to goal

h^m: same, but for pair/triples/quadruples/etc. of variables

all of them: critical path heuristics

relaxation and critical path heuristics

relaxation: ignore delete effects
critical path: obtain something = obtain its hardest part

delete effects irrelevant to h¹
also a relaxation heuristics

h^m keeps them into account for m ≥ 2
not a relaxation heuristics

admissibility

maximal and its generalization h^m:
cost = maximal cost of a subset
indeed: subset needs to be achieved
admissible

sum and FF:
sum the cost of actions
but, some actions may be redundant
in such cases, cost is overestimated
not admissible