Antoine Chaillet

Hiroshi Ito

A sensitivity trade-off arising in small-gain design for nonlinear systems: an iISS framework

This note investigates the trade-off arising in disturbance attenuation for nonlinear feedback systems in the framework of integral input-to-state stability. Similarly to the linear case, we show that if a gain tuning on one subsystem is used to drastically reduce the effect of its exogenous disturbances, then the other subsystem's disturbance attenuation is qualitatively the same as in open loop.

I. INTRODUCTION

The objective of the present paper is to provide some insights on how the well-known sensitivity / co-sensitivity trade-off arising for feedback linear time-invariant (LTI) systems extends to nonlinear plants. More precisely, given two feedback nonlinear subsystems, assume that the nonlinear gain of one subsystem can be made smaller by a convenient control design. Then the nonlinear loop gain becomes smaller and the small-gain stability criterion is satisfied with a larger margin. A natural question is then whether this induces stronger robustness to disturbances for the overall feedback system. We give an answer to this question in the dissipative formulation for input-to-state stability (ISS, [START_REF] Sontag | Smooth stabilization implies coprime factorization[END_REF]) and integral ISS (iISS, [START_REF] Sontag | Comments on integral variants of ISS[END_REF]) systems.

The results presented along this paper rely on small gain arguments. More precisely, we make use of recent results on Lyapunov-based small gain theorems for iISS [START_REF] Ito | Necessary and sufficient small gain conditions for integral input-to-state stable systems: A Lyapunov perspective[END_REF], which include ISS as a special case. Compared to other nonlinear small gains existing in the literature such as [START_REF] Jiang | Small gain theorems for ISS systems and applications[END_REF], [START_REF] Jiang | A Lyapunov formulation of nonlinear small gain theorem for interconnected systems[END_REF], [START_REF] Teel | A nonlinear small gain theorem for the analysis of control systems with saturation[END_REF], [START_REF] Angeli | A tight small gain theorem for not necessarily ISS systems[END_REF], [START_REF] Dashkovskiy | Small gain theorems for large scale systems and construction of ISS Lyapunov functions[END_REF], this result allows both to deal with not necessarily ISS systems, and to provide an explicit construction of a Lyapunov function for the overall interconnection in the presence of exogenous inputs, which are two helpful features for this work.

Instead of relying on the exact knowledge of differential equation models, we employ iISS dissipation inequalities to describe nonlinear systems in feedback loop. Compared to the frequency analysis for LTI systems (cf. classical textbooks such as [START_REF] Franklin | Feedback Control of Dynamic Systems[END_REF]), iISS dissipation inequalities do not provide an equality between the input and its response, but rather an inequality that provides only a "worst-case" estimate (sometimes not very tight) of the input influence on the overall system: no distinction can be made between A. Chaillet is with L2S -EECI -Univ. Paris Sud 11 -Supélec, 3 rue Joliot Curie, 91192 Gif sur Yvette, France chaillet@ieee.org systems that are strongly sensitive to inputs, and those for which the dissipation inequality is simply too loose.

In order to overpass this difficulty, we proceed in two different manners. The first one (Section IV) consists in building, for a given pair (α, γ) of iISS supply rates, an iISS system ẋ = f (x, d) for which these estimates are tight, in the sense that all disturbances that may act on that system have a negative impact on the system's performance and that this effect is not compensated by a dissipation rate stronger than the prescribed one. Roughly speaking, this is done by imposing (at least in some relevant state regions)

∂V ∂x (x)f (x, d) = -α(|x|) + γ(|d|) ,
where V denotes a given Lyapunov function candidate. The equality sign in this equation guarantees the sought tightness of the estimates. We show that, given an iISS supply pair (α, γ), Lyapunov-based small gain arguments always authorize the existence of such a system and consequently the nonrejection of some disturbances. Of course, this first approach is of purely theoretical interest, as the constructed system has typically no practical relevance. The second approach (Section V) demonstrates this trade-off without introducing such fictitious subsystems. Assuming that a disturbance does have a negative effect on one subsystem's performance, we show that, in feedback, this effect cannot be attenuated by the gain tuning of the other subsystem.

Notation. Given x ∈ R n , |x| denotes its Euclidean norm. Given a set A ⊂ R n , |x| A := inf z∈A |x -z|. Given a constant δ > 0, B δ := {x ∈ R n : |x| ≤ δ}. Given a set A ⊂ R and a constant a ∈ R, A ≥a := {s ∈ A : s ≥ a}. sat δ : R n → R n is defined, for all x ∈ R n , by sat δ (x) := (δsat(x 1 /δ), . . . , δsat(x n /δ))
T , where sat(s) := min(|s|, 1)sign(s) for all s ∈ R. Given a function σ : R m → R n , ker(σ

) := {x ∈ R m : σ(x) = 0}. A continuous function α : R ≥0 → R ≥0 is said to be of class PD if it is positive definite. It is said to be in class K if, in addition, it is increasing. It is said to be of class K ∞ if it is of class K and α(s) → ∞ as s → ∞. A function β : R ≥0 × R ≥0 → R ≥0 is said to be of class KL if β(•, t) ∈ K
for any fixed t ≥ 0 and β(s, •) is continuous non-increasing and tends to zero at infinity for any fixed s ≥ 0.

Given α ∈ K, α(∞) ∈ R ≥0 ∪ {∞} is defined as lim s→∞ α(s). Given α, γ ∈ K, α(∞) > γ(∞) means that either α ∈ K ∞ , or α(∞) = c α ∈ R ≥0 and γ(∞) = c γ ∈ R ≥0 with c α > c γ . U m is the set of measurable locally essentially bounded signals d : R ≥0 → R m . Given u ∈ U m , u := ess sup t≥0 |u(t)|. Given ∆ ≥ 0, U m ≤∆ := {u ∈ U m : u ≤ ∆}. V : R n → R ≥0 is called a Lyapunov function candidate if it is C 1 ,
positive definite and radially unbounded.

II. PROBLEM STATEMENT

We consider two dynamical systems Σ 1 and Σ 2 interconnected in a feedback configuration through their outputs y 1 and y 2 , and subject to exogenous disturbances d 1 and d 2 , cf. Fig. 1. It is well known that, when Σ 1 and Σ 2 are LTI, the sensitivity / co-sensitivity tradeoff impedes the disturbance rejection of both d 1 and d 2 at the same frequency. To sketch out this tradeoff, consider single input -single output systems and let H i denote the transfer function of

Σ i , i ∈ {1, 2}. If H 1 is tuned in such a way that H 2 H 1 (1-H 2 H 1 ) -1 → 0 at a given frequency, then one cannnot avoid (1-H 1 H 2 ) -1 → 1. This results in H 2 (1-H 1 H 2 ) -1 → H 2 ,
meaning that the d 1rejection imposes that the effect of d 2 is the same as in openloop. This fundamental obstruction to control design was first studied in [START_REF] Bode | Network analysis and feedback amplifier design[END_REF]. It imposes, in particular, a compromise between precision / output disturbance rejection and sensor noise attenuation. See [START_REF] Freudenberg | Frequency domain properties of scalar and multivariable feedback systems[END_REF], [START_REF] Maciejowski | Multivariable feedback design[END_REF], [START_REF] Seron | Fundamental limitations in filtering and control[END_REF], [START_REF] Freudenberg | Fundamental design limitations of the general control configuration[END_REF] for an in-depth analysis. The aim of this paper is to analyze to what extent this result can be adapted to nonlinear plants. The feedback interconnection considered in this note is

ẋ1 = f 1 (x 1 , x 2 , d 1 , θ) (1a) ẋ2 = f 2 (x 2 , x 1 , d 2 ) , (1b)
where

(x T 1 , x T 2 ) T =: x ∈ R n1+n2 denote the state of each subsystem, (d T 1 , d T 2 ) T =: d ∈ U m1+m2
are exogenous disturbances, and θ ∈ Θ ⊂ R p is a free parameter as, for instance, a vector of tuning gains. The functions f 1 and f 2 are assumed to be continuous. We stress that this structure does not necessarily require that the subsystems (1a) and (1b) be connected through their whole states, but rather authorizes output feedback interconnection as f 1 (resp. f 2 ) may involve only part of x 2 (resp. x 1 ) or a function of its entries.

While the above LTI reasoning does not require any stability assumption on Σ 1 and Σ 2 when considered individually, the small-gain approach we follow in this note imposes that each subsystem be iISS with a class K dissipiation rate [START_REF] Sontag | Comments on integral variants of ISS[END_REF].

Assumption 1 There exist α 1 , γ 1 , ϕ 1 ∈ K, α 1 , α 1 ∈ K ∞ , and a C 1 function V 1 : R n1 → R ≥0 satisfying α 1 (|x 1 |) ≤ V 1 (x 1 ) ≤ α 1 (|x 1 |) such that, given any λ > 1, there exist θ ∈ Θ such that, for all (x 1 , x 2 ) ∈ R n1+n2 and all d 1 ∈ R m1 , ∂V 1 ∂x 1 f 1 ≤ -α 1 (|x 1 |) + 1 λ [γ 1 (|x 2 |) + ϕ 1 (|d 1 |)] . (2)
This first assumption not only guarantees iISS for the x 1subsystem (1a), but also that the disturbance rejection for this subsystem can be tuned at will by a convenient choice of the parameter θ. More precisely, considering u 1 := (x T 2 , d T 1 ) T as the exogenous input of (1a) and relying on classical reasonings for iISS systems (cf. [2, Corollary IV.3]), Assumption 1 naturally yields the following trajectory estimate for (1a):

|x 1 (t)| ≤ β(|x 10 | , t) + η Ç 1 λ t 0 γ1 (|u 1 (τ )|)dτ å (3)
where

x 1 (•) := x 1 (•; x 10 , x 2 , d 1 , θ), x 2 (•) := x 2 (•; x 20 , x 1 , d 2 ), γ1 (•) := 2 max{γ 1 (•), ϕ 1 (•)
} and η and β denote respectively class K and KL functions. Thus, once the exogenous signals x 2 and d 1 are given, the above estimate illustrates the possibility to arbitrarily reject their effect on the behavior of the x 1 -subsystem by conveniently tuning θ (i.e. by increasing λ). Note that the dissipation rate α 1 is assumed to belong to class K rather than simply PD as in [START_REF] Angeli | A characterization of integral input to state stability[END_REF]. This is motivated by the small gain argument [START_REF] Ito | Necessary and sufficient small gain conditions for integral input-to-state stable systems: A Lyapunov perspective[END_REF] we invoke in the sequel. Hence, Assumption 1 actually imposes iISS plus ISS with respect to small inputs1 with an assignable supply rate. We stress that, under specific matching conditions, Assumption 1 can be ensured by control designs available in the literature such as [17, Lemma 3]. The results in [START_REF] Teel | On assigning the derivative of a disturbance attenuation Control Lyapunov Function[END_REF], [START_REF] Liberzon | Universal construction of feedback laws achieving ISS and integral-ISS disturbance attenuation[END_REF] may also be inspiring. See [4, Proposition 1] for a relevant example. Anyway, even though Assumption 1 may be hard to achieve in practice, this note aims precisely at showing that, despite such a strong stabilizability assumption, disturbance rejection cannot be expected to be arbitrary in a feedback interconnection.

On the other hand, the x 2 -subsystem is assumed to be iISS, with a fixed supply rate. Again, the dissipation rate is assumed to be in class K, thus guaranteeing ISS with respect to small inputs.

Assumption 2 There exist α 2 , γ 2 , ϕ 2 ∈ K, α 2 , α 2 ∈ K ∞ , and a C 1 function V 2 : R n2 → R ≥0 such that, for all (x 1 , x 2 ) ∈ R n1+n2 and all d 2 ∈ R m2 , α 2 (|x 2 |) ≤ V 2 (x 2 ) ≤ α 2 (|x 2 |) (4) ∂V 2 ∂x 2 f 2 (x 2 , x 1 , d 2 )≤-α 2 (|x 2 |) + γ 2 (|x 1 |) + ϕ 2 (|d 2 |). (5)

