Alexandre Seuret

Karl H Johansson

Networked control under time-synchronization errors

Keywords: Networked control systems, Time-delay, clocks synchronization errors, Lyapunov-Krasovskii functionals

A robust controller is derived for networked control systems with uncertain plant dynamics. The link between the nodes is disturbed by time-varying communication delays, samplings and timesynchronization. A stability criterion for a robust control is presented in terms of LMIs based on Lyapunov-Krasovskii techniques. A second-order system example is considered and the relation between the admissive bounds of the synchronization error and the size of the uncertainties is computed.

Introduction

Internet technology appears as a natural and cheap way to ensure the communication link in remotely controlled systems [START_REF] Abdallah | Delay effect in the networked control of mobile robot[END_REF][START_REF] Hespanha | A survey of recent results in networked control systems[END_REF][START_REF] Zampieri | A survey of recent results in Networked Control Systems[END_REF]. Today, the available Quality of Service is often good enough for that kind of applications. However, such a communication link constitutes an additional dynamical system, which great influence on stability was already mentioned in the 60's [START_REF] Ferrel | Remote manipulation with transmission delay[END_REF]. Indeed, several dynamics and perturbations (communication delay, real-time sampling, packet dropout and synchronization errors) are unavoidably introduced and have to be taken into account during the design of the control/observation loop.

In the literature, many authors assume that the nodes of the NCS are synchronized [START_REF] Hespanha | A survey of recent results in networked control systems[END_REF]. However the synchronization is an fundamental issue of NCS since ensuring several nodes are synchronized is not easy and some error in it may reduce the performances of the controller [START_REF] Freris | Fundamental Limits on Synchronization of Affine Clocks in Networks[END_REF]. The article focusses on the lake of time-synchronization and provides a robust controller for continuous networked control systems with synchronization error and to parameter uncertainties. A time-delay representation which takes into account the transmission delays, the sampling and the synchronization errors.

Several works on networked controlled systems introduced the question of transmission delays [START_REF] Azorin | Dynamic analysis for a teleoparation system with time delay[END_REF]. It is well known that delays generally lead to unstable behavior [START_REF] Niculescu | Delay Effects on Stability. A Robust Control Approach[END_REF] [START_REF] Richard | Time delay systems: an overview of some recent advances and open problems[END_REF]. Moreover in networked control situations, the delays are basically variable (jitter phenomenon) and unpredictable. This is a source of problem when the classical predictor-based controllers are intended to be applied. These techniques generally need the constant delay, i.e. h i (t) = h i . In the case of variable delays, some researches have used independent-of-delay conditions. Because such i.o.d. conditions may be conservative in general, particular cases such as constant or symmetric delays were considered [START_REF] Eusebi | Force-Reflecting telemanipulators with Time-delay: Stability Analysis and control design[END_REF]. These assumptions refers to the case where the transmission delays are equal, i.e.

h 1 (t) = h 2 (t) = R(t)/2,
where R(t) denotes the round trip time (RTT). Another interesting approach was recently given in [START_REF] Witrant | Remote output stabilization via communication networks with a distributed control law[END_REF], which generalized the predictor techniques to the case of variable delays.

Considering unknown time-varying delays and samplings, some stability and stabilization results, [START_REF] Yue | State feedback controller design for networked control systems[END_REF] have been provided known introducing bounds of the delays and of the sampling interval (h m , h M and T such that 0 ≤ h m ≤ h(t) ≤ h M and such that the difference between two successive sampling instants is less than T ), which is not that restrictive. In this paper, the same assumptions are done to ensure the stability of the NCS using a observer-based controller which extends the controller from [START_REF] Motestruque | Stability of model-based networked control system with time-varying transmission time[END_REF] to the case of time varying delays, synchronization errors and parameter uncertainties.

The present article is organized as follows. Section II concerns the problem formulation providing a presentation of the plant and of the communication. Section III exposes the control strategy. Section IV deals with the stability of the controller. An example is provided in Section V.

Preliminaries

The network control problem is described in Fig. 1. The plant and the controller are connected through a network which induces additional dynamics. It is assumed that the time synchronization of the process and controller clocks is not achieved. Then the time t p given by the plant's clock and the time t c delivered by the controller's clock do not have the same sense. The reference time is given by the plant clock. It means that t c = t p + (t) where corresponds to a timevarying error of synchronization. The features of the plant and the assumptions on the network are described in the following.

Definition of the plant

Consider the uncertain systems:

ẋ(t) = (A + ∆ γ A)x(t) + (B + ∆ γ B)u(t), y(t) = (C + ∆ γ C)x(t). ( 1
)
where x ∈ R n , u ∈ R m and y ∈ R p are, respectively, the state, input and output vectors. The constant and known matrices A, B and C correspond to the

Actuators

Controller Plant

Sensors Network Network Fig. 1: Plant controller through a network nominal behavior of the plant. The (time-varying) uncertainties are given in a polytopic representation:

∆ γ A = γ N i=1 λ i (t)A i , ∆ γ B = γ N i=1 λ i (t)B i ∆ γ C = γ N i=1 λ i (t)C i
where N corresponds to the numbers of vertices. The matrices A i , B i and C i are constant and known. The scalar γ ∈ R characterizes the size of the uncertainties. Note that when γ = 0, no parameter uncertainty is disturbing the system. However the greater the γ, the greater the disturbances. The functions λ i (.) are weighted scalar functions which follow a convexity property, ie. for all i = 1, .., N and for all t ≥ 0: λ i (t) ≥ 0 and N i=1 λ i (t) = 1. It is also assumed that the computation power is low on the plant and its functions are limited to receive control packets, to apply control and to send output measurement data. The computation thus is removed in a centralized controller.

Synchronization and delays models

In addition to parameter uncertainties, the stability of the closed-loop system must be ensured whatever the delays, the possible aperiodicity of the real-time sampling processes and synchronization error. Concerning the transmission delays, the delays are assumed to be non-symmetric but have known minimal and maximal bounds h m and h M , so that:

