It  is  common  to  consider  admissible  heuristics  that  are  also  consistent,  although  exceptions  are  possible  [34].  In  our 
case, the heuristic function c2 is based on minimum lengths or costs of paths in an abstract graph, so it always satisﬁes 
the triangle inequality, i.e. c2(s, t) ≤ c2(s, u) + c2(u, t) for all states s, t, u ∈ S2. Suppose τ is admissible, i.e. c2( f (s), f (t)) ≤
c1(s, t) for all s, t ∈ S1. Then, for all s, t, u ∈ S1 we get that

k

7 We use reals for generality of the results. In practice we are, of course, restricted to integers and rationals, and the choice of the numeric domain 
inﬂuences the computational complexity of ﬁnding cost-optimal paths [1].

25

C. Bäckström and P. Jonsson

Artiﬁcial Intelligence 302 (2022) 103608

G2:

G1:

1

f

11

12

2

21

22

3

31

32

Fig. 10. A transformation that is PS↑ but not A↓. Unit label (cid:2) assumed.

c2( f (s), f (t)) ≤ c2( f (s), f (u)) + c2( f (u), f (t)) ≤ c1(s, u) + c2( f (u), f (t)),
A-framework-for-analysing-state-abstraction-metho_2022_Artificial-Intelligen