A reﬁnement abstraction must satisfy two criteria in order to always produce correct solutions:

1. It must be complete, i.e. if there is a ground path from s to t in G1, then there must also be an abstract path in G2

from  f (s) to  f (t).

9

C. Bäckström and P. Jonsson

Artiﬁcial Intelligence 302 (2022) 103608

2. It must be sound, i.e. if there is an abstract path from  f (s) to  f (t) in G2, then there must also be a ground path from 

s to t in G1.

One may also consider different degrees of these concepts. For instance, soundness could be strengthened to require that 
every abstract solution can be reﬁned into a ground solution. We will consider such degrees of reﬁnement later in this sec-
tion.
A-framework-for-analysing-state-abstraction-metho_2022_Artificial-Intelligen