III. TUNING FOR d 1 -REJECTION

The following result formally shows that, as expected, the tuning of θ allows for arbitrary attenuation of d 1 .

Proposition 1 Let Assumptions 1 and 2 hold and assume that the following implication holds true for each i ∈ {1, 2}:

γ 3-i ∈ K ∞ ⇒ α i ∈ K ∞ . ( 6
)
Assume also that the small-gain condition

2 c 2 γ 2 • α -1 1 • α 1 • α -1 1 • c 1 γ 1 (s) ≤ α 2 • α -1 2 • α 2 (s) (7
) holds for all s ≥ 0, where c 1 > 0 and c 2 > 1 denote some constants. Then, there exist β ∈ KL, α, γ, ζ ∈ K ∞ , and ∆ > 0 and, given any > 1, there exist θ ∈ Θ such that, for all x 0 ∈ R n1+n2 , all d 1 ∈ U m1 and all d 2 ∈ U m2 , the feedback interconnection ( 1) is iISS and ISS with respect to small inputs, and its solution satisfies

α(|x(t)|) ≤ β(|x 0 | , t) + t 0 γ (|d 1 (τ )| / ) dτ + t 0 γ(|d 2 (τ )|)dτ , ∀t ≥ 0 , (8)
and, for all

d 1 ∈ U m1 ≤ ∆ and all d 2 ∈ U m2 ≤∆ , |x(t)| ≤ β(|x 0 | , t) + ζ( d 1 / ) + ζ( d 2 ). (9)
It is worth noting that the upper and lower bounds on V i (namely, α i and α i ), i ∈ {1, 2}, involved in ( 7) could be removed if ( 2) and ( 5) were replaced by dissipation inequalities involving only V i rather than x i . We keep the original small-gain condition [START_REF] Freeman | Robust Nonlinear control design: State-space and Lyapunov control techniques[END_REF] of [START_REF] Ito | Necessary and sufficient small gain conditions for integral input-to-state stable systems: A Lyapunov perspective[END_REF] as the bounds ( 2) and ( 5) are usually easier to establish in practice.

We also stress that small-gain condition in [START_REF] Ito | Necessary and sufficient small gain conditions for integral input-to-state stable systems: A Lyapunov perspective[END_REF] requires both c 1 and c 2 to be greater than 1. Relaxing to only c 1 > 0 in ( 7) is made possible by the fact that, in the context of this article, the constant λ multiplying the supply rate γ 1 is tunable at will through the parameter θ (cf. Assumption 1).

Apart from these details, the iISS and ISS with respect to small inputs of the feedback interconnection (1) under ( 6)- [START_REF] Freeman | Robust Nonlinear control design: State-space and Lyapunov control techniques[END_REF] directly follows from previous results of the second author [START_REF] Ito | Necessary and sufficient small gain conditions for integral input-to-state stable systems: A Lyapunov perspective[END_REF]. See [START_REF] Chaillet | A sensitivity trade-off arising in small-gain design for nonlinear systems: an iISS framework[END_REF] for the complete proof. Let us recall that the small-gain condition (7) is not symmetric. We have chosen to assume [START_REF] Freeman | Robust Nonlinear control design: State-space and Lyapunov control techniques[END_REF] rather than its counterpart:

c 1 γ 1 • α -1 2 • α 2 • α -1 2 • c 2 γ 2 (s) ≤ α 1 • α -1 1 • α 1 (s)
, in order to allow for the interconnection of not necessarily ISS subsystems. See [START_REF] Ito | Necessary and sufficient small gain conditions for integral input-to-state stable systems: A Lyapunov perspective[END_REF] for details.

Compared to [START_REF] Ito | Necessary and sufficient small gain conditions for integral input-to-state stable systems: A Lyapunov perspective[END_REF], the novelty of Proposition 1 stands in the explicit estimate of the disturbance attenuation allowed by the tuning gain θ. Indeed, since the functions α, β, γ and ζ in ( 8)-( 9) are independent of , Proposition 1 guarantees that the effect of the exogenous disturbance d 1 over the solutions' behavior can be made arbitrarily small provided a convenient tuning of θ (i.e., corresponding to sufficiently large λ and ). In addition, since (9) ensures ISS with respect to all d 1 of amplitude smaller than ∆, with ∆ independent of , the class of ISS-tolerated disturbances can be enlarged at will. These constitute two interesting features for the rejection of the d 1 disturbance.

However, no such d 2 -disturbance attenuation appears in the trajectory estimates ( 8)-( 9). This fact could either be due to an intrinsic property of feedback interconnections, or simply to the looseness of the upper bounds ( 8)- [START_REF] Freudenberg | Frequency domain properties of scalar and multivariable feedback systems[END_REF]. The rest of the paper shows that this property is indeed intrinsic and that no such d 2 -attenuation can be expected in general.

The proof of Proposition 1 is omitted due to lack of space, but can be found on the on-line preprint [START_REF] Chaillet | A sensitivity trade-off arising in small-gain design for nonlinear systems: an iISS framework[END_REF]. It relies on the following lemma, whose proof can be found along the lines of [START_REF] Ito | Necessary and sufficient small gain conditions for integral input-to-state stable systems: A Lyapunov perspective[END_REF].

Lemma 1 For each i ∈ {1, 2}, let V i : R ni → R ≥0 be a C 1 function satisfying, for all x i ∈ R ni , α i (|x i |) ≤ V i (x i ) ≤ α i (|x i |) with α i , α i ∈ K ∞ ,
and assume that there exist α i , γ i , ϕ i ∈ K such that (6) holds and, for all s ≥ 0,

c 2 γ 2 • α -1 1 • α 1 • α -1 1 • c 1 γ 1 (s) ≤ α 2 • α -1 2 • α 2 (s) (10) with c 1 , c 2 > 1. Then there exist ρ 1 , ρ 2 , α, γ ∈ K such that, for all (x 1 , x 2 ) ∈ R n1 × R n2 , 2 i=1 ρ i (V i (x i )) -α i (|x i |)+γ i (|x 3-i |)+ϕ i (|d i |) ≤ -α(|x|) + γ(|d|) .

IV. SENSITIVITY TO d 2 : A "WORST CASE" SYSTEM

In contrast to the previous section, we now show that the increase of λ, by a convenient tuning of the gain θ, is in general of no help in reducing the influence of d 2 over x 2 . The proof of this result is provided in Section VII-A.

∂V 2 ∂x 2 (x 2 ) = 0 , ∀x 2 = 0 . (11)
Then one can always find class K functions ν 2 and η 2 , and a vector field

f 2 : R n2 × R n1 × R m2 → R n2 , continuous on R n2 ×R n1 ×(R m2 \ {0}
), satisfying Assumption 2 with these prescribed functions α 2 , γ 2 and ϕ 2 , and such that, given any θ ∈ Θ, any initial state x 20 ∈ R n2 and any disturbance

d 1 ∈ U m1 and d 2 ∈ U m2 satisfying d min 2 ≤ d 2 (t) ≤ d max 2 , (12)
all forward complete solutions of (1) starting with

|x 20 | ≥ η 2 ( d 2 ) satisfy |x 2 (t)| ≥ ν 2 (ess inf τ ≥0 |d 2 (τ )|), ∀t ≥ 0. ( 13
)
Theorem 1 shows that the only knowledge of the dissipation inequality associated to each subsystem cannot guarantee, in general, an arbitrary d 2 -disturbance attenuation even when control gains can be tuned in order to decrease the sensitivity of the x 1 -subsystem with respect to its inputs. Indeed, it guarantees that such an interconnection may always yield, for some particular systems, the existence of an incompressible lower bound [START_REF] Jiang | A Lyapunov formulation of nonlinear small gain theorem for interconnected systems[END_REF] whose size is somewhat "proportional" to the minimal value of |d 2 |, for solutions starting sufficiently far from the origin. The crucial point is that this lower bound holds regardless of the chosen gain θ. It is therefore hopeless to expect arbitrary d 2 -disturbance rejection for this system by relying only on the associated dissipation inequalities.

Remark 1 If in addition to the assumptions of Theorem 1, the small gain condition [START_REF] Freeman | Robust Nonlinear control design: State-space and Lyapunov control techniques[END_REF] holds, then the assumptions of Proposition 1 are satisfied and consequently the feedback interconnection ( 1) is iISS and ISS with respect to small inputs (cf. ( 8)-( 9)) if λ is made small enough by a convenient choice of θ. In particular, (1) results forward complete and the lower bound [START_REF] Jiang | A Lyapunov formulation of nonlinear small gain theorem for interconnected systems[END_REF] holds at all times.

The property stated as Theorem 1 is quite intuitive once the inequality ( 5) is sufficiently tight. The contribution of this result is, in fact, to show that such a dissipation inequality is always tight for some particular systems. More precisely, the proof of Theorem 1 relies on the following lemma, that may have interest on its own. It is similar in spirit to [START_REF] Ito | Necessary and sufficient small gain conditions for integral input-to-state stable systems: A Lyapunov perspective[END_REF]Lemma 1], but applies to any given Lyapunov function candidate. Its proof omitted due to lack of space, but can be found in [START_REF] Chaillet | A sensitivity trade-off arising in small-gain design for nonlinear systems: an iISS framework[END_REF].

Lemma 2 Given m, n ∈ N ≥1 , let ϕ : R n × R m → R be any continuous function satisfying |x| ≤ σ(u) ⇒ ϕ(x, u) ≥ 0 , ( 14
)
for some continuous function σ : R m → R ≥0 . Consider any Lyapunov function candidate V : R n → R ≥0 satisfying

∂V ∂x (x) = 0 , ∀x = 0 . (15)
Then, there exists a vector field f :

R n × R m → R n , continuous on R n ×(R m \ ker(σ)), such that, all x ∈ R n and all u ∈ R m , ∂V ∂x (x)f (x, u) ≤ ϕ(x, u) (16)
|x| ≥ σ(u) ⇒ ∂V ∂x (x)f (x, u) = ϕ(x, u) . (17)
This lemma shows that, under mild assumptions, the dissipation inequality (5) is always "tight" for what we refer to as a worst-case system. In other words, any Lyapunov function candidate constitutes a tight iISS/ISS estimate of the behavior of these systems. This can be seen by taking ϕ as an iISS or ISS supply pair for this system. Here we refer to a "worst case" situation as, for this system, the application of any input signal works against the convergence of the associated Lyapunov function, and that it can be compensated by no greater dissipation rate than α(|x|).

Remark 2

The right-hand side f of the constructed system may not be locally Lipschitz. However, depending on the choice of the function ϕ, the existence of solutions may be guaranteed at all time. For instance, the application of the comparison lemma guarantees forward completeness for any function ϕ satisfying, at least for large |x|,

ϕ(x, u) ≤ cV (x) + η(|u|) ,
where c ∈ R and η : R m → R denotes a continuous function. See [START_REF] Ito | Interpreting the iISS Small-Gain Theorem as Transient Plus ISS Small-Gain Regulation[END_REF] for further discussions on how forward completeness of feedback systems can be guaranteed. Also, the fact that f is not necessarily continuous in u = 0 is not a crucial issue as Lemma 2 will typically be used for inputs lower-bounded away from zero.

V. SENSITIVITY TO d 2 : IMPEDING DISTURBANCES

In most situations, exogenous inputs do not systematically work against the convergence of the associated Lyapunov function, as opposed to the worst-case systems developed in Section IV. For instance, for the scalar system ẋ = -x + d, any positive signal d tends to slowing down the convergence of x to zero for positive values of the initial state x 0 , but it actually speeds it up if x 0 ≤ 0. This observation suggests that no tight Lyapunov function, in the sense of Lemma 2, exists for most dynamical systems of practical relevance, nor can a Lyapunov function candidate W satisfying

