# Scaling regimes of the one-dimensional phase turbulence in the deterministic
complex Ginzburg-Landau equation

Francesco Vercesi 1, Susie Poirier 1, Anna Minguzzi1, Léonie Canet1,2 1
Université Grenoble Alpes, CNRS, LPMMC, 38000 Grenoble, France,
2 Institut Universitaire de France, 5 rue Descartes, 75005 Paris

###### Abstract

We consider the one-dimensional deterministic complex Ginzburg-Landau equation
in the regime of phase turbulence, where the order parameter displays a
defect-free chaotic phase dynamics mapping to the Kuramoto-Sivashinsky
equation, characterized by negative viscosity and a modulational instability
at linear level. In this regime, the dynamical behavior of the large
wavelength modes is captured by the Kardar-Parisi-Zhang (KPZ) universality
class, determining their universal scaling and their statistical properties.
These modes exhibit the characteristic KPZ sub-diffusive scaling with the
dynamical critical exponent $z=3/2$. We present numerical evidence of the
existence of an additional scale-invariant regime, with the dynamical exponent
$z=1$, emerging at scales which are intermediate between the microscopic ones,
intrinsic to the modulational instability, and the macroscopic ones. We argue
that this new scaling regime belongs to the universality class corresponding
to the inviscid limit of the KPZ equation.

††preprint: APS/123-QED

##  I Introduction

The complex Ginzburg-Landau equation (CGLE) is a prototype model for the
effective dynamics of spatially extended systems out of equilibrium, ranging
from hydrodynamical instabilities [1], pattern formation [2], chemical
turbulence [3], to driven-dissipative bosonic condensates [4]. Its success in
providing a reliable qualitative description of a vast variety of phenomena in
terms of a few parameters has earned the CGLE a conspicuous interest [3].
Important efforts have been devoted to characterizing the rich phase diagram
of the CGLE, both in one and in higher spatial dimensions [5, 6, 7, 8, 3]. In
one dimension, the CGLE can yield chaotic, non-chaotic and intermittent
dynamics. We focus in this paper on the weakly turbulent regime, also known as
phase turbulence, characterized by spatio-temporal chaos in absence of
topological defects [5, 9, 10, 11, 12, 13]. In this regime, the amplitude of
the order parameter weakly fluctuates around a finite steady value. Its
dynamics can be integrated out resulting in a mapping of the CGLE to the
Kuramoto-Sivashinsky (KS) equation [14, 15] governing the effective dynamics
of the phase. The KS equation is a deterministic nonlinear model for
fluctuating interfaces, which exhibits nontrivial behavior: indeed, this
equation features a negative viscosity, which yields an intrinsic modulational
instability of the linearized equation, saturated at nonlinear level. This
induces a chaotic dynamics when the size of the system is large with respect
to the typical scale of the instability pattern [16, 17]. This dynamics
exhibits a steady state, whose essential statistical features are captured by
the celebrated Kardar-Parisi-Zhang (KPZ) equation [18].

Originally introduced for modeling the random growth of non-equilibrium
interfaces [18], the KPZ equation is a stochastic nonlinear partial
differential equation which has become a paradigm of nonequilibrium
criticality, encompassing a wide collection of systems counting, besides
driven rough interfaces, randomly stirred viscous fluids [19], directed
polymers in random media [20], the coherence of driven-dissipative bosonic
condensates [21, 22, 23], quantum spin chains [24], strongly correlated bosons
[25], and many more [26]. In one dimension, the KPZ equation yields a
universal critical regime characterized by a sub-diffusive scaling behavior
with the exact dynamical critical exponent $z=3/2$ [18], as well as by
precisely known non-Gaussian statistics [27, 26]. In the limit of vanishing
nonlinearity, the KPZ equation reduces to the Edwards-Wilkinson (EW) equation
[28], which leads to a diffusive scaling with $z=2$ and Gaussian statistics.
Recently, a new scaling regime, characterized by a dynamical exponent $z=1$,
has been unveiled in different systems belonging to the KPZ universality class
[29, 30, 31, 25, 32]. This new regime emerges in the limit of vanishing
surface tension for the KPZ equation, or equivalently in the limit of
vanishing viscosity for the stochastic Burgers equation, which governs the
dynamics of the velocity of the interface [29, 30, 31, 25]. The functional
renormalization group analysis carried out in Ref. [32] has shown that this
new scaling regime is controlled by a fixed point of the KPZ equation which
had not yet been identified, and which corresponds to its inviscid limit. This
fixed point was termed “inviscid Burgers” (IB) fixed point and it describes a
new universality class, featuring in particular the $z=1$ dynamical exponent.
Its associated universal scaling function was determined using the functional
renormalization group in Ref. [32].

The fact that the large-scale behavior of the deterministic KS equation
belongs to the KPZ universality class was early conjectured [16], and
supported by some indications in numerical simulations [33] and perturbative
renormalization group analysis of the noisy KS equation [34, 35]. Yet, the
clear signature of the KPZ universal scaling in this system has long eluded
numerical observation due to the very large system size and run time needed.
The scaling regime found in early simulations was rather compatible with the
EW one. A definitive evidence of KPZ scaling has only been recently provided
by the massive numerical simulations performed by the authors of Ref. [36],
which allowed them to quantitatively determine the scaling exponents and the
statistical properties of the one-dimensional deterministic KS equation, and
show that they correspond to the KPZ ones.

In this paper, we present a numerical study of the statistical properties of
the deterministic CGLE in the phase turbulence regime, and show that, besides
the KPZ universal scaling, also the Inviscid Burgers one arises. We provide
arguments to explain the systematic appearance of the IB universality in the
CGLE, and in the Kuramoto-Sivashinsky equation. In details, we simulate the
deterministic CGLE, starting from random initial conditions, and we compute
the spatio-temporal correlations of the phase by averaging over independent
realizations. We first show that the scaling behavior of the long wavelength
modes is the EW one ($z=2$), as expected for to the system size considered. We
then focus on intermediate scales and show that they exhibit a different
scaling, with $z=1$, corresponding to the IB universality class. We compute
the associated scaling function. Finally, as proposed for the KS equation in
Ref. [35], we introduce a stochastic white noise in the CGLE and identify a
window of parameters in which the KPZ universality emerges, despite the small
system size and the finite probability of noise-activated defect formation
[37, 38].

##  II  The deterministic complex Ginzburg-Landau equation

###  II.1  Regime of phase turbulence

We consider the complex Ginzburg Landau equation defined by:

$i\partial_{t}\psi=i\psi+(c_{2}-i)|\psi|^{2}\psi-(c_{1}-i)\partial_{x}^{2}\psi$
(1)

where $\psi$ is the complex order parameter and $c_{1}$, $c_{2}$ are
dimensionless real coefficients. The homogeneous solution
$\psi_{0}=1\times\mathrm{e}^{-ic_{2}t}$ is linearly unstable when
$1+c_{1}c_{2}<0$. Under this condition, a modulational instability, which is
known as the Benjamin-Feir (BF) instability [39, 3], triggers a turbulent
behavior which, depending on the values of $c_{1}$ and $c_{2}$, is either
characterized by the presence of topological defects, where the amplitude
$|\psi|$ goes to zero, or by defect-free phase modulations [3]. The two
regimes are usually labeled defect and phase turbulence, respectively. The
latter arises if $c_{1},c_{2}$ are chosen close to the BF instability line
$1+c_{1}c_{2}=0$ [13], in which case the amplitude slightly fluctuates around
1, while the phase dynamics is mapped to the Kuramoto-Sivashinsky equation
[14, 15]:

$\partial_{t}\theta=\left(\nu\partial_{x}^{2}+\eta\partial_{x}^{4}\right)\theta+\frac{\lambda}{2}(\partial_{x}\theta)^{2}$
(2)

with $\nu=1+c_{1}c_{2}$, $\eta=-c_{1}^{2}/2$, $\lambda=2(c_{2}-c_{1})$. We
report the derivation of this phase equation in Appendix B. One readily
notices that the instable regime of the CGLE corresponds to a negative value
of the viscosity $\nu$ in the phase equation (2). The instability primarily
concerns the low momentum modes, since the linear dispersion $-\nu k^{2}+\eta
k^{4}$ is positive for $0\leq k<k_{0}$ with $k_{0}=\sqrt{\nu/\eta}$. In the
following, we focus on the regime of phase turbulence, by appropriately
choosing $c_{1}$ and $c_{2}$ close to the BF instability line.

###  II.2 Large scale behavior

The statistical properties of the large wavelength fluctuations of the KS
phase are expected to belong to the KPZ universality class [16], which means
that their effective macroscopic dynamics can be described by the KPZ equation
[18]:

$\partial_{t}\theta=\nu_{\rm eff}\partial_{x}^{2}\theta+\frac{\lambda_{\rm
eff}}{2}(\partial_{x}\theta)^{2}+\xi(x,t)$ (3)

where $\nu_{\rm eff}>0$ and $\xi(x,t)$ is a white noise with
$\langle\xi(x,t)\xi(x^{\prime},t^{\prime})\rangle=2D_{\rm
eff}\delta(x-x^{\prime})\delta(t-t^{\prime})$. However, it was shown that a
sufficiently large system size is required for KPZ universality to emerge,
while smaller systems were observed to display EW scaling [36].

We emphasize that if one considers from the start a noisy version of the CGLE
(1) and chooses $c_{1}$, $c_{2}$ within the stable region (implying $\nu>0$ in
(2)), the term proportional to $\partial_{x}^{4}$ becomes subdominant and the
phase dynamics simply inherits the stochastic nature of the CGLE. In this
case, one directly obtains the KPZ equation [22, 21]. This is the case for
driven-dissipative bosonic condensates described by the generalized stochastic
Gross-Pitaevskii equation, in which the large-scale coherence, controlled by
phase fluctuations, was shown to exhibit the KPZ scaling [21, 22, 23] and non-
Gaussian statistics [40, 41] even in small systems.

Conversely, in the deterministic case and in the unstable regime where
$\nu<0$, the phase dynamics maps to the deterministic KS equation, and the
parameters $\nu_{\rm eff}$ and $D_{\rm eff}$ of the effective KPZ equation are
not primarily determined, but are generated by the chaotic dynamics. The
perturbative renormalization group analysis of Ref. [35] showed the emergence
of a positive macroscopic viscosity from the noisy microscopic KS equation.
Indeed, they find that while coarse-graining by including the fluctuations
from small to large scales, the effective viscosity changes sign, from the
microscopic value $\nu<0$ to an effective value $\nu_{\rm eff}>0$ in the
macroscopic limit. We emphasize that in this process, the viscosity crosses
zero at some intermediate scale: this is the very origin of the appearance of
the IB regime at intermediate scales [42]. Note that the Galilean invariance
of the KS equation imposes $\lambda_{\rm eff}=\lambda$ at all scales, although
in practice the value of $\lambda_{\rm eff}$ may be renormalized by effect of
the space discretization [33] or, as in the present case, of the higher-order
nonlinearities neglected when mapping the CGLE to the KS equation (see
Appendix B).

