The Pre-Processing Algorithm Input: The action and predicate definitions of a domain and the objects of a problem.

Output: The distance estimate from the goals *dist*(p) and the related facts *rel(p*) for each ground fact p of a problem.

1. **Let** Actions be the set of all **inverted ground actions in the given**
problem. For each α ∈ Actions**, set** dist(α)=+∞.

2. **Let** Agenda **be a list of inverted actions. Set** Agenda=∅. 3. **Let** Facts **be the set of all problem's ground facts. For each** f ∈
Facts set dist(f)= +∞.

4. **For each** f ∈ Goals set dist(f)=**0 and** rel(f)=Goals. 5. For each **action** α ∈ Actions, if A**GGREGATE**(Pre(α))<+∞**, then set**
dist(α)=A**GGREGATE**(Pre(α))+1 and add α **at the end of the** Agenda.

6. **While** Agenda ≠ ∅ do:
a) **Extract the first action from the** Agenda**, say** α. b) For every fact f ∈ Add(α**), if** dist(f)>dist(α**), then:**
- dist(f)=dist(α)
- rel(f**) =** Pre(α) ∪ rel(Pre(α)) ∪ Add(α)\Del(α)
- **For every action** b ∈ Actions**, such that** f ∈ Pre(b**), if**
A**GGREGATE**(Pre(b**))+1<**dist(b**), then** dist(b)=A**GGREGATE**(Pre(b**))+1 and**
push action b **at the end of the** Agenda.
The *Agenda* works on a FIFO basis. An action can be re-inserted in the *Agenda* if its cost becomes smaller. Thus, each fact can be achieved several times, each time with a smaller cost. The cost of applying the Pre-Processing Algorithm is polynomial in the number of problem ground facts and ground actions.

Proposition 5. The Pre-Processing Algorithm preserves Axiom 2.

Proof: In step 6b, the cost of applying an action is set to be equal to the cost of achieving simultaneously the preconditions of the action plus one. This cost is assigned to the add effects of the action, except if lower costs have already been assigned to them. Thus, Axiom 2 is preserved. Proposition 6. Function AGGREGATE preserves Axiom 1. Proof: We will prove Proposition 6 by induction. Axiom 1 holds for the *Goals*, which have zero distances from themselves and are related to each other. Besides, Propositions 3 and 4 and Corollaries 1, 2 and 3 hold also for them. Suppose next that Axiom 1 and all the induced Propositions and Corollaries hold for the currently achieved facts *Facts*. It suffices to prove that for any action a, such that Pre(a) ⊆ *Facts*, Axiom 1 holds for the new set of achieved facts Facts'=Facts ∪ *Add(a*).

Consider a set of facts P ⊆ *Facts*'. We will prove that function AGGREGATE preserves Axiom 1, with regard to the randomly selected set P. Let p be the fact with the maximum distance among the facts of P. According to the definition of AGGREGATE function, it suffices to prove that p or another fact of equal distance is included in M2.