Ẇ ≥ -α(|x|) + γ(|u|) , ∀x ∈ R n , ∀u ∈ R m ,
with α, γ ∈ K, be expected in general. On the other hand, in many cases, disturbances do induce an increase of the associated Lyapunov function at least in some regions of the state space. It is also reasonable to assume that their size are bounded for bounded states. This motivates the following assumption, which can be seen as a destabilizing counterpart of the small control property, cf. e.g. [START_REF] Sontag | A "universal" construction of Artstein's theorem on nonlinear stabilization[END_REF], [START_REF] Freeman | Robust Nonlinear control design: State-space and Lyapunov control techniques[END_REF].

Assumption 3 There exists a Lyapunov function candidate W 2 : R n2 → R ≥0 , a K function Υ 2 and a continuous3 function d 2 : R n1+n2 → R m2 such that, given any

x = (x T 1 , x T 2 ) T ∈ R n1+n2 , |d 2 (x)| ≤ Υ 2 (|x|) (18)
∂W 2 ∂x 2 (x 2 )f 2 (x 2 , x 1 , d 2 (x)) > 0 .
This assumption ensures that at least one disturbance, whose size is somewhat "proportional" to the state norm, tends to destabilize the x 2 -subsystem with x 1 as an input. For feedback systems satisfying Assumption 3, the following result shows that the tuning of the gain θ cannot be expected to induce arbitrary d 2 -disturbance rejection. Due to space constraints, its proof cannot be included here, but can be found in the on-line preprint [START_REF] Chaillet | A sensitivity trade-off arising in small-gain design for nonlinear systems: an iISS framework[END_REF].

Theorem 2 Let Assumption 3 hold. Then there exists Υ ∈ K such that, given any δ > 0, there exists a signal

d 2 ∈ U m2 satisfying d 2 ≤ Υ(δ) (19)
such that, given any θ ∈ Θ and any d 1 ∈ U m1 , the set R n \B δ is globally attractive for the feedback interconnection (1) (i.e., lim inf t→∞ |x(t; x 0 , d)| ≥ δ for all x 0 ∈ R n ) if the latter is forward complete.

The above result establishes that, for all systems satisfying Assumption 3, either the resulting interconnection is not forward complete (in which case disturbance rejection is obviously not achieved), or any ball centered at the origin can be made repellent for the overall interconnection, regardless of the choice of the tuning gain θ, by a bounded disturbance d 2 whose amplitude is "proportional" to the size of the chosen ball. This means that the maximum disturbance rejection is purely a function of the applied disturbance d 2 and that the tuning of θ has no effect on it. We stress that, in the above result, the larger the upper bound in ( 19) is, the further away from origin solutions will asymptotically go to (as B δ grows larger).

Remark 3 If, in addition, the vector fields f 1 and f 2 are chosen according to Assumptions 1 and 2 and the small gain condition (7) holds, then Proposition 1 ensures that the overall system is iISS (hence, forward complete).

VI. CONCLUSION

Motivated by the observation that the smaller the loop gain is, the larger the internal stability margin is for a feedback system, this paper has investigated the effect of decreasing the loop gain on external stability, and established a natural trade-off between rejection of disturbances entering in different places in the feedback loop. If one subsystem's parameters are tuned to reduce the effects of its disturbances, then the other subsystem eventually has been shown to behave as if it were in open-loop. While this trade-off is quite natural, the dissipation formulation of this paper enables to confirm the property for nonlinear systems, thus without relying on transfer functions. This iISS framework employed in this paper also allows to encompass subsystems whose solutions are not necessarily bounded for bounded inputs. The extension to the interconnection of more than two subsystems cas be envisioned based on large-scale small gain theorems such as [START_REF] Dashkovskiy | Small gain theorems for large scale systems and construction of ISS Lyapunov functions[END_REF].

VII. PROOFS A. Proof of Theorem 1

First of all, notice that, since V 2 is a Lyapunov function candidate, (4) holds for some α

2 , α 2 ∈ K ∞ . Let u 2 := (x T 1 , d T 2 ) T and consider ϕ(x 2 , u 2 ) = -α 2 (|x 2 |) + γ 2 (|x 1 |) + φ2 (|d 2 |) ,
where φ2 is the class K function defined as φ2 (s) := 1 2 min {ϕ 2 (s); α 2 (s)} , ∀s ≥ 0 .

This construction of φ2 ensures that the function α -1 2 • φ2 is well defined over R ≥0 . Also, this function satisfies [START_REF] Khalil | Nonlinear systems[END_REF] for any continuous nonnegative function σ such that, for all u 2 ∈ R n1+m2 , σ(u 2 ) ≤ α -1 2 • φ2 (|d 2 |). In particular, this condition is fulfilled with σ(u 2 ) = σ 2 (|d 2 |), if σ 2 is the K function defined as

Applying Lemma 2 to V 2 with the above functions ϕ and σ ensures the existence of a vector field f 2 such that V2 :=

Let θ ∈ Θ be any arbitrary tuning gain, let d 1 ∈ U m1 , and consider any forward complete solution of (1) starting with an initial condition x 0 = (x T 10 , x T 20

) T ∈ R n1 ×R n2 satisfying |x 20 | ≥ α -1 2 • φ2 (d 2 ) . (23)
In view of [START_REF] Sontag | A "universal" construction of Artstein's theorem on nonlinear stabilization[END_REF], this ensures in particular that

|x 20 | > σ 2 ( d 2 ) . (24)
Let t 1 ∈ R ≥0 ∪ {∞} be defined as In view of (24) and invoking the continuity of solutions, it holds that t 1 ∈ R >0 ∪ {∞} and, for all t ∈ [0, t 1 ), it holds from ( 4) and ( 21) that

v2 (t) ≥ -α 2 (|x 2 (t)|) + φ2 (|d 2 (t)|) ≥ -α 2 • α -1 2 (v 2 (t)) + φ2 (d 2 ) , (26)
where v 2 (•) := V 2 (x 2 (•)). We then rely on the following lemma, whose proof is given in Section VII-B.

Lemma 3 Let α be a class K locally Lipschitz function and let a ∈ R ≥0 . Let [0, t) ⊂ R ≥0 be the maximum interval of existence of a diffentiable function v whose derivative satisfies v(t) ≥ -α(v(t)) + a for all t ∈ [0, t). Then the following implication holds:

  H. Ito is with Dept. of Systems Design and Informatics, Kyushu Institute of Technology, 680-4 Kawazu, Iizuka Fukuoka 820-8502, Japan hiroshi@ces.kyutech.ac.jp H. Ito's work is supported in part by Grant-in-Aid for Scientific Research of JSPS under grant 19560446 and 22560449.

Fig. 1 .

 1 Fig. 1. Feedback interconnection.

Theorem 1 2 < d max 2

 122 Let Assumption 1 hold, let d min be two positive constants, and let α 2 , γ 2 , ϕ 2 denote some given K functions. Let V 2 : R n2 → R ≥0 be any Lyapunov function candidate satisfying

t 1 :

 1 = sup {t ≥ 0 : |x 2 (τ )| > σ 2 ( d 2 ) ∀τ ∈ [0, t)} . (25)

  ∂V2 ∂x2 (x 2 )f 2 (x 2 , x 1 , d 2 ) ≤ -α 2 (|x 2 |) + γ 2 (|x 1 |) + φ2 (|d 2 |),for all x ∈ R n and all d 2 ∈ R n2 . This makes Assumption 2 fulfilled by noticing that φ2 (s) ≤ ϕ 2 (s) for all s ∈ R ≥0 . Lemma 2 also guarantees that, for all x and d 2 satisfying|x 2 | ≥ σ 2 (|d 2 |), V2 = -α 2 (|x 2 |) + γ 2 (|x 1 |) + φ2 (|d 2 |) ≥ -α 2 (|x 2 |) + φ2 (|d 2 |) .(21)Note that, since σ(u2 ) = σ 2 (|d 2 |) and σ 2 ∈ K, ker(σ) = R n1 × (R m2 \ {0}). Lemma 2 thus ensures that f 2 is continuous over R n2 × R n1 × (R m2 \ {0}). Now, consider any disturbance d 2 ∈ U m2 satisfying (12) and let d 2 := ess inf τ ≥0 |d 2 (τ )|. Note that it holds that d 2 ≥ d min

2 , d 2 ≤ d max 2 .

This combination is sometimes referred to as Strong iISS.

Condition[START_REF] Freeman | Robust Nonlinear control design: State-space and Lyapunov control techniques[END_REF] requires in particular that either γ 1 (∞) is finite or α 1 ∈ K∞. In both cases, Assumption 1 guarantees that a convenient tuning of θ makes (1a) ISS with respect to x 2 . More details can be found in[START_REF] Ito | Necessary and sufficient small gain conditions for integral input-to-state stable systems: A Lyapunov perspective[END_REF].

The continuity requirement on d 2 may probably be relaxed by relying on Arstein-type constructions[START_REF] Sontag | A "universal" construction of Artstein's theorem on nonlinear stabilization[END_REF] to get a continuous destablizing feedback. Since such a construction is of limited interest in the context of this note, we assume continuity of d 2 for simplicity.

Recalling that the function α 2 • α -1 2 is invertible over [0, φ2 (d 2 )] by construction of φ2 , Equation (26) together with Lemma 3 ensure that

which yields, in view of (4),

where the functions η 2 , ν 2 ∈ K are defined as

Equation [START_REF] Teel | On assigning the derivative of a disturbance attenuation Control Lyapunov Function[END_REF] guarantees that the left-hand side of the above implication holds true. Hence

In other words, Theorem 1 is proved if we show that t 1 = +∞. If it were not the case, then it would mean, in view of (25), that

Consider the greatest time t 2 ≥ 0 for which

In view of (28), we necessarily have that t 2 ≥ t 1 . But [START_REF] Sontag | A "universal" construction of Artstein's theorem on nonlinear stabilization[END_REF] and (27) ensure that σ 2 (d 2 ) < ν 2 (d 2 ). The continuity of solutions together with (25), ( 29) and (30) then impose that t 2 < t 1 , which induces a contradiction. Thus, t 1 is infinite, which makes (28) valid for all t ≥ 0 and concludes the proof.

B. Proof of Lemma 3

We distintiguish between two cases. Case 1: a < α(∞). Consider the differential equation ẏ = -α(y) + a. Then letting z := y -α -1 (a) yields ż = -α(z) where α is the locally Lipschitz class K function defined as α(s) := α(s + α -1 (a)) -a. By [14, Lemma 4.4], z(•) exists over R ≥0 and satisfies z(t) = β(z(0), t), where β ∈ KL, for all z(0) ≥ 0, and all t ≥ 0. In terms of y, this reads y(t) = β(y(0) -α -1 (a), t) + α -1 (a) for all y(0) ≥ α -1 (a). But [START_REF] Khalil | Nonlinear systems[END_REF]Lemma 3.3] guarantees that, if v(0) ≥ y(0), then v(t) ≥ y(t) for all t ∈ [0, t). It follows that, for all v(0) ≥ α -1 (a), v(t) ≥ α -1 (a) for all t ∈ [0, t).

Case 2: a ≥ α(∞). In this case, v(t) ≥ 0 for all t ∈ [0, t), which makes the claim trivial.

VIII. ACKNOWLEDGEMENT

The author warmly thank an anymous reviewer of a previous version of this work, who greatly helped improving the clarity and readability of this document. The authors also thank W. Pasillas-Lépine and L. Greco for fruitful comments.


Esten Grotli

Antoine Chaillet

Elena Panteley

Jan Tommy Gravdahl

Esten I Grøtli

Optimal controller gain tuning for robust stability of spacecraft formation