In order to characterize the statistical properties of the phase dynamics, we
analyze both the transient regime and the steady state. In the transient
regime, i.e. during the kinetic roughening, the dynamical scaling behavior of
the interface $\theta(x,t)$ is captured by the structure function, defined as

$S(k,t)=\langle\theta(k,t)\theta(-k,t)\rangle$ (4)

where in the deterministic case $\langle.\rangle$ denotes the average over
independent trajectories with randomly chosen initial conditions, while for
the stochastic equation, in Sec. III.3, the average is over independent noise
realizations. The choice (4) is particularly suited when different scaling
behaviors coexist at different scales $k$ [43]. The Family-Vicsek scaling
Ansatz [44] for $S(k,t)$ reads:

$S(k,t)=k^{-(2\chi+1)}s(k^{z}t)$ (5)

where $\chi$ is the roughness critical exponent, $z$ is the dynamical critical
exponent, and $s(y)$ is a universal scaling function with the properties
$s(y\rightarrow 0)\sim y^{2\chi+1}$ and $s(y\rightarrow\infty)\rightarrow
s_{0}$. For each mode $k$, the structure function converges to the stationary
average occupation when the time $t_{ss}(k)\sim k^{-z}$ has elapsed.

In the steady state, we focus on the velocity field $u=\partial_{x}\theta$ and
compute the temporal correlations of its Fourier modes $C(k,t)=\langle
u(k,t+t_{0})u^{*}(k,t_{0})\rangle$, with $t_{0}>t_{ss}(k)$ for all the modes
$k$ considered. The correlations exhibit the scaling behavior

$C(k,t)=C(k,0)f\left(k^{z}t\right)$ (6)

where $f(y)$ is a universal scaling function and the exponents $\chi$, $z$ are
the same as in Eq. (5). Note that $t$ in Eq. (5) is the absolute time whereas
it denotes in Eq. (6) the time delay.

###  II.3 KPZ fixed points

The KPZ equation (3) can be rescaled to obtain a single relevant parameter
$g=\lambda^{2}D/\nu^{3}$. Depending on the value of $g$, there are three
possible scaling regimes, controlled by the corresponding fixed points:

  1. i)

the KPZ regime ($g$ finite): $\chi=1/2$, $z=3/2$ and $f=f^{\rm KPZ}$ given by
the universal KPZ scaling function, exactly calculated in Ref. [27]

  2. ii)

the EW regime ($g=0$): $\chi=1/2$, $z=2$ and $f=f^{\rm EW}$ the universal
scaling function of the linear theory, given by

$f^{\rm EW}(y)=\frac{D}{\nu}e^{-\sqrt{\nu}y^{2}}$ (7)

  3. iii)

the IB regime ($g=\infty$): $\chi=1/2$, $z=1$ and $f=f^{\rm IB}$ computed via
the functional renormalization group in Ref. [32]. The short-time asymptotic
behavior of $f^{\rm IB}$ was shown to endow a simple Gaussian form [29, 30,
32]:

$f^{\rm IB}(y\ll y_{0})\sim\,e^{-ay^{2}}\,.$ (8)

In one dimension, the only attractive fixed point in the infrared (at large
distance) for any finite $g$ is the KPZ fixed point. However, in a finite-size
system, the other two EW and IB fixed points, although repulsive in the
infrared, can influence the scaling properties of the system when $g$ is
respectively very small or very large, especially for the intermediate modes
[30, 32].

Let us emphasize that in one dimension all the three regimes of the KPZ
equation share a common value $\chi=1/2$ for the roughness exponent. This
implies that the stationary state is characterized by a flat energy spectrum
$C(k,0)=\langle|u(k)|^{2}\rangle=k^{2}S(t>t_{ss},k)=s_{0}=\frac{2D}{\nu}$. The
equipartition of energy is a consequence of the “accidental” time-reversal
symmetry of the KPZ equation in one dimension, whereby the spatial properties
of the stationary interface coincides with the equilibrium one (i.e. the
Brownian interface of the diffusive EW case) [26]. The associated fluctuation-
dissipation relation [45] constrains the effective macroscopic viscosity and
noise strength to conserve the ratio they have at the microscopic level. We
underline that the ratio $\nu_{\rm eff}/D_{\rm eff}$ is not defined for the
deterministic KS equation, for which the time-reversal symmetry is an emergent
property at large scales [35].

More subtle is the inviscid limit of the KPZ (Burgers) equation. Indeed, the
typical solutions of the inviscid Burgers equation in an infinite system
generate dissipative shocks in a finite time [19, 46]. However, in the
presence of an ultraviolet cutoff and if the time evolution is energy-
conserving, the system evolves instead to a thermalized state with the
equilibrium static exponent $\chi=1/2$, and a dynamical exponent $z=1$ [29,
30, 32]. This implies that the inviscid limit $\nu\rightarrow 0$ is approached
by preserving a constant finite ratio $\nu/D$, thus coinciding with the
deterministic limit. As a final remark, we mention that the authors of Ref.
[31] characterized the scaling behavior of an inviscid and noisy version of
the KPZ equation, which breaks the time-reversal symmetry. In this case, they
report an anomalous kinetic roughening behavior with different local and
global roughness exponents ($\chi_{\rm loc}=1\neq\chi=1/2$), while conserving
the dynamical exponent $z=1$. To fully understand the connection between this
regime and the thermalized one of Ref. [29, 30, 32] is an exciting, although
non-trivial task.

##  III  Results

We have performed numerical simulations of the CGLE (1) with random initial
conditions $\psi(t=0,x)=1+\sigma(x)$, where $\sigma(x)\in\mathbb{C}$ is a
random complex number drawn independently for every $x$ from a Gaussian
distribution of zero mean and variance 0.01 111The winding number, defined as
$w=\frac{1}{2\pi}\int_{0}^{L}\partial_{x}\theta dx$, is thus always zero in
our initial conditions. In the phase turbulence regime $w$ is conserved. We
exclude the drifted phase turbulence scenario of Ref. [10], obtained by
setting $w\neq 0$ at $t=0$, in which case the KS dynamics develops on top of a
plane wave of wavenumber $k=2\pi w/L$.. We consider the equation in its
dimensionless form (1), with a space discretization chosen as $dx=1.0$ or
$dx=1.5$ – the change corresponding to a slightly modified weight of the
kinetic term with respect to the others in the CGLE. We study the statistical
properties of the interface defined as the unwrapped phase
$\theta(x,t)=\mathrm{Arg}(\psi(x,t))+2\pi j$, where $j$ is an integer chosen
in order for the temporal evolution to be smooth in time, i.e.
$\theta(x,t+\delta t)-\theta(x,t)\in(-\pi,\pi]$. We first present the results
for the large-scale behavior, which exhibits the EW scaling, then discuss the
behavior of the intermediate scales where we find the IB scaling, and finally
show that, adding a small noise, the KPZ scaling emerges at the large scales,
replacing the EW regime.

Figure 1: Scaling behavior of the structure function compared with the EW
theory (7), with $\chi=1/2$, $z=2$. The plotted window is $2\pi/L<k<2k_{0}$.
The parameters are: $c_{1}=3.5$, $c_{2}=-0.6$ ($k_{0}=0.36$), $L=49152$,
$dx=1.5$, $N_{\rm sim}=1024$

###  III.1  Kinetic roughening behavior

The structure function $S(t,k)$ in the transient roughening regime is
displayed in Fig. 1. During the early evolution, i.e. for $t\lesssim 500$ \-
not represented, the population of unstable low momentum modes $k<k_{0}$ is
transferred to the dissipative sector $k>k_{0}$ via nonlinear coupling, until
a typical cellular structure arises, whose wavenumber corresponds to the local
maximum observed in $S(t,k)$. Thereafter, the roughening process progressively
fills the low momentum sector. The structure function is found to endow the
scaling Ansatz (5), and the collapse obtained with the EW exponents $z=2$,
$\chi=1/2$, shown in Fig. 1, is excellent. The scaling function coincides with
the EW one given by $s^{\rm EW}(y)=\frac{2D_{\rm eff}}{\nu_{\rm
eff}}\left(1-\,e^{-2\sqrt{\nu_{\rm eff}}y^{2}}\right)$ with the argument
$y=kt^{1/2}$. We find $\nu_{\rm eff}\approx 12$ and $D_{\rm eff}\approx
4.7\times 10^{-3}$. These numbers, together with the effective non-linearity
$\lambda_{\rm eff}\approx\lambda=2(c_{1}-c_{2})$, give the KPZ coupling
$g_{\rm eff}\approx 1.7\times 10^{-4}$. Following Refs. [33, 48], we can
estimate the threshold system size and crossover time needed for the effective
KS dynamics to exhibit the KPZ behavior, for which we obtain respectively
$L_{c}\approx 6\times 10^{5}$, $t_{c}=6\times 10^{8}$, thus confirming a
posteriori the expectation of the EW scaling emerging for our system size.

Figure 2: Top panel: energy spectrum $C(0,k)=\langle|u(k)|^{2}\rangle$. Bottom
panel: correlation time $\tau_{1/2}$, defined as
$C(\tau_{1/2},k)=\frac{1}{2}C(0,k)$. The parameters are: $c_{1}=2.1$,
$c_{2}=-0.8$ ($k_{0}=0.434$), $L=8192$, $dx=1.0$, $N_{\rm sim}=1024$. The
solid lines represent the $\sim k^{-z}$ behaviors.

###  III.2  Inviscid Burgers regime

Figure 3: Scaling behavior of the correlations $C(k,t)$ in the IB regime. Left
panel: correlation decay $C(t,k)/C(0,k)$. Right panel: collapse onto the
scaling function $f(y=kt^{1/z})$ with $z=1$. The plotted window is
$2\pi/L<k<2k_{0}$. The dashed line shows the fitted asymptotic Gaussian
behavior of $f^{\rm IB}$ at short times, also plotted in logarithmic scale in
the inset. The parameters are: $c_{1}=2.7$, $c_{2}=-0.8$ ($k_{0}=0.44$),
$L=2048$, $dx=1.0$, $N_{\rm sim}=1024$.