A1 (maximal allowed delay) : h m ≤ h i (t) ≤ h M .
(

Since we aim at limiting the value of h m , the use of the User Datagram Protocol (UDP) is preferred to Transmission Control Protocol (TCP), the reliability mechanisms of which may needlessly slow down the feedback loop. Another feature of UDP is that the packets do not always arrive in their chronological emission order. The reception function will be added a re-ordering mechanism thanks to some "time-stamps" added in packets. This can be expressed as:

A2 (packet reordering) : ḣi (t) < 1. ( 3
)
Another disturbance implied by the network comes from the samplers and zero-holders. Following the lines of [START_REF] Fridman | Robust Sampled-Data Stabilization of Linear Systems: An Input Delay Approach[END_REF], we consider they produce an additional variable delay t -t k , where t k is the k th sampling instant. Moreover, because of

Reference Actuators

Controller Plant

Observer Sensors Controller Fig. 2: Architecture of the networked controller the operating system, the sampling is generally not periodic. So, we only assume there exists a known maximum sampling interval T so that:

A3 (max. sampling interval) : 0 ≤ t k+1 -t k ≤ T. ( 4
)
Assume the function is time-varying and there exists a known constant ¯ such that:

A4 : | (t)| ≤ ¯ (5)
3 Observer-based networked control

The system architecture is exposed in Fig. 2. The controller has to estimate present state of plant, using output measurements, and to compute the control value which will be sent to the plant.

D1

The control law: The controller computes a control law which considers some set-values to be reached. The static state feedback control u(t) = K x(t) is defined considering the state estimate x given by the observer. The difficulty is to determine a gain K guaranteeing stability despite the delay δ 1 (t). D2 Transmission of the control u: The k th packets sent by the controller to the process includes the designed control u(t 1,k ) and a sampling time t 1,k when it was produced. The plant receives this information at time t r 1,k . This time does not have the same meaning for both parts. The term t r 1,k -t 1,k , corresponding to the transmission delay, corrupted by , is estimated by the plant once the packet has reached it. D3 Receipt and processing of the control data: The control, sent at time t 1,k , is received by the process at time t r 1,k ≥ t 1,k + h m . There is no raison that the controller also knows the time t r 1,k when the control u(t 1,k ) will be injected into the plant input. Finally, there exists k such that h m ≤ t 1,k ≤ h M + T and the process is governed by:

ẋ(t) = (A + ∆ γ A)x(t) + (B + ∆ γ B)u(t 1,k ) (6)
D4 Transmission of the output information: The process have access to its output y only in discrete-time. A packet contains the output y(t

ẋ(t) = Ax(t) + Bu(t 1, k + ) -L(y(t 2,k ) -ŷ(t 2,k -)), ŷ(t) = C x(t). ( 7
)
The design of an observer gain L ensuring stability is not straightforward.

Note that the observation is based on the nominal values of the system definition.

No assumption is introduced to estimate the uncertainties and the λ i functions.

The time stamp t 1, k corresponds to the time where the control input is assumed to be implemented into the plant input. The index k corresponds to the most recent output information the controller has received. The time t r 1,k and the control u(t 1,k ) (see D2) are not known from the observer.

An improve with respect to [START_REF] Seuret | Networked Control using GPS Synchronization[END_REF] is that no buffers are required in the controller. This allows considering the input packets as soon as they arrive.

Stabilization under synchronization error

This section focusses on developing asymptotic stability of the networked control architecture detailed in Fig. 2.

Closed-loop system

The input delay approach to sampled-data signals allows a homogenized definition of the delays δ 1 (t) t -t 1,k where k corresponds to the real sampling implemented in the plant, δ1 (t) t -t 1, k and δ 2 (t) t -t 2,k to be considered. The observer dynamics are then driven by:

ẋ(t) = Ax(t) + Bu(t -δ1 (t) + ) -L(y(t -δ 2 (t)) -ŷ(t -δ 2 (t) -)), ŷ(t) = C x(t), (8)
where the features of the system lead to

h m ≤ δ i (t) ≤ h M + T for i = 1, 2. Equivalently, if the average delay δ(h m , h M , T ) = (h M + T + h m )/2 and the maximum delay amplitude µ(h m , h M , T ) = (h M + T -h m )/2 is used, then: δ -µ ≤ δ i (t) ≤ δ + µ, ∀i = 1, 2. ( 9
)
According to ( 6) and ( 7) and for given k and any t ∈ [t r 1,k + h m , t r 1,k+1 + h m [, there exist k and k such that the global remote system is governed by:

ẋ(t) = (A + ∆ γ A)x(t) + (B + ∆ γ B)K x(t 1,k ), ẋ(t) = Ax(t) + BK x(t 1, k -) -∆ γ LCx(t 2,k ) -LC(x(t 2,k ) -x(t 2,k + )). ( 10
)
Rewriting the equations with the error e(t) = x(t) -x(t), the dynamics become:

ẋ(t) = (A + ∆ γ A)x(t) + (B + ∆ γ B)K(x(t 1,k ) -e(t 1,k )) ė(t) = Ae(t) + LCe(t 2,k ) + ∆Ax(t) + ∆BK(x(t 1,k ) -e(t 1,k )) + ∆ γ LCx(t 2,k ) -BK t 1, k + t 1,k [ ẋ(s) -ė(s)]ds + LC t 2,k t 2,k -[ ẋ(s) -ė(s)]ds.
Applying the input delay representation [START_REF] Fridman | Robust Sampled-Data Stabilization of Linear Systems: An Input Delay Approach[END_REF] yields:

ẋ(t) = (A + ∆ γ A)x(t) + (B + ∆ γ B)Kx(t -δ 1 ) -∆ γ BKe(t -δ 1 ) ė(t) = Ae(t) + ∆ γ Ax(t) + ∆ γ BK(x(t -δ 1 ) -e(t -δ 1 )) + L∆ γ Cx(t -δ 2 ) +LCe(t -δ 2 ) -BK t-δ1+ t-δ1 [ ẋ(s) -ė(s)]ds + LC t-δ2 t-δ2-[ ẋ(s) -ė(s)]ds. ( 11
) with δ 1 (t) = t -t 1,k and δ 2 (t) = t -t 2,k .
From the fact that the communication delays belong to the interval [h m , h M ] where h m and h M are given by the network properties. Then the condition (9) on the delays still holds.

In an ideal case, ie. = 0 (from A2, synchronized case), the C2P delays are assumed to be well known, ie. δ 1 (t) = δ1 (t) (see [START_REF] Seuret | Networked Control using GPS Synchronization[END_REF]) and the model is assumed to be perfectly known and constant (γ = 0). For this ideal case, Theorem 2 and 3 from [START_REF] Seuret | Networked Control using GPS Synchronization[END_REF] deliver controller and observer gains, since the global system is rewritten using the error vector e(t) = x(t) -x(t) as:

ẋ(t) = Ax(t) + BKx(t -δ 1 (t)) -BKe(t -δ 1 (t)) ė(t) = Ae(t) + LCe(t -δ 2 (t))

Stability Criteria

It is now accepted that δ 1 (t) = δ1 (t) and = 0. The stability of the controller and of the observer is not ensured anymore by Theorem 2 and 3 in [START_REF] Seuret | Networked Control using GPS Synchronization[END_REF], as = 0 leads error in the delay measurement. As in equation [START_REF] Richard | Time delay systems: an overview of some recent advances and open problems[END_REF], there are interconnection terms between the two variables x and e, a separation principle is no longer applicable to prove the global stabilization. The stability proof requires to consider now both variables simultaneously.

Theorem 1. For given K and L, suppose that, there exists for q representing the subscript x or e, positive definite matrices : P q1 , S q , R qa , R q , S xe , Q xe and R b and matrices of size n × n: P q2 , P q3 , Z ql for l = 1, 2, 3, Y ql for l = 1, 2 such that the following LMI's hold :

   Θ i x Θ i x12 µP T x A i K P T x A i K µP T x A i K * -Sx + 2R b 0 0 0 * * -µRxa 0 0 * * * -S xe 0 * * * * -µR b    < 0, (12)
    Π i P T e 0 γA i 0 αP T e 0 γB i K 0 (1 + µ)P T e 0 γLC i 0 * -Qxe 0 0 * * -αR b 0 * * * -(1 + µ)R b     < 0, ( 13
) Rq Yq1 Yq2 * Z q1 Z q2 * * Z q3 ≥ 0, q ∈ {x, e}, ( 14
)
where α = (1 + 2µ), β = 2(µ + ¯ ), P q = P q1 0 Pq2 Pq3 and

Π i =      Θe Θ i e12 µP T e A L ¯ P T e A L ¯ P T e A L βP T e A K βP T e A K * -Se + Sxe 0 0 0 0 0 * * -µR ea 0 0 0 0 * * * -¯ R e 0 0 0 * * * * -¯ R x 0 0 * * * * * -βRe 0 * * * * * * -βRx      Θ x12 = P T x A i K -Y T x1 Y T x2 , Θ e12 = P T e 0 LC -γBiK -Y T e1 Y T e2 , Θ i x = Θ ni x + Qxe 0 0 2βRx + 4µR b , Θ e = Θ n e + 0 0 0 2βRe + 4µR b , Θ ni x = P T x 0 I Āi -I + 0 I Āi -I T P x + Sx + Yx1 + Y T x1 + δZx1 Yx2 + δZx2 * δRx + 2µRxa + δZx3 , Θ n e = P T e 0 I A -I + 0 I A -I T P e + Se + Ye1 + Y T e1 + δZe1 Ye2 + δZe2 * δRe + 2µRea + δZe3 ,
and where

A K = 0 BK , A i K = 0
BiK and A L = 0 LC . Then, the NCS ( 10) is asymptotic stable.

The proof of Theorem 3 is given in the appendix.

Remark 1. Theorem 1 guarantees the robust stability of the global remote to be guaranteed system with respect to the synchronization error and for observer and controller gains given in [START_REF] Seuret | Networked Control using GPS Synchronization[END_REF]. Since the problems of designing observer and controller gains are dual, to develop constructive LMI's is not straightforward.

Application to a mobile robot

This study is illustrated on the model of a mobile robot (Slave) which can move in one direction. The identification phase gives the following dynamics:

ẋ = 0 1 0 -11, 32 -ζγ x + 0 -11, 32 + ζγ u(t -δ 1 ), y = [ 1 + ζγ/10 0 ] x, ( 15
)
where the scalar function ζ(t) lies in [-1, 1] and is taken as

ζ(t) = sin(6t).
The characteristics of transmission delays in a classical network (between Lens and Lille in France (50km)) allows h m = 0, 1s and h M = 0.4s. Consider now that the bandwidth of the network allows the sampling period as T = 0.1s to be defined. For these values, Theorems 2 and 3 in [START_REF] Seuret | Networked Control using GPS Synchronization[END_REF] produce the following gains L = [ -0.9119 -0.0726 ] T and K = [ -0.9125 -0.0801 ]. This gains ensures that, in the ideal case the remote system is α-stable for α x = α e = 1.05. Theorem 1 ensures that, with these features, the global system is asymptotically stable and robust without any time-varying synchronization error less than ¯ = 0.04s in [START_REF] Freris | Fundamental Limits on Synchronization of Affine Clocks in Networks[END_REF] for γ = 0. Figure 3 shows the the maximal admissive ¯ for greater values Figure 4a shows the simulation results for γ = 0.1 and = 0.03 (point (2) in Figure 3). The state of the process and the sampled input and output are provided. It can be seen that the state convergence to the reference. The stability of the system despite the synchronization error and the parameters uncertainties is ensured.

Figure 4b present simulations for γ = 0 and = 0 (point ( 1)) and for γ = 1.5 and = 0.03 (point (3)). In comparison to Figure 4a, the results for (1) are closed to the ones obtained for [START_REF] Azorin | Dynamic analysis for a teleoparation system with time delay[END_REF]. Concerning (3), Theorem 1 does not ensure the stability. However the controller still stabilize the system. It means that the conditions from Theorem 1 are conservative. Further results would investigate in reducing the conservativeness of the stability conditions.

Concluding remarks

This paper presents a strategy for an observer-based control of a networked controlled systems under synchronization erros. No buffering technique was involved, which allows using the available information as soon as received. Various perturbations were dealt with jittery, non-symmetric and unpredictable delays, synchronization error, aperiodic sampling (real-time) and uncertainties in the model. A remaining assumption in [START_REF] Seuret | Networked Control using GPS Synchronization[END_REF] which is that the clocks have to be synchronized is not required anymore.

A characteristic feature of this control strategy is to consider that the observer based controller runs in continuous time (i.e., with small computation step) whereas the process provides discrete-time measurements. Thus, the observer keeps on providing a continuous estimation of the current state, even if the data are not sent continuously.

r(t) x 1 (t) x 2 (t) r(t) x 1 (t) x 2 (t)
(b) Simulations for ( 1) and ( 3)

Fig. 4: Simulation results

The proposed conditions are conservative. New and less conservative results which guarantee stability of system with sampled-data control recently appears and might help in reducing the conservativeness. It would be interesting to apply these new technics on the present system.

A Proof of Theorem 1

To analyze the asymptotic stability property of such a system, equations [START_REF] Richard | Time delay systems: an overview of some recent advances and open problems[END_REF] are rewritten by using the descriptor representation [START_REF] Fridman | A descriptor system approach to H ∞ control of linear time-delay systems[END_REF] with x(t) = col{x(t), ẋ(t)}, ē(t) = col{e(t), ė(t)}. In this section, when there is no confusion, any function considered at time 't' will be written without '(t)'. Consider the Lyapunov-Krasovskii (LK) functional: [START_REF] Zampieri | A survey of recent results in Networked Control Systems[END_REF] where the sub-LK functionals are, for q representing the subscript of the variables 'x' and 'e': V qn = qT EP q q + 0 -δ t t+θ qT (s)R q q(s)dsdθ + t t-δ q T (s)S q q(s)ds,

V = V xn + V xa + V x + V en + V ea + V e + V xe
V qa = µ -µ t t+θ-δ qT (s)R qa q(s)dsdθ, V q = 2 µ+¯ -µ-¯ t t+θ-δ qT (s)R q q(s)dsdθ V qb = 2 µ -µ t t+θ-δ qT (s)R b q(s)dsdθ
with E = diag{I n , 0} and P x , P e defined in Theorem 1.

The signification of each sub-LK functional has to be explain. The first functionals V xn and V en deal with the stability of the Slave and the observer systems subject to the constant delay δ while V xa and V ea refer to the disturbances due to the delay variations. Even if the functionals do not explicitly depend on each time varying delay, it will be considered both different delays δ 1 and δ 2 . The functionals V q are concerned with synchronization errors. The last functionals V qb deals with the interconnection between the variables x and e. Consider as a first step, the polytopic representation of the dynamics in x:

ẋ = N i=1 λ i Āi x + Bi K(x(t -δ 1 ) -e(t -δ 1 )) (17)
where Āi = A + γA i and Bi = B + γB i . According to Theorem 2 in [START_REF] Seuret | Sampled-data exponential stabilization of neutral systems with input and state delays[END_REF], if LMI ( 14) holds for q = x and for all vertices of the polytopic system, the following inequality holds:

Vxn + Vxa ≤ N i=1 λ i ξ T x Ψ i x1 Θ i x12 * -S x ξ x + η i x ( 18
)
where ξ x = col{x, ẋ, x(t -δ)} and:

η i x = -2x T P T x A i K e(t -δ 1 ), Ψ i x1 = Θ ni x + µP T x A i K R -1 xa A iT K P x .
Using the Leibnitz formula and a classical LMI bounding, it yields, for i = 1, 2:

η i x ≤ xT P T x A i K (S -1 xe + µR -1 b )A iT K P x x +e T (t -δ)S xe e(t -δ) + | t-δ t-δ1 ėT (s)R b ė(s)ds| (19)
where S xe and R b are positive definite matrices which represent the presence of the error vector in the state equation. Then, the following inequality holds:

Vxn + Vxa ≤ N i=1 λ i ξ T x Ψ ni x2 Θ i x12 * -S x ξ x +e T (t -δ)S xe e(t -δ) + | t-δ t-δ 1 ėT (s)R b ė(s)ds|, (20)
where

Ψ ni x2 = Θ ni x + P T x A i K (S -1 xe + µR -1 xa + µR -1 b )A iT K P x .
Concerning the errors dynamics, differentiating V en + V ea along the trajectory of [START_REF] Richard | Time delay systems: an overview of some recent advances and open problems[END_REF] and assuming that LMI [START_REF] Witrant | Remote output stabilization via communication networks with a distributed control law[END_REF] holds with q = e yields:

Ven + Vea ≤ N i=1 λ i {ξ T e Ψe1 P T e A L -Y T e * -Se ξ e -η x e1 +η e e1 -η x e2 + η e e2 + η xi ∆A + η xi ∆B + η ei ∆B + η xi ∆C , (21)
where ξ e = col{e, ė, e(t -δ)} and where

Ψ e1 = Θ n e + µP T e A L R -1 ea A iT L P e , η q e1 = 2ē T P T e A K t 1, k + t 1,k q(s)ds, η q e2 = -2ē T P T e A L t 2,k t 2,k -q(s)ds, η xi ∆A = 2ē T P T e [ 0 γA T i ] T x, η xi ∆B = 2ē T P T e [ 0 γ(B i K) T ] T x(t -δ 1 ), η ei ∆B = -2ē T P T e [ 0 γ(B i K)T ] T e(t -δ 1 ), η xi ∆C = 2ē T P T e [ 0 γ(LC i ) T ] T x(t -δ 1 ),
with q representing either x or e. Note that the functions η q ei , for q ='x','e' and i = 1, 2 correspond to the disturbance due to the synchronization error. Consider i = 1: Noting that from assumption A4, inequality t 1, k + -t 1,k ≤ ¯ + 2µ holds, then a classical bounding leads to:

η x q1 ≤ (¯ + 2µ)ē T P T e A K R -1 q A T K P e ē + t 1, k + t 1,k qT (s)R q q(s)ds. ( 22
)
By the same way, the following inequalities hold:

η q e2 ≤ ¯ ēT P T e A L R -1 q A T L P e ē + t 2,k t 2,k -
qT (s)R q q(s)ds.

(23)

Following the same method as in (19), the following inequalities hold: Differentiating V x , V e , V xb and V eb leads to: Vq = 2β qT R q q -2 t-δ+µ+¯ t-δ-µ-¯ qT (s)R x q(s)ds Vqb = 4µ qT R b q -2 t-δ+µ t-δ-µ qT (s)R b q(s)ds,

Combining (20), ( 25) and (26) and noting that the sum of the negative integrals in (26) with the integrals from (23) is negative, the following inequality holds: Then the Schur complement leads to the LMI's given in [START_REF] Seuret | Sampled-data exponential stabilization of neutral systems with input and state delays[END_REF] and [START_REF] Seuret | Networked Control using GPS Synchronization[END_REF]. Then LMI's from Theorem 1 are satisfied, the system (11) is asymptotically stable.

V ≤ N i=1 λ i ξ T x Ψ i x Θ xi

Fig. 3 :

 3 Fig. 3: Maximal synchronization error with respect to the disturbances

  Simulation results for γ = 0.1 and = 0

P

  e ē + x T Q xe x, η xi ∆B ≤ (1 + µ)ē T P T (t -δ)R b x(t -δ) + | t-δ t-δ 1 ẋT (s)R b ẋ(s)ds|, η ei ∆B ≤ µē T P )R b ė(s)ds|, η xi ∆C ≤ (1 + µ)ē T P T (t -δ)R b x(t -δ) + | t-δ t-δ2 ẋT (s)R b ẋ(s)ds|. (24)Finally, the following inequality holds:Ven + Vea ≤ ξ T e Ψ n e2 Θ ei 12 * -S e + R b ξ e + x T Q xe x +2x T (t -δ)R b x(t -δ) -2ē T P T e 0 γB i K e(t -δ) +| t-δ t-δ2 ẋT (s)R b ẋ(s)ds| + q=x,e | t-δ t-δ1 qT (s)R b q(s)ds| + t 1, k + t 1,k qT (s)R qp q(s)ds + t 2,k t 2,k - qT (s)R qp q(s)ds) ,(25)whereΨ n e2 = Θ n e + P T e A L (µR ea + ¯ R -1 x + ¯ R -1 e ) -1A T L P e +βP T e A K (R -1x + R -1 e )A T K P e + P

  12 * -S x + Rex ξ x + ξ T e Ψ e Θ ei 12 * -S e + S xe ξ e where Ψ i x = Ψ ni x2 + 0 0 0 2βR x + 4µR b , and Ψ e = Ψ n e + 0 0 0 2βR e + 4µR b .

  2,k ) and the sampling time t 2,k . The controller receives the output packet at time t r 2,k . D5 Observation of the process: For a given k and any t ∈ [t 1, k + (h Mh m )/2, t 1, k+1 + (h M -h m )/2[, there exists a k such that:

This work was supported by the European project FeedNetBack (http://www.feednetback.eu/)


Michael Katz

Joerg Hoffmann

Malte Helmert

Jörg Hoffmann

Jörg Hoffmann

How to Relax a Bisimulation?

Keywords: artificial intelligence, planning, heuristic search intelligence artificielle, planification, recherche heuristique

Merge-and-shrink abstraction (M&S) is an approach for constructing admissible heuristic functions for cost-optimal planning. It enables the targeted design of abstractions, by allowing to choose individual pairs of (abstract) states to aggregate into one. A key question is how to actually make these choices, so as to obtain an informed heuristic at reasonable computational cost. Recent work has addressed this via the well-known notion of bisimulation. When aggregating only bisimilar states -essentially, states whose behavior is identical under every planning operator -M&S yields a perfect heuristic. However, bisimulations are typically exponentially large. Thus we must relax the bisimulation criterion, so that it applies to more state pairs, and yields smaller abstractions. We herein devise a fine-grained method for doing so. We restrict the bisimulation criterion to consider only a subset K of the planning operators. We show that, if K is chosen appropriately, then M&S still yields a perfect heuristic, while abstraction size may decrease exponentially. Designing practical approximations for K, we obtain M&S heuristics that are competitive with the state of the art.

Introduction

Heuristic forward state-space search with A * and admissible heuristics is a state of the art approach to cost-optimal domain-independent planning. The main research question in this area is how to derive the heuristic automatically. That is what we contribute to herein. We design new variants of the merge-andshrink heuristic, short M&S, whose previous variant [START_REF] Nissim | The Merge-and-Shrink planner: Bisimulationbased abstraction for optimal planning[END_REF] won a 2nd price in the optimal planning track of the 2011 International Planning Competition (IPC), and was part of the 1st-prize winning portfolio [START_REF] Helmert | Fast Downward Stone Soup[END_REF].

M&S uses solution cost in a smaller, abstract state space to yield an admissible heuristic. The abstract state space is built incrementally, starting with a set of atomic abstractions corresponding to individual variables, then iteratively merging two abstractions (replacing them with their synchronized product) and shrinking them (aggregating pairs of states into one). In this way, M&S allows to select individual pairs of (abstract) states to aggregate. A key question, that governs both the computational effort taken and the quality of the resulting heuristic, is how to actually select these state pairs. M&S was first introduced for planning by Helmert et al. [START_REF] Helmert | Flexible abstraction heuristics for optimal sequential planning[END_REF], with only a rather naïve method for selecting the state pairs to aggregate. Nissim et al. [START_REF] Nissim | Computing perfect heuristics in polynomial time: On bisimulation and merge-and-shrink abstraction in optimal planning[END_REF] more recently addressed this via the notion of bisimulation, adopted from the verification literature (e. g., [START_REF] Milner | Operational and algebraic semantics of concurrent processes[END_REF]). Two states s, t are bisimilar, roughly speaking, if every transition label (every planning operator) leads into equivalent abstract states from s and t. If one aggregates only bisimilar states, then the behavior of the transition system (the possible paths) remains unchanged. This property is invariant over both the merging and shrinking steps in M&S, and thus the resulting heuristic is guaranteed to be perfect. Unfortunately, bisimulations are exponentially big even in trivial examples, including benchmarks like, for example, Gripper.

A key observation made by Nissim et al. is that bisimulation is unnecessarily strict for our purposes. In verification, paths must be preserved because the to-be-verified property shall be checked within the abstracted system. However, here we only want to compute solution costs. Thus it suffices to preserve not the actual paths, but only their cost. Nissim et al. design a label reduction technique, that changes the path inscriptions (the associated planning operators) but not their costs. This leads to polynomial behavior in Gripper and some other cases, but the resulting abstractions are still much too large in most planning benchmarks. Nissim et al. address this by (informally) introducing what they call greedy bisimulation, which "catches" only a subset of the transitions: s, t are considered bisimilar already if every transition decreasing remaining cost leads into equivalent abstract states from s and t. That is, "bad transitions"those increasing remaining cost -are ignored. This is a lossy relaxation to bisimulation, i. e., a simplification that results in smaller abstractions but may (and usually does) yield an imperfect heuristic in M&S: "bad transition" is defined locally, relative to the current abstraction, which does not imply that the transition is globally bad. For example, driving a truck away from its own goal may be beneficial for transporting a package. Under such (very common) behavior, greedy bisimulation is not invariant across the M&S merging step, because the relevant transitions are not caught.

We herein adopt the same approach for relaxing bisimulation -we catch a subset of the transitionsbut we take a different stance for determining that subset. We first select a subset of labels (operators). Then, throughout M&S, we catch the transitions bearing these labels. This simple technique warrants that the thus-relaxed bisimulation is invariant across M&S. Thanks to this, to guarantee a quality property φ of the final M&S heuristic, it suffices to select a label subset guaranteeing φ when catching these labels in a bisimulation of the (global) state space.

We consider two properties φ: (A) obtaining a perfect heuristic; (B) guaranteeing that A * will not have to search. (A) is warranted by selecting all remaining-cost decreasing operators in the (global) state space. (B) is a generalization that only requires to catch a subset of these operators -those within a certain radius around the goal.

In practice, it is not feasible to compute the label sets just described. To evaluate their potential in principle, we prove that they may decrease abstraction size exponentially, and we run experiments on IPC benchmarks small enough to determine these labels. To evaluate the potential in practice, we design approximation methods. Running these on the full IPC benchmarks, we establish that the resulting M&S heuristics are competitive with the state of the art, and can improve coverage in some domains.

We next give the necessary background. We revisit Nissim et al.'s idea of greedy bisimulation, then introduce our own relaxation principle, evaluate it, and conclude.

Background

A planning task is a 4-tuple Π = (V, O, s 0 , s ⋆ ). V is a finite set of variables v, each v ∈ V associated with a finite domain D v . A partial state over V is a function s on a subset V s of V, so that s(v) ∈ D v for all v ∈ V s ; s is a state if V s = V.
The initial state s 0 is a state. The goal s ⋆ is a partial state. O is a finite set of operators, each being a pair (pre, eff) of partial states, called its precondition and effect. Each o ∈ O is also associated with its cost c(o) ∈ R + 0 (note that 0-cost operators are allowed). A special case we will mention are uniform costs, where c(o) = 1 for all o.

The semantics of planning tasks are defined via their state spaces, which are (labeled) transition systems. Such a system is a 5-tuple Θ = (S, L, T, s 0 , S ⋆ ) where S is a finite set of states, L is a finite set of transition labels each associated with a label cost c(l) ∈ R + 0 , T ⊆ S × L × S is a set of transitions, s 0 ∈ S is the start state, and S ⋆ ⊆ S is the set of solution states. We define the remaining cost h * : S → R + 0 as the minimal cost of any path (the sum of costs of the labels on the path), in Θ, from a given state s to any s ⋆ ∈ S ⋆ , or h * (s) = ∞ if there is no such path.

In the state space of a planning task, S is the set of all states. The start state s 0 is the initial state of the task, and s ∈ S ⋆ if s ⋆ ⊆ s. The transition labels L are the operators O, and (s, (pre, eff), s ′ ) ∈ T if s complies with pre, and s

′ (v) = eff(v) for all v ∈ V eff while s ′ (v) = s(v) for all v ∈ V \ V eff . A plan is a path from s 0 to any s ⋆ ∈ S ⋆ . The plan is optimal iff its summed-up cost is equal to h * (s 0 ).
A heuristic is a function h : S → R + 0 ∪ {∞}. The heuristic is admissible iff, for every s ∈ S, h(s) ≤ h * (s); it is consistent iff, for every (s, l, s ′ ) ∈ T , h(s) ≤ h(s ′ ) + c(l); it is perfect iff h coincides with h * . The A * algorithm expands states by increasing value of g(s) + h(s) where g(s) is the accumulated cost on the path to s. If h is admissible, then A * returns an optimal solution. If h is consistent then A * does not need to re-open any nodes. If h is perfect then, as will be detailed later, A * "does not need to search"; we will also identify a more general criterion sufficient to achieve this last property.

How to automatically compute a heuristic, given a planning task as input? Our approach is based on designing an abstraction. This is a function α mapping S to a set of abstract states S α . The abstract state space Θ α is defined as (S α , L, T α , s α 0 , S α ⋆ ), where

T α := {(α(s), l, α(s ′ )) | (s, l, s ′ ) ∈ T }, s α 0 := α(s 0 ), and S α ⋆ := {α(s ⋆ ) | s ⋆ ∈ S ⋆ }.
The abstraction heuristic h α maps each s ∈ S to the remaining cost of α(s) in Θ α ; h α is admissible and consistent. We will sometimes consider the induced equivalence relation ∼ α , defined by setting s ∼ α t iff α(s) = α(t).

How to choose a good α in general? Inspired by work in the context of model checking automata networks [START_REF] Dräger | Directed model checking with distancepreserving abstractions[END_REF], Helmert et al. [START_REF] Helmert | Flexible abstraction heuristics for optimal sequential planning[END_REF] propose M&S abstraction as a method allowing fine-grained abstraction design, selecting individual pairs of (abstract) states to aggregate. The approach builds the abstraction in an incremental fashion, iterating between merging and shrinking steps. In detail, an abstraction α is an M&S abstraction over V ⊆ V if it can be constructed using these rules:

(i) For v ∈ V, π {v} is an M&S abstraction over {v}.

(ii) If β is an M&S abstraction over V and γ is a function on S β , then γ • β is an M&S abstraction over V .

(iii) If α 1 and α 2 are M&S abstractions over disjoint sets

V 1 and V 2 , then α 1 ⊗ α 2 is an M&S abstraction over V 1 ∪ V 2 .
Inria Rule (i) allows to start from atomic projections. These are simple abstractions π {v} (also written π v ) mapping each state s ∈ S to the value of one selected variable v. Rule (ii), the shrinking step, allows to iteratively aggregate an arbitrary number of state pairs, in abstraction β. Formally, this simply means to apply an additional abstraction γ to the image of β. In rule (iii), the merging step, the merged abstraction α 1 ⊗ α 2 is defined by (α 1 ⊗ α 2 )(s) := (α 1 (s), α 2 (s)). 1The above defines how to construct the abstraction α, but not how to actually compute the abstraction heuristic h α . For that computation, the constraint V 1 ∩ V 2 = ∅ in rule (iii) is important. While designing α, we maintain also the abstract state space Θ α . This is trivial for rules (i) and (ii), but is a bit tricky for rule (iii). We need to compute the abstract state space Θ α1⊗α2 of α 1 ⊗ α 2 , based on the abstract state spaces Θ α1 and Θ α2 computed (inductively) for α 1 and α 2 beforehand. We do so by forming the synchronized product Θ α1 ⊗ Θ α2 . This is a standard operation, its state space being S α1 × S α2 , with a transition from (s 1 , s 2 ) to (s ′ 1 , s ′ 2 ) via label l iff (s 1 , l, s ′ 1 ) ∈ T α1 and (s 2 , l, s ′ 2 ) ∈ T α2 . As Helmert et al. [START_REF] Helmert | Flexible abstraction heuristics for optimal sequential planning[END_REF] show, the constraint V 1 ∩ V 2 = ∅ is sufficient (and, in general, necessary) to ensure that this is correct, i. e., that Θ α1 ⊗ Θ α2 = Θ α1⊗α2 .

To implement M&S in practice, we need a merging strategy deciding which abstractions to merge in (iii), and a shrinking strategy deciding which (and how many) states to aggregate in (ii). Throughout this paper, we use the same merging strategy as the most recent work on M&S [START_REF] Nissim | Computing perfect heuristics in polynomial time: On bisimulation and merge-and-shrink abstraction in optimal planning[END_REF]. What we investigate is the shrinking strategy. Helmert et al. [START_REF] Helmert | Flexible abstraction heuristics for optimal sequential planning[END_REF] proposed a strategy that leaves remaining cost intact within the current abstraction. This is done simply by not aggregating states whose remaining cost differs. The issue with this is that it preserves h * locally only. For example, in a transportation domain, if we consider only the position of a truck, then any states s, t equally distant from the truck's target position can be aggregated: locally, the difference is irrelevant. Globally, however, there are transportable objects to which the difference in truck positions does matter, and thus aggregating s and t results in information loss.

We need a shrinking strategy that takes into account the global effect of state aggregations. Nissim et al. [START_REF] Nissim | Computing perfect heuristics in polynomial time: On bisimulation and merge-and-shrink abstraction in optimal planning[END_REF] address this (in a uniform-cost setting)via the well-known notion of bisimulation, a criterion under which an abstraction preserves exactly the behavior (the transition paths) of the original system: Definition 1 Let Θ = (S, L, T, s 0 , S ⋆ ) be a transition system. An equivalence relation ∼ on S is a bisimulation for Θ if s ∼ t implies that: (1) either s, t ∈ S ⋆ or s, t ∈ S ⋆ ; [START_REF] Domshlak | BJOLP: The big joint optimal landmarks planner[END_REF] for every transition label

l ∈ L, {[s ′ ] | (s, l, s ′ ) ∈ T } = {[t ′ ] | (t, l, t ′ ) ∈ T }.
As usual, [s] for a state s denotes the equivalence class of s. Intuitively, s ∼ t only if (1) s and t agree on the status of the goal, and (2) whatever operator applies to s or t applies to both, and leads into equivalent states. An abstraction α is a bisimulation iff the induced equivalence relation ∼ α is.

Note that there are potentially many bisimulations. For example, the identity relation, where [s] = {s}, is one. A bisimulation ∼ ′ is coarser than another bisimulation ∼ if ∼ ′ ⊇∼, i. e., if every pair of states equivalent under ∼ is also equivalent under ∼ ′ . A unique coarsest bisimulation always exists, and can be computed efficiently based on an explicit representation of Θ [START_REF] Milner | Operational and algebraic semantics of concurrent processes[END_REF]. Thus the proposed shrinking strategy is to reduce, in any application of rule (ii), Θ β to a coarsest bisimulation of itself.

It is easy to see that the bisimulation property is invariant over merging and shrinking steps. We spell out the claim for merging steps since we will generalize this result later on:

Lemma 1 [START_REF] Nissim | Computing perfect heuristics in polynomial time: On bisimulation and merge-and-shrink abstraction in optimal planning[END_REF] Let Θ 1 and Θ 2 be transition systems, and let α 1 and α 2 be abstractions for Θ 1 and Θ 2 respectively. If α 1 is a bisimulation for Θ 1 , and α 2 is a bisimulation for Θ 2 , then α 1 ⊗α 2 is a bisimulation for Θ 1 ⊗ Θ 2 .

Proof: Note the slight abuse of notation here: α i is a function on Θ i , not on Θ 1 ⊗ Θ 2 ; the precise claim is that α 1 ⊗ α 2 is a bisimulation for Θ 1 ⊗ Θ 2 , where α 1 (s 1 , s 2 ) := α 1 (s 1 ) and α 2 (s 1 , s 2 ) := α 2 (s 2 ). We omit this distinction to avoid notational clutter.

Denote Θ 12 = Θ 1 ⊗ Θ 2 where Θ 12 = (S 12 , L, T

s 2 ∼ α2 t 2 . This is simply because (α 1 ⊗ α 2 )(s) = (α 1 (s), α 2 (s)) = (α 1 (s 1 ), α 2 (s 2 )) and similar for t, so if (α 1 ⊗ α 2 )(s) = (α 1 ⊗ α 2 )(t) then we have α 1 (s 1 ) = α 1 (t 1 ) and α 2 (s 2 ) = α 2 (t 2 ).
Due to [START_REF] Brafman | On reachability, relevance, and resolution in the planning as satisfiability approach[END_REF] ). Then by ( 5) and [START_REF] Helmert | Fast Downward Stone Soup[END_REF] we have (t, l, t ′ ) ∈ T 12 . By ( 6) and ( 8), we have that

α 1 (s ′ 1 ) = α 1 (t ′ 1 ) and α 2 (s ′ 2 ) = α 2 (t ′ 2 ), thus (α 1 (s ′ 1 ), α 2 (s ′ 2 )) = (α 1 (t ′ 1 ), α 2 (t ′ 2 )), thus (α 1 ⊗ α 2 )(s ′ ) = (α 1 ⊗ α 2 )(t ′ ), thus s ′ ∼ α1⊗α2 t ′ as desired.
In other words, if we combine bisimulations for two transition systems, then we obtain a bisimulation for the synchronization of these systems. Due to this invariance property, bisimulation gets preserved throughout M&S: if we build an M&S abstraction α over the entire variable set V = {v 1 , . . . , v n }, and we always shrink by coarsest bisimulation, then the abstraction will be a bisimulation for

Θ πv 1 ⊗ • • • ⊗ Θ πv n .
The latter is isomorphic to the global state space [START_REF] Helmert | Flexible abstraction heuristics for optimal sequential planning[END_REF], thus α is a bisimulation for the global state space. Since bisimulation preserves transition paths exactly, this implies that h α is a perfect heuristic (see the proof of Lemma 2 below).

As previously discussed, bisimulations are exponentially big even in trivial examples. A key point for improving on this is that, in contrast to verification where bisimulation is traditionally being used, we need to preserve not the solutions but only their cost. Nissim et al. [START_REF] Nissim | Computing perfect heuristics in polynomial time: On bisimulation and merge-and-shrink abstraction in optimal planning[END_REF] define a label reduction technique to this end, the details of which are not important here (we do use it in our implementation). What is important is that, even with the label reduction, in most benchmarks the resulting abstractions are still huge. The way out we employ here is to relax Definition 1 by applying constraint (2) to only a subset of the transitions in T -by catching this transition subset, as we will say from now on. We will show that this can be done while still computing a perfect heuristic, provided we catch the right transitions.

Nissim et al. already mentioned an approach -"greedy bisimulation"-catching a transition subset. The approach preserves h * locally (in the current abstraction), but not globally. We next revisit it, then we introduce new techniques that preserve h * globally.

Greedy Bisimulation

Nissim et al. propose greedy bisimulation as a more approximate shrinking strategy in practice, accepting its lack of global foresight. They introduce the concept informally only; formally, it is defined as follows:

Definition 2 [START_REF] Nissim | Computing perfect heuristics in polynomial time: On bisimulation and merge-and-shrink abstraction in optimal planning[END_REF] Let Θ = (S, L, T, s 0 , S ⋆ ) be a transition system. An equivalence relation ∼ on S is a greedy bisimulation for Θ if it is a bisimulation for the system (S, L, T G , s 0 , S ⋆ ) where

T G = {(s, l, s ′ ) | (s, l, s ′ ) ∈ T, h * (s ′ ) ≤ h * (s)}.

Inria

In other words, greedy bisimulation differs from bisimulation in that it catches only the transitions not increasing remaining cost. Since a greedy bisimulation is a bisimulation on a modified transition system, it is obvious that a unique coarsest greedy bisimulation still exists and can be computed efficiently. More interestingly, greedy bisimulation still preserves (local) remaining cost: Lemma 2 Let Θ be a transition system, and let α be a greedy bisimulation for Θ. Then h α is perfect.

Proof: We first show that any full bisimulation yields perfect heuristics. Say that (A, l, A ′ ) starts a cheapest abstract solution for [s] = A. By definition of the abstract transition system, there exists a transition (t, l, t ′ ) ∈ T where

[t] = A and [t ′ ] = A ′ . By Definition 1 (2), we have a transition (s, l, s ′ ) in Θ so that s ′ ∈ [t ′ ] = A ′ .
Thus the abstract plan step has a real correspondence in the state s at hand. Iterating the argument yields, with Definition 1 (1), a real solution path with the same cost. Now we show that h * = h G , where h G denotes remaining cost in Θ G = (S, L, T G , s 0 , S ⋆ ). Since the transitions of T G are a subset of those of T , and otherwise the two transition systems are the same, any solution path (for any state) in T G is a solution path in T . Thus h * ≤ h G . On the other hand, any optimal solution path in T is a solution path in T G : optimal solution paths never use transitions that increase h * , so all transitions used are contained in T G . Thus h * ≥ h G as desired.

Let h ′ be the heuristic function defined by the optimal solution costs in the quotient system Θ G /α. Then h ′ = h G , since α is a bisimulation of Θ G , and thus we have h ′ = h * . Note that h α can be obtained as optimal solution distances in a transition system obtained from Θ G /α by adding all abstract transitions that correspond to the transitions

T \ T G . Any transition (s, l, s ′ ) ∈ T \ T G has h * (s ′ ) > h * (s), and thus h ′ ([s ′ ]) > h ′ ([s]). Thus adding ([s], l, [s ′ ])
does not change the optimal solution distances in Θ G /α, and hence h α = h ′ , from which the claim follows.

The bad news, as indicated, is that remaining costs are not preserved at the global level. Say our shrinking strategy is to reduce, in any application of rule (ii), Θ β to a coarsest greedy bisimulation of itself. Then, in difference to full bisimulation as per Definition 1, the final abstraction is not guaranteed to be a greedy bisimulation for the global state space. That is because greedy bisimulation is not invariant over merging steps, i. e., there is no equivalent of Lemma 1: a greedy bisimulation for Θ 1 does not catch transitions t that increase (local) remaining cost in Θ 1 , however such t may decrease (global) remaining cost in Θ 1 ⊗ Θ 2 . A simple example is that where Θ 1 is a truck, Θ 2 is a package, and t drives the truck away from its own goal -which globally is a good idea in order to transport the package.

Not being invariant across M&S does not, by itself, imply that greedy bisimulation cannot result in useful heuristic functions in practice. Still, its unpredictable global effect is undesirable. And anyhow, greedy bisimulation actually catches more transitions than needed to preserve local remaining cost. We now introduce techniques addressing both.

Catching Relevant Labels

Instead of catching individual transitions with a criterion local to the current abstraction, we now devise techniques that catch them based on a label subset that we fix, with a global criterion, at the very beginning. Throughout the M&S process, we catch a transition iff its label is inside this subset. 2We next show that such label-catching bisimulations are invariant in M&S. We then define a subset of labels catching which guarantees a perfect heuristic. Subsequently, we show how this label subset can be further diminished, while still guaranteeing that A * will terminate without any search.

Catching Label Subsets

Our definition is straightforward: Definition 3 Let Θ = (S, L, T, s 0 , S ⋆ ) be a transition system, and let K be a set of labels. An equivalence relation ∼ on S is a K-catching bisimulation for Θ if it is a bisimulation for the system (S, K, T K , s 0 , S ⋆ ) where

T K = {(s, l, s ′ ) | (s, l, s ′ ) ∈ T, l ∈ K}.
As indicated, K-catching bisimulation is invariant over M&S rule (iii), i. e., we can generalize Lemma 1 as follows:

Lemma 3 Let Θ 1 and Θ 2 be transition systems, let K be a set of labels, and let α 1 and α 2 be abstractions for Θ 1 and Θ 2 respectively. If α 1 is a K-catching bisimulation for Θ 1 , and

α 2 is a K-catching bisimulation for Θ 2 , then α 1 ⊗ α 2 is a K-catching bisimulation for Θ 1 ⊗ Θ 2 .
Proof: The proof is almost identical to the proof of Lemma 1. The only difference is that we demand l ∈ K ⊆ L. For the sake of completeness we present the full proof here.

Denote 12 , by definition of the synchronized product, we have that (1)

Θ 12 = Θ 1 ⊗ Θ 2 where Θ 12 = (S 12 , L, T 12 , s 12 0 , S 12 ⋆ ). Let s = (s 1 , s 2 ), s ′ = (s ′ 1 , s ′ 2 ), t = (t 1 , t 2 ) ∈ S 12 and l ∈ K, s.t. s ∼ α1⊗α2 t and (s, l, s ′ ) ∈ T 12 . To show that α 1 ⊗ α 2 is a K-catching bisimulation,
(iii) s 1 ∈ S 1 ⋆ iff t 1 ∈ S 1 ⋆ and s 2 ∈ S 2 ⋆ iff t 2 ∈ S 2 ⋆ , altogether giving us the desired s ∈ S 12 ⋆ iff t ∈ S 12 ⋆ . Now, since (s, l, s ′ ) ∈ T
(s 1 , l, s ′ 1 ) ∈ T 1 and (2) (s 2 , l, s ′ 2 ) ∈ T 2 . Since s ∼ α1⊗α2 t, by definition of ∼ α1⊗α2 we have that (3) s 1 ∼ α1 t 1 and (4) s 2 ∼ α2 t 2 . This is simply because (α 1 ⊗ α 2 )(s) = (α 1 (s), α 2 (s)) = (α 1 (s 1 ), α 2 (s 2 )) and similar for t, so if (α 1 ⊗ α 2 )(s) = (α 1 ⊗ α 2 )(t) then we have α 1 (s 1 ) = α 1 (t 1 ) and α 2 (s 2 ) = α 2 (t 2 ).
Due to (1) and (3) and because α 1 is a K-catching bisimulation for Θ ). Then by ( 5) and [START_REF] Helmert | Fast Downward Stone Soup[END_REF] we have (t, l, t ′ ) ∈ T 12 . By ( 6) and ( 8), we have that

α 1 (s ′ 1 ) = α 1 (t ′ 1 ) and α 2 (s ′ 2 ) = α 2 (t ′ 2 ), thus (α 1 (s ′ 1 ), α 2 (s ′ 2 )) = (α 1 (t ′ 1 ), α 2 (t ′ 2 )), thus (α 1 ⊗ α 2 )(s ′ ) = (α 1 ⊗ α 2 )(t ′ ), thus s ′ ∼ α1⊗α2 t ′ as desired.
Thus we get invariance over the entire M&S process: Lemma 4 Let Π be a planning task with variables V and state space Θ, and let K be a set of labels. Let α be an M&S abstraction over V where, in any application of rule (ii), γ is a K-catching bisimulation for Θ β . Then α is a K-catching bisimulation for Θ.

Proof: Starting with the atomic M&S abstractions as per rule (i), note that these are K-catching bisimulations. Lemma 3 gives us invariance over the application of rule (iii). Finally, it is easy to see that a K-catching bisimulation of a K-catching bisimulation is, again, a K-catching bisimulation. So we have invariance over rule (ii) as well, from which the claim follows.

Catching a smaller label set can only decrease abstraction size, and can only increase the error made by the heuristic: Lemma 5 Let Θ be a transition system, and let K ′ ⊆ K be sets of labels. Then the coarsest K ′ -catching bisimulation is coarser than the coarsest K-catching bisimulation.

Proof: Denoting the coarsest K ′ -catching (K-catching) bisimulation with ∼ K ′ (∼ K ), we need that s ∼ K t implies s ∼ K ′ t. This holds because {[s ′ i ] | (s i , l, s ′ i ) ∈ T, l ∈ K} = {[t ′ i ] | (t i , l, t ′ i ) ∈ T, l ∈ K} implies {[s ′ i ] | (s i , l, s ′ i ) ∈ T, l ∈ K ′ } = {[t ′ i ] | (t i , l, t ′ i ) ∈ T, l ∈ K ′ }.

Inria

Globally Relevant Labels

We now employ an idea similar to that of Nissim et al.'s greedy bisimulation, except that we select the transitions based on a global view, and a little more carefully: 3

Definition 4 Let Π be a planning task with state space Θ = (S, L, T, s 0 , S ⋆ ). A label l ∈ L is globally relevant if there exists (s, l, s ′ ) ∈ T such that h * (s ′ ) + c(l) = h * (s).

The transitions caught by this definition differ from those of Definition 2 in that (A) we identify them via their labels, rather than individually Proof: Due to Lemma 5, it suffices to consider the case K = G. The proof of Lemma 2 remains valid except in two details. When proving that h * = h G , we now rely on h * (s ′ ) + c(l) > h * (s) to show that transitions not in T G do not take part in optimal solution paths. When proving that h ′ = h α , we now rely on the same fact, namely that the transitions (s, l, s

′ ) ∈ T \ T G have h * (s ′ ) + c(l) > h * (s) and thus h ′ (s ′ ) + c(l) > h ′ (s).
Clearly, as before this implies that adding ([s], l, [s ′ ]) does not change the optimal solution distances in Θ G /α.

Combining Lemmas 4 and 6, we get the desired result:

Theorem 1 Let Π be a planning task with variables V and state space Θ, let G be the globally relevant labels, and let K ⊇ G. Let α be an M&S abstraction over V where, in any application of rule (ii), γ is a K-catching bisimulation for Θ β . Then h α is perfect.

Note that Definition 4 catches the globally relevant labels G based on the entire state space S. As defined here, that state set contains all states in the planning task, also those that are not actually reachable from the initial state. This is important: Theorem 1 does not hold if we collect G based on reachable states only.

Example 1 Let x, y, and z be three binary domain variables with initial values x = 0, y = 0, z = 0, goal values x = 1, y = 1, and A = {a, b, c, d} be the set of uniform cost actions as follows:

• a : x = 0 → x = 1, y = 0, • b : x = 1, y = 0 → y = 1,
• c : x = 0, y = 1 → x = 1, and

• d : x = 0, y = 0, z = 1 → y = 1, z = 0.
The state space of the planning task is described in Figure 1 (a). Note that restricting ourselves to reachable states will result in the set of globally relevant labels being {a, b}. Figure 1 (b) shows the result of merging the atomic abstractions of variables x and y. Note that the states 00 and 01 are {a, b}-catching bisimilar, and thus the abstraction obtained as a result of shrinking by the {a, b}-catching bisimilation is depicted in Figure 1 (c). Merging with the third variable z will result in abstraction described in Figure 1 (d). Note that the heuristic value for the initial state 000 obtained from that abstraction is 1, which is smaller that the true cost of solving the task. As this example shows, if we do not catch labels relevant for unreachable states, then such a state s may end up in the same equivalence class with a reachable state t although h * (s) < h * (t). We then get h α (t) ≤ h * (s) < h * (t). Note here that the abstraction considers solution paths (in particular the one constituting h * (t)) within unreachable parts of the state space. In other words, the transition system considered when collecting the globally relevant labels (the reachable state space) is different from the transition system considered when building the abstraction (the full state space). That difference can arise in M&S because, during the construction of the abstraction, reachability is over-approximated. The same difference can be illustrated in a simple fashion by a hypothetical algorithm that works directly on the reachable vs. non-reachable state space: if we collect the globally relevant labels K in the reachable state space as in Figure 1 (a), and then build a K-catching bisimulation of the non-reachable state space, we obtain an abstract transition system isomorphic to the one shown in Figure 1 (c), and thus in particular we obtain the same error for h α (s 0 ) as in Example 1. 4If there are no 0-cost operators, then with perfect h α A * does not need to search. Precisely, A * finds an optimal plan after expanding a number of nodes linear in the plan's length, provided we break ties in A * based on smaller h α . That is, if g(s)+h α (s) = g(s ′ )+h α (s ′ ) and h α (s) < h α (s ′ ), then we expand s prior to s ′ . Given this, we know that (I) any state s ′ not on an optimal plan has g(s ′ )+h α (s ′ ) > g(s 0 )+h α (s 0 ); and (II) along the states on any optimal plan, h α decreases strictly monotonically. Due to (I), we do not expand any sub-optimal states. Due to (II), within the set of optimal states (which may be large), the tie-breaking leads directly to the goal in depth-first manner.

In the presence of 0-cost operators, (II) is no longer true, and in general there is no way to guarantee avoiding search (e. g., if all costs are 0 and h * is devoid of information).

Bounded-Radius Relevant Labels

To avoid search in A * , it is not necessary for the heuristic to be perfect everywhere. It suffices to guarantee the conditions (I) and (II) above. We show that, to accomplish this, we can consider a radius R around the goal: Definition 5 Let Π be a planning task with state space Θ = (S, L, T, s 0 , S ⋆ ), and let

R ∈ R + 0 . A label l ∈ L is R-relevant if there exists (s, l, s ′ ) ∈ T such that h * (s ′ ) + c(l) = h * (s) ≤ R.
This "radius" in terms of a label subset translates into a radius guaranteeing heuristic quality: Lemma 7 Let Π be a planning task with state space Θ, let R ∈ R + 0 , let G be the R-relevant labels, and let K ⊇ G. Let α be a K-catching bisimulation for Θ. Then, for every s ∈ S with h * (s) ≤ R, we have h α (s) = h * (s); and for s ∈ S with h * (s) > R, we have h α (s) > R.

Proof: By a minor extension of the proof to Lemma 6. The claimed property is obvious for h G , so we also have it for h ′ , since for h * (s) ≤ R, we preserve all optimal-path transitions, and for h * (s) > R, removing transitions can only increase the remaining cost. We show now that the claimed property is invariant over adding any transition (s, l, s

′ ) from T \ T G to Θ G /α. If h * (s) > R, h ′ ([s]) could be decreased to h ′ ([s ′ ]) + c(l); if h * (s ′ ) ≤ R then by invariance assumption h ′ ([s ′ ]) = h * (s ′ ) and thus h ′ ([s ′ ]) + c(l) ≥ h * (s) > R; if h * (s ′ ) > R then by invariance assumption h ′ ([s ′ ]) > R so h ′ ([s ′ ]) + c(l) > R as well. If h * (s) ≤ R, then h * (s ′ ) + c(l) > h * (s). If h * (s ′ ) > R, then h ′ ([s ′ ]) > R, and h ′ ([s]) will not be decreased; otherwise h ′ ([s ′ ]) = h * (s ′ ) and thus h ′ ([s]) could be decreased only to h ′ ([s ′ ]) + c(l) = h * (s ′ ) + c(l) > h * (s).
Combining this with Lemma 4 we get that, if we fix a label subset K catching all R-relevant labels, and if we implement the shrinking step as coarsest K-catching bisimulation, then the resulting heuristic h α will have the claimed quality on the global state space. Thus, in the absence of 0-cost operators and when setting R to optimal plan cost, conditions (I) and (II) still hold, and A * is efficient: Theorem 2 Let Π be a planning task all of whose operators have non-0 cost. Let V be the variables of Π, let Θ be the state space of Π, let G be the h * (s 0 )-relevant labels, and let K ⊇ G. Let α be an M&S abstraction over V where, in any application of rule (ii), γ is a K-catching bisimulation for Θ β . Then A * with h α , breaking ties in favor of smaller heuristic values, expands a number of states linear in the length of the plan returned.

One may speculate whether it is possible to generalize the circles defined here (by the radius R) to ellipses. Definition 5 would then define l to be R-relevant if there exists (s, l, s ′ ) ∈ T such that f * (s ′ ) + c(l) = g(s ′ ) + h * (s ′ ) + c(l) = g(s) + h * (s) = f * (s) ≤ R. For Theorem 2 to still hold, we would need the adapted version of Lemma 7 stating that (A) for every s ∈ S with f * (s) ≤ f * (s 0 ) we have g(s) + h α (s) = f * (s), and (B) for s ∈ S with f * (s) > f * (s 0 ), we have g(s) + h α (s) > f * (s 0 ). For (A), the argument stated in the proof of Lemma 7 remains valid: f * is constant on optimal solution paths, and any optimal solution for s is part of an optimal solution for s 0 . The latter does, however, not apply in case (B), where s is not part of an optimal solution for s 0 . Indeed, it is easy to construct cases where the only (costly) path P from s to the goal does not contain any states on an optimal solution for s 0 , and where thus no operator on P is f * (s 0 )-relevant according to the modified definition. Then all states along P are aggregated, and we get g(s) + h α (s) < f * (s 0 ).

Results Using Exact Label Sets

The label subsets introduced in the previous section cannot be computed efficiently, so they must be approximated in practice. We will do so in the next section. Here, we assess the power of our techniques from a principled perspective, ignoring this source of complication. We consider what would happen if we did use the exact label sets as defined.

Theoretical Results with Exact Labels

Catching globally relevant labels matches full bisimulation in that it yields a perfect heuristic (cf. Theorem 1); greedy bisimulation does not give that guarantee. Compared to both full bisimulation and greedy bisimulation, catching globally relevant labels is potentially better because it makes less distinctions. This can yield an exponential advantage:

Proposition 1 There exist families of planning tasks {Π n }, with variable subsets {V n } and globally relevant labels {G n }, so that M&S abstractions over V n are exponentially smaller with the shrinking strategy using G n -catching bisimulation, than with the shrinking strategies using either of bisimulation or greedy bisimulation.

Proof: Consider the family of uniform-cost planning tasks with variables V n = {g, v 1 , . . . , v n , v}, where g, v 1 , . . . , v n are Boolean, and v has domain {1, . . . , n}. The initial state sets all variables to 0, the goal is g = 1, and the operators are:

• o g : g = 0 → g = 1 • o i : v i = 0, v = i → v i = 1 • o vij : v = i → v = j • o G : g = 0, v 1 = 1, . . . , v n = 1 → g = 1
We can always achieve the goal in one step using o g , but we can also go through the entire set v 1 , . . . , v n to finally achieve the goal via o G . Say our variable order is any one ordering variable v last.

We show first that any full bisimulation or greedy bisimulation must have exponential size at some point during the abstraction process. Consider the set of states S in the product of all variables except v. Consider any two non-goal states s, t ∈ S whose subset of v i with value 0 is different. Then the sets of outgoing labels o i are different, even under label reduction because v is not projected away. Thus s and t are not bisimilar, and 2 n is a lower bound on the number of abstract states in a full bisimulation. For greedy bisimulation, we also need to show that the labels o i do not increase abstract solution distance; that is trivial because solution distance, and thus abstract solution distance, is globally bounded by 1 and the solution distance of s, t is greater than 0 by construction.

We now show that bisimulation catching the globally relevant labels has constant size throughout the abstraction process. Clearly, the globally relevant labels are {o g , o G }. Say that, at any point during the abstraction process, we aggregate states s and t iff they agree on the value of g (if already merged) and so that either both s and t make one already-merged v i false, or both s and t make all already-merged v i true. Then, clearly, o g , o G is applicable to s iff it is applicable to t; and the respective outcome states are aggregated. Thus this abstraction is a bisimulation catching the globally relevant labels. Obviously, the size of this abstraction is ≤ 4.

Likewise, imposing a radius on the caught labels can have an exponential advantage (while still guaranteeing A * to be efficient, cf. Theorem 2): Proposition 2 There exist families of planning tasks {Π n }, with variable subsets {V n }, globally relevant labels {G n }, and h * (s 0 )-relevant labels {R n }, so that M&S abstractions over V n are exponentially smaller with the shrinking strategy using R n -catching bisimulation, than with the shrinking strategies using either of G n -catching bisimulation, bisimulation, or greedy bisimulation.

Inria

Proof: Consider the family of uniform-cost planning tasks with variables V n = {g, v 1 , . . . , v n , v}, where v 1 , . . . , v n are Boolean, g has domain {-1, 0, 1}, and v has domain {1, . . . , n}. The initial state sets all variables to 0, the goal is g = 1, and the operators are:

• o ¬g : g = 0 → g = -1 • o g : g = 0 → g = 1 • o i : v i = 0, v = i → v i = 1 • o vij : v = i → v = j • o G : g = -1, v 1 = 1, . . . , v n = 1 → g = 0
Here, the set v 1 , . . . , v n is no longer a sub-optimal alternative to achieving the goal; instead, it serves to recover the initial value of g, should we have made the mistake of applying o ¬g . Thus, now, all labels except o ¬g are globally relevant. Say our variable order is g, v 1 , . . . , v n , v.

We show first that any bisimulation catching all globally relevant labels, as well as any greedy bisimulation, must have exponential size at some point during the abstraction process. Consider the set of states S in the product of all variables except v. Consider any two states s, t ∈ S whose subset of v i with value 0 is different. Then the sets of outgoing labels o i are different, even under label reduction because v is not projected away. Thus s and t are not bisimilar, and 2 n is a lower bound on the number of abstract states. Since the labels o i are globally relevant, this holds for any bisimulation catching all globally relevant labels (independently of the order in which we merged g, v 1 , . . . , v n ).

For greedy bisimulation, the same argument applies for states s, t ∈ S where g = 0. Each of these has goal distance 1, so any transition that leaves g untouched is caught by greedy bisimulation. The latter applies to the outgoing labels o i , catching which leads to a 2 n lower bound as above.

We now show that bisimulation catching the h * (s 0 )-relevant labels has constant size throughout the abstraction process. Clearly, the only h * (s 0 )-relevant label is o g . Say that, at any point during the abstraction process, we aggregate states s and t iff they agree on the value of g (if already merged). Then, clearly, o g is applicable to s iff it is applicable to t; and the respective outcome states are aggregated. Thus this abstraction is a bisimulation catching the h * (s 0 )-relevant labels. Obviously, the size of this abstraction is ≤ 3.

Propositions 1 and 2 hold regardless whether or not Nissim et al.'s label reduction technique is used. Note that the situations underlying the proofs are quite natural. In particular, as we will see in the next sub-section, most IPC benchmarks contain at least some operators as described. This notwithstanding, to our knowledge none of the benchmarks actually contains a family as claimed in Propositions 1 and 2. Intuitively, the described situations do occur, but to a lesser extent. An exception is Dining-Philosophers in a direct finite-domain planning encoding, for which Nissim et al. showed that greedy bisimulation yields perfect heuristics with polynomial effort. The same is true when catching globally or h * (s 0 )relevant labels.

Empirical Results with Exact Labels

We ran M&S with no shrinking and no reachability pruning (no removal of non-reachable abstract states during M&S) to compute the full state space, and thus the exact label sets; Table 1 shows results on the 172 IPC benchmark instances where this process did not run out of memory. We show, summed-up per instance, the label set size and the size of the largest abstractions generated during M&S, when catching all labels ("All") vs. the globally relevant labels ("Global") vs. the h * (s 0 )-relevant labels ("h * (s 0 )").

A quick look at the left-hand side of the table confirms that there tend to be quite some labels that can be ignored without sacrificing heuristic quality. The single domain with no irrelevant labels at all is TPP. 1: Summed-up sizes of exact label sets (all vs. globally relevant vs. h * (s 0 )-relevant), and of maximum abstraction sizes during M&S for bisimulation catching these.

Often, only about two thirds of the labels are h * (s 0 )-relevant; in Trucks, only one third are. At the same time, a look at the right-hand side of the table shows that the reduced label sets are not very effective in reducing abstraction size. In only 10 out of 24 domains with reduced labels, the maximal abstraction size is reduced as well. The reduction is typically small, except in a few domains like PegSol (factor 1.92) and Rovers (factor 4.63). In two cases (ParcPrinter and Trucks), the size actually grows. This discrepancy with Lemma 5 is due to removal of non-reachable abstract states, done in our code, but not in the lemma. In rare cases, the coarser abstraction (catching less labels) has more reachable abstract states:

Example 2 Let x and y be two variables with domain transition graphs as shown in Figure 2(a,b). Given that the only goal leading action is the one changing y from 0 to 1, the bisimulation catching globally relevant labels will not distinguish between the two values of x, while the regular bisimulation will. Thus, the abstract state spaces obtained after merging the shrinked abstraction for x and the abstraction for y are as shown in Figure 2(c,d), having 3 and 2 reachable states, respectively. We can scale this example by including n indepenedent pairs of variables x and y as shown. The size difference then multiplies, yielding 3 n reachable states for bisimulation catching globally relevant labels, and 2 n reachable states for regular bisimulation. Thus the size difference can be exponential.

The present data should be treated with caution as the instances considered are very small; the abstraction size reductions might be more significant in larger instances. This notwithstanding, in practice it may be advisable to approximate the label subsets aggressively, catching less labels in the hope to reduce abstraction size more, while not losing too much information. We consider such methods next.

Results Using Approximate Label Sets

We describe our label-subset approximation techniques, then run experiments on the standard IPC benchmarks.

Approximation Techniques

The word "relevant" in the names of the label sets identified in Definitions 4 and 5 was chosen because the intuition behind these -subsets of operators used in optimal plans -is very close to previous notions of relevance (e. g., [START_REF] Nebel | Ignoring irrelevant facts and operators in plan generation[END_REF][START_REF] Brafman | On reachability, relevance, and resolution in the planning as satisfiability approach[END_REF][START_REF] Hoffmann | RIFO revisited: Detecting relaxed irrelevance[END_REF]). This creates a potential for synergy. We implemented one method inspired by this, and one method that integrates particularly well with M&S:

• Backward h 1 . This is a variant of backward-chaining relevance detection, using a straightforward backwards version of the equations defining h 1 [START_REF] Haslum | Admissible heuristics for optimal planning[END_REF]. We collect all operators that appear within the radius R given by the product of (forward) h 1 (s 0 ) and a parameter β ∈ [0, 1]. Note that, for h m with large m, the selected labels would be exactly the h * (s 0 )-relevant ones. Setting β allows to select less labels, controlling the trade-off between abstraction size and accuracy. For β = 0, we use the smallest β yielding a non-empty label set.

• Intermediate Abstraction (IntAbs). We run full bisimulation until abstraction size has reached a parameter M . The labels are then collected by applying either of Definition 4 or 5 to the present abstraction, and M&S continues with bisimulation catching that label subset. With very large M (and when not removing non-reachable abstract states), the label set would be exact. Small M results in smaller labels sets because non-0 cost operators on variables not yet merged will not be considered relevant. We run BJOLP [START_REF] Domshlak | BJOLP: The big joint optimal landmarks planner[END_REF] and LM-cut [START_REF] Helmert | Landmarks, critical paths and abstractions: What's the difference anyway?[END_REF] because they were the two non-M&S components in Fast Downward Stone Soup, the portfolio winning the 1st prize in the track for optimal planners at IPC'11. We ran 9 M&S configurations from the work by Nissim et al., setting N ∈ {10K, 100K, ∞} and using either full bisimulation, or greedy bisimulation, or strict-greedy bisimulation (s-greedy). The latter is the variant of Definition 2 catching all transitions (s, l, s ′ ) ∈ T where h * (s ′ ) < h * (s), rather than h * (s ′ ) ≤ h * (s). This variant is not mentioned by Nissim et al., but actually is what is run in their experiments and in the IPC. As for the parameter N , in all M&S variants, this is a bound on abstraction size reaching which forces the shrinking strategy to aggregate more states, dropping any bisimulation guarantees [START_REF] Helmert | Flexible abstraction heuristics for optimal sequential planning[END_REF][START_REF] Nissim | Computing perfect heuristics in polynomial time: On bisimulation and merge-and-shrink abstraction in optimal planning[END_REF]. For N = ∞, the bisimulation guarantee is always held up (and the abstraction might run out of memory). Given the limited space in Table 2, we show data for 4 of the 9 Nissim et al. configurations: N = 10K with full bisimulation, the one with highest overall coverage; N = ∞ with full bisimulation, for reference (in difference to all other M&S configurations here, this guarantees the heuristic to be perfect); and the Inria two configurations taking part in Fast Downward Stone Soup, N = 100K and N = ∞ with strict-greedy bisimulation. 5We also run 4 new M&S variants using strict-greedy bisimulation, with the parameter M of our Intermediate Abstraction (IntAbs) label approximation. These configurations start with full bisimulation, then switch to s-greedy bisimulation once abstraction size M is reached. This allows for a very direct comparison with our IntAbs configurations: the only difference to these lies in their use of label-catching bisimulation, rather than s-greedy bisimulation, after M is reached. We do not show data for IntAbs with Definition 5 (h * (s 0 )-relevant labels), because these configurations are dominated by the ones using Definition 4 (globally relevant labels). Compared to the variants orginally designed by Nissim et al, the new s-greedy variants have a significant adavantage in total coverage. They also have a small such advantage vs. the IntAbs variants. However, the former have the edge in a larger number of individual domains. The respective configuration with best coverage is strictly better for IntAbs in 15 domains, is equally good in 23 domains, and is worse only in 6 domains. An interesting observation within IntAbs is that, as expected, smaller M yields more greedy abstractions. For N = ∞, M = 10K completes 1336 abstractions, vs. 1049 completed by M = 100K.

We finally run 11 M&S variants with the Backward h 1 label-catching strategy: N = 10K with 4 values of β (β = 0.75 not shown because it is always dominated by one of the others); and N = ∞ with 7 values of β. For N = 10K, β has hardly any effect since enforcing the bound makes the abstraction very greedy anyhow. By contrast, for N = ∞, smaller β decreases computational effort drastically (consider the bottom row in Table 2). In effect, in 35 of the 44 domains, coverage increases monotonically as we decrease β. Note also that, for β = 1.0, performance is almost identical to that of full bisimulation with = ∞. Indeed, the number of labels caught (not shown here) is typically close to the total number of labels.

Comparing the per-domain perfomance of the Backward h 1 configurations with the IntAbs configurations, the latter have a slight edge. The configuration with best coverage is strictly better for Backward h 1 in 11 domains, is equally good in 18 domains, and is worse in 15. Comparing the new M&S variants (IntAbs and Backward h 1 ) with all "old" ones (including the novel s-greedy variants), the best-coverage configuration is better for new M&S in 10 domains, equally good in 23, and worse in 11. Comparing the new M&S variants against all other planners, the best-coverage configuration is better for new M&S in 5 domains, equally good in 16, and worse in 23. Altogether, the new heuristics are certainly not a breakthrough in coverage of cost-optimal planners, but they can contribute. We reconfirm this below by considering portfolios built from different subsets of configurations.

Figure 3 examines more closely how β trades off abstraction effort against accuracy. The coverage and "M&S built" data (left y-axis) are as in Table 2. "Expansions X" (right y-axis) shows the average number of expanded states in the subset of instances solved by all configurations where β ≤ X. That subset contains much larger instances for smaller β, hence the average expansions grow. Note however that there is a consistent pattern within each of these curves. Expansions increase a lot as we step from β = 0.75 to β = 0.5 (e. g., from 64976 to 212362 for "Expansions 1.0"), but remain almost constant at both sides of this step. This suggests a kind of phase transition, where for β ≥ 0.75 the heuristic is close to perfect, whereas for β going below 0.5 it is quite bad, and does not get a lot worse while still dramatically reducing abstraction effort. The latter does a lot to help coverage, and one could try to catch even less labels when β = 0. One could also try to add complementary label selection techniques, in the hope to push the "phase transition" to smaller β. Both are topics for future work.

Different M&S heuristics often have complementary strengths. Table 3 examines this in detail, listing the best performance any sequential portfolio of a given size |P | ∈ {2, 4, 6} can obtain, when selecting its components from particular subsets of configurations. Comparisons should be made only within groups of portfolios with same |P |, as each component uses 5 minutes and thus |P | determines the computational resources used. In the "Design" row, "BL" is BJOLP+LM-cut, and "FDSS" has the same configurations as Fast Downward Stone Soup (cf. above). By "X+Y " we denote portfolios P in which the components X are fixed and only the remaining |P | -|X| components are selected from Y . "O" ("Old") refers to the 13 "old" M&S configurations we run here. "N" ("New") refers to 13 of the IntAbs and Backward h 1 configurations (to obtain groups "O" and "N" of same size, we omitted Backward h 1 with N = ∞ and β > 0). "BL" is included only for reference. The data for |P | = 4 and "BL+Y " design shows that, in our setting here, different M&S variants than in "FDSS" yield better coverage; the data for |P | = 6 and "BL+Y " design shows that adding even more M&S configurations still improves the outcome. Generally, portfolios of only "O" M&S configurations are better than those of only "N" ones, but the best option is to combine the two.

Conclusion

Label-catching bisimulation is very appealing in principle: it is invariant over M&S, guarantees a perfect heuristic if we catch all relevant labels, may be exponentially smaller than full bisimulation even in this case, and allows a fine-grained effort/accuracy trade-off by plugging in approximations of relevance. At the same time, our empirical results are a bit disappointing, performance being improved only in few domains. As indicated, one could try to design different relevance approximations. The authors' speculation is that there is more potential in combining M&S heuristics, i. e., automatically constructing sets of heuristics specifically designed to be complementary, for a given planning task.

Figure 1 :

 1 Figure 1: The (a) full state space and the abstractions obtained after (b) merging x and y, (c) shrinking the outcome using {a, b}-catching bisimulation, and (d) merging the outcome with variable z, of the planning task in Example 1.

Figure 2 :

 2 Figure 2: Example 2 domain transition graphs for variables (a) x and (b) y; state spaces of the merged abstractions, with reachable and relevant states marked for (c) G-catching and (d) regular bisimulations.

Figure 3 :

 3 Figure 3: Scaling β in Backward h 1 with N = ∞.

  , t 2 ) ∈ S12 and l ∈ L, s.t. s ∼ α1⊗α2 t and (s, l, s ′ ) ∈ T 12 . To show that α 1 ⊗ α 2 is a bisimulation, we need to show that (I) s ∈ S12 ⋆ iff t ∈ S 12 ⋆ , and (II) there exists t ′ ∈ S 12 s.t. (t, l, t ′ ) ∈ T 12 and s ′ ∼ α1⊗α2 t ′ .

	12 , s 12 0 , S 12 ⋆ ). Let s = (s 1 , s 2 ), s ′ = (s ′ 1 , s ′ 2 ), t =
	(t 1 To show (I), note that by definition of composed transition systems we have (i) s ∈ S 12 ⋆ iff s 1 ∈ S 1 ⋆ and s 2 ∈ S 2 ⋆ , and (ii) t ∈ S 12 ⋆ iff t 1 ∈ S 1 ⋆ and t 2 ∈ S 2 ⋆ . By definition of bisimulation we have (iii) s 1 ∈ S 1 ⋆ iff t 1 ∈ S 1 ⋆ and s 2 ∈ S 2 ⋆ iff t 2 ∈ S 2 ⋆ , altogether giving us the desired s ∈ S 12 ⋆ iff t ∈ S 12 ⋆ . Now, since (s, l, s ′ ) ∈ T 12 , by definition of the synchronized product, we have that (1) (s 1 , l, s ′ 1 ) ∈ T 1 and (2) (s 2 , l, s ′ 2 ) ∈ T 2 . Since s ∼ α1⊗α2 t, by definition of ∼ α1⊗α2 we have that (3) s 1 ∼ α1 t 1 and
	(4)

  and (3) and because α 1 is a bisimulation for Θ 1 , there exists t ′

	1 s.t. (5) (t 1 , l, t ′ 1 ) ∈ T 1 1 . Due to (2) and (4) and because α 2 is a bisimulation for Θ 2 , there exists t ′ 1 ∼ α1 t ′ and (6) s ′ 2 s.t. (7) (t 2 , l, t ′ 2 ) ∈ T 2 and (8) s ′ 2 ∼ α2 t ′ 2 .
	Define t ′ := (t ′ 1 , t ′ 2

  we need to show that (I) s ∈ S12

⋆ iff t ∈ S 12 ⋆ , and (II) there exists t ′ ∈ S 12 s.t. (t, l, t ′ ) ∈ T 12 and s ′ ∼ α1⊗α2 t ′ . To show (I), note that by definition of composed transition systems we have (i) s ∈ S 12 ⋆ iff s 1 ∈ S 1 ⋆ and s 2 ∈ S 2 ⋆ , and (ii) t ∈ S 12 ⋆ iff t 1 ∈ S 1 ⋆ and t 2 ∈ S 2 ⋆ . By definition of K-catching bisimulation we have

  ; (B) they refer to the global state space, not to the local abstraction; and (C) we do not catch transitions whose own cost exceeds the reduction in h * . (A) is important to obtain invariance in M&S, as just discussed. (B) is needed because the global state space is what we wish to approximate. (C) suffices to obtain a perfect heuristic:Lemma 6 Let Π be a planning task with state space Θ, let G be the globally relevant labels, and let K ⊇ G. Let α be a K-catching bisimulation for Θ. Then h α is perfect.

Table 2 :

 2 Selected coverage data in IPC benchmarks. Best results overall (of all M&S heuristics) are highlighted in bold (with a "*"). "Σ M&S built": number of tasks for which computing the M&S abstraction did not exceed the available time/memory.

Table 3 :

 3 Portfolios. "|P |": number of components within portfolio. "Design": portfolio design space (see text). "|C|": number of components to choose from. "Upper bound": solved by any possible component.

"Best P ": best coverage of any portfolio.

RR n°7901

Note that M&S abstractions are constructed over subsets V of the variables V. Indeed, in practice, there is no need to incorporate all variables. Like the previous work on M&S, we do not make use of this possibility: all M&S abstractions in our experiments are over the full set of variables V = V.RR n°7901

There is an interaction between "catching" labels, and "reducing" them as proposed by Nissim et al.[START_REF] Nissim | Computing perfect heuristics in polynomial time: On bisimulation and merge-and-shrink abstraction in optimal planning[END_REF]. We do not reduce l and l ′ to the same label if l is caught but l ′ is not.RR n°7901

In this definition, S and T (as defined in the background) include states not reachable from s 0 . This is because, during M&S, reachability is over-approximated. If we do not catch the respective labels, then the abstraction is done on a transition system larger than that based on which we collected the labels, which may result in an imperfect heuristic even on reachable states. We illustrate this phenomenon below in Example 1.

If we do both, collecting the globally relevant labels K and building a K-catching bisimulation, in the same transition system, say the reachable part of the state space, then the proof of Lemma 6 applies, and h α is perfect within that transition system. Inria

Actually, N = 200K was used in the IPC; the performance for N = 100K is almost identical to that.RR n°7901

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgments. Michael Katz was supported by the French National Research Agency (ANR), project ANR-10-CEXC-003-01. Inria

Neither technique guarantees, in general, to catch all globally relevant/h * (s 0 )-relevant labels. They are practical approximations whose merits we now evaluate experimentally.

Experiments

Our techniques are implemented in Fast Downward, and all results we report use the same A * implementation. We ran a total of 32 M&S configurations, plus two competing heuristics, on 1396 instances from 44 IPC benchmark domain suites. To make these 47464 runs feasible, the runtime for each was limited to 5 minutes. The memory limit was 2 GB. The runs were conducted on machines equipped with two quad-core CPUs (AMD Opteron 2384). Coverage data is shown in Table 2. To save space, we omit domains from IPC'08 that were run also in IPC'11.

Approach IntAbs Global

Backward h 1 strict-greedy bisimulation Nissim et al.