Keywords: Robustness, ISS, Moving average of disturbances, Spacecraft formation, gain tuning

The spacecraft formation control problem sets high demands to the performance, especially with respect to positional accuracy. The problem is further complicated due to scarce fuel resources and limited actuation effects, in addition to the many sources of disturbances. This paper addresses the problem of finding the optimal gains of spacecraft formation controllers. By optimal, we mean the gains that minimizes a cost functional which penalizes both the control efforts and the state deviation, while still guaranteeing stability of the closed-loop systems in the presence of disturbances.

INTRODUCTION

Formations of spacecraft are mainly motivated by their flexibility and increased baseline length compared to monolithic spacecraft. They are complex systems which require precise control to maintain relative trajectories, even in the presence of disturbances. These disturbances are often only described by the statistical or averaged characteristics of the perturbing signals (e.g. amplitude, energy, average energy, etc.), and are due to for instance intervehicle interference, solar wind and radiation and gravitational effects. To account for the limited fuel resources, the control law should minimize the fuel consumption, while still guaranteeing a predefined accuracy.

Ignoring the disturbances, an optimal control, that is the control input that minimizes some sensible cost function, can be derived using the Hamilton-Jacobi-Bellman equation or Pontryagin's maximum principle. With the introduction of H ∞ methods, by [START_REF] Zames | Feedback and optimal sensitivity: model reference transformations, multiplicative seminorms, and approximate inverses[END_REF], one can specify the level of plant uncertainty and the signal gain from disturbance inputs to error outputs [START_REF] Doyle | Robust and optimal control[END_REF]. Although the H ∞ control problem was initially stated for systems described by transfer matrices, the ideas were soon translated into a state space setting [START_REF] Tadmor | Worst-case design in the time domain: The maximum principle and the standard H ∞ problem[END_REF], by realizing that the H ∞ norm is the L 2 induced norm in the time domain. The nonlinear equivalent of the H ∞ problem was shown by [START_REF] Van Der Schaft | L 2 -gain analysis of nonlinear systems and nonlinear state feedback H ∞ control[END_REF] to be determined by the Hamilton-Jacobi-Isaacs (HJI) equation or inequality. An analytic solution to the HJI equation is general difficult to find. With the introduction of the inverse optimal control problem by [START_REF] Freeman | Robust nonlinear control design: state-space and Lyapunov techniques[END_REF], the performance index is a posteriori determined rather than a priori.

In [START_REF] Krstić | Inverse optimal design of input-to-state stabilizing nonlinear controllers[END_REF] this idea was applied to systems with disturbances, and it was shown that inputto-state stabilizability is a necessary and sufficient condition for what is known as the inverse optimal gain assignment problem to be solvable. The sufficiency part is relying on the Sontag type control law introduced in [START_REF] Sontag | A 'universal' construction of Artstein's theorem on nonlinear stabilization[END_REF]. By solving the inverse optimal control problem solutions to a whole family of HJI equations are found. In [START_REF] Kazantizis | Optimal controller tuning for nonlinear processes[END_REF] the link between optimality and closed-loop stability was further investigated by relating the cost function to a Lyapunov function, with the purpose of an optimal selection of the controller design parameters.

The problem of study in this paper is similar to the problem in [START_REF] Kazantizis | Optimal controller tuning for nonlinear processes[END_REF], however we do not use the Lyapunov function as our cost function. Instead we introduce a new cost function, and solve the optimization problem with the stability constraints based on the Lyapunov analysis. The Lyapunov analysis of was performed in a previous paper by the authors, [START_REF] Grøtli | Robustness of ISS systems to inputs with limited moving average, with application to spacecraft formations[END_REF], and a guarantee for a hard bound on the state norm for input-to-state stable (ISS) systems in presence of signals with limited moving average were found. Furthermore, it was shown that the Lyapunov function can give an explicit estimate of the maximum of the disturbances' moving average that can be tolerated for a given precision. For the sake of completeness, some of the results are repeated here. In this paper we address the problem of finding the optimal gains, subject to constraints imposed by the Lyapunov analysis to achieve the above mentioned precision and stability. We consider a cost functional that is quadratic in both state and control variables, and the optimization is performed using fmincon, because of its ability to handle nonlinear constraints. We emphasize that we are not doing optimal control in usual sense, as the the controller and observer has already been designed without necessarily optimality in mind. It is obvious that the performance is restricted by parameterization of the chosen control law. andβ(s, •) is decreasing and tends to zero as s tends to infinity. The solutions of the differential equation ẋ = f (x, u) with initial condition x 0 ∈ R n is denoted by x(•; x 0 , u). We use | • | for the Euclidean norm of vectors and the induced norm of matrices. The closed ball in R n of radius δ ≥ 0 centered at the origin is denoted by B δ , i.e. B δ := {x ∈ R n : |x| ≤ δ}. | • | δ denotes the distance to the ball B δ , that is |x| δ := inf z∈B δ |x -z|. U denotes the set of all measurable locally essentially bounded signals u : R ≥0 → R p . For a signal u ∈ U, u ∞ := ess sup t≥0 |u(t)|. The maximum and minimum eigenvalues of a symmetric matrix A are denoted by λ max (A) and λ min (A), respectively. I n and 0 n denote the identity and zero matrices of R n×n respectively. We use E for the expectancy operator.

Notation and terminology A continuous function

α : R ≥ → R ≥0 is of class K (α ∈ K ), if it is strictly increasing and α(0) = 0. If, in addition, α(s) → ∞ as s → ∞, then α is of class K ∞ (α ∈ K ∞ ). A continuous function β : R ≥0 × R ≥0 → R ≥0 is said to be of class K L if, β(•,t) ∈ K for any t ∈ R ≥0 ,

ISS SYSTEMS AND SIGNALS WITH LOW MOVING AVERAGE

We start by recalling some classical definitions related to the stability and robustness of nonlinear systems of the form ẋ = f (x, u),

where x ∈ R n , u ∈ U and f : R n × R p → R n is locally Lipschitz and satisfies f (0, 0) = 0.

Definition 1. Let δ be a nonnegative constant and W ⊂ U. The ball B δ is said to be globally exponentially stable (GES) for (1) with respect to W if there exists some positive constants k 1 and k 2 such that the solution of (1) satisfies

|x(t; x 0 , u)| ≤ δ + k 1 |x 0 |e -k 2 t , ∀t ≥ 0. ( 2
)
for all x 0 ∈ R n and all u ∈ W .

We next recall the definition of ISS, originally introduced in [START_REF] Sontag | Smooth stabilization implies coprime factorization[END_REF].

Definition 2. The system ẋ = f (x, u) is said to be input-to-state stable (ISS) if there exist β ∈ K L and γ ∈ K ∞ such that, for all x 0 ∈ R n and all u ∈ U, the solution of (1)

satisfies |x(t; x 0 , u)| ≤ β(|x 0 |,t) + γ( u ∞ ) , ∀t ≥ 0 . (3)
ISS thus imposes an asymptotic decay of the norm of the state up to a function of the amplitude u ∞ of the input signal.

We also recall the following well-known Lyapunov characterization of ISS, originally established in [START_REF] Praly | Stabilization in spite of matched unmodeled dynamics and an equivalent definition of input-to-state stability[END_REF] and thus extending the original characterization proposed by Sontag in [START_REF] Sontag | On characterizations of the input-to-state stability property[END_REF].

Proposition 1. The system (1) is ISS if and only if there exist α, α, γ ∈ K ∞ and κ > 0 such that, for all x ∈ R n and all u ∈ R p ,

α(|x|) ≤ V (x) ≤ α(|x|) (4)
∂V ∂x (x) f (x, u) ≤ -κV (x) + γ(|u|) . (5)
γ is then called a supply rate for (1).

The input signals we consider in this paper are slightly more restrictive than those in for instance [START_REF] Angeli | Power characterizations of input-to-state stability and integral inputto-state stability[END_REF], but the advantage is that a hard bound on the state norm can be guaranteed. Namely, we consider input signals with bounded moving average. Definition 3. Given some constants E, T > 0 and some function γ ∈ K , the set W γ (E, T )

denotes the set of all signals u ∈ U satisfying t+T t γ(|u(s)|)ds ≤ E , ∀t ∈ R ≥0 .
The main concern here is the measure E of the maximum energy that can be fed into the system over a moving time window of given length T . These quantities are the only information on the disturbances that are taken into account in the control design. More parsimonious control laws than those based on the disturbances' amplitude or energy can therefore be expected. We stress that signals of this class are not necessarily globally essentially bounded, nor are they required to have a finite energy. Robustness to this class of signals thus constitutes an extension of the typical properties of ISS systems.

With input signals with bounded moving average, the following result of [START_REF] Grøtli | Robustness of ISS systems to inputs with limited moving average, with application to spacecraft formations[END_REF] guarantees global exponential stability of some neighborhood of the origin.

Corollary 1. Assume there exists a continuously differentiable function V : R n → R ≥0 , class K ∞ function γ, functions α (s) = cs p and α (s) = cs p , with c, c, p positive constants, and a positive constant κ such that (4) and ( 5) hold for all x ∈ R n and all u ∈ R p . Then, given any T, δ > 0, the ball B δ is GES for (1) with any signal u ∈ W γ (E, T ) provided that E(T, δ) ≤ cδ p 2 e κT -1 2e κT -1 .

SPACECRAFT FORMATION CONTROL

The results of Section 2 were in [START_REF] Grøtli | Robustness of ISS systems to inputs with limited moving average, with application to spacecraft formations[END_REF] exploited to demonstrate robustness of a spacecraft formation control in a leader-follower configuration. We will here only include the parts necessary to keep this section self-contained. For further details, the reader is referred to the original paper.

Spacecraft models

The model for the leader spacecrafts motion with respect to a moving coordinate frame is given by p

+C (ν o ) ṗ + D (ν o , νo ) p + n (r o , p) = F l (6)
while the model for follower spacecraft with respect to the leader is given by

ρ +C (ν o ) ρ + D (ν o , νo ) ρ + n (r o + p, ρ) = F f -F l , (7)
where

F l := (u l + d l )/m l , F f := (u f + d f )/m f ,
and where subscripts l and f stand for the leader and follower spacecraft respectively. p is the position of the leader spacecraft with respect to a coordinate frame in a Keplerian orbit, where as ρ is the position of the follower spacecraft with respect to the leader. m l and m f are the spacecraft' masses, u l and u f are the control inputs, and d l and d f denote all exogenous perturbations acting on the spacecraft. Furthermore,

C (ν o ) := 2ν o C, C :=   0 -1 0 1 0 0 0 0 0   , D (ν o , νo ) := ν2 o D + νo C, D := diag(-1, -1, 0), and
n (r o , p) := µ r o + p |r o + p| 3 - r o |r o | 3 ,
with r o being the origin of the coordinate reference frame, and ν o the true anomaly. We make the following assumptions on the first and second derivatives of ν o :

Assumption 1 The true anomaly rate νo and true anomaly rate-of-change νo of the reference frame satisfy νo ∞ ≤ β νo and νo ∞ ≤ β νo , for some positive constants β νo and β νo .

Controller and observer design

In [START_REF] Grøtli | Robustness of ISS systems to inputs with limited moving average, with application to spacecraft formations[END_REF] the proposed controller of the leader spacecraft were:

u l =m l pd +C (ν o ) ṗd + D (ν o , νo ) p + n (r o , p) -k l ( ṗ0 -ṗr ) (8)
with p d being the reference trajectory, e l = pp d the tracking error, p = pp the estimation error, ṗr = ṗdl e l , ṗ0 = ṗl p, and with velocity estimate provided by

ṗ =a l + (l l + l ) p (9) ȧl = pd + l l l p . ( 10
)
The controller for the follower spacecraft has a similar structure, given by