We now focus on the intermediate-scale modes, for which the spectrum becomes
stationary at short times, typically for $t\gtrsim 500$. We analyze the
correlations $C(t,k)$ in the stationary state. The energy spectrum, given by
$C(k,0)$, is displayed in Fig. 2. It exhibits a plateau at small $k$ resulting
from equipartition of energy. In order to identify the potential scaling
regimes, we first compute the scale-dependent correlation time $\tau_{1/2}(k)$
defined for each mode $k$ from $C(t=\tau_{1/2},k)=\frac{1}{2}C(t=0,k)$. It is
expected to behave as $\tau_{1/2}\sim k^{z}$ in a scaling regime. The result,
displayed in Fig. 2, clearly shows two distinct scaling behaviors: for small
$k$, we retrieve the diffusive EW regime with $z=2$, while at intermediate $k$
we observe a different power-law dependence which is $\tau_{1/2}\sim k^{-1}$.
To further characterize this scaling regime, we select the modes $k$ within
the $z=1$ scaling region, and compute the full correlation $C(k,t)$, which is
shown in Fig. 3. The level lines coincide with constant $y=kt$, which
indicates that $z=1$ in the scaling Ansatz (6). We indeed obtain a remarkable
collapse of the spatio-temporal data when plotted in the scaling variable
$kt$, as shown in Fig. 3. Furthermore, the short-time behavior of $f(y)$ is
found in excellent agreement with the analytical prediction in the IB regime,
Eq. (8), obtained by the FRG calculation [32]. The full shape of $f(y)$ is
also qualitatively compatible with the FRG result for $f^{\rm IB}$ and with
its estimate in the numerical simulations of the Galerkin-truncated inviscid
Burgers equation [30, 29], which both exhibit a negative dip at a finite value
of $y$ after the initial Gaussian decay. However, the depth and position of
the negative dip we observe here do not quantitatively compare with the values
found in these works. This discrepancy is likely to originate in another
essential difference of our work with the “ideal” IB regime of Refs. [30, 29,
32]. At the intermediate scales considered here, the roughness exponent is
slightly lower than $\chi=1/2$, as can be observed in the energy spectrum of
Fig. 2, where a residual slope replaces the plateau for these intermediate
modes. The extracted value for $\chi$ has been found to depend on the
parameters, ranging from $0.28$ to $0.43$ when $c_{1}$, $c_{2}$ take values
within the square (2.70, -0.80), (2.10, -0.80), (2.10, -0.60), (2.70, -0.60).
This signals that the equipartition of energy is not perfectly established for
the modes that exhibit the IB scaling $z=1$. We remind that in order for the
equipartition to settle while approaching the inviscid limit of the stochastic
Burgers equation, it is crucial that the noise obeys the fluctuation-
dissipation relation [30]. In our case, the random noise and the positive
viscosity are effective properties of the small $k$ modes, emerging from the
underlying chaotic dynamics of the CGLE. As a consequence, it is not
guaranteed that they fulfill the time-reversal symmetry. We can thus
reasonably expect a quantitative difference in the shape of the scaling
function $f^{\rm IB}$. A more detailed characterization of the IB regime
emerging within the KS equation can be obtained by means of functional
renormalization group [42]. Nevertheless, the results presented here suggest
that the value of the dynamical exponent $z=1$ and the qualitative shape of
$f^{\rm IB}$ are robust against a weak loss of equipartition. The more general
analyzis of the inviscid regime for different types of noise, breaking the
time-reversal symmetry would be interesting, but is left for future work.

Figure 4: Correlation time $\bar{\tau}$ averaged over 10 values of
$\alpha\in[0.3,0.6]$ where $\alpha=C(k,\tau_{\alpha})/C(k,0)$. The parameters
are: $c_{1}=1.9$, $c_{2}=-0.70$ ($k_{0}=0.35$), $L=4096$, $dx=1.0$, $N_{\rm
sim}=1024$. The solid lines are guidelines to identify the different scaling
behaviors.

###  III.3  Adding noise: crossover to KPZ

Figure 5: Scaling behavior of the correlations $C(k,t)$ in the KPZ regime.
Left panel: correlation decay $C(t,k)/C(0,k)$. Right panel: collapse onto the
scaling function $f(y=kt^{1/z})$ with $z=3/2$. The plotted window is
$2\pi/L<k<2k_{0}$. The dashed line shows the exact KPZ scaling function
$f^{\rm KPZ}$ from [27]. The parameters are: $c_{1}=1.9$, $c_{2}=-0.7$
($k_{0}=0.35$), $\sigma=0.05$, $L=4096$, $dx=1.0$, $N_{\rm sim}=1024$.

In this section, we discuss the effect of adding a stochastic noise of small
amplitude to the CGLE on the large-scale scaling behavior of the phase
turbulence. We thus consider the equation

$i\partial_{t}\psi=i\psi+(c_{2}-i)|\psi|^{2}\psi-(c_{1}-i)\partial_{x}^{2}\psi+\sqrt{\sigma}\xi$
(9)

where $\xi(x,t)$ is a complex white noise with $\langle\xi(x,t)\rangle=0$ and
$\langle\xi(x,t)\xi*(x^{\prime},t^{\prime})\rangle=2\delta(x-x^{\prime})\delta(t-t^{\prime})$.
We replace the statistical average over trajectories starting from different
initial conditions with an average over independent realizations of the noise.

For the KS equation, the stochastic formulation yields considerable
advantages. At a theoretical level, it allows one to cast the problem into a
field theory and study it by means of dynamical renormalization group [34, 35]
or non-perturbative functional renormalization group [42]. At a numerical
level, it allows one to observe the KPZ universality emerging at large scales
for much smaller system sizes since the effective non-linearity $g_{\rm eff}$
is higher [35]. However, for the CGLE, the addition of noise is more subtle.
The noisy CGLE, widely employed as a mean-field model for open quantum fluids
[49, 4], exhibits a richer phase diagram than its deterministic version [37,
38]. In particular, it was shown that, at large noise, the compact nature of
the phase becomes crucial since topological defects (phase slips or space-time
vortices in 1D) can be thermally activated by the noise, breaking down the
analogy with growing interfaces. In tuning the noise amplitude $\sigma$, we
are thus restrained to small values in order not to enter the vortex-turbulent
phase of Ref. [37, 38]. We observe that the region of defect-free phase
turbulence in the $(c_{1},c_{2})$ phase diagram shrinks as the noise amplitude
is increased. We could obtain such a regime only for small noise amplitude
$\sigma\lesssim 0.1$ and by tuning $c_{1},c_{2}$ closer to the BF instability
line.

The effect of the noise on the kinetic roughening properties of the phase is
again encoded in the scale-dependent correlation time $\tau_{\alpha}(k)$, with
$\alpha=C(\tau_{\alpha},k)/C(k,0)\in(0,1]$ (which is a slight generalization
of the $\tau_{1/2}$ defined in Sec. III.2 corresponding to $\alpha=0.5$). We
show in Fig. 4 the behavior of
$\bar{\tau}=\langle\tau_{\alpha}\rangle_{\alpha}$, where an average over
$0.3\leq\alpha\leq 0.6$ is performed in order to increase the statistics.
First, we find that the IB regime with $z=1$ is always present at the
intermediate scales, robust to the addition of a small noise. Let us now
comment on the behavior at the large scales (small $k$ modes). For the
smallest value of the noise $\sigma=0.01$, they follow the same scaling as for
the deterministic case, i.e. we identify the EW regime with $\bar{\tau}\sim
k^{-2}$. At intermediate noise, here $\sigma=0.05$, the EW regime is replaced
by the KPZ one, with $\bar{\tau}\sim k^{-3/2}$. This corroborates the results
found for the KS equation when adding noise. However, for stronger noise, here
$\sigma=0.10$, the large scale behavior is affected by the presence of
defects, which eventually destroy the KPZ regime, since the phase can no
longer be unwrapped. In this regime we find $\bar{\tau}\simeq$ constant as
expected in presence of vortices. In fact, as shown in Refs. [37, 38], since
defects are formed in randomly located space-time points, the phase
trajectories are characterized by a finite homogeneous density of uncorrelated
phase jumps. As a result, at length scales beyond the average vortex distance
$l_{v}$, the phase dynamics can be interpreted as the result of a random
deposition process, implying a scale-independent correlation time, i.e.
$\tau(k\lesssim 2\pi/l_{v})\sim$ constant.

In order to fully characterize the KPZ regime for the intermediate noise
value, we proceed as for the IB regime. We select the low modes for which
$\bar{\tau}\sim k^{-3/2}$, and compute the full correlation $C(t,k)$ function
in this window, shown in Fig. 5. The level lines are now observed at constant
$y=k^{3/2}t$ as expected for the KPZ regime. Moreover, a very good collapse is
obtained, and the scaling function extracted from the numerical data compares
accurately with the exact KPZ scaling function $f^{\rm KPZ}$ of Ref. [27].
Thus, our results show that adding a noise, provided it is small enough to
prevent the proliferation of defects, allows one to observe the KPZ scaling
regime without having to resort to very large system sizes. This confirms that
the phase turbulence of the CGLE equation belongs to the KPZ universality
class. Moreover, the IB regime systematically appears at intermediate scales,
and is an intrinsic feature of this system. Its origin can be traced to the
necessary vanishing of the effective viscosity to crossover from a negative
microscopic value to an effective positive value at large scales.

##  IV  Conclusions and perspectives

We have studied the phase turbulence of the deterministic complex Ginzburg
Landau equation in one spatial dimension, focusing on the statistical behavior
of the large and intermediate wavelength modes. In this regime, the phase
dynamics maps to the Kuramoto-Sivashinsky equation. This chaotic dynamics
results in an effective noise, and generates an effective positive viscosity
at large scales. These elements, together with the intrinsic non-linearity of
the phase dynamics, yield that the critical behavior of the CGLE belongs to
the 1D KPZ universality class. In our numerical simulations, we have first
recovered the known results, namely we observe at large scales the EW scaling
expected for the system size considered, smaller than the typical size
necessary for the KPZ behavior to settle.

Focusing on the scales intermediate between the wavelength of the instability
pattern and the onset of the EW (KPZ) behavior, we have evidenced the
emergence of an additional, distinct scaling regime, characterized by the
dynamical exponent $z=1$. We have argued that this regime corresponds to the
inviscid limit of the KPZ equation, which has recently been shown to be
controlled by a genuine fixed point, the inviscid Burgers one, of the KPZ
equation in one dimension. Indeed, while the viscosity crosses over from a
negative value at the microscopic scale in the KS equation to a positive value
at the macroscopic scale in the effective KPZ equation, it has to vanish at
some intermediate scale. This generates a region of scales with vanishingly
small viscosity, and these scales are inherently controlled by the IB fixed
point. This explains the systematic appearance of the IB scaling $z=1$ in the
CGLE, and KS equation.

We have also considered the noisy version of the CGLE, widely used in the
context of driven-dissipative quantum fluids. By focusing on the weakly
unstable region of the parameter space, we have shown that the KPZ scaling
could be observed, enhanced by the presence of the noise, although the region
of validity of the phase description shrinks due to noise-activated defects.
This result allows us, on the one hand, to confirm that the phase turbulent
regime of the CGLE belongs to the KPZ universality class. On the other hand,
it represents a yet unexplored regime of the noisy CGLE, for which the weakly
unstable regime (phase turbulence) is found to be resilient to a small noise.
This opens up the route to potential applications to generic open systems in
which the microscopic fluctuations are not negligible in the hydrodynamical
description, such as exciton-polariton condensates.

###### Acknowledgements.

We acknowledge Nicolás Wschebor and Marc Brachet for insightful discussions.
F.V. acknowledges the support from France 2030 ANR QuantForm-UGA and from the
Laboratoire d’excellence LANEF in Grenoble (ANR-10-LABX-51-01). A.M.
acknowledges funding from the Quantum-SOPHA ANR Project ANR-21-CE47-0009-02.
L.C. acknowledges support from Institut Universitaire de France (IUF).

##  Appendix A Stability analysis

The stability of the homogeneous rotating solution $\psi_{0}=e^{-ic_{2}t}$ is
studied by considering the linearized evolution of plane waves on top of
$\psi_{0}$. The dispersion is given by

