Distance between Attribute Values

We use some kind of heuristic distance computation between different values of an attribute. One often used (and also used by us) heuristic is to define distance between two values A and B to be the number of actions it takes to go from A to B, ignoring any other preconditions and contributions of the actions.

Distance between Object References

In some cases the distance between object references are important. This is considered in detail in the post http://crackpotplanner.blogspot.com/2009/03/implementation-diary-march-5-2009.html

Modelling Uncertainty in Heuristic Distance Computation of AttributeInstances

We can extend this model of heuristic distance to include uncertainty in the distance. If there is a series of actions that really take from A to B, and has no other preconditions and contributions, then there is no uncertainty for this path from A to B. If there is a series of actions from A to B having many other preconditions, then the uncertainty would be large.

The original context that lead to this (small) idea was justifying a statement in Alex's paper "Local Search Heuristics for Generative Planning" - an action is inserted in proportion to 1/d^3, where d is the distance between the desired value and the resultant value after inserting the action. Why 1/d^3?

In case there is no uncertainty, the better action should be greedily selected (with probability 1). Suppose there are two actions A1 and A2 with distance d1 and d2 and uncertainty of distances u1 and u2, and u1 <> u2. This is a tricky case.

If there is no action that can convert from one value to another, then the distance would be infinite.