u f =m f pd + ρd +C (ν o ) ( ṗd + ρd ) + D (ν o , νo ) (p + ρ) + n (r o + p, ρ) + n (r o , p) -k l ( ṗ0 -ṗr ) -k f ( ρ0 -ρr ) (11)
with ρ being the reference trajectory, e f = ρρ d the follower spacecraft tracking error, ρ = ρρ the estimation error, auxiliary signals ρr = ρdf e f and ρ0 = ρf ρ, and with the observer

ρ =a f + (l f + f ) ρ (12)
ȧ f = ρd + l f f ρ (13)
The parameters k l , l l , l , k f , l f and f denote some positive tuning gains. The closedloop system may now be summarized into the equations

Ẋ = A(ν o (t), θ)X + Bd , (14)
where X := (X l , X f ) with X l := (e l , ė l , p , ṗ ) and

X f := (e f , ė f , ρ , ρ ) , d := (d l , d f ) , θ := (k l , l , l l , k f , f , l f ) and A := blckdiag(A l , A f ) with A i (ν o ) :=     0 3 I 3 0 3 0 3 a 21 a 22 (ν o ) a 23 a 24 0 3 0 3 0 3 I 3 a 41 a 42 (ν o ) a 43 a 44     , (15)
for i ∈ {l, f }. Out of notational compactness, the following matrices have been used:

a 21 := a 41 := -k i i I 3 , a 22 := a 42 := -C(ν o ) -k i I 3 , a 23 := k i i I 3 , a 24 := k i I 3 , a 43 := (k i -l i ) i I 3 and a 44 := (k i -l i -i )I 3 . Finally, B := (B l , B f ) with B l := 1 m l     0 3 0 3 I 3 0 3 0 3 0 3 I 3 0 3     and B f := 1 m l m f     0 3 0 3 -m f I 3 m l I 3 0 3 0 3 -m f I 3 m l I 3     .

Robustness of the overall formation

The following result establishes robustness of the controlled formation to a wide class of disturbances: Proposition 2. Let Assumption 1 hold. Let the controller of the leader spacecraft be given by ( 8)- [START_REF] Krstić | Inverse optimal design of input-to-state stabilizing nonlinear controllers[END_REF] and the controller of the follower spacecraft be given by ( 11)- [START_REF] Van Der Schaft | L 2 -gain analysis of nonlinear systems and nonlinear state feedback H ∞ control[END_REF] with, for each i ∈ {l, f }, l i ≥ 2k i , k i > 2k i , where

k i := i + βi if k i -i ≤ k i 2 i βi / 2 i otherwise, with βi := β νo 2 2 i + 1 + 1 + m 2 f m 2 l l 2 i + 1 m 2 i . ( 16
)
Given any precision δ > 0 and any time window T > 0, consider any average energy satisfying

E ≤ 1 4 min i∈{l, f } 2 i - 1 2 4 4 i + 1 + 1 2 δ 2 e κT -1 2e κT -1 , (17)
where

κ := min i∈{l, f } k i / max i∈{l, f } k i i max i∈{l, f } 2 i + 1 2 4 4 i + 1 + 1 2 . (18)
Then, for any d ∈ W γ (E, T ) where γ(s) := s 2 , the ball B δ is GES for the overall formation summarized by [START_REF] Serrani | Robust coordinated control of satellite formations subject to gravity perturbations[END_REF].

The proof of the proposition is found in [START_REF] Grøtli | Robustness of ISS systems to inputs with limited moving average, with application to spacecraft formations[END_REF].

As already stressed, the results recalled in Section 2 allow to expect more parsimonious solicitation of the actuators than classical ISS-based reasonings. However, such an improvement will only be made practical if the gains of Proposition 2 are tuned in an adequate manner. The rest of the document focuses on this issue.

Optimal controller and observer gain tuning

Of simplicity we will in the following consider the unperturbed version of ( 14),

Ẋ = A(ν o (t), θ)X , ( 19
)
since d is only characterized by its moving average and therefore difficult to incorporate in the optimization problem we will set forth in the sequel. One possibility to incorporate the disturbance into the optimization problem would be to look at the worst case scenario, which is typical of differential game problems or the inverse optimal gain assignment problem mentioned in the introduction. The worst case excitation due to the disturbances with limited moving average, can for a linear system be found using the results of [START_REF] Houska | Robust nonlinear optimal control of dynamic systems with affine uncertainties[END_REF]. We however, aim at finding the parameters θ, which are the best compromise between fast state convergence and limited control efforts, while ignoring the effect of the disturbance. If the problem is posed as an optimization problem, a common choice is to use a cost function which quadratically penalizes control and state deviation, i.e. a cost function of the form

J(θ) = t h t 0 X(τ) QX(τ) + u(τ) Ru(τ)dτ (20)
with weighting matrices Q ∈ R 24×24 and R ∈ R 6×6 both being symmetric and positive definite, optimization horizon t h and u = (u l , u f ) , where

u l = m l D (ν o , νo ) e l -k l ( ṗ0 -ṗr ) (21)
and

u f = m f D (ν o , νo ) (e l + e f ) -k l ( ṗ0 -ṗr ) -k f ( ρ0 -ρr ) (22)
are the terms of ( 8) and ( 11), respectively, that we want to penalize. It can be noticed, that we have chosen not to penalize the feed-forward terms from the reference and the gravity compensation in ( 8) and [START_REF] Ploen | Dynamics of earth orbiting formations[END_REF]. The cost (20), can be written as:

J(θ) = t h t 0 X (τ)(Q + (T + Ξ) R(T + Ξ))X(τ)dτ (23)
with

T := m f m l m f k l l I 3 m l m f k l I 3 -m l m f k l l I 3 -m l m f k l I 3 0 3 0 3 0 3 0 3 k l l I 3 k l I 3 -k l l I 3 -k l I 3 k f f I 3 k f I 3 -k f f I 3 -k f I 3 , (24)
and

Ξ := m l D(ν o , νo ) 0 3 0 3 m f D(ν o , νo )
I 3 0 3 0 3 0 3 0 3 0 3 0 3 0 3 I 3 0 3 0 3 0 3

I 3 0 3 0 3 0 3 . ( 25
)
We now introduce the state transition matrix Φ(t,t o ) which is the unique solution of

∂ ∂t Φ(t,t 0 ) = A(ν o (t), θ)Φ(t,t 0 ) , (26)
with initial condition

Φ(t 0 ,t 0 ) = I 24 . ( 27
)
The solution to [START_REF] Zames | Feedback and optimal sensitivity: model reference transformations, multiplicative seminorms, and approximate inverses[END_REF] is

X(t) = Φ(t,t 0 )X 0 , (28)
and is used to rewrite the cost function into the following form

J(θ) = X 0 t h t 0 Φ (τ,t 0 )(Q + (T + Ξ(τ)) R(T + Ξ(τ)))Φ(τ,t 0 )dτX 0 . ( 29
)
We will avoid dependency of the cost function on initial conditions, and will assume that X 0 are randomized variables with zero mean, and covariance matrix equal to identity, that is E{X 0 X 0 } = I 24 . By defining

P(t h ,t 0 ) := t h t 0 Φ (τ,t 0 )(Q + (T + Ξ(τ)) R(T + Ξ(τ)))Φ(τ,t 0 )dτ (30)
and using the fact that

E{X 0 P(t h ,t 0 )X 0 } = E{trace X 0 P(t h ,t 0 )X 0 } = E{trace X 0 X 0 P(t h ,t 0 )} = trace E{X 0 X 0 }P(t h ,t 0 ) = trace P(t h ,t 0 ) ,
our optimization problem can be formulated as

min θ E{J(θ)} = min θ trace P(t h ,t 0 ) (31) subject to ∂ ∂t Φ(t,t 0 ) = A(ν o (t), θ)Φ(t,t 0 ) , (32)
with Φ(t 0 ,t 0 ) = I 24 ,

∂ ∂t P(t,t 0 ) = Φ (t,t 0 )(Q + (T + Ξ(t)) )R(T + Ξ(t)))Φ(t,t 0 ) , (33)
with

P(t 0 ,t 0 ) = (Q + (T + Ξ(t 0 )) R(T + Ξ(t 0 ))), for each i ∈ {l, f }, l i ≥ 2k i (34) k i > 2k i ( 35
)
where

k i := i + βi if k i -i ≤ k i 2 i βi / 2 i otherwise, ( 36
) with βi := β νo 2 2 i + 1 + 1 + m 2 f m 2 l l 2 i + 1 m 2 i , (37)
and

k l , l , k f , f ∈ [0, 2] (38) l l ∈ [0, 10] (39) l f ∈ [0, 15] . (40)
The constraints (38)-( 40) are introduced to more efficiently solve the problem. The problem was solved using the interior point algorithm of the function fmincon in MAT-LAB.

The true anomaly, ν o , of the reference frame can be obtained by numerical integration of the equation

νo (t) = √ µ (1 + e o cos ν o (t)) 2 1 2 (r a + r p ) (1 -e 2 o ) 3/2 , (41)
where radius of perigee and apogee is chosen as r p = 10 7 m and r a = 3 × 10 7 m, respectively. The true anomaly rate and rate of change are calculated using (41) and

νo (t) = -2µe o (1 + e o cos ν o (t)) 3 sin ν o (t) 1 2 (r p + r a ) (1 -e 2 o ) 3 . (42)
The eccentricity can be calculated from r a and r p to be e o = 0.5, and we see from (42), that the constant β νo in Assumption 1 can be chosen as β νo = 4×10 -7 . The constant β νo in Assumption 1 can be chosen as β νo = 8 × 10 -4 as seen from ( 41). We have assumed that the reference frame is initially at perigee, that is ν o (t 0 ) = 0 and νo (t 0 ) = v p /r p , where

v p = 2µ 1 r p - 1 (r p + r a ) . ( 43
)
The horizon of the problem was chosen as t h = 30, and the optimization problem was solved using R = I 24 and Q with ones along the diagonal except that

Q(2, 2) = Q(3, 3) = Q(14, 14) = Q(15, 15) = 20.
It can be argued that choosing the elements of R and Q is as hard as finding the parameters θ in the original problem. However, with the common choice of diagonal Q and R, choosing Q and R is more intuitive in the authors opinion. The optimization problem, was solved with all combinations of initial conditions θ i ∈ {0, 1, 2}, and the results are summarized in 1, we see that the parameters l l and l f are most affected by different initial guesses for the parameters.

The parameters giving the lowest cost function were then used as initial guess, and the problem was solved with different values for the horizon t h . The results in Table 2 suggests that the found parameters represent a good local minimum.

Simulations

We will now provide simulations of the spacecraft formation, using the gains achieved from the optimization procedure in the previous section. For simplicity, we choose the desired trajectory of the leader spacecraft to coincide with the reference orbit, i.e. p d (•) ≡ (0, 0, 0) . The reference orbit is generated by numerical integration of ro = -

µ |r o | 3 r o , (44)
with r o (0) = (r p , 0, 0) and ṙo (0) = (0, v p , 0), with v p as in (43). Initial values of the leader spacecraft are p (0) = (2, -2, 3) and ṗ (0) = (0.4, -0.8, -0.2) . The initial values of the observer are chosen as p (0) = (0, 0, 0) and a l (0) = (0, 0, 0) . The reference trajectory of the follower spacecraft are chosen as the solutions of a special case of the Clohessy-Wiltshire equations, cf. [START_REF] Clohessy | Terminal guidance system for satellite rendezvous[END_REF]. We use