$\displaystyle\omega^{\pm}(k)=$ $\displaystyle-i(1+k^{2})\;\pm$
$\displaystyle\pm$
$\displaystyle\sqrt{-(1+k^{2})^{2}+2(1+c_{1}c_{2})k^{2}+(1+c_{1}^{2})k^{4}}\,.$

We define $\omega^{\pm}(k)=\epsilon^{\pm}(k)+i\gamma^{\pm}(k)$, where a
positive growth rate $\gamma^{\pm}$ gives the instability condition. For small
enough $k$, the square-root is purely imaginary. The rate $\gamma^{-}(k)$ is
always negative, we thus focus on $\gamma^{+}(k)$ and expand it up to fourth
order in $k$ to obtain

$\displaystyle\gamma^{+}(k)$
$\displaystyle=-(1+c_{1}c_{2})k^{2}-\frac{1}{2}c_{1}^{2}(1+c_{2}^{2})k^{4}+...$
$\displaystyle=\nu k^{2}+\tau k^{4}+...$

The instability onset is controlled by the sign of $\nu=1+c_{1}c_{2}$. When
$\nu<0$, some low wavelength modes are unstable, approximately
$0<k<k_{0}=\sqrt{\nu/\tau}$.

##  Appendix B Phase equation

In this Appendix, we detail the mapping from the CGLE to the phase equation.
The CGLE is given by

$i\partial_{t}\psi=i\psi+(c_{2}-i)|\psi|^{2}\psi-(c_{1}-i)\partial_{x}^{2}\psi.$
(10)

In the amplitude-phase representation $\psi=\sqrt{\rho}\;e^{i\theta}$, it
yields the two coupled equations for the amplitude and for the phase

$\begin{cases}\frac{\partial_{t}\rho}{2\rho}&=1-\rho\;+\\\
&+\left\\{\frac{\partial_{x}^{2}\rho}{2\rho}-\frac{\left(\partial_{x}\rho\right)^{2}}{4\rho^{2}}-\left(\partial_{x}\theta\right)^{2}\right\\}-c_{1}\left\\{\partial_{x}^{2}\theta+\frac{\partial_{x}\rho\partial_{x}\theta}{\rho}\right\\}\\\
\partial_{t}\theta&=-c_{2}\rho\;+\\\
&+\;c_{1}\left\\{\frac{\partial_{x}^{2}\rho}{2\rho}-\frac{\left(\partial_{x}\rho\right)^{2}}{4\rho^{2}}-\left(\partial_{x}\theta\right)^{2}\right\\}-\left\\{\partial_{x}^{2}\theta+\frac{\partial_{x}\rho\partial_{x}\theta}{\rho}\right\\}\,.\end{cases}$
(11)

We emphasize that small rigid ($\partial_{x}\,\cdot\,=0$) fluctuations of the
amplitude around 1 have a relaxation time of order 1 (for this choice of
units), while no such time-scale appears explicitly for the phase dynamics.
This is a known consequence of the U(1) symmetry of the CGLE, which leads to
assume that slow phase modulations dominate the fluctuations at the
macroscopic scale. The fast fluctuations of the amplitude around its
stationary homogeneous value can thus be neglected, so that its modulations
can be considered as enslaved to the slow phase dynamics. By inserting the
Ansatz $\rho=1+w(\theta,\partial_{x}^{2}\theta,(\partial_{x}\theta)^{2},...)$
and substituting it into the amplitude equation, one obtains
$w=\left(-c_{1}\partial_{x}^{2}\theta-\left(\partial_{x}\theta\right)^{2}\right)$.
By inserting $w$ into the phase equation, considering linear terms up to order
4, we obtain:

$\partial_{t}\theta=(1+c_{1}c_{2})\partial_{x}^{2}\theta-\frac{c_{1}^{2}}{2}\partial_{x}^{4}\theta+(c_{1}-c_{2})\left(\partial_{x}\theta\right)^{2}+...$
(12)

which is the KS equation with $\nu=1+c_{1}c_{2}$, $\tau=-\frac{c_{1}^{2}}{2}$
and $\lambda=2(c_{1}-c_{2})$. The higher-order nonlinear terms, proportional
to $\partial_{x}\theta\partial_{x}^{3}\theta$ and
$\partial_{x}^{2}\theta(\partial_{x}\theta)^{2}$, have been neglected. They
are considered as unimportant in the long wavelength dynamics, while their
effect is relevant for the short scales, when studying for instance the
divergences which lead to the breakdown of the phase description [5].

We underline that the expression of $\tau$ obtained here is different from the
one obtained from expanding the growth rate $\gamma^{+}(k)$ in perturbations
in Appendix A. The reason of the discrepancy is that $\gamma^{+}(k)$ can be
considered as a phase-like branch only for small $k$. Unlike the pure phase
diffusion $\nu k^{2}$, the order 4 term is affected since at increasing $k$
the off-diagonal perturbations, mixing phase and amplitude, become larger.

## References

  * Manneville [1990] P. Manneville, Dissipative structures and weak turbulence, in  _Chaos — The Interplay Between Stochastic and Deterministic Behaviour_ (Springer Berlin Heidelberg, 1990) pp. 257–272.
  * Cross and Greenside [2009] M. Cross and H. Greenside,  _Pattern Formation and Dynamics in Nonequilibrium Systems_ (Cambridge University Press, 2009).
  * Aranson and Kramer [2002] I. S. Aranson and L. Kramer, The world of the complex Ginzburg-Landau equation, Reviews of Modern Physics 74, 99 (2002).
  * Carusotto and Ciuti [2013] I. Carusotto and C. Ciuti, Quantum fluids of light, Reviews of Modern Physics 85, 299 (2013).
  * Sakaguchi [1990] H. Sakaguchi, Breakdown of the phase dynamics, Progress of Theoretical Physics 84, 792 (1990).
  * Shraiman  _et al._ [1992] B. Shraiman, A. Pumir, W. van Saarloos, P. Hohenberg, H. Chaté, and M. Holen, Spatiotemporal chaos in the one-dimensional complex Ginzburg-Landau equation, Physica D: Nonlinear Phenomena 57, 241 (1992).
  * Chaté [1994] H. Chaté, Spatiotemporal intermittency regimes of the one-dimensional complex Ginzburg-Landau equation, Nonlinearity 7, 185 (1994).
  * Chaté and Manneville [1996] H. Chaté and P. Manneville, Phase diagram of the two-dimensional complex Ginzburg-Landau equation, Physica A: Statistical Mechanics and its Applications 224, 348 (1996).
  * Egolf and Greenside [1995] D. A. Egolf and H. S. Greenside, Characterization of the transition from defect to phase turbulence, Physical Review Letters 74, 1751–1754 (1995).
  * Montagne  _et al._ [1996] R. Montagne, E. Hernández-García, and M. San Miguel, Winding number instability in the Phase-Turbulence regime of the complex Ginzburg-Landau equation, Physical Review Letters 77, 267–270 (1996).
  * Montagne  _et al._ [1997] R. Montagne, E. Hernández-García, A. Amengual, and M. San Miguel, Wound-up phase turbulence in the complex Ginzburg-Landau equation, Phys. Rev. E 56, 151 (1997).
  * Torcini  _et al._ [1997] A. Torcini, H. Frauenkron, and P. Grassberger, Studies of phase turbulence in the one-dimensional complex Ginzburg-Landau equation, Physical Review E 55, 5073 (1997).
  * van Baalen [2004] G. van Baalen, Phase turbulence in the complex Ginzburg-Landau equation via Kuramoto-Sivashinsky phase dynamics, Communications in Mathematical Physics 247, 613 (2004).
  * Kuramoto [1978] Y. Kuramoto, Diffusion-induced chaos in reaction systems, Progress of Theoretical Physics Supplement 64, 346 (1978).
  * Sivashinsky [1977] G. Sivashinsky, Nonlinear analysis of hydrodynamic instability in laminar flames—i. derivation of basic equations, Acta Astronautica 4, 1177 (1977).
  * Hyman  _et al._ [1986] J. M. Hyman, B. Nicolaenko, and S. Zaleski, Order and complexity in the Kuramoto-Sivashinsky model of weakly turbulent interfaces, Physica D: Nonlinear Phenomena 23, 265 (1986).
  * Papageorgiou and Smyrlis [1991] D. T. Papageorgiou and Y. S. Smyrlis, The route to chaos for the Kuramoto-Sivashinsky equation, Theoretical and Computational Fluid Dynamics 3, 15 (1991).
  * Kardar  _et al._ [1986] M. Kardar, G. Parisi, and Y.-C. Zhang, Dynamic scaling of growing interfaces, Physical Review Letters 56, 889 (1986).
  * Burgers [1948] J. Burgers, A mathematical model illustrating the theory of turbulence, in  _Advances in Applied Mechanics Volume 1_ (Elsevier, 1948) p. 171–199.
  * Krug  _et al._ [1992] J. Krug, P. Meakin, and T. Halpin-Healy, Amplitude universality for driven interfaces and directed polymers in random media, Physical Review A 45, 638–653 (1992).
  * Ji  _et al._ [2015] K. Ji, V. N. Gladilin, and M. Wouters, Temporal coherence of one-dimensional nonequilibrium quantum fluids, Phys. Rev. B 91, 045301 (2015).
  * He  _et al._ [2015] L. He, L. M. Sieberer, E. Altman, and S. Diehl, Scaling properties of one-dimensional driven-dissipative condensates, Phys. Rev. B 92, 155307 (2015).
  * Fontaine  _et al._ [2022] Q. Fontaine, D. Squizzato, F. Baboux, I. Amelio, A. Lemaître, M. Morassi, I. Sagnes, L. L. Gratiet, A. Harouri, M. Wouters, I. Carusotto, A. Amo, M. Richard, A. Minguzzi, L. Canet, S. Ravets, and J. Bloch, Kardar–Parisi–Zhang universality in a one-dimensional polariton condensate, Nature 608, 687 (2022).
  * Moca  _et al._ [2023] C. u. u. u. u. P. m. c. Moca, M. A. Werner, A. Valli, T. c. v. Prosen, and G. Zaránd, Kardar-parisi-zhang scaling in the hubbard model, Phys. Rev. B 108, 235139 (2023).
  * Fujimoto  _et al._ [2020] K. Fujimoto, R. Hamazaki, and Y. Kawaguchi, Family-vicsek scaling of roughness growth in a strongly interacting bose gas, Phys. Rev. Lett. 124, 210604 (2020).
  * Takeuchi [2018] K. A. Takeuchi, An appetizer to modern developments on the Kardar–Parisi–Zhang universality class, Physica A: Statistical Mechanics and its Applications 504, 77 (2018).
  * Prähofer and Spohn [2004] M. Prähofer and H. Spohn, Exact scaling functions for one-dimensional stationary KPZ growth, Journal of Statistical Physics 115, 255 (2004).
  * Edwards and Wilkinson [1982] S. F. Edwards and D. R. Wilkinson, The Surface Statistics of a Granular Aggregate, Proc. R. Soc. Lon. A 381, 17 (1982).
  * Majda and Timofeyev [2000] A. J. Majda and I. Timofeyev, Remarkable statistical behavior for truncated Burgers–Hopf dynamics, Proceedings of the National Academy of Sciences 97, 12413 (2000).
  * Cartes  _et al._ [2022] C. Cartes, E. Tirapegui, R. Pandit, and M. Brachet, The Galerkin-truncated Burgers equation: crossover from inviscid-thermalized to Kardar–Parisi–Zhang scaling, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 380, 20210090 (2022).
  * Rodríguez-Fernández  _et al._ [2022] E. Rodríguez-Fernández, S. N. Santalla, M. Castro, and R. Cuerno, Anomalous ballistic scaling in the tensionless or inviscid Kardar-Parisi-Zhang equation, Phys. Rev. E 106, 024802 (2022).
  * Fontaine  _et al._ [2023] C. Fontaine, F. Vercesi, M. Brachet, and L. Canet, Unpredicted scaling of the one-dimensional kardar-parisi-zhang equation, Phys. Rev. Lett. 131, 247101 (2023).
  * Sneppen  _et al._ [1992] K. Sneppen, J. Krug, M. H. Jensen, C. Jayaprakash, and T. Bohr, Dynamic scaling and crossover analysis for the Kuramoto-Sivashinsky equation, Physical Review A 46, R7351 (1992).
  * Cuerno and Lauritsen [1995] R. Cuerno and K. B. Lauritsen, Renormalization-group analysis of a noisy Kuramoto-Sivashinsky equation, Physical Review E 52, 4853 (1995).
  * Ueno  _et al._ [2005] K. Ueno, H. Sakaguchi, and M. Okamura, Renormalization-group and numerical analysis of a noisy Kuramoto-Sivashinsky equation in $1+1$ dimensions, Phys. Rev. E 71, 046138 (2005).
  * Roy and Pandit [2020] D. Roy and R. Pandit, One-dimensional kardar-parisi-zhang and kuramoto-sivashinsky universality class: Limit distributions, Phys. Rev. E 101, 030103 (2020).
  * He  _et al._ [2017] L. He, L. M. Sieberer, and S. Diehl, Space-time vortex driven crossover and vortex turbulence phase transition in one-dimensional driven open condensates, Phys. Rev. Lett. 118, 085301 (2017).
  * Vercesi  _et al._ [2023] F. Vercesi, Q. Fontaine, S. Ravets, J. Bloch, M. Richard, L. Canet, and A. Minguzzi, Phase diagram of one-dimensional driven-dissipative exciton-polariton condensates, Phys. Rev. Res. 5, 043062 (2023).
  * Benjamin [1967] T. B. Benjamin, Instability of periodic wavetrains in nonlinear dispersive systems, Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences 299, 59–76 (1967).
  * Squizzato  _et al._ [2018] D. Squizzato, L. Canet, and A. Minguzzi, Kardar-parisi-zhang universality in the phase distributions of one-dimensional exciton-polaritons, Phys. Rev. B 97, 195453 (2018).
  * Deligiannis  _et al._ [2021] K. Deligiannis, D. Squizzato, A. Minguzzi, and L. Canet, Accessing Kardar-Parisi-Zhang universality sub-classes with exciton polaritons, EPL (Europhysics Letters) 132, 67004 (2021).
  * Vercesi  _et al._ [2024] F. Vercesi, A. Minguzzi, N. Wschebor, and L. Canet, (in preparation) (2024).
  * Ramasco  _et al._ [2000] J. J. Ramasco, J. M. López, and M. A. Rodríguez, Generic dynamic scaling in kinetic roughening, Physical Review Letters 84, 2199–2202 (2000).
  * Family and Vicsek [1985] F. Family and T. Vicsek, Scaling of the active zone in the eden process on percolation networks and the ballistic deposition model, Journal of Physics A: Mathematical and General 18, L75–L81 (1985).
  * Canet  _et al._ [2011] L. Canet, H. Chaté, B. Delamotte, and N. Wschebor, Nonperturbative renormalization group for the kardar-parisi-zhang equation: General framework and first applications, Phys. Rev. E 84, 061128 (2011).
  * Frisch and Bec [2001] U. Frisch and J. Bec, Course 7: “Burgulence”, in  _New Trends in Turbulence_ , Vol. 74, edited by M. Lesieur, A. Yaglom, and F. David (2001) p. 341.
  * Note [1] The winding number, defined as $w=\frac{1}{2\pi}\intop\ilimits@_{0}^{L}\partial_{x}\theta dx$, is thus always zero in our initial conditions. In the phase turbulence regime $w$ is conserved. We exclude the drifted phase turbulence scenario of Ref. [10], obtained by setting $w\not=0$ at $t=0$, in which case the KS dynamics develops on top of a plane wave of wavenumber $k=2\pi w/L$.
  * Grinstein  _et al._ [1996] G. Grinstein, C. Jayaprakash, and R. Pandit, Conjectures about phase turbulence in the complex Ginzburg–Landau equation, Physica D: Nonlinear Phenomena 90, 96 (1996).
  * Wouters and Carusotto [2007] M. Wouters and I. Carusotto, Excitations in a nonequilibrium bose-einstein condensate of exciton polaritons, Phys. Rev. Lett. 99, 140402 (2007).