ρ d (t) =   10 cos ν o (t) -20 sin ν o (t) 0   . (45)
This choice imposes that the two spacecraft evolve in the same orbital plane, and that the follower spacecraft makes a full rotation about the leader spacecraft at each orbit around the Earth. The initial values of the follower spacecraft are ρ (0) = (9, -1, 2) and ρ (0) = (-0.3, 0.2, 0.6) . The initial parameters of the observer are chosen to be ρ (0) = ρ d (0) = (10, 0, 0) and a f (0) = (0, 0, 0) . We use m f = m l = 25 kg both in the model and the control structure. With θ as the best value in Table 1, we find from (18) that κ = 0.0901. Over a 10 second interval (i.e. T=10), the average excitation must satisfy E(T, δ) ≤ 0.0061 δ 2 , according to [START_REF] Sontag | On characterizations of the input-to-state stability property[END_REF]. We consider two types of disturbances acting on the spacecraft: "impacts" and continuous disturbances. The "impacts" have random amplitude, but with maximum of 1.5 N in each direction of the Cartesian frame. For simplicity, we assume that at most one impact can occur over each 10 second interval, and we assume that the duration of each impact is at most 0.1s. The continuous disturbances are taken as sinusoids, also acting in each direction of the Cartesian frame, and are chosen to be (0.1 sin 0.01t, 0.25 sin 0.03t, 0.3 sin 0.04t) for both spacecraft. Notice from (7) that the relative dynamics are influenced by disturbances acting on the leader and follower spacecraft, so the effect of the continuous part of the disturbance on the relative dynamics is zero. It can easily be shown that the disturbances satisfy the following: 2(d) that the effect of the continuous part of the disturbance is canceled out (since we consider relative dynamics and both spacecraft are influenced by the same continuous disturbance), whereas the effect of the impacts has increased compared to the effect of the impacts on the leader spacecraft. Since E = 1.42, and should satisfy E ≤ 0.0061δ 2 , this gives a very large δ. As can be seen from Figure 1(a), 1(b), 2(a), 2(b) the actual precision reached, is much better than the theoretical expectations. The reason for this is that the constraints on the control gains are based on Lyapunov analysis, which in general yields very conservative results, and also conservative estimates of the disturbances the control system is able to handle. However, we stress that the constraints on the gains based on moving average of the disturbance are much more relaxed than those obtained through a classical ISS approach, i.e. relying on the disturbance magnitude. Figure 1(c) and Figure 2(c), shows that the conservative estimates results in large transients in the actuation, but by finding the optimal parameters, the control efforts are heavily reduced compared to [START_REF] Grøtli | Robustness of ISS systems to inputs with limited moving average, with application to spacecraft formations[END_REF], while the tracking errors are kept at a reasonable level.

  )| 2 dτ ≤ 1.42 , ∀t ≥ 0 .

Fig. 1 .

 1 Fig. 1. Leader spacecraft.

Figure 1 (

 1 Figure 1(a), 1(b) and 1(c) show the position tracking error, position estimation error and control history of the leader spacecraft, whereas Figure 2(a), 2(b) and 2(c) are the equivalent figures for the follower spacecraft. Figure 1(d) and 2(d) show the effect of d l and d fd l acting on the formation. Notice in Figure2(d) that the effect of the continuous part of the disturbance is canceled out (since we consider relative dynamics and both spacecraft are influenced by the same continuous disturbance), whereas the effect of the impacts has increased compared to the effect of the impacts on the leader spacecraft. Since E = 1.42, and should satisfy E ≤ 0.0061δ 2 , this gives a very large δ. As can be seen from Figure1(a), 1(b), 2(a), 2(b) the actual precision reached, is much better than the theoretical expectations. The reason for this is that the constraints on the control gains are based on Lyapunov analysis, which in general yields very conservative results, and also conservative estimates of the disturbances the control system is able to

Fig. 2 .

 2 Fig. 2. Follower spacecraft.

Table 1 .

 1 The reason for solving

	Parameter k l	l	l l	k f	f	l f
	Best value 0.3382 0.2658 2.0048 0.3738 0.3302 1.7644
	Mean 0.3280 0.2809 1.6541 0.3855 0.3154 1.8660

Table 1 .

 1 Optimization result of 729 iterations, covering all combinations of initial conditions θ i ∈ {0, 1, 2}. By Best value, we mean the parameters which gives the lowest cost function value.the optimization problem with several different initial values, is to find, if not a global minimum, then at least a good local minimum. Looking at mean values in Table

Table 2 .

 2 Optimization result with different values of the horizon length t h .

	Horizon k l	l	l l	k f	f	l f
	20 0.3195 0.2743 1.5802 0.3829 0.3200 1.8948
	50 0.3382 0.2658 2.0048 0.3738 0.3302 1.7644
	100 0.3382 0.2658 2.0048 0.3738 0.3302 1.7644
	300 0.3415 0.3089 1.9524 0.3631 0.3245 1.7608
	1000 0.3382 0.2658 2.0048 0.3738 0.3302 1.7644


Krzysztof ; Kujawski
email: krzysztof.kujawski@pwr.wroc.pl

Jerzy Świątek

Cyclogram Unfolding in Dynamic Hoist Scheduling Problem

Keywords: hoist scheduling problem, DHSP hoist scheduling problem, dynamic hoist scheduling problem, electroplating, real time scheduling, flexible manufacturing system

  L'archive ouverte pluridisciplinaire

INTRODUCTION

In electroplating industry a HSP -Hoist Scheduling Problem occurs. It deals with creating a proper schedule for machinery working on a production line. To fulfil customer needs, there is a necessity of flexible production systems. In such systems, there is a possibility to produce many types of products. The production orders change frequently. Such conditions are often in electroplating lines, although printed circuit board production lines and some food processing lines are organized similarly. An electroplating production line most important feature is chemical processing. It implies surface treatment constraints on the production. Products cannot stay in workstations after processing, because they would be destroyed, e.g. melted in acid or rendered too hot. No-buffer rule also applies here. Semi-finished products cannot be stored in order to be used later, since they would lose their qualities. A schedule, which does not meet no-wait and no-buffer constraints, is treated as infeasible. Mentioned constraints render the hoist transportation the most important subject of scheduling process. No-wait constraint requires a hoist to be present when maximum processing time is reached. Hoist is also only "buffer" available. Only during transportation, a product is not being processed. Additionally, transportation times are comparable to processing times, what makes them important in real-life schedules. A workstations schedule can be determined directly from a hoists schedule.

A production in electroplating lines can be variously organized. One or multiple hoists may be present at the production line, one or multiple types of items production can be scheduled. Cyclic (Cyclic Hoist Scheduling Problem) or dynamic production are also considered. In CHSP schedule is static. It is repeated in order to produce more items. Items must be introduced to line cyclically and the type of produced items is constant over time. In DHSP (Dynamic Hoist Scheduling Problem) schedule is created during production, items may vary both in type and sequence of introduction times.

In this paper, a heuristic scheduling method for the dynamic case is proposed.

HOIST SCHEDULING

An electroplating line covers processed items with thin material coatings using chemical reactions -usually by galvanization process. It is an automated production system, which use hoists as transportation medium. A production line consists of series of workstations capable of performing different elementary chemical reactions or material processing operations. In order to achieve a proper effect, a rough input product must be subjected to several reactions in specific sequence.

A production line consists of:

• Baths (tanks), a production line workstations, which perform a certain stage of processing. Tanks are capable of performing a specific chemical or material processing. Some baths can perform more than one task -they are called multifunctional baths. Some stages processing times, are significantly longer, than Usage of cyclograms has a number of advantages. The production can be easily controlled, due to a constant number of steps, which create a cyclogram.

Performance of production is known in advance and constant. In spite of those positive aspects, there are some boundaries of this type of production. It is difficult to create an efficient cyclogram supporting production of multiple item types. In case of any small change in items order, a costly line reset is required.

When flexibility of production is a priority, dynamic scheduling is used. so the line state outdates, found schedule will be impossible to implement, as it will refer to the past. This is a typical problem of responding in sufficient time in real-time systems. Introduction frequency of new items also has to be decided. Designating an item to production quickly may increase performance, but it also may cause that it is difficult to find a feasible schedule since a load of the resources is higher.

This paper focuses on solving a local scheduling problem.

Formulation of the Local Scheduling Problem

The problem of finding the schedule for a specified line, a queue of items, and a line the line, a queue of to be processed items, are also considered. A result schedule can be described by decisive variables of this problem: routes of hoists, assignments of pickup operations to hoists, assignments of put down operations to workstations in groups, times of pickup and put down operations. The optimization criterion is minimizing the time of a last put down operation. Such criterion maximizes the performance of the production line for a given product order. Similarly, to other scheduling problems, DHSP has many constraints. Schedule must fulfill process requirements -processing sequence must be correct, processing times must not be shorter than specified minimum times and longer than specified maximum times. A hoist can carry only one item at the time. A workstation can process only one item at the time. Hoists cannot move outside their physical capabilities, and they cannot collide. We provide only relevant symbols that are necessary to describe the cyclogram unfolding method.

N -number of product types,

{ } ∈ = ) 1,..., n N N . ( ) ( ) { } ( ) ( ) { } ( ) ( ) { } δ δ = = ∪ 1 ,..., 1 ,..., 1 ,..., Z z z K s s KC KQ -queue of items to be produced, ( )∈ ) s k N -in process products types upon rescheduling, ( ) δ ∈ ) k N - products in queue. ( )∈ ) z k N ,
( ) { } λ λ ∈ ϒ , , 1,..., U h
-the routes of hoists, represented as position of hoist h in production time λ . ϒ -time of production cease. The variables

( ) ( ) , k i z k t , ( ) ( ) , k i z k t
-the moments of picks and puts of products in i -th step workstation have to be established as well. The activities of picking up and putting down a product from/to workstation have to be assigned to the specific hoists

( ) ( ) ∈ ) , k i z k h H , ( ) ( ) ∈ ) , k i z k h H .
Additionally, for a given step of product processing, a specific station from group has to be chosen:

( ) ( ) , k i z k a
. Note that not all decisive variables need to be found. Pickup and putdowns of items already in process are already calculated up to the time of adaptation t τ = + ∆ . Initial hoists positions are in fact hoists positions in adaptation time ( ) ( )

= , 0 , U h U h t .
An optimization criterion used to reach a maximum manufacturing performance is

( ) ( ) ( ) = , max k I z k Q t .
The optimal solution is found when the criterion reaches a minimum. The criterion is minimized when last item in sequence leaves production line as soon it is possible.

Besides other constraints, the relevant are that

( ) ( ) ( ) ( ) ( ) + < , , 1 k i z k k i z k t t , ( ) ( ) ( ) ( ) < , , k i z k k i z k t t
-conditions of proper processing sequence of products and Jegou 2006 proposed somewhat better solution. This heuristic deals also with deciding when items are introduced to production. The method uses an agent system, to react at production events: new product, product processing reached a minimum time etc. A schedule is built as a result of reacting on these production events.

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) µ η ≤ - ≤ , , , , k i z k k i z k z k w i z k z k w i z k t t -condition
Schedule is created only in short time extent, waiting for another event. Solution supports multiple hoists and workstation groups.

Reactive scheduling is an almost perfect solution for non-cyclic manufacturing systems. The system is very flexible and can support production state changes.

Authors state that even hoist breakdown during production can be supported.

Calculation steps of scheduling are small and homogenous, which is important in realtime computation. There are also cons of this solution. It may happen that some products will be defective. Another problem is that the proposed solution does not support multifunction workstations and created schedules have low performance.

There are also a number of surface treatment systems, which are similar to

CYCLOGRAM UNFOLD METHOD

In described scheduling problem many of its elements have combinatory character. In spite of constraints, finding the optimal solution would require a full subspace search.

In real-life cases of big scale manufacturing, where many product types are considered, this is not an option. Scheduling in real-time is making this problem even more difficult. As a consequence, heuristics are used instead of exact methods.

Although heuristics do not guarantee that found solutions will be optimal, they allow creating high performance schedules, while providing lower computational complexity than exact methods.