11institutetext: 1University of Bristol, Bristol BS8 1TH, UK
11email<EMAIL_ADDRESS>
2Schlumberger Cambridge Research Center, Cambridge CB3 0EL, UK
11email<EMAIL_ADDRESS>
# D-VAL: An automatic functional equivalence validation tool for planning
domain models ††thanks: Supported by EPSRC grant EP/P510427/1 in collaboration
with Schlumberger

Anas Shrinah1 Derek Long2 Kerstin Eder1

###### Abstract

In this paper, we introduce an approach to validate the functional equivalence
of planning domain models. Validating the functional equivalence of planning
domain models is the problem of formally confirming that two planning domain
models can be used to solve the same set of problems. The need for techniques
to validate the functional equivalence of planning domain models has been
highlighted in previous research and has applications in model learning,
development and extension. We prove the soundness and completeness of our
method. We also develop D-VAL, an automatic functional equivalence validation
tool for planning domain models. Empirical evaluation shows that D-VAL
validates the functional equivalence of most examined domains in less than
five minutes. Additionally, we provide a benchmark to evaluate the feasibility
and scalability of this and future related work.

##  1 Introduction

Validation of planning domain models is a key challenge in Knowledge
Engineering in Planning and Scheduling (KEPS). Among other tasks, this
activity is concerned with checking the correctness of a planning domain model
with respect to its specification, requirements or any other reference. If the
reference is described informally, then the process of validating the
correctness of domain models is also informal [9]. On the other hand, when the
requirements are described formally, it is feasible to perform formal
validation and to automate this process.

Our research focuses on validating the functional equivalence of planning
domain models. Two planning domain models are functionality equivalent if both
can be used to solve the same set of planning problems. The need for a
technique to analyse planning domain models for functional equivalence has
been highlighted in the literature [11, 12, 9]. One example application is the
evaluation of the quality of planning model learning algorithms [1, 14]. This
can be achieved by using hand-crafted models to generate a number of plans
which are then fed to the model learning method to produce the learnt planning
domain models. The functional equivalence of the original and learnt models is
then checked to evaluate the quality of the learning algorithm.

Another application is to validate that the modifications performed by
optimisation methods that are applied to planning domain models do not alter
the functionality of the original domain. This includes reformulation, re-
representation [13] and tuning [8] of domain models in order to increase the
efficiency of planners using them. Examples of domain reformulation include
macro-learning [10, 3] and action schema splitting [2].

To prove functional equivalence of two planning domains, we introduce a method
that uses a planner to match each operator from one domain with potentially
equivalent macros from the other domain. A Satisfiability Modulo Theories
(SMT) solver is then used to find a consistent and legal mapping between the
predicates of the two domains. Thus, it (constructively) proves the functional
equivalence of two planning domain models. Our algorithm is the VAL [7]
equivalent for validating the functional equivalence of planning domain
models. Hence, we refer to it as D-VAL.

In this paper, we first formally define the functional equivalence of two
planning domain models. We then prove that if two domains are functionally
equivalent, then our method can find a consistent predicate mapping that makes
the two domains functionally redundant. Furthermore, we introduce a test
benchmark covering a range of published domains and perform empirical
experiments on this benchmark to demonstrate the feasibility and scalability
of our method. This work considers typed domains STRIPS subsets of PDDL
without implicit equality predicates.

This paper is organised as follows. 2 contrasts our method with related work.
3 presents planning theory background. 4 introduces the planning domain model
functional equivalence definition and theories. An example is provided in 5. 6
explains our method. 7 reports and discusses the experimental results.
Finally, 8 concludes the paper and suggests future work.

##  2 Related work

Our definition of planning domain model functional equivalence is a relaxed
version of [11] equivalence definition. They defined planning domain model
weak equivalence as a relation between two domains when both can represent the
same set of planning problems and every valid plan that can be produced from
the first domain is also a valid plan in the second domain under a certain
bijective mapping of the components of the two domains.

We relax their definition in two ways. Firstly, we require a bijective mapping
between the predicates only, not between other parts of the domains. Secondly,
we consider planning domain models to be functionally equivalent if they can
solve the same set of planning problems, even if the solutions differ.

In fact, it can be argued that their weak and strong equivalence are
identical. For two domains to produce the same set of plans for the same set
of problems, the directed graphs representing the reachable state space of
both domains must be isomorphic. Isomorphism is a strong bi-simulation
relation. For the directed graphs of the reachable state space of two domains
to be isomorphic, both domains should be identical apart from the names of the
domains’ components. Hence, the requirement to generate the same plans for
every planning problem can be achieved only through strong equivalence.

The logic behind our definition is that if two methods are proven to always
find similar answers for any set of problems, then they can do the same job
regardless of the steps taken by each method. Thus, we consider them
functionally equivalent. With this mindset, we propose our planning domain
model functional equivalence definition. If two domains can be used to solve
the same set of problems (under a certain mapping) regardless of the actions
taken, then we call them functionally equivalent domains. This paper extends
the work in [11] by formally defining planning domain model functional
equivalence, and proposing a method to prove this equivalence. Moreover, we
provide two theories along with their proofs to form the theoretical basis of
our method.

[9] argued the correctness of domain models is an essential factor in the
overall quality of the planning function. They considered a knowledge model to
be a planning domain model and a planning problem instance and suggested to
translate the components of the knowledge model into assertions. A knowledge
model is then defined to accurately capture their requirements, if the
interpretation given by the requirements satisfies the assertions in the
knowledge model.

Our notion of “functional equivalence” is closely related to their notion of
“accuracy”. If two planning domain models are functionally equivalent, then
both domain models satisfy the same requirements and both represent these
requirements to the same degree of accuracy.

In addition to that, [9] outlined an approach to check the accuracy of
operators from a planning domain model with the help of a single planning
instance. Their approach is limited to individual planning instances, whereas
our proposed method is independent from the planning problems. Besides that,
this paper describes a working implementation of our method and it reports on
its feasibility by the means of empirical evaluation.