In this section, a heuristic method is described. It minimizes calculation overhead during real-time schedule generation by using earlier prepared plans. The method emulates a behaviour of a line during cyclic production. It modifies a schedule of line reset in the way it is the shortest. For a proper working, a method of cyclogram unfolding requires a set of plans called cyclograms. Creating cyclograms is quite a challenge itself. However, since cyclograms are often used on real-world installations, there are many works present concerning cyclic production and creating cyclograms. They can be used as source of the cyclograms for cyclogram unfolding method. The described method requires at least one cyclogram for each of N types of processed products. As soon as a part completes processing on a machine, it must be immediately removed from that machine and transferred to the next machine.

Cyclogram

Cyclograms can support multiple hoists, multifunction tanks and workstation groups. All those features are also available in cyclogram unfold method, depending on the used cyclograms. Workstation 6,7 form a group, hence hoist pick and put operations are connected.

Note that hoists do not collide because they do not get close enough in any time moment. Such charts are frequently used by electroplating companies because they give an overview of schedule and allow easy verification of feasibility.

Cyclic scheduling can be formulated as an optimization problem similarly as dynamic scheduling.

Some of the notion is common in both problems and will not be repeated.

Main features of cyclogram is capacity and cycle time. Cycle time is a length of cyclogram in time domain. Capacity is a number of cycles needed to be done in order to fully load a production line and produce first item. After a production line is loaded each next cycle produces a new item. There can be many feasible cyclograms for one item type. Let us assume that there are a number cyclograms for each item type

{ } 1,..., n N ∈ referred as 1 ,..., N V V , ( ) { } 1,..., n n v V n V ∈ = )
. n V -number of cyclograms prepared for item type n . ( )

n T v -cycle-time of cyclogram n v , ( ) n G v -capacity of cyclogram n v .
Cyclogram can be defined similarly as schedules in DHSP -routes, times of operations and assignment of operations to hoists. ( )

, , n U v h Λ , ( ) { } 0,..., n T v Λ ∈ -routes

The Cyclogram Unfolding

Let us mark ( ) . The segmenting operation divides new order to subsequences of items of the same type. E.g. for queue Z={ } 1,1,3,1, 2, 2,3,3 , ( )

, n C x v = ( ) ( ) ( ) G n n v x T v + ⋅ - [ ] [ ] load unload T T n n v v + . ( )
Z Ξ means that following segments are created: { } 1,1 ,{ } 3 ,{ } 1 ,{ } 2, 2 ,{ } 3,3 .
That means that order of 8 products of 3 types is divided to 5 segments. The segmenting operation keeps the original sequence of products in queue.

For each segment created by ( )

Z Ξ
we can propose a route using cyclogram unfolding operation ( )

) ( ) ( ) ( ) , , k i z k k i z k t t + ∆ , ( ) ( ) ( ) ( ) , , k i z k k i z k t t + ∆ , ( ) ( ) ( ) , , 0 , , 0 , 0 U h t t U h t U h t τ τ  -∆ ->   -≤   .
In order to find a valid schedule for a given queue { } = 1 ,..., K Z z z by using segments, a series of time shifts ∆ s between all segments in queue Z has to be determined, where

{ } ∈ - 1,..., 1 s SEG
. Besides time shifts a hoist routes ( ) , U h t must also be determined, because the Ψ operation may break collision constraints.

Determining of time shifts and routes can be performed sequentially by

determining respectively ∆ 1 , ∆ 2 , etc. It is possible because of constraint - ∆ < ∆ < < ∆ 1 2 1 ... SEG .
Scheduling item queues composed from many segments may be solved as many updates of the queue segment by segment. It does not interfere with finding routes, as they need to be defined after all items from segments are completed.

In this way local scheduling problem is divided to several independent problems, with decisive variables reduced to ∆ s and hoist route matrix to be determined. Decisive variables of the original problem

( ) ( ) ( ) ( ) , ,
, ,

k i z k k i z k t t ( ) ( ) ( ) ( ) , ,
,

k i z k k i z k h h and
( ) ( ) , k i z k a
are already determined by cyclogram unfolding procedure, or are bound to value of ∆ s . Solving such simplified task may not give optimal solution, tough solving itself is much easier and less complex procedure.

Referring to original problem one additional constraint is present:

( ) ε + < ∆ ≤ + = ,0 , 1 , ( ) , a a I a x
x S x t t a s -a time shift must be at least bigger, than time of introduction of last item from last segment and it can be only smaller, than time of finishing this product. When

( ) ε + ∆ = + = , 1 , ( ) , a
ε + ∆ = + = , 1 , , a I a s s K s t a z
. It is similar situation as if new production was started when line is unloaded. ε -is minimal time needed for hoists to take their start up positions.

ε is constant value which can be calculated basing on production line parameters.

When dealing with segments, some of the constraints from the original problem are always satisfied. For instance the time of stage processing and that items are processed in valid sequence. Some of the other constraints are also always satisfied, in time intervals outside of segment overlapping. This makes scheduling much easier.

The Cyclogram Unfolding Method Algorithm

The cyclogram unfolding method is a heuristic method, which is able to create schedule for given DHSP problem. It bases on segmenting operation Ξ , shifting operation Ψ and routing method (point 4b) proposed in [START_REF] Kujawski | Zagadnie nie optymalizacji działania wybranych linii produkcyjnych[END_REF] Cyclogram Unfolding 1) Calculate Ξ for queue Z 2) for x = 1 to SEG in

( ) ( ) { } ( ) ( ) { } 1 1,1 ,..., 1, ... ,1 ,..., , SEG s s S s SEG s SEG S ∪ ∪ 2a) Select arbitrary ,1 x s v from { } ,1 1,..., x s V 2b) Calculate S(x)= ( ) ,1 , x x s C S v . 3) Result = S(1) 4) for x = 2 to SEG 4a) Create ) ∆ -set of x ∆ to check by constraints propagation 4b) Find smallest x ∆ from )
∆ that there exists collision-less routing for Result ( ) ( )

, x S x ∪Ψ ∆ . 4c) Result=Result ( ) ( ) , x S x ∪Ψ ∆
Results provided in the next sections are generated assuming that in point 2a)

we select the cyclogram with the shortest cycle-time. Point 2a) is the next field of research. In Kujawski 2009 we show that there is no optimal cyclogram from a given set that minimizes the overall criterion. ∆ in point 4a) of the algorithm is done by propagating two of the problem constraints. At the beginning x ∆ is some number, constrained from above and below by

( ) ε + < ∆ ≤ + = ,0 , 1 , ( ) , a a I a x x S x t t a s
. The constraints that a hoist can carry only one item at time and that a workstation can process one item at time are used to limit number of individual time shifts to check.

One of the advantages of the cyclogram unfolding method is that exact item processing times for processing stages are known in advance. They are always equal to the time of the item processing in a cyclogram that we use in step 2a). The time of the processing of i-th stage of each item from n-th segment is equal to

( ) ( ) ( ) ( )
, ,

n n t v i n t v i n -
. If we always select the same cyclogram for given item type, the exact processing time is known before the production starts.

The real-time scheduling

The cyclogram unfolding method can be described as largely flexible method in context of real-time scheduling of upcoming orders during production. Flexibility is provided by:

• Work on segments allows splitting large orders to a separate, smaller local problems. In this way the created schedule can be appended many times. Schedule update for single segment is faster than for whole new order. Each found time shift ∆ x , causes update of the production schedule and pushes out-of-date border of real-time system further into the future. It gives more time for finding feasible schedule in general. • When out-of-date border is close and our scheduler cannot find a proper time shift, method can quickly return less efficient but feasible schedule. A time shift can be set to

( ) ε + ∆ = + = , 1 , ( ) , a I a x
x S x t a s , which we know that is the definitely feasible shift. • The most of time-consuming decisions were eliminated from on-line scheduling.