[4] defined the equivalence of two domains with regards to a planning instance
using graph isomorphism. According to their definition, two domains are
equivalent if the directed graphs representing the reachable state space of
both domains are isomorphic. This criterion proves the equivalence between the
two domains for individual planning instances. On the contrary, our method
proves the functional equivalence for any set of problems. Another subtle
difference is that our method is invariant to the domains' state space paths
as it is weak equivalence, whereas their approach checks strong equivalence.
Hence, their approach is sensitive to any variation in the possible state
space paths between the two domains. The paths sensitivity in their method is
due to the fact that their definition is based on graph isomorphism.
Furthermore, proving isomorphism between two graphs is computationally
dependent on the size of the planning problems, whereas, the computational
cost of our method is dependent only on the size of the given domains.

##  3 Preliminaries

In classical planning, world objects are represented by unique constants which
are the elements of the finite set Obj. The properties of the objects are
described using predicates. Let $P$ be a finite set of the predicates of all
objects of a world.

A state of the world, $s$, is defined by the status of all objects in this
world. The status of an object is defined by the truth evaluation of its
predicates. The state space of a world is the set, $S$, of all states, where
$|S|=2^{\\{\text{number of all ground predicates}\\}}$. False predicates are
not included in the state definition and a closed-world assumption is made.

A planning domain model is a tuple $D=(P,O)$ where $P$ is a set of predicates
and $O$ is a set of operators.

A planning operator, $o$, is a tuple

$\mathit{o=(name(o),pre(o),eff^{-}(o),eff^{+}(o))}$

where $name(o)=op\ name(x_{1},\ldots,x_{k})$, $op\ name$ is a unique operator
name and $x_{1},\ldots,x_{k}$ are variable symbols (arguments) appearing in
the operator, and $pre(o),\mathit{eff}^{-}(o)$ and $\mathit{eff}^{+}(o)$ are
sets of (ungrounded) predicates, specifying preconditions, negative and
positive effects, respectively, with variables taken only from
$x_{1},\ldots,x_{k}$.

An action is a ground instance of an operator. Actions are instantiated from
operators by grounding the predicates of the operators, i.e. by substituting
their variables with objects.

An action name is the same as the name of the operator from which the action
has been instantiated. An action's precondition, positive effect and negative
effects are sets of ground predicates. Action $a$ is applicable in state $s$
iff $pre(a)\subseteq s$. The application of $a$ in $s$ results in the
successor state $\gamma(s,a)=(\mathit{s\setminus eff^{-}(o))\cup eff^{+}(o)}$
provided that $a$ is applicable in $s$.

##  4 Definitions and theorems

The functionality of a planning domain model is characterised by the set of
planning problems that can be solved using this domain. For a domain to be
able to solve a planning problem, it has to be able to produce the required
transitions in the state space from the initial state to one of the goal
states. Thus, a domain model can be described by the set of transitions that
can be produced by this domain model for a given planning problem. For a given
set of objects, we call the set of all transitions for a domain model the
reach set of this domain. Defining the reach set of a planning domain model
requires the following definitions.

###### Definition 4.1

_The reach set of an operator_ $o$ over a set of objects Obj is defined using
the set of actions $A_{\\{o,Obj\\}}$ which is instantiated from the operator
$o$ with the set of objects Obj as $\Gamma(o,Obj)=\\{(s,\gamma(s,a))\mid s\in
S,\ a\in A_{\\{o,Obj\\}}\text{ and }a\text{ applicable in }s\\}$.

###### Definition 4.2

_The reach set of a sequence of operators_ $seq$ over a set of objects Obj is
defined using the set of action sequences $\Pi_{\\{seq,Obj\\}}$ which are
instantiated from the sequence of operators $seq$ with the set of objects Obj
as $\Gamma(seq,Obj)=\\{(s,\gamma(s,\pi))\mid s\in S,\
\pi\in\Pi_{\\{seq,Obj\\}}\text{ and }\pi\text{ applicable in }s\\}$. Where
$\gamma(s,\pi)$ is the successor state of a state $s$ when the sequence $\pi$
of actions is applied. A sequence of operators could consist of a single or
many operators where some items can be repeated.

###### Definition 4.3

The _reach set of a planning domain model_ $D$ over a set of objects Obj is
then defined as: $\Gamma(D,Obj)=\bigcup_{seq\in Seq}\Gamma(seq,Obj)$, where
$Seq$ is the set of all possible sequences of operators generated from $D$.

Now we can informally define planning domain model functional equivalence. Two
planning domains $D_{1}$ and $D_{2}$ are _functionally equivalent_ if and only
if there is a bijective mapping from the predicates of $D_{1}$ to the
predicates of $D_{2}$ such that when the predicates of $D_{1}$ are substituted
with the predicates from $D_{2}$ using the predicate mapping, the reach set of
each domain is equal to the reach set of the other domain for any set of
objects.

###### Definition 4.4

Two planning domain models $D_{1}=(P_{1},O_{1})$ and $D_{2}=(P_{2},O_{2})$ are
_functionally equivalent_ , $D_{1}\equiv_{\mathit{Func}}D_{2}$, iff:

  1. 1.

$\exists f:P_{1}\rightarrow P_{2}\ \text{where $f$ is a bijective function.}$

  2. 2.

$D^{\prime}_{1}=\Theta(D_{1})$ where $\Theta$ is a substitution function that
substitutes the predicates $P_{1}$ in $D_{1}$ with $f(P_{1})$.

  3. 3.

$\forall Obj:\ \Gamma(D^{\prime}_{1},Obj)=\Gamma(D_{2},Obj)$.

The following theorems are essential for us to prove the correctness of our
planning domain model functional equivalence method.

###### Theorem 4.1

For a set of objects and two planning domain models, $D_{1}$ and $D_{2}$, with
the same set of predicates, the reach set of the planning domain model $D_{1}$
is a subset of the reach set of the planning domain model $D_{2}$ if and only
if the reach set of each operator from the domain $D_{1}$ is a subset of the
reach set of a sequence of operators from the domain $D_{2}$.

Formally, for two planning domain models $D_{1}=(P_{1},O_{1})$ and
$D_{2}=(P_{2},O_{2})$ with the same set of predicates and a set of objects
Obj, $\Gamma(D_{1},Obj)\subseteq\Gamma(D_{2},Obj)$ if and only if for all
$o^{\prime}\in O_{1}$, there exists $seq=\langle
o_{0},o_{1},\dots,o_{n}\rangle$, where $o_{i}\in O_{2}$, such that
$\Gamma(o^{\prime},Obj)\subseteq\Gamma(seq,Obj)$.

To prove this theorem, the biconditional is broken into forward and backward
implications that are proven separately. For brevity, the set Obj is dropped
from the reach set notation in the proofs as it is common to all reach sets.

First, we prove the forward implication:
$\Gamma(D_{1})\subseteq\Gamma(D_{2})\implies$ for all $o^{\prime}\in O_{1}$,
there exists $seq=\langle o_{0},o_{1},\dots,o_{n}\rangle$, where $o_{i}\in
O_{2}$, such that $\Gamma(o^{\prime})\subseteq\Gamma(seq)$.

###### Proof

The contrapositive of the forward implication is there exists $o^{\prime}\in
O_{1}$ such that for all $seq=\langle o_{0},o_{1},\dots,o_{n}\rangle$, where
$o_{i}\in O_{2}$, $\Gamma(o^{\prime})\not\subseteq\Gamma(seq)$
$\implies\Gamma(D_{1})\not\subseteq\Gamma(D_{2})$.

Since both reach sets of operators and sequences are sets of transitions, we
have

$\displaystyle\exists t\in S^{2}:t\in\Gamma(o^{\prime})\implies
t\not\in\Gamma(seq).$ (1)

As $seq$ is quantified over all possible sequences $Seq_{2}$ from $D_{2}$, the
right-hand side of (1) can be rewritten as

$\displaystyle t\not\in\bigcup_{seq\in Seq_{2}}\Gamma(seq).$ (2)

From Definition 4.3, we infer

$\displaystyle t\not\in\Gamma(D_{2}).$ (3)

From the left-hand side of (1) and because the reach set of any operator is
contained in the reach set of its domain as per Definition 4.3, we deduce

$\displaystyle t\in\Gamma(D_{1}).$ (4)

The implication in (1) can therefore be rewritten as

$\displaystyle\exists t\in S^{2}:t\in\Gamma(D_{1})\implies
t\not\in\Gamma(D_{2}).$ (5)

Thus, $\Gamma(D_{1})\not\subseteq\Gamma(D_{2})$. This proves the
contrapositive of the forward implication of Theorem 4.1.

Second, we prove the backward implication: For all $o^{\prime}~{}\in~{}O_{1}$,
there exists $seq=\langle o_{0},o_{1},\dots,o_{n}\rangle$, where $o_{i}\in
O_{2}$, such that
$\Gamma(o^{\prime})\subseteq\Gamma(seq)\implies\Gamma(D_{1})\subseteq\Gamma(D_{2})$.

###### Proof

Let $D_{3}=(P_{3},O_{3})$ be a planning domain model where
$P_{3}=P_{1}=P_{2}$, and the set of its operators $O_{3}=\\{seq:seq\in
Seq_{2},\forall\ o^{\prime}\in
O_{1}:\Gamma(o^{\prime})\subseteq\Gamma(seq)\\}$. From the construction of
$O_{3}$, we have $O_{3}\subseteq Seq_{2}$, thus
$\Gamma(D_{3})\subseteq\Gamma(D_{2})$. Furthermore, the definition of $O_{3}$
implies $\Gamma(O_{1})\subseteq\Gamma(O_{3})$, which means any transition made
by $D_{1}$ can be matched by a transition made by $D_{3}$. Thus we have
$\Gamma(D_{1})\subseteq\Gamma(D_{3})$. Therefore,
$\Gamma(D_{1})\subseteq\Gamma(D_{2})$.

Though Theorem 4.1 requires $D_{1}$ and $D_{2}$ to have the same set of
predicates, it can be easily extended to two domains with different predicates
as long as there is a bijective mapping between the predicates of the two
domains.

###### Theorem 4.2

For two planning domain models $D_{1}$ and $D_{2}$ and two bijective functions
$f:P_{1}\rightarrow P_{2}$ and $g:P_{2}\rightarrow P_{1}$, Let
$D_{1}^{\prime}=f(D_{1})$ be the image of $D_{1}$ using $f$ to substitute its
predicates with those of $D_{2}$ and $D_{2}^{\prime}=g(D_{2})$ be the similar
image of $D_{2}$ under $g$. Then we have for a set of objects Obj:

  1. 1.

$\Gamma(D_{1}^{\prime},Obj)\subseteq\Gamma(D_{2},Obj)$ and
$\Gamma(D_{2}^{\prime},Obj)\subseteq\Gamma(D_{1},Obj)\implies\Gamma(D_{1},Obj)=\Gamma(D_{2}^{\prime},Obj)$
and $\Gamma(D_{1}^{\prime},Obj)=\Gamma(D_{2},Obj)$

  2. 2.

$f=g^{-1}$

###### Proof

First, substitute $D_{1}^{\prime}$ with $f(D_{1})$ and $D_{2}^{\prime}$ with
$g(D_{2})$ in the antecedent of the implication to obtain:

$\displaystyle\Gamma(f(D_{1}))\subseteq\Gamma(D_{2})\text{ and}$ (6)
$\displaystyle\Gamma(g(D_{2}))\subseteq\Gamma(D_{1}).$ (7)

$f(D_{1})$ and $D_{2}$ have the same predicates and the reach set of
$f(D_{1})$ is a subset of the reach set of $D_{2}$. If we rename the
predicates of $f(D_{1})$ and $D_{2}$ in the same way, say using $f^{-1}$, then
$f^{-1}(f(D_{1}))$ and $f^{-1}(D_{2})$ both have the same predicates and the
reach set of $f^{-1}(f(D_{1}))$ is a subset of the reach set of
$f^{-1}(D_{2})$. Therefore,

$\displaystyle\Gamma(D_{1})\subseteq\Gamma(f^{-1}(D_{2}))\text{ and}$ (8)
$\displaystyle\Gamma(D_{2})\subseteq\Gamma(g^{-1}(D_{1})).$ (9)

Since $\Gamma(D_{2}^{\prime})\subseteq\Gamma(D_{1})$ and from (8) we have

$\displaystyle|\Gamma(D_{1})|\geq|\Gamma(g(D_{2}))|\text{ and}$ (10)
$\displaystyle|\Gamma(D_{1})|\leq|\Gamma(f^{-1}(D_{2}))|\text{ respectively}.$
(11)

Since $f$ and $g$ are bijective functions,
$|\Gamma(g(D_{2}))|=|\Gamma(f^{-1}(D_{2}))|=|\Gamma(D_{2})|$. Thus
$|\Gamma(D_{1})|=\Gamma(g(D_{2}))|=|\Gamma(f^{-1}(D_{2}))|$.

$\Gamma(D_{1})$ contains $\Gamma(g(D_{2}))$ as per (7) and both have equal
cardinality, hence:

$\displaystyle\Gamma(D_{1})=\Gamma(g(D_{2})).$ (12)

$\Gamma(D_{1})$ is a subset of $\Gamma(f^{-1}(D_{2}))$ as per (8) and both
have equal cardinality, hence:

$\displaystyle\Gamma(D_{1})=\Gamma(f^{-1}(D_{2})).$ (13)

From (12) and (13) we infer that $\Gamma(g(D_{2}))=\Gamma(f^{-1}(D_{2}))$.
Hence, $g=f^{-1}$. Moreover, (12) can be rewritten as
$\Gamma(D_{1})=\Gamma(D_{2}^{\prime})$. This proves the first part of the
consequent of the implication. Following the same steps we can prove
$f=g^{-1}$ and $\Gamma(D_{2})=\Gamma(D^{\prime}_{1})$.

The concept of a sequence of operators will be referred to as a macro
hereafter. It is useful to define the terms potentially functionally
equivalent and functionally equivalent between a macro and an operator as
follows.

###### Definition 4.5

A macro from domain $D_{1}$ is potentially functionally equivalent to an
operator from domain $D_{2}$ iff the reach set of the macro is equal to the
reach set of the operator for all sets of objects and under a mapping of the
predicates of the macro and the operator.

In addition to the previous conditions, we say the macro is functionally
equivalent to the operator if the predicate mapping is also consistent among
all macros and operators of the two domains.

##  5 Example

This example illustrates the steps required to prove that two domains are
functionally equivalent. A detailed explanation of how each step can be
realised is provided in 6.

Suppose we have two versions of the Rover111Can be obtained from
http://ipc.icaps-conference.org. planning domain model, $D_{1}$ and $D_{2}$.
Let $D_{1}$ be the original version, and $D_{2}$ be a copy of $D_{1}$ with
additional operator “calibrate-take-image-M”. Also let the predicates and
operators of $D_{2}$ be suffixed with “-M”. First, find a list of potentially
functionally equivalent macros from $D_{1}$ for each operator from $D_{2}$. 1
lists some interesting operators in the domain $D_{2}$ with their potentially
equivalent macros from $D_{1}$.

$D_{2}$ | $D_{1}$
---|---
calibrate-take-image-M |  $\langle$ calibrate, take-image $\rangle$
sample-soil-M |  |  $\langle$ sample-soil $\rangle$ or
---
$\langle$ sample-rock $\rangle$
sample-rock-M |  |  $\langle$ sample-soil $\rangle$ or
---
$\langle$ sample-rock $\rangle$
communicate-soil-data-M |  |  $\langle$ communicate-soil-data $\rangle$ ,
---
$\langle$ communicate-rock-data $\rangle$ or
$\langle$ communicate-image-data $\rangle$
navigate-M |  $\langle$ navigate $\rangle$
Table 1: Potentially functionally equivalent macros of some of the $D_{2}$
operators.

The second step is to choose for every operator from $D_{2}$ a macro from the
list of the potentially functionally equivalent macros from $D_{1}$. Each
selection will impose a certain mapping on the predicates of the relevant
$D_{2}$ operator and its respective potential macro. Only when a consistent
mapping among all $D_{2}$ operators and their respective $D_{1}$ macros is
found, can $D_{1}$ and $D_{2}$ be considered functionally equivalent.

To explain the idea of the consistent mapping between the predicates of
$D_{1}$ and $D_{2}$, let us explore how the predicate $\operatorname{(at-M\
?x\ ?p)}$ from the precondition of $\operatorname{sample-soil-M}$ will be
mapped. The preconditions, add effects and delete effects of
$\operatorname{sample-soil-M}$ must be mapped to the predicates of either
$\operatorname{sample-soil}$ or $\operatorname{sample-rock}$ in their
preconditions, add effects and delete effects, respectively. For instance,
predicate $\operatorname{(at-M\ ?x\ ?p)}$ in the precondition of
$\operatorname{sample-soil-M}$ can be assigned to either any one of the
predicates in the precondition of $\operatorname{sample-soil}$, namely
$\operatorname{(at\ ?x\ ?p)}$, $\operatorname{(at-soil-sample\ ?p)}$,
$\operatorname{(equipped-for-soil-analysis\ ?x)}$, $\operatorname{(store-of\
?s\ ?x)}$, $\operatorname{(empty\ ?s)}$, or any one of the predicates in the
precondition of $\operatorname{sample-rock}$, namely $\operatorname{(at?x\
?p)}$ $\operatorname{(at-rock-sample\ ?p)}$, $\operatorname{(equipped-for-
rock-analysis\ ?x)}$, $\operatorname{(store-of\ ?s\ ?x)}$,
$\operatorname{(empty\ ?s)}$.

The options of mapping the predicate $\operatorname{(at-M\ ?x\ ?p)}$ are
further constrained by the options of mapping the predicate
$\operatorname{(at-M\ ?x\ ?y)}$ from $\operatorname{navigate-M}$. This
additional constraint is required because $\operatorname{(at-M\ ?x\ ?p)}$ and
$\operatorname{(at-M\ ?x\ ?y)}$ both have the same name, therefore they must
be assigned to the same predicate in $D_{1}$. The operator
$\operatorname{navigate-M}$ has $\operatorname{navigate}$ as the only
potential macro, see 1. Therefore, the predicate $\operatorname{(at-M\ ?x\
?y)}$ from $\operatorname{navigate-M}$ can be assigned only to
$\operatorname{(at\ ?x\ ?y)}$ from the macro $\operatorname{navigate}$.
Consequently, predicate $\operatorname{(at-M\ ?x\ ?p)}$ in the precondition of
$\operatorname{sample-soil-M}$ would need to be assigned to the predicate
$\operatorname{(at\ ?x\ ?p)}$ specifically. The process of resolving these
constraints ensures a consistent assignment of the predicate with the name
“at” among all operators and their respective potential macros. Only with a
consistent mapping, some of the potential macros will be valid macros and
under the found predicate mapping, they can substitute their relevant
operators.

##  6 Method

We propose a method to prove the functional equivalence between two planning
domain models $D_{1}$ and $D_{2}$. Our method finds at least one functionally
equivalent macro from each domain for every operator in the other domain.
Therefore, in accordance with Theorem 4.1, the reach set of each domain is
proven to be a subset of the reach set of the other domain under a certain
mapping. Consequently, and in agreement with Theorem 4.2, $D_{1}$ and $D_{2}$
will have equal reach sets under a certain mapping. Hence, $D_{1}$ and $D_{2}$
will be functionally equivalent according to Definition 4.4.

###  6.1 Find potential functionally equivalent macros for an operator

To find potential functionally equivalent macros for a given operator, we use
FF planner [6] with a macro building planning domain model, let us call this
domain a meta domain. Our meta domain consists of meta operators which add the
operators of the given domain in a sequential order until the required macro
is reached. For each type in the given domain, a set of constants is added to
the meta domain. The number of these constants is equal to the larger number
of same-type parameters in the considered operator. In our meta planning
problem, the goal is a signature of the required macro. This signature is
specified by the number of predicates in the macro's preconditions, the delete
effects of predicates that are not in the preconditions, the delete effects of
predicates that are in the preconditions and the add effects. We refer to
these values by $\operatorname{prem-count}$, $\operatorname{delm-not-prem-
count}$, $\operatorname{delm-prem-count}$ and $\operatorname{addm-count}$,
respectively. An operator is added to the macro if the macro does not have a
delete effect of one of the preconditions of the considered operator. Every
time an operator is added to the macro, the values of the variables of the
macro signature are updated according to the following rules.

Let the considered operator be $o$ and the macro under construction be $m$.
For all $p$ in $pre(o)$ ($add(o)$), $\operatorname{prem-count}$
($\operatorname{add-count}$) is increased by one and $p$ is added to $pre(m)$
($add(m)$) if $p$ is neither in $add(m)$ nor in $pre(m)$. For all $p$ in
$add(o)$, $\operatorname{delm-not-prem-count}$ ($\operatorname{delm-prem-
count}$) is deceased by one and $p$ is removed from $del(m)$ if $p$ is in
$del(m)$ and not in $pre(m)$ (in $pre(m)$).

For all $p$ in $del(o)$, $p$ is added to $del(m)$ and:

  1. 1.

$\operatorname{addm-count}$ is deceased by one and $p$ is removed from
$add(m)$ if $p$ is in $add(m)$,

  2. 2.

$\operatorname{delm-not-prem-count}$ ($\operatorname{delm-prem-count}$) is
increased by one if either:

    1. (a)

$p$ is in $pre(o)$, in $add(m)$ (not in $add(m)$) and was not in $del(m)$; or

    2. (b)

$p$ is not in $pre(o)$, not in $pre(m)$ (in $pre(m)$) and was not in $del(m)$.

###  6.2 Find consistent and legal mapping between the predicates of two
domains

In the previous section we showed how to find potential functionally
equivalent macros from $D_{1}$ for every operator in $D_{2}$. To find a
consistent and legal mapping from the predicates of $D_{2}$ to the predicates
of $D_{1}$, we task the Z3 SMT solver [5] to find an assignment that satisfies
the following constraints. Firstly, legal mapping constraints:

  1. 1.

Predicates from $D_{2}$ should be mapped to predicates from $D_{1}$ with equal
arity. Semantically, predicates are descriptors of the state of objects (unary
predicates) or relations between two or more objects (binary, ternary or n-ary
predicates). Therefore, mapping predicates from across arity groups, e.g.
mapping a unary predicate (state of one object) to a binary predicate
(relation between two objects), would not make sense in a practical set-up.

  2. 2.