The original scheduling problem included decisions about assignment of pickups to hoists (complexity ( )

Experimental results

In order to compare work results of the proposed hoist scheduling method with results of methods presented in literature, a series of tests on benchmark problems were analyzed. We present comparison of results from [START_REF] Jegou | A contract net based intelligent agent system for solving the reactive hoist scheduling problem[END_REF][START_REF] Paul | A heuristic scheduling procedure for multiitem hoist production lines[END_REF][START_REF] Lamothe | A multihoist model for the real time hoist scheduling problem[END_REF]. We will consider two item types that are frequently ordered together. Let us mark the technology process of technical chroming as a "type A" and process of nickeling as a "type B". The Table 2 and the Table 3 define the processes sequence and quality constraints for process, A and B respectfully. All pick up and put down times are 8 seconds.

Table 2: The process A definition The step number 10, "Chroming" lasts extensively longer than other steps. For that reason, the chroming bath is multiplied to three workstations.

Table 3. The process B definition To calculate the time required to move a hoist from the workstation, i to j the distance between workstation centers is divided by the maximum hoist speed and rounded up to whole seconds. In order to transport an item from a group hoist need to go to the group center, pick the item up (8 seconds), move to the destination bath and put the item down (8 seconds). In Table 4 positions of workstations are defined to calculate the time of hoist movement during item transfer.

Figure 1

 1 Figure 1 presents an overview of typical electroplating lines. There are two

  state can be described as optimization problem. The problem parameters are: the properties of the line (workstations locations, sizes, workstation counts), the hoists count, the hoists speed. Other parameters concern produced product types: the sequence of workstation for each product type, minimum and maximum times of processing in visited workstations. The parameters describing the line state in adaptation time: hoist positions, processing stages of products, which are already on

  KQ -number of items in queue. KC -number of items processed on line during rescheduling. = + K KC KQ . L -number of workstation groups present on line, l g -number of workstations of type group type of i -th product processing stage of type n . .., i n I n I n where ( ) I n is number of steps in of product type n processing sequence. H -number of hoists present on line, minimum and maximum amount of time needed for product of type n should be processed in l -th workstation group. Parameters are derived from physical properties of a production line and a line state in moment of rescheduling. A schedule can be created basing on values of following optimization problem decisive variables: routes of hoists

FIGURE

  FIGURE HERE->>>>>>>>Figure 3 Cyclogram of two hoists with one group of baths(6, 7)

  as cyclogram unfold operation, for x items of type n using cyclogram n v . As a result of ( ) , n C x v we get a schedule based on cyclogram n v , which produces x items of type n . Cyclogram operations are repeated certain number of times until x items leave the line. Length of this schedule: ϒ = ( )

  . Schedules generated for segments are not enough to create a valid schedule for whole queue Z , but they can be adapted together. In order to fit routes generated by cyclogram unfolding to the final schedule, operation of time shift is used. As well as rerouting of hoists operation. Let us use time ∆ of cyclogram unfolding ( ) , n C x v .The Ψ operation causes following changes in values of decisive variables:

(

  ). Thanks to the cyclogram unfolding the most of these decisions are already made during creation of cyclograms. They do not influence complexity of scheduling during adaptation.

  Figure 1 Electroplating Line

  other. For those stages, resource is multiplied in order to avoid a bottleneck. Such multiplied instances of baths, of the same type are called bath group. Baths are arranged in line, and they create an axis of a hoist movement.• Loading and unloading stations. Some workstations only introduce new products to line or are the place where finished products go. • Hoists, controllable automatons, capable of transferring products between workstations. Hoists move only in production line axis. Hoists cannot pass each other. The hoist can pick up and put down products to workstation. Hoists cannot pass products between each other. Because of chemical nature, processing starts when a hoist plunges an item to a bath as a consequence of putting the carried item down. Processing stops, when the hoist picks the item out of bath.

	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

According to those rules cyclical and dynamic production is taken into consideration. In CHSP, it is assumed that new items are available in input buffers every constant amount of time. Usually it is considered that only one type of product is introduced each cycle. For these conditions, a schedule called cyclogram can be created. Cyclogram can be repeated at will, each repetition is producing a number of items. Cyclic scheduling is the most frequently considered organization of production in surface treatment systems, i.e. Brauner 2001 or one of the first papers describing hoist scheduling

[START_REF] Phillips | Mathematical programming solution of a hoist scheduling problem[END_REF]

  The described problem was a topic of many publications. Nevertheless, the most of works are referring to the simplified problem, as they introduce additional constraints.

	REVIEW OF EXISTING SOLUTIONS
	A method proposed by Hindi 2004 deals with a scheduling problem, which is
	equivalent to the DHSP Local Problem. The presented method tries to create an
	optimal schedule, by solving a scheduling problem as the CSP (Constraint
	Satisfaction Problem). Constraints are propagated and heuristic forward checking and F r o backtracking is done. In spite promising results achieved, the method is hardly usable
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

of proper realization of i -th step of item k z production. in real cases because of simplifications. Only one hoist is supported, no multifunction tanks or bath groups are considered.

  hoists work but collisions are not taken into consideration. Additionally stages of productions do not have specific minimum and maximum processing time, but are defined as intervals, with one maximum time set as infinity.

	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

DHSP, yet are treated as separate problems, since they differ in vital details. For instance, in paper Chauvet 2000, authors describe a production line where multiple

  schedule. Cyclograms are widely used in surface treatment systems[START_REF] Che | Single-track multi-hoist scheduling problem: a collision-free resolution based on a branch and bound approach[END_REF][START_REF] Liu | Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution[END_REF][START_REF] Mak | Modeling of material handling hoist operations in a PCB manufacturing facility[END_REF]. Cyclograms are very useful when only one item type is going to be produced for a significant amount of time, because all scheduling can be done before production starts. There are a variety of successful methods of creating cyclograms.Integer, linear programming solutions presented by[START_REF] Liu | Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution[END_REF] Liu 2008. Branch and Bound algorithms presented by[START_REF] Yan | Algorithm for optimal cyclic scheduling in a robotic cell with flexible processing times[END_REF][START_REF] Che | Single-track multi-hoist scheduling problem: a collision-free resolution based on a branch and bound approach[END_REF]. And other heuristic methods, like presented in[START_REF] Mak | Modeling of material handling hoist operations in a PCB manufacturing facility[END_REF][START_REF] Kujawski | Zagadnie nie optymalizacji działania wybranych linii produkcyjnych[END_REF]. Since cyclogram unfolding method is able to use any cyclograms, the best results of mentioned methods can be selected for real-time scheduling. On the other hand, not all methods support multiple hoists[START_REF] Che | Cyclic hoist scheduling in large real-life electroplating lines[END_REF][START_REF] Liu | Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution[END_REF][START_REF] Liu | A heuristic algorithm for the two-hoist cyclic scheduling problem with overlapping hoist coverage ranges[END_REF] only two hoists, Yan 2008), arbitrary production sequence (i.e.[START_REF] Che | Single-track multi-hoist scheduling problem: a collision-free resolution based on a branch and bound approach[END_REF][START_REF] Leung | Optimal cyclic scheduling for printed-circuit-board production lines with multiple hoists and general processing sequences[END_REF][START_REF] Yan | Algorithm for optimal cyclic scheduling in a robotic cell with flexible processing times[END_REF], workstation groups (i.e.

	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

A Cyclogram is a hoist route plan. Its length is called cycle-time T . A Cyclogram is built in the way, that it can be repeated infinitely, and it is still feasible manufacturing

[START_REF] Leung | Optimal cyclic scheduling for printed-circuit-board production lines with multiple hoists and general processing sequences[END_REF][START_REF] Liu | Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution[END_REF]

, other features like multi-function workstations, multiple columns, etc.... We will only consider cyclograms where one product is finished and leaves the line each cycle. The line performance is directly connected with cycle length in such case. In literature there can be found higher grade cyclograms

[START_REF] Che | Apolynomial algorithm for no-wait cyclic hoist scheduling in an extended electroplating line[END_REF], Che 2009

) , which produce more products each cycle, but they are less valuable in the current context and are not going be considered from now on. Mentioned papers Che 2005, Che 2009 are addressed to the slightly modified problem, with "no-wait" rule.

  of hoists, represented as position of hoist h in production time Λ for

	n-th in cyclogram n v ,	( ) h v i n , ( ) , n	( ) h v i n -indexes of hoists which perform i-th pick ( ) , n
	and put of product n-th in cyclogram n v .	( ) a v i n x -number of workstation in ( ) , , n
	group ( ) i n w in cycle x .
	Although a line can consist of groups of workstations, there is no need of
	assigning putdowns and pickups to specific workstation for each processing stage. In
	cyclic work, it is assumed that workstation group is used as FIFO queue. It means that F r o ( ) ( ) , , mod 1 n l a v i n x x g = + where ( ) = i n l w .
	An optimization criterion used to reach a maximum manufacturing P performance is ( ) = n Q T v , providing that number of items produced is not smaller e than ( ) n G v . Optimal solution is found when criterion reaches a minimum. e r Hoist speed constraints, no collision policy, one product per hoist and
	R workstation requirements are still in place. A Cyclogram must also bend to pickup
	e and putdown times relation constraint: v i e ( ) ( ) ( ) ( ) ( ) ( ) µ η ≤ -+ + ⋅ -≤ , , , , mod 1 n i n n i n n l n l w i n t t T T T g , where	g	( ) ( ) w i n	is a number of
	workstations in workstation group performing	w
							O n l
							y
	cyclogram n v .	( ) t v i n , ( ) , n	(	,	( )	)

n t v i n -moments of pick and put of i-th stage of product i -th step of product n and T is a cycle-time of cyclogram.

Table 1 .

 1 Comparison to literature benchmark problems In Jegou 2006 a local scheduling problem of 3 types of products and 2 hoists is given as the example. A goal was to create a schedule for 8 hours of work and see how many products will be finished in this time.

	In Paul 2007 benchmark deals with 4 types of products on single hoist line. A
	mean of 10 tests with random sequence of 40 products with given quantities of each
	product is presented as the result. Presented results are for default parameters
	presented in Paul 2007.
	Lamothe 1996 presents a classic benchmark problem known in HSP,
	introduced by Phillips 1976. Only one type of product is processed. Lamothe 1996
	uses this process definition for scheduling with two hoists and queue of items. Since
	only one type of product is scheduled and new item is always accessible in input
	buffer, although no cyclic assumption, authors claim that schedule should have cyclic
	nature in this case.
	The Case Study
	The production line in Wrocław, Poland is a typical small electroplating line. It is
	used in production of metal furniture elements. The line consists of 16 workstation
	groups composed into one column. One group has 3 workstations, and the other
	groups are in fact, singular workstations. Two hoists are available. Hoists maximum
	speed is 0.7 m/s. Hoist collision zone is 2 meters -two hoists centers cannot be closer
	than 2 meters or the collision occurs.

Table 4 .

 4 The Workstation Centers PositionsWe performed four tests on the defined production line. The first test was for several queues and assumption that we create an initial schedule, so we solve some checks how the system works for same quantity ratios, but orders (next segment) are specified in real-time, 100 seconds before the last item of the current queue is loaded to the line. In the fourth test orders are specified in the time when the last item of the current queue is loaded to the line. All calculations are performed on Intel Q9300 2.5GHz processor. Results for random sequences are calculated from 100 instances.

	Local Problem. The second test is similarly the crating initial schedule, but we
	consider the random sequence from 40 items in two different quantity ratios: 16
	products A plus 24 products B; 18 products A plus 22 products B. The third test

Table 5 .

 5 Queues analyzed in first testIn order to show how much time can be gained using calculated schedule, we compare their length to a base solution length. To calculate the base solution length,

we sum up all the products minimum times, pick up times, putdown times, and transition times required to produce items from the given queue. The utilization ratio is a length of base solution divided by a length of schedule.

Table 6

 6 Ratio 16:24; The Scenario Selection Table7Ratio 18:22; The Scenario Selection In all analyzed cases, during real-time tests, there was no need establish new adaptation time because all calculations managed to be completed before outdating. any offsets. One segment is directly created by unfolding cyclogram. This leads to a conclusion, that performance of a result is directly connected to cycle time of used cyclogram. Used cyclogram had cycle time sufficiently shorter to gain advantage over the Lamothe 1996 method. All cyclograms used in benchmarking were generated by the method presented in paper Kujawski 2007.An efficiency of production dynamically driven by orders may be high enough to introduce such production organization to electroplating lines. The main economic consequence is that dynamic scheduling has low requirements conforming to time extent of orders. This eases middle term planning, as it constrains orders minimally.

	Conclusion
	The cyclogram unfold method generates high performance results both for
	benchmarks and Wrocław production line. It must be pointed out that, quality of
	unfolded cyclograms used during scheduling have big influence on the result. This
	can be observed in Lamothe 1996 case. Only one type of item is produced and all
	items are available from scratch. In this case cyclogram unfold method algorithm is
	simplified only to one segment. Only one segment is used without the need of finding

Additionally, experiments show that dynamic hoist scheduling is superior to cyclic scheduling because schedules manage to achieve higher level of resource utilization thanks to parallel multiple item type processing. Cyclic scheduling in the most cases requires sequential item processing of different types, while dynamic scheduling takes advantage of different item types produced together on mutually exclusive resources.

Nevertheless, further research is needed in order to identify such superiority cases.

Table 1 .

 1 Comparison to literature benchmark problems Type of benchmark Result from literature Results of Cyclogram Unfolding

	Jegou 2006	62 products in	108 products in 8:00:00 hours
		8:00:00 hours	62 products in 4:44:00 hours
	Paul 2007	27:56:27±2:37:47	24:14:45±1:28:53
	Lamothe 1996	00:04:11 hours	00:03:29 hours
	(sequence 1,2,3,…,13)
	Lamothe 1996	00:04:55 hours	00:04:02 hours
	(sequence 1,5,6,…,1)

Table 2 :

 2 The process A definition No. Step Step name Min. time Max. time Group No.

	Page 25 of 27
	1	Loading station	-	-	1
	2	Chem. degreasing	300	420	10
	3	Dripping	30	90	11
	4	Electrochem. degr.	60	180	12
	5	Warm rinse	30	90	13
	6	Rinse I	20	80	14
	7	Cascade rinse I	20	80	15
	8	Cascade rinse II	20	80	16
	9	Anode etching	150	210	9
	10	Chroming	1200	1300	8(3)
	11	Salvaging rinse	20	80	7
	12	Rinse II	20	80	6
	13	Rinse with chrome reduction 20	80	5
	14	Rinse III	20	80	4
	15	Timed rinse.	20	80	3
	16	Blow in bath	30	90	2
	17	Unloading station	-	-	1

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.

uk International Journal of Production Research

	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

Table 3 .

 3 The process B definition No. Step Step name Min. time Max. time Group No.

	1	Loading station	-	-	1
	2	Timed rinse.	300	400	3
	3	Salvaging rinse I 30	90	5
	4	Salvaging rinse II 30	90	7
	5	Degreasing I	60	180	10
	6	Electrochem. degr. 20	80	12
	7	Rinse I	20	80	14
	8	Cascade rinse I	20	80	16
	9	Cascade rinse II	20	80	15
	10	Warm rinse	150	210	13
	11	Nickeling	200	400	11
	12	Degreasing II	20	80	10
	13	Rinse II	20	80	6
	14	Rinse III	20	80	4
	15	Blow in bath	30	90	2
	16	Unloading station -	-	1
	Table 4. The Workstation Centers Positions
	Group No. 1 2 3	4 5	6
	Position (m) 0.3 0.94 1.56 2.18 2.8 3.43
	Group No. 7 8(1) 8(2) 8(3) 9	10
	Position (m) 4.08 4.85 5.75 6.65 7.46 8.14
	Group No. 11 12 13 14 15 16
	Position (m) 8.76 9.42 10.08 10.7 11.27 11.79

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.ukInternational Journal of Production Research

where θ is counter of passing product between two cycles.

( ) ( )