Operators from $D_{2}$ should be matched with macros from $D_{1}$ with the
same number of parameters. Operators are tools that can be applied to some
objects to change their status or relations. Therefore, for macros to be
semantically sound, they should have the same number of parameters as the
operators that they are functionally equivalent to.

  3. 3.

The predicates mapping must be bijective as per Definition 4.4.

Secondly, consistent mapping constraints:

  1. 1.

Predicates in preconditions, add effects and delete effects of operators from
$D_{2}$ should be assigned to predicates in preconditions, add effects and
delete effects of the same potential macro from $D_{1}$, respectively.

  2. 2.

Operators from $D_{2}$ should be matched with one of their functionally
equivalent macros from $D_{1}$.

##  7 Experiment

To demonstrate the feasibility and evaluate the scalability of our method, we
modified some domains from the International Planning Competition (IPC). We
then applied our method to verify the functional equivalence of the original
domains and their modified versions. 2 lists the domains and the applied
modifications. For functionally equivalent macros, our approach returns a
consistent predicate mapping that makes the two domains functionally
redundant. The verdict of functionally inequivalent domains could be either
that no potential functionally equivalent macro can be found for an operator;
or a consistent predicate mapping cannot be found between the potentially
equivalent macros and their respective operators from the two domains.

To manage computing resources, the method is first applied in agile mode and
then, if necessary, in normal mode. In agile mode the planner is allowed 180
seconds time slots to find subsequent macros after it finds the first
potential functionally equivalent macro for an operator. In normal mode, the
planner goes through the entire search space when searching for all potential
functionally equivalent macros for each operator. If no consistent predicate
assignment is found in the agile mode, the method is restarted in the normal
mode.

Our implementation is applicable only to typed domains STRIPS subsets of PDDL
without implicit equality predicates. This has limited the range of IPC
domains that are suitable as inputs to our implementation. The experiments
were run on a 2 x 2.6GHz 8-core Intel E5-2670 chip and 4GB of RAM per core.
The algorithm had a time limit of 30 minutes to terminate.

###  7.1 Results and discussion

The experiments show that our algorithm managed to decide on the functional
equivalence of the small to medium sized domains within a short period of
time. The size of the domain can be linked to the number of its predicates,
operators and the counts of their same-type parameters. The size of a meta
planning problems (the problem of finding potential macros using a meta
domain) is related to the size of the input domains, and is expressed by the
number of grounded meta operators (GMO). The algorithm decided on all domains
with GMO less than 3192 apart from the Rover and Scanalyzer domains with a
deleted operator. In these two cases, our method has to fully explore the
search space of the meta planning problem in the search for a proof of
unsolvability of the problem of finding a potential macro for the deleted
operator.

On the other hand, the algorithm could not terminate within the time limit
when validating two versions of the Freecell domain and one Pipesworld version
with GMOs from 17572. Note that our algorithm managed to terminate for the
Freecell domain against its renamed version. Although this task has a GMO of
17572, our algorithm managed to reach a conclusive decision thanks to using
the agile mode first. The huge increase of the number of grounded meta
operators in association with the input domain size shows that our method
suffers from the state space explosion problem. This is because our method
formulates the task of finding a potential macro as a combinatorial problem.
Additionally, the use of a planner to prove the unsolvability of the meta
planing problems has limited the size of the input domains that can be
validated within the time limit. Searching for all potential macros
necessitates proving unsolvability of the meta planning problem with the goal
of finding one more potential macro. Moreover, the planner using a general
heuristic did not help in reducing the impact of the the curse of
dimensionality.

Domain |  Version |  Eq |  CPU time |  States |  P |  O |  GMO $D_{1}$ / $D_{2}$
---|---|---|---|---|---|---|---
Gripper |  Add macro |  Yes |  0.29 |  2413 |  4 |  3 |  40 / 30
Gripper |  Del Pred. |  No |  0.04 |  43 |  4 |  3 |  (22)
Peg-soliatire |  Add macro |  Yes |  0.43 |  772 |  5 |  3 |  46 / 43
Peg-soliatire |  Del Pred. |  No |  0.12 |  256 |  5 |  3 |  (31)
Blocksworld |  Add macro |  Yes |  0.35 |  1710 |  5 |  4 |  28 / 24
Blocksworld |  Del Pred. |  No |  0.008 |  4 |  5 |  4 |  (20)
Elevator |  Add macro |  Yes |  0.51 |  1710 |  5 |  4 |  40 / 36
Elevator |  Del Op |  No |  0.04 |  2 |  5 |  4 |  26 / 18
Parking |  Add macro |  Yes |  16.73 |  33452 |  5 |  4 |  264 / 96
Parking |  Del Pred. |  No |  1.63 |  14437 |  5 |  4 |  (96)
hiking |  Add macro |  Yes |  127.93 |  352680 |  8 |  7 |  (484)
hiking |  Del Op |  No |  103.68 |  458006 |  8 |  7 |  (404)
floor-tile |  Add macro |  Yes |  113.56 |  380276 |  10 |  7 |  450 / 252
floor-tile |  Del Op |  No |  0.58 |  5764 |  10 |  7 |  216 / 224
ChildSnack |  Add macro |  Yes |  0.51 |  518 |  14 |  6 |  86 / 102
ChildSnack |  Del Op |  No |  0.1 |  89 |  14 |  6 |  (81)
Logistics |  Add macro |  Yes |  270.92 |  3228714 |  10 |  11 |  464 / 338
Logistics |  Del Pred. |  No |  76.73 |  1128360 |  10 |  11 |  356 / 332
CaveDiving |  Add macro |  Yes |  91.35 |  762318 |  15 |  7 |  329 / 297
CaveDiving |  Del Pred. |  No |  4.45 |  49753 |  15 |  7 |  (265)
Rover |  Add macro |  Yes |  750.98 |  74192 |  25 |  9 |  2236 / 2786
Rover |  Del Op |  - |  - |  - |  25 |  9 |  1237 / 2678
Pipesworld |  Add macro |  - |  - |  - |  12 |  6 |  29280 / 480
Pipesworld |  Del Pred. |  No |  6.16 |  30112 |  12 |  6 |  (480)
scanalyzer |  Add macro |  Yes |  747.61 |  6436 |  6 |  4 |  2904 / 3192
scanalyzer |  Del Pred. |  - |  - |  - |  6 |  4 |  (2896)
Freecell |  Add macro |  - |  - |  - |  11 |  10 |  50432 / 17572
Freecell |  rename |  Yes |  956* |  61506 |  11 |  10 |  (17572)
Freecell |  Del Pred. |  - |  - |  - |  11 |  10 |  (17572)

Table 2: Eq: functional equivalence. CPU time (s). States: number of explored
states by the planner. P, O: number of predicates and operators in the tested
domain (original version). GMO: the sum of the number of grounded meta
operators of each macro finding task part of the validation process. GMO
values in parentheses indicate GMO of $D_{1}$ and $D_{2}$ are equal. * Agile
mode time limit set to 11 sec for this experiment.

##  8 Conclusions and future work

Validating the functional equivalence of planning domain models has many
application in KEPS, yet this topic has not received much attention from
researchers. In this paper, we formally defined the concept of functional
equivalence between planning domain models. Additionally, we introduced D-VAL,
an automatic functional equivalence validation tool that uses a planner and an
SMT solver to validate the functional equivalence of planing domain models.
The soundness and completeness of our approach is theoretically proven. For
functionally equivalent domains, D-VAL finds a consistent predicate mapping;
under this mapping the domains are functionally redundant. On the other hand,
for functionally inequivalent domains, D-VAL identifies operators have no
functionally equivalent candidates in the other domain. It also detects cases
when all operators have potentially functionally equivalent macros but an
overall consistent mapping cannot be found.

Our experimental evaluation confirms the feasibility of our method and
presents its scalability limitation. The experiments show that the performance
of our method is impacted when the number of parameters of similar types is
increased in the predicates and the operators of the input domains. This is an
inherent problem in combinatorial search tasks.

As future work, we intend to develop a heuristic to help direct the search for
potential macros. In addition to that we aim to study different methods for
proving the unsolvaiblity of the meta planning problems as our approach
requires all potential macros for all operators to decide on non equivalent
domains. Another suitable research direction is to automatically set the value
of the agile mode time limit. This can be approximated from the GMO of the
meta planning problem.

## References

  * [1] Aineto, D., Jiménez, S., Onaindia, E.: Learning strips action models with classical planning. In: Twenty-Eighth International Conference on Automated Planning and Scheduling (2018)
  * [2] Areces, C., Bustos, F., Domínguez, M.A., Hoffmann, J.: Optimizing planning domains by automatic action schema splitting. In: ICAPS. Citeseer (2014)
  * [3] Botea, A., Enzenberger, M., Müller, M., Schaeffer, J.: Macro-ff: Improving ai planning with automatically learned macro-operators. Journal of Artificial Intelligence Research 24, 581–621 (2005)
  * [4] Cresswell, S.N., McCluskey, T.L., West, M.M.: Acquiring planning domain models using locm. Knowledge Engineering Review 28(2), 195–213 (2013)
  * [5] De Moura, L., Bjørner, N.: Z3: An efficient smt solver. In: International conference on Tools and Algorithms for the Construction and Analysis of Systems. pp. 337–340. Springer (2008)
  * [6] Hoffmann, J., Nebel, B.: The ff planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research 14, 253–302 (2001)
  * [7] Howey, R., Long, D., Fox, M.: Val: Automatic plan validation, continuous effects and mixed initiative planning using pddl. In: 16th IEEE International Conference on Tools with Artificial Intelligence. pp. 294–301. IEEE (2004)
  * [8] Hutter, F., Hoos, H.H., Leyton-Brown, K., Stützle, T.: Paramils: an automatic algorithm configuration framework. Journal of Artificial Intelligence Research 36, 267–306 (2009)
  * [9] McCluskey, T.L., Vaquero, T.S., Vallati, M.: Engineering knowledge for automated planning: Towards a notion of quality. In: Proceedings of the Knowledge Capture Conference. pp. 1–8 (2017)
  * [10] Newton, M.A.H., Levine, J., Fox, M., Long, D.: Learning macro-actions for arbitrary planners and domains. In: ICAPS. vol. 2007, pp. 256–263 (2007)
  * [11] Shoeeb, S., McCluskey, T.: On comparing planning domain models. In: Proceedings of the Annual PLANSIG Conference. pp. 92–94. UK PLANNING AND SCHEDULING Special Interest Group (2011)
  * [12] Vallati, M., Chrpa, L., Cerutti, F.: Towards automated planning domain models generation. In: The 5th Italian Workshop on Planning and Scheduling, 4th December 2013, Turin, Italy. (2013)
  * [13] Vallati, M., Hutter, F., Chrpa, L., McCluskey, T.L.: On the effective configuration of planning domain models. In: International Joint Conference on Artificial Intelligence (IJCAI). AAAI press (2015)
  * [14] Zhuo, H.H., Kambhampati, S.: Action-model acquisition from noisy plan traces. In: Twenty-Third International Joint Conference on Artificial Intelligence (2013)