S Baldi
email: s.baldi@tudelft.nl

Leaderless synchronization of heterogeneous oscillators by adaptively learning the group model Simone Baldi and Paolo Frasca

Abstract-This note addresses the problem of leaderless synchronization in a network of linear heterogeneous oscillators. It is well known that a synchronizing controller can be constructed when a common reference model is available to (some of) the agents. In this note, we show that synchronization can also be achieved without any access to such reference, by letting the agents cooperatively learn a suitable common model, which we refer to as group model. We show that there exists a group model that has the same structure as the oscillators and that the agents can learn its parameters and synchronize to it, by using a combination of consensus dynamics and adaptive regulation. This learning is even possible if the agents do not know their own dynamics, by using adaptive state observers. The distinguishing feature of this approach is making the agents collectively selforganize to their natural group model, instead of making them synchronize to an external reference.

Index Terms-Adaptive synchronization, heterogeneous oscillators, unknown dynamics.

I. INTRODUCTION

A N important problem in cooperative control is to achieve a common behavior for the entire network in a distributed way (i.e. using local information): this is the so-called synchronization problem [START_REF] Wieland | An internal model principle is necessary and sufficient for linear output synchronization[END_REF]- [START_REF] Kim | Adaptation and disturbance rejection for output synchronization of incrementally output-feedback passive systems[END_REF], which is sometimes referred to as the consensus problem when the behaviour to be achieved is a constant value [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF]- [START_REF] Monshizadeh | Agreeing in networks: Unmatched disturbances, algebraic constraints and optimality[END_REF]. While static diffusive couplings between the agents are sufficient to ensure synchronization between homogeneous agents [START_REF] Fax | Information flow and cooperative control of vehicle formations[END_REF], synchronizing heterogeneous agents is essentially harder and static couplings are not sufficient [START_REF] Seyboth | On robust synchronization of heterogeneous linear multiagent systems with static couplings[END_REF]. Crucially, the existence of a common reference model is necessary for linear output synchronization. If this common reference model is available to all agents, synchronization can be achieved under mild connectivity assumptions [START_REF] Wieland | An internal model principle is necessary and sufficient for linear output synchronization[END_REF], [START_REF] Kim | Output consensus of heterogeneous uncertain linear multi-agent systems[END_REF]. In some variations of the synchronization problem, the agents can also synchronize to a leader exosystem, provided at least some of the agents can access the exosystem signal. The idea behind this approach is that the agents that are not connected to the exosystem generating the reference signal will construct an observation of such signal in a distributed way, by coupling the so-called regulator equations with a distributed observer [START_REF] Su | Cooperative output regulation of linear multi-agent systems[END_REF]- [START_REF] Seyboth | Cooperative control of linear multi-agent systems via distributed output regulation and transient synchronization[END_REF]. A common assumption to all these works is that all the agents know the common dynamical model to which they need to synchronize: this assumption can be quite restrictive and, recently, the authors of [START_REF] Cai | The adaptive distributed observer approach to the cooperative output regulation of linear multiagent systems[END_REF] have relaxed it by showing that the common model can be known to some agents only, while being estimated in a distributed way by the others.

However, relevant questions remain open: what if none of the agents knows the common model? And pushing the boundary of uncertainty even further: what if the agents neither know their own dynamics? To the best of the authors' knowledge, the study of adaptive synchronization for heterogeneous uncertain systems is limited to special classes of systems/uncertainty, e.g. unknown control directions [START_REF] Chen | Adaptive consensus of multi-agent systems with unknown identical control directions based on a novel Nussbaum-type function[END_REF], unknown leader parameters [START_REF] Su | Cooperative adaptive output regulation for a class of nonlinear uncertain multi-agent systems with unknown leader[END_REF], uncertain systems in output-feedback [START_REF] Ding | Distributed adaptive consensus control of nonlinear output-feedback systems on directed graphs[END_REF] or parametric strict-feedback [START_REF] Wang | Distributed adaptive asymptotically consensus tracking control of nonlinear multi-agent systems with unknown parameters and uncertain disturbances[END_REF] form. Leaderless consensus to a constant trajectory without resorting to any common model has been shown in classes of Euler-Lagrange [START_REF] Nuno | Synchronization of networks of nonidentical Euler-Lagrange systems with uncertain parameters and communication delays[END_REF] or passive systems [START_REF] Hatanaka | Passivity-Based Control and Estimation in Networked Robotics[END_REF]Chap. 8]. However, synchronization to more complex trajectories (e.g. periodic) would necessarily require a leader for which a desired trajectory is explicitly defined.

In this note we answer, for a class of linear agents that are harmonic oscillators, two questions: how to achieve synchronization when a common model is unknown to all agents? How to achieve synchronization when even the agent dynamics are unknown? None of the aforementioned approaches answers these two questions.

Our analysis focuses on harmonic oscillators, i.e. secondorder point-mass systems exhibiting periodic motion. These systems have recently attracted increasing attention, as some of the application fields include resonance phenomena, acoustic vibrations, electrical networks, motion coordination [START_REF] Ren | Synchronization of coupled harmonic oscillators with local interaction[END_REF]- [START_REF] Zhang | Synchronization of discretely coupled harmonic oscillators using sampled position states only[END_REF]. From a theory point of view, harmonic oscillators are also suitable to effectively using adaptive control tools, since they guarantee persistence of excitation. As compared to literature on nonlinear oscillators, e.g. limit-cycle or phase oscillators [START_REF] Strogatz | Sync: The emerging Science of spontaneous Order. Hyperion[END_REF], [START_REF] Dorfler | Synchronization in complex networks of phase oscillators: A survey[END_REF], harmonic oscillators allow, via linear regulation theory, for necessary and sufficient conditions regarding the existence of a group model: in fact, being the group model a priori unknown, it is fundamental to study a setting whose solution is well posed, even in the presence of uncertainty. For example, in synchronization of nonlinear agents via nonlinear regulation theory [START_REF] Isidori | Robust output synchronization of a network of heterogeneous nonlinear agents via nonlinear regulation theory[END_REF], a solution may not exist if parametric uncertainty is too large.

II. PROBLEM FORMULATION AND PRELIMINARIES

We consider n linear heterogeneous harmonic oscillators, indexed by i ∈ {1, . . . , n}

ẋi = 0 1 -ω 2 i 0 A i x i + 0 1 B i =B u i , y i = [0 1] C i =C x i (1)
where for i ∈ {1, . . . , n} we let x i ∈ R 2 be the state, y i ∈ R be the measurable output, u i ∈ R be the input, and ω i > 0. Without loss of generality, the oscillators (1) have been taken in the chain-of-integrators canonical form. Note that the pairs (A i , B) and (C, A i ) in (1) are stabilizable and detectable, respectively, by construction. The oscillators in (1) can communicate with each other according to an undirected connected graph (N , E ) with node set N = {1, . . . , n} and edge set E ⊂ N × N : its (weighted) adjacency matrix is A = [a i j ], which satisfies the relations a ii = 0 and a i j = a ji > 0 if ( j, i) ∈ E ; its (weighted) Laplacian matrix is L = [l i j ], which satisfies the relations l ii = ∑ n j=1 a ji and l i j = -a ji if j = i. A control strategy u i is said to be a distributed control strategy if it respects the communication flows described by the graph (N , E ).

We let v ∈ R 2 be the state of a group model to be found in the form v = Sv [START_REF] Turci | Adaptive pinning control: A review of the fully decentralized strategy and its extensions[END_REF] and let e i ∈ R be the regulated output in the form

e i = y i -[0 1] R i =R v. ( 3
)
We are now ready to formulate the following two problems:

Problem 1 (Synchronization with unknown group model).

Given the network (1), find a distributed controller u i such that all systems synchronize to an a priori unknown group model in the form (2), i.e. lim t→∞ e i = 0, ∀i ∈ {1, . . . , n}.

Problem 2 (Synchronization with unknown dynamics and group model). Given the network (1), find a distributed controller u i such that, without the knowledge of the system parameters in [START_REF] Wieland | An internal model principle is necessary and sufficient for linear output synchronization[END_REF], all systems synchronize to an a priori unknown group model (2), i.e. lim t→∞ e i = 0, ∀i ∈ {1, . . . , n}.

The following Lemmas will be used for stability analysis.

Lemma 1 (Stability under decaying disturbances [START_REF] Cai | The adaptive distributed observer approach to the cooperative output regulation of linear multiagent systems[END_REF]). Consider the following system

ẋ = Fx + F 1 (t)x + F 2 (t) (4)
where F ∈ R n×n is Hurwitz, F 1 (t) and F 2 (t) are bounded and piecewise continuous for all t ≥ t 0 . If lim t→∞ F 1 , F 2 = 0 (exponentially), then lim t→∞ x = 0 (exponentially).

Lemma 2 (Synchronization under decaying disturbances).

Consider the perturbed leaderless synchronization dynamics

ẋi = Sx i + K n ∑ j=1 a i j (x j -x i ) + f i (t)x i ( 5
)
where x i ∈ R m , S ∈ R m×m is marginally stable, K ∈ R m×m is such that (S -λ k K)
is Hurwitz for all non-zero eigenvalues λ k of the Laplacian L , and f i (t) is bounded, continuously differentiable, and converges to zero exponentially. The definition of the error

ε i = ∑ n j=1 a i j (x j -x i ) leads to the error dynamics ε = [(I n ⊗ S) + (L ⊗ K)] ε + F(t)ε ( 6
)
where ε = [ε ′ 1 ε ′ 2 • • • ε ′ n ] ′ = (L ⊗ I m )x, x = [x ′ 1 x ′ 2 • • • x ′ n ] ′ , and F(t) = diag( f 1 I m , • • • , f n I m ). Then, lim t→∞ ε i = 0, i ∈ {1, . . . , n}.
Proof. This proof is provided because, although similar results have appeared in the leader-follower setting [START_REF] Cai | The adaptive distributed observer approach to the cooperative output regulation of linear multiagent systems[END_REF], we are not aware of a leaderless counterpart. From the explicit solution of ( 6), superposition of a marginally stable autonomous linear system and a time-varying autonomous system with exponentially decreasing state matrix, we know that ε is bounded. For undirected and connected graphs, there exists a unitary matrix U ∈ R n×n such that U ′ L U = diag(0, λ 2 , . . . , λ n ) Λ, where λ k , k = 2, . . . , n, are the non-zero eigenvalues of the Laplacian matrix L . Define the transformation ε

= (U ⊗ I m )ε with ε = [ε ′ 1 ε′ 2 . . . ε′ n ] ′
, where it can be checked that ε1 = 0 [START_REF] Li | Consensus of multiagent systems and synchronization of complex networks: A unified viewpoint[END_REF]. Consider the positive definite Lyapunov function candidate

V = 1 2 ε T (I n ⊗ P)ε
with P a positive definite matrix to be chosen later. Using ( 6)

V =ε ′ (I n ⊗ P) [[(I n ⊗ S) + (L ⊗ K)] ε + F(t)ε]
where we have used the property

(A ⊗ B)(C ⊗ D) = AC ⊗ BD. Using the transformation ε = (U ⊗ I m )ε we have V = ε′ [(I n ⊗ PS) + (Λ ⊗ PK)] ε + ε ′ (I n ⊗ P)Fε = n ∑ i=2 ε′ i P(S -λ k K) + (S -λ k K) ′ P εi Vi + ε ′ (I n ⊗ P)Fε F . (7)
Being (S -λ k K) Hurwitz for all non-zero eigenvalues λ k of the Laplacian L , there exists a matrix P such that P(S -λ k K) + (S -λ k K) ′ P < 0 that is, Vi is negative semidefinite: also, F goes to zero exponentially (being ε bounded). After integrating [START_REF] Fax | Information flow and cooperative control of vehicle formations[END_REF] we have

V (t) ≤ V (0) + Ξ, where Ξ = t 0 | F(τ)| dτ is finite since the exponentially decaying term is integrable. Therefore, V (t) is bounded. Furthermore, we derive that V (t) is a uniformly continuous function of time because V (t) is a bounded function of time. In fact V =2 ε′ [(I n ⊗ PS) + (Λ ⊗ PK)] • [(I n ⊗ S) + (Λ ⊗ K)] ε + (U ′ ⊗ I m )Fε + Ḟ ( 8
)
where all variables are bounded. Barbalat's lemma [29, Lemma 3.2.6] implies that V → 0 as t → ∞ and hence ε → 0.

III. SYNCHRONIZATION WITH UNKNOWN GROUP MODEL

If a group model S in (2) were known, a distributed control strategy could be constructed, provided there exist solutions (Π i , Γ i ), i ∈ {1, . . . , n} such that the following equations, commonly referred to as the regulator equations, hold

A i Π i + BΓ i = Π i S CΠ i = R. ( 9
)
Then, synchronization would be guaranteed by the distributed control scheme [1, Theorem 5]

u i = -F i (z i -Π i ζ i ) + Γ i ζ i (10a) żi =A i z i + B i u i + L i (y i -Cz i ) (10b) ζi =Sζ i + K n ∑ j=1 a i j (ζ j -ζ i ) (10c) provided K, F i , L i are chosen such that S -λ k K A i -BF i A i -L i C (11)
are Hurwitz for all i ∈ {1, . . . , n} and all non-zero eigenvalues λ k of the Laplacian L associated to A .

Remark 1 (On the controller stability conditions). The controller [START_REF] Su | Cooperative output regulation of linear multi-agent systems[END_REF] comprises: a static observer-based controller (10a), a Luenberger observer (10b), and a distributed observer (10c) for reference generation: therefore, for every agent, the controller has four states. The Hurwitz properties of A i -BF i and of A i -L i C can be guaranteed by design in decentralized way. Instead, the Hurwitz condition of S -λ k K in principle re- quires some knowledge about the network. However, provided S is in the form of a harmonic oscillator, any K = κI with κ > 0 guarantees the condition, irrespective of the network topology. In what follows, we take K = κI.

Since we are assuming that all individual models are harmonic oscillators, it is natural to seek a group model that is a harmonic oscillator as well, namely

S = 0 1 -β 0 .
The following result ensures that a suitable harmonic oscillator is indeed a solution to the regulator equations.

Proposition 1 (Existence of a harmonic oscillator solution).

A solution to [START_REF] Kim | Output consensus of heterogeneous uncertain linear multi-agent systems[END_REF] for dynamics (1) is given by

S =   0 1 -1 n n ∑ ℓ=1 ω 2 ℓ 0   , Π i = Π = I, (12a)
Γ i = 1 n n ∑ ℓ=1 (ω 2 i -ω 2 ℓ ) 0 . ( 12b
)
Proof. The regulator equations ( 9) take the form

0 1 -ω 2 i 0 Π i + 0 1 Γ i = Π i S, 0 1 Π i = R.
If we assume the group model to be an oscillator, then, without loss of generality, Γ i = [γ 1 i γ 2 i ] and the first equation in (9) boils down to

(Π i ) 11 = (Π i ) 22 γ 1 i = -(Π i ) 11 (β -ω 2 i ) (Π i ) 21 = -β (Π i ) 12 γ 2 i = -(Π i ) 12 (β -ω 2 i
). If we choose Π i = I (from the second equation in ( 9)), then we obtain γ 2 i = 0 and γ

1 i = -β + ω 2 i . Let us now take β = 1 n ∑ n ℓ=1 ω 2 ℓ , i.e
. the group model is the average of the frequencies available in the network: this leads us to

γ 1 i = ω 2 i -1 n ∑ ℓ ω 2 ℓ .
Therefore, the solution to ( 9) is [START_REF] Seyboth | Cooperative control of linear multi-agent systems via distributed output regulation and transient synchronization[END_REF]. Proposition 1 suggests that the mean of the squared frequencies of oscillation gives a legitimate group model S. However, such an S is not directly known to the individual agents. For this reason, we propose to estimate S in a distributed way via consensus dynamics. More precisely, we replace each individual copy of S in (10c) by a local version

S i = 0 1 -β i 0 ( 13
)
and update β i by the consensus dynamics

βi = n ∑ j=1 a i j (β j -β i ), β i (0) = ω 2 i . ( 14
)
For an undirected connected graph, it is well known that ( 14) converges to β in [START_REF] Seyboth | Cooperative control of linear multi-agent systems via distributed output regulation and transient synchronization[END_REF] [30, Thm. 2.2].

The solution to Problem 1 arises from combining the distributed scheme [START_REF] Su | Cooperative output regulation of linear multi-agent systems[END_REF] with the consensus dynamics [START_REF] Chen | Adaptive consensus of multi-agent systems with unknown identical control directions based on a novel Nussbaum-type function[END_REF], as formalized by the following result.

Theorem 1 (Group controller). Consider the network of harmonic oscillators (1) communicating according to an undirected connected graph (N , E ): then, the following distributed control strategy

u i = -F i (z i -ζ i ) + ω 2 i -β i 0 ζ i (15a) żi =A i z i + Bu i + L i (y i -Cz i ), z i (0) = 0 (15b) ζi = 0 1 -β i 0 ζ i + κ n ∑ j=1 a i j (ζ j -ζ i ), ζ i (0) = 0 (15c) βi = n ∑ j=1 a i j (β j -β i ), β i (0) = ω 2 i ( 15d
)
achieves synchronization to the group model S as in [START_REF] Seyboth | Cooperative control of linear multi-agent systems via distributed output regulation and transient synchronization[END_REF], provided the Hurwitz conditions in [START_REF] Lu | Distributed feedforward approach to cooperative output regulation subject to communication delays and switching networks[END_REF]. In addition, we have lim t→∞ S i = S, i ∈ {1, . . . , n}.

Proof. Let us define Γi = ω 2 i -β i 0 to be an estimate of

Γ i = - ∑ℓ ω 2 ℓ n + ω 2 i 0 . Also, let us define F η i = Γ i -F i , Fη i = Γi -F i and Fη i = Γ i -F i -F η i .
Motivated by the manifold to which we want to converge, we define the coordinate change xi = x iv and zi = z iv, where v satisfies v = Sv. The dynamics of these two signals are

ẋi = A i x i + Bu i -Sv = A i x i + Bu i -A i v -BΓ i v = A i xi + B ũi żi = A i zi + B ũi + L i C( xi -zi )
where we have used the fact that e i = Cx i -Cv = C xi , and we have defined ũi

= u i -Γ i v = -F i zi + Fη i (ζ i -v) + Fη i v.
Therefore, it is convenient to write the following dynamics ẋi ẋiżi

= A i -BF i BF i 0 A i -L i C xi xi -zi + B 0 Fη i (ζ i -v) + B 0 Fη i v. ( 16
)
Observe that from (15c) and defining āi j = κa i j we obtain

ζi = Sζ i + n ∑ j=1 āi j (ζ j -ζ i ) + (S i -S)ζ i .
The first two terms of the right-hand side constitute the synchronization dynamics of homogeneous oscillators, while the third one is a disturbance that converges to zero exponentially, because lim t→∞ β i = β and lim t→∞ S i = S exponentially for all i ∈ {1, . . . , n}. Thus, Lemma 2 allows to conclude lim t→∞ ζ i -v = 0, i ∈ {1, . . ., n}. Finally, the term Fη i goes to zero exponentially. By looking at [START_REF] Ding | Distributed adaptive consensus control of nonlinear output-feedback systems on directed graphs[END_REF], we notice that the Hurwitz properties of A i -BF i and of A i -L i C make the system matrix of ( 16) Hurwitz and, in addition, the system is driven by decaying disturbances: therefore, Lemma 1 guarantees that xi converges to zero, from which we obtain convergence of e i to zero. This concludes the proof.

Remark 2 (Extension to chains-of-integrators). Even though this note focuses on harmonic oscillators, we can show that the proposed results directly extend to the wider class of systems in the chain-of-integrators canonical form, resulting in

Y i (s) U i (s) = 1 s m + a 1 i s m-1 + . . . + a m i . ( 17
)
For all systems in the form [START_REF] Wang | Distributed adaptive asymptotically consensus tracking control of nonlinear multi-agent systems with unknown parameters and uncertain disturbances[END_REF], a possible solution to [START_REF] Kim | Output consensus of heterogeneous uncertain linear multi-agent systems[END_REF] is

S = 0 I m-1 -1 n ∑ i a m i . . . -1 n ∑ i a 1 i , Π i = I (18a) Γ i = 1 n ∑ n ℓ=1 (a m i -a m ℓ ) . . . 1 n ∑ n ℓ=1 (a 1 i -a 1 ℓ ) . ( 18b
)
The extension to Theorem 1 follows directly.

IV. SYNCHRONIZATION WITH UNKNOWN DYNAMICS AND GROUP MODEL

The implementation of ( 15) requires the knowledge of the parameter ω i , i.e. of the agent dynamics. In the following, we would like to remove this assumption and endow the agents with the ability to estimate it. To this purpose, we propose the following adaptive state observer

żi = 0 1 -ωi 0 Âi z i + 0 1 B u i + l 1 i (t) l 2 i (t) L i (y i -x2 i ) x2 i = 0 1 z i ( 19
)
where ωi is the estimate of ωi =ω 2 i and L i (t) must be such that Âi (t) -L i (t)C is Hurwitz at every time instant.

In order to produce the estimate ωi , we derive the following parametric model by exploiting the chain-of-integrators form of the oscillators

s 2 s 2 + λ 1 s + λ 2 x 2 i - s s 2 + λ 1 s + λ 2 u i ξ i = ω 2 i -1 s 2 + λ 1 s + λ 2 x 2 i φ i (20)
where the state has been decomposed as x i = x 1 i x 2 i , and λ 1 , λ 2 > 0 are such that s 2 + λ 1 s + λ 2 is a Hurwitz polynomial. Similarly to [START_REF] Ioannou | Robust Adaptive Control[END_REF]Sect. 4.2], we have used a Laplace streamlined notation to indicate the filtering of the signals x 2 i and u i . The parametric model ( 20) is a linear-inthe-parameter model for which the following gradient-based adaptation law [START_REF] Ioannou | Robust Adaptive Control[END_REF]Sect. 5.3]

can be designed ωi = Pro j[γ(ξ i -ωi φ i )φ i ], ωi (0) = ω0 i > 0 (21) =    γ(ξ i -ωi φ i )φ i if ωi < 0 or if ωi = 0 and (ξ i -ωi φ i )φ i ≥ 0 0 otherwise
where γ > 0 is an adaptive gain, ω0 i is an initial estimate of the squared frequency ω 2 i , ωi is the on-line estimate of ωi and Pro j [•] is the projection operator to keep ωi > 0. In addition, the following proposition gives another suitable group model (2) for the network.

Proposition 2 (Alternate harmonic oscillator solution). A solution to [START_REF] Kim | Output consensus of heterogeneous uncertain linear multi-agent systems[END_REF] is given by

S = 0 1 -1 n ∑ n ℓ=1 ω0 ℓ 0 , Π i = Π = I, ( 22a
)
Γ i = 1 n n ∑ ℓ=1 ( ω0 i -ωℓ ) 0 (22b)
Proof. The proof follows the same steps as Proposition 1.

Notice that, differently from ( 12), the group model S is now chosen to be the average of the initial estimates ω0 i of the squared frequencies in the network. It is important to mention that, even in the presence of uncertain dynamics, the solution ( 22) is always well defined when ω0 i , ωi > 0, i ∈ {1, . . . , n}.

The solution to Problem 2 arises from combining the distributed scheme [START_REF] Su | Cooperative output regulation of linear multi-agent systems[END_REF] with the adaptive state observer [START_REF] Hatanaka | Passivity-Based Control and Estimation in Networked Robotics[END_REF] and adaptive law [START_REF] Liu | Design of coupled harmonic oscillators for synchronization and coordination[END_REF], as formalized by the following result.

Theorem 2 (Group controller with unknown dynamics). Consider the network of harmonic oscillators (1) interconnected according to an undirected connected graph (N , E ): then, the following distributed control strategy

u i = -F i (z i -ζ i ) + ωi -β i 0 ζ i (23a) żi = Âi z i + Bu i + L i (y i -Cz i ), z i (0) = 0 (23b) ζi = 0 1 -β i 0 ζ i + κ n ∑ j=1 a i j (ζ j -ζ i ), ζ i (0) = 0 (23c) βi = n ∑ j=1 a i j (β j -β i ), β i (0) = ω0 i (23d) ωi =Pro j[γ(ξ i -ωi φ i )φ i ], ωi (0) = ω0 i , ( 23e
)
achieves synchronization to an a priori unknown group model S, with S as in [START_REF] Tuna | Synchronization of harmonic oscillators under restorative coupling with applications in electrical networks[END_REF], provided F i , L i (which can be time-varying) are chosen such that

Âi -BF i Âi -L i C
are Hurwitz at every time instant. In addition, we have lim t→∞ S i = S, i ∈ {1, . . . , n}, with S as in [START_REF] Tuna | Synchronization of harmonic oscillators under restorative coupling with applications in electrical networks[END_REF].

Proof. Similarly to the derivation of Theorem 1, we can find the dynamics of xi = x iv and zi = z iv, which are

ẋi = A i xi + B ũi żi = Âi zi + B ũi + L i C( xi -zi ) + Ãi v
where Ãi = Âi -A i : also, we have used the fact that e i = Cx i -Cv = C xi , and we have defined ũi

= -F i zi + Fη i (ζ i -v) + Fη i v.
This leads to the following dynamics ẋi ẋi

-żi = Âi -BF i BF i 0 Âi -L i C xi xi -zi + -Ãi xi + B Fη i (ζ i -v) + B Fη i v -Ãi x i . (24)
In addition, it is convenient to write the dynamics of

z i -ζ i żi -ζi = ( Âi -BF i )(z i -ζ i ) + L i C(x i -z i ) -κ n ∑ j=1 a i j (ζ j -ζ i ). (25)
By observing the terms on the right-hand side of (25), we have that lim t→∞ C(x iz i ) = 0 (because a well-known result of the adaptive observer [START_REF] Hatanaka | Passivity-Based Control and Estimation in Networked Robotics[END_REF] is that the output observation error y i -x2 i converges to zero for t → ∞ [29, Thm. 5.3.1]) and lim t→∞ ∑ n j=1 a i j (ζ j -ζ i ) = 0 (by applying Lemma 2 as in the proof of Theorem 1). Therefore, being Âi -BF i Hurwitz, we have that the system matrix of ( 25) is Hurwitz. Therefore, similarly to (4), we have stable dynamics driven by decaying disturbances. From Lemma 1 we obtain convergence to zero of the state of (25), i.e. lim t→∞ z i -ζ i = 0. Now, by looking at (23), we have that u i is the sum of two terms: a vanishing one (z i -ζ i ) and a sinusoidal one (ζ i ). It is well known that the state of a harmonic oscillator is persistently exciting: using standard properties on persistently exciting signals [START_REF] Ioannou | Robust Adaptive Control[END_REF]Lemma 4.8.3], we have that u i is sufficiently rich of order 2 [29, Def. 5.2.1].

An adaptive observer with sufficiently rich inputs guarantees that the state observation error x iz i and the parameter error ωiωi converge to zero exponentially fast [START_REF] Ioannou | Robust Adaptive Control[END_REF]Thm. 5.3.1]. The last convergence implies that the term Ãi in (24) also converges to zero exponentially fast. At this point we are in a similar situation as in Theorem 1, with an asymptotically stable system affected by decaying disturbances: therefore, Lemma 1 guarantees that xi converges to zero, from which we obtain convergence of e i to zero. This concludes the proof.

Remark 3 (Actual ωi =ω 2

i and estimated ωi ). The difference between the consensus dynamics in (23d) and those in (15d) is the initial condition, which reflects the a priori knowledge. In fact, in (15d) we can use the known ω 2 i as initial conditions, while in (23d), being the actual dynamics unknown, we can use only their initial estimates ω0 i . Despite unknown dynamics, a solution [START_REF] Tuna | Synchronization of harmonic oscillators under restorative coupling with applications in electrical networks[END_REF] is always guaranteed to exist.

A. Average model as group model

It must be noted that the solution to Problem 2 presented so far in this section does not guarantee the group model to be the average of the actual individuals models, as instead was the case in our solution to Problem 1. In other words, S in (12) (average of the actual individuals models) might be different from S in [START_REF] Tuna | Synchronization of harmonic oscillators under restorative coupling with applications in electrical networks[END_REF] (average of the estimated individuals models). With the pursuit of bridging this gap, we now provide an extension to our framework [START_REF] Song | Leader-following synchronization of coupled homogeneous and heterogeneous harmonic oscillators based on relative position measurements[END_REF] that is able to converge to a group model S, with S as in [START_REF] Seyboth | Cooperative control of linear multi-agent systems via distributed output regulation and transient synchronization[END_REF], i.e. being the average of the actual individuals models. We propose the following adaptive controller

u i = -F i (z i -ζ i ) + ωi -β i 0 ζ i (26a) żi = Âi z i + Bu i + L i (y i -Cz i ), z i (0) = 0 (26b) ζi = 0 1 -β i 0 ζ i + κ n ∑ j=1 a i j (ζ j -ζ i ), ζ i (0) = 0 (26c) βi = ωi + n ∑ j=1 a i j (β j -β i ), β i (0) = ω0 i (26d) ωi =Pro j[-γ(R ω ωi + Q ω )], ωi (0) = ω0 i (26e) Ṙω = -µR ω + φ 2 i , R ω (0) = 0 (26f) Qω = -µQ ω + φ i ξ i , Q ω (0) = 0, (26g)
with γ, µ > 0 being adaptive gains, and provided the Hurwitz conditions on Âi -BF i and Âi -L i C. The essential differences with respect to [START_REF] Song | Leader-following synchronization of coupled homogeneous and heterogeneous harmonic oscillators based on relative position measurements[END_REF] lie in the modified consensus (26d) and in the estimation scheme (26e)-(26g). The former exploits the availability of ωi in order for β i to converge to the actual average of squared frequencies, while the latter is a gradientbased estimation with integral cost [START_REF] Ioannou | Robust Adaptive Control[END_REF]Thm. 4.3.3].

Remark 4 (Convergence proof for [START_REF] Dorfler | Synchronization in complex networks of phase oscillators: A survey[END_REF]). As compared to [START_REF] Song | Leader-following synchronization of coupled homogeneous and heterogeneous harmonic oscillators based on relative position measurements[END_REF], the additional difficulty in the analysis of [START_REF] Dorfler | Synchronization in complex networks of phase oscillators: A survey[END_REF] Despite the difficulty in generalizing the algorithm ( 26), numerical experiments (cf. Sect. V) suggest that the combination of (26a)-( 26d) and (23e) (i.e. the modified consensus with the standard gradient-based estimation) is able to converge to the actual average of squared frequencies.

V. NUMERICAL EXAMPLES

ω 2 i ω0 i x 0 ζ i #1 1 1.5 [ 1 -1]' [0 -1]' #2 5 3 [ 1 1]' [0 1]' #3 0.5 1 [-1 -1]' [0 -1]' #4 4 5 [-1 0]' [0 0]' #5 2 1.5 [ 0 -1]' [0 -1]' #6 6 4 [ 1 0]' [0 0]' #7 3 2 [-1 1]' [0 1]'
Fig. 1: The undirected communication graph Simulations are carried out on the undirected graph shown in Fig. 1, where the table reports the squared frequencies ω 2 i of each oscillators and the initial estimates ω0 i (the latter to be used for the case in which ωi = ω 2 i is unknown). The other parameters are: F i are chosen such that A i -BF i (or Âi -BF i ) have poles in -0.75 and -1.5; L i are chosen such that A i -L i C (or Âi -L i C) have poles in -2.25 and -4.5; κ = 3 for all i, z i (0) = 0 for all i, λ 1 = 2, λ 2 = 1 and γ = 100.

On this set-up, we simulated the evolution of the controlled dynamics by using controllers ( 15), ( 23) and ( 26). In case ω 2 i are known, the outputs y i and inputs u i resulting from [START_REF] Su | Cooperative adaptive output regulation for a class of nonlinear uncertain multi-agent systems with unknown leader[END_REF] are shown in Fig. 2: synchronization of the outputs to the same frequency is achieved, whereas it can be noted that each agent has a different input in view of the heterogeneous dynamics. The frequency to which the systems converge is defined by the convergence of β i , as shown in Fig. 3. In case ω 2 i are unknown, they cannot be used for control design and ( 23) is employed. The resulting outputs y i and inputs u i are shown in Fig. 4. The frequency to which all agents synchronize depends upon the consensus dynamics over ω0 i as shown in Fig. 5: therefore the synchronizing frequency is not necessarily the same as in the previous case (around 2.57 in Fig. 5 and around 3.07 in Fig. 3). In addition, Fig. 5 shows that the estimates ωi converge to ω 2 i asymptotically. Finally, as anticipated after Remark 4, Figs. 6 and7 show the effectiveness of (26a)-(26d) and (23e) in practice. Note the convergence of β i to a value around 3.07, exactly as in Fig. 3: therefore, convergence occurs to a group model being the average of the actual individuals models.

VI. CONCLUSION

In order to construct a distributed controller to make heterogeneous agents synchronize to a common trajectory, prior works postulated that a reference model be known to at least some agents. The goal of this work was to lift this assumption, by letting the agents cooperatively learn the parameters of a common model (the group model) that are initially unknown to all agents. We have also shown that even when the agents do not know the parameters of their own dynamics, the group model exists and the agents can cooperatively learn its parameters and synchronize to its dynamics. Future work can address some of the restrictive assumptions of our results. First, in our learning scheme the observer gain κ is common to all systems, in line with the literature on synchronization for heterogeneous systems [START_REF] Cai | The adaptive distributed observer approach to the cooperative output regulation of linear multiagent systems[END_REF]: a relevant open problem is to design or adapt such gain independently for each agent, similarly to what can be done for homogeneous agents [START_REF] Turci | Adaptive pinning control: A review of the fully decentralized strategy and its extensions[END_REF]. Second, our work focused on harmonic oscillators as a specific relevant class of (heterogeneous) systems, but we are confident that its ideas can be extended to more general systems. Considering harmonic oscillators has allowed us to derive the structure of the group model analytically and just leave to the agents the task of learning its parameters. Such a structural knowledge, which in the linear case is justified by the fact that the regulation problem typically considers a marginally stable exosystem [START_REF] Francis | The linear multivariable regulator problem[END_REF], might be restrictive for more general classes of systems. In future work, it would be interesting to study whether the group model structure can be learned by the agents themselves, e.g. via neural-network approaches.

Fig. 2 :Fig. 3 :

 23 Fig. 2: Known ω 2 i : synchronizing outputs y i and inputs u i .

Fig. 4 :Fig. 5 :

 45 Fig. 4: Unknown ω 2 i : synchronizing outputs y i and inputs u i .

Fig. 6 :Fig. 7 :

 67 Fig. 6: Unknown ω 2 i , average model: outputs y i and inputs u i .


Christian Commault
email: christian.commault@gipsa-lab.grenoble-inp.fr

Jacob Van Der Woude
email: j.w.vanderwoude@tudelft.nl

Paolo Frasca
email: paolo.frasca@gipsa-lab.grenoble-inp.fr

Functional target controllability of networks: structural properties and efficient algorithms

In this paper we consider the problem of controlling a limited number of target nodes of a network. Equivalently, we can see this problem as controlling the target variables of a structured system, where the state variables of the system are associated to the nodes of the network. We deal with this problem from a different point of view as compared to most recent literature. Indeed, instead of considering controllability in the Kalman sense, that is, as the ability to drive the target states to a desired value, we consider the stronger requirement of driving the target variables as time functions. The latter notion is called functional target controllability. We think that restricting the controllability requirement to a limited set of important variables justifies using a more accurate notion of controllability for these variables. Remarkably, the notion of functional controllability allows formulating very simple graphical conditions for target controllability in the spirit of the structural approach to controllability. The functional approach enables us, moreover, to determine the smallest set of steering nodes that need to be actuated to ensure target controllability, where these steering nodes are constrained to belong to a given set. We show that such a smallest set can be found in polynomial time. We are also able to classify the possible actuated variables in terms of their importance with respect to the functional target controllability problem.

INTRODUCTION

The network community has shown a real interest in control concepts in the recent years [START_REF] Strogatz | Exploring complex networks[END_REF], [START_REF] Lombardi | Controllability analysis of networks[END_REF], [START_REF] Sorrentino | Controllability of complex networks via pinning[END_REF] and the control community has reciprocated by a growing interest in network applications [START_REF] Egerstedt | Interacting with networks: How does structure relate to controllability in single-leader, consensus networks?[END_REF], [START_REF] Parlangeli | On the reachability and observability of path and cycle graphs[END_REF], [START_REF] Pasqualetti | Controllability metrics, limitations and algorithms for complex networks[END_REF], [START_REF] Olshevsky | Minimal controllability problems[END_REF], [START_REF] Bianchin | The observability radius of networks[END_REF], [START_REF] Zhao | Gramian-based reachability metrics for bilinear networks[END_REF], [START_REF] Lindmark | Minimum energy control for complex networks[END_REF]. Most of the papers in literature study controllability according to the most common definition in systems theory, that is, the ability to steer the state to a target point: we shall refer to this definition as point-wise controllability. This definition (and the criticism of its limits [START_REF] Cowan | Nodal degree, not degree distributions, determine the structural controllability of complex networks[END_REF], [START_REF] Pasqualetti | Controllability metrics, limitations and algorithms for complex networks[END_REF]) have also been the starting point of a series of works that approached more advanced questions like quantifying the energy required for control [START_REF] Yan | Controlling complex networks: how much energy is needed?[END_REF], [START_REF] Klickstein | Energy scaling of targeted optimal control of complex networks[END_REF], [START_REF] Lindmark | Minimum energy control for complex networks[END_REF] and the robustness of the controllability properties [START_REF] Menara | The structured controllability radius of symmetric (brain) networks[END_REF], [START_REF] Bianchin | The observability radius of networks[END_REF], [START_REF] Johnson | The structured distance to the nearest system without property P[END_REF], [START_REF] Pasqualetti | Fragility and controllability tradeoff in complex networks[END_REF] in the context of networks.

For linear systems, the classical notion of point-wise controllability lends itself to what is called the "structural" approach, as it was introduced four decades ago by Lin [START_REF] Lin | Structural controllability[END_REF], [START_REF] Murota | Systems Analysis by Graphs and Matroids, ser. Algorithms and Combinatorics[END_REF]. In this approach, the controllability properties are characterised in terms of the sole topology of the network associated to the system: the potential of these methods in network science has become manifest in the last few years [START_REF] Liu | Controllability of complex networks[END_REF], [START_REF] Ruths | Control profiles of complex networks[END_REF], [START_REF] Menara | Structural controllability of symmetric networks[END_REF]. The controllability problem under study in these references is known as the Minimum Input Problem [START_REF] Liu | Controllability of complex networks[END_REF], or more generally the Minimum Controllability Problem [START_REF] Olshevsky | Minimal controllability problems[END_REF], and can be formulated as follows. Given an autonomous dynamical system, one looks for the minimal number of driver nodes (nodes which are directly connected with a control input) such that we have a point-wise control of all the states, i.e., we are able to drive the global state from any initial point to any final point in any fixed positive time.

Since controlling the whole state may be too demanding, and often not necessary, several authors have dealt with the so-called "target control" [START_REF] Gao | Target control of complex networks[END_REF], [START_REF] Klickstein | Energy scaling of targeted optimal control of complex networks[END_REF], [START_REF] Li | Structural target controllability of undirected networks[END_REF], [START_REF] Van Waarde | A distance-based approach to strong target control of dynamical systems[END_REF]. In this case, one defines a set of important variables and requires to control the corresponding states only: this choice of course induces a relaxation of the controllability conditions, since the system no longer needs be controllable in the usual, full-state, sense. Furthermore, target controllability can in principle be checked by using a natural extension of the Kalman controllability condition. However, this definition is not so easy to deploy as it seems, for two main reasons.

The first difficulty is the inability to leverage the structural approach. A structural characterisation of target controllability was left as an open problem in [START_REF] Murota | Note on a graph-theoretic criterion for structural output controllability[END_REF] and, to the best of our knowledge, no graph characterisation for structural target controllability is available to date (unlike for structural point-wise state controllability). In the literature on structural target controllability, the authors either develop approximate approaches [START_REF] Gao | Target control of complex networks[END_REF], [START_REF] Wu | Network output controllability-based method for drug target identification[END_REF], or study particular types of systems: for instance, the problem has an elegant solution when the dynamics of the system is symmetric [START_REF] Li | Structural target controllability of undirected networks[END_REF].

The second difficulty is the intrinsic hardness of the problem: the Minimum Controllability Problem for target controllability has recently been proved to be a NP-hard problem [START_REF] Czeizler | Structural target controllability of linear networks[END_REF]. This negative result implies the need for heuristic solutions in practical situations: one such approximate algorithm is provided in [START_REF] Czeizler | Structural target controllability of linear networks[END_REF].

To overcome these difficulties, we propose in this paper to use a different point of view on structural target controllability. We consider here functional output controllability, i.e., we ask for the possibility to follow any output profile, and not only the possibility to reach any particular point in the output space. This is more demanding than the usual (point-wise) controllability. In particular, when the number of inputs is less than the number of states, the whole state space cannot be functionally controllable. Moreover, we assume that the steering nodes must be chosen in a given set, defined by physical or technological considerations, that we call available nodes [START_REF] Olshevsky | Minimum input selection for structural controllability[END_REF].

Our opinion is that, since we only concentrate on some important variables, a more accurate controllability can be desirable and be afforded for these variables. To illustrate our point of view, we may think of examples from as diverse domains as automotive and drug delivery. Let us think about a car with an automatic gear box. The main control actuators are the accelerator, the driving wheel and the brake. With these three controls, the driver can influence the hundreds of variables which can be listed in a reasonable physical model of the vehicle. However, for the driver, very few of these variables are really important, roughly speaking, only the velocity and the direction of the vehicle are essential. On another hand, for these two variables, we need a precise control of their time behaviour, not only a point-wise control. In biology networks, in particular for pathology treatment [START_REF] Wu | Network output controllability-based method for drug target identification[END_REF], [START_REF] Kanhaiya | Controlling directed protein interaction networks in cancer[END_REF], only some variables are essential to be controlled, and it is of interest to identify the nodes (or cells) where drugs must be applied to avoid the abnormal behaviour of these essential variables. For these sensitive health parameters, it is thought that a trajectory controllability is much more desirable than the possibility to evolve from one value to another one without mastering the transient behaviour, which could be dangerous. Moreover, is clear that for this type of application the drug cannot in general be applied to any node of the network, the steering nodes can only be chosen in a restricted set of admissible nodes.

Owing to this new point of view, the main contributions of our work can be summarized in the following four points.

• We define the notion of functional target controllability and characterise it in graph terms for structured systems. This characterisation (given in Corollary 1) is a direct consequence of results on the structural rank of transfer matrices which appeared around three decades ago [START_REF] Ohta | Structural invertibility of transfer functions[END_REF], [START_REF] Commault | Disturbance rejection for structured systems[END_REF], [START_REF] Van Der Woude | A graph theoretic characterization for the rank of the transfer matrix of a structured system[END_REF], [START_REF]On the structure at infinity of a structured system[END_REF]. • We define the Minimum Target Controllability Problem (MTCP) when controllability is understood in the functional sense and with the constraint that the steering nodes have to be chosen within a given set of available nodes. By exploiting the above characterisation of controllability, we give a full solution to it (Proposition 2). Indeed, we characterise the minimum number of steering nodes and describe a procedure to find a set of steering nodes with minimum size, which ensure functional target controllability. • We establish (Theorem 3) a classification of the available nodes depending on their importance for the functional target controllability, namely dividing them into essential, useful and useless nodes. • We show that solving the MTCP and classifying the available nodes can be done with polynomial complexity by using standard algorithms that solve Maximum Flow problems, such as the Ford-Fulkerson algorithm (Proposition 4).

In order to present these contributions, the outline of this paper will be the following. In Section 2 we present the target controllability problem with the two different points of view. In Section 3 we recall the main results of structured systems concerning the graph characterisations of the types of controllability and we illustrate the results by two examples. We state the main result on the Minimum Target Controllability Problem in Section 4. In Section 5 we give a classification of available states with respect to the MTCP. Section 6 deals with algorithmic and complexity aspects of the main result. Finally, in section 7 we conclude the paper with some remarks and topics for future research.

OUTPUT CONTROLLABILITY: POINT-WISE vs

FUNCTIONAL, AND PROBLEM FORMULATION

In this paper, we consider a large scale system composed of n agents interacting together with linear dynamics. We can then represent the whole behaviour of the system by the simple equation

ẋ(t) = Ax(t), (1)
where x(t) ∈ R n is the state vector and A is a real n × n matrix. We will also consider the system when the dynamics is influenced by external input signals, and when some variables called outputs, which are linear combinations of state variables, give an external view of the system. The global system can then be represented as

Σ : ẋ(t) = Ax(t) + Bu(t), y(t) = Cx(t), (2)
where u(t) ∈ R m is the input vector, y(t) ∈ R p is the output vector, and B and C are real matrices of suitable dimensions.

Occasionally, we will distinguish m states, called the steering states S = {x i1 , . . . , x im }, with i k ∈ {1, . . . , n} and i 1 < i 2 < • • • < i m . To each steering state x i k (t) we associate a control input u k (t) which acts only on this state variable. In this case, the input matrix will be denoted by B S . The B S matrix has m columns, and column k has all its entries equal to 0 except for b i k k . Similarly, a certain number of state variables T = {x j1 , . . . , x jp }, with j l ∈ {1, . . . , n} and j 1 < j 2 < • • • < j p , called target variables, are of a prominent importance. Each target state x j l (t) is associated with a unique output y l (t).

The set of target variables induces therefore the C T matrix. The C T matrix has p rows, each row l has all its entries equal to 0 except for c lj l .

Point-wise output controllability

A first possibility for considering output controllability is to define it as an extension of the classical state controllability.

Definition 1 (Point-wise controllability). The system (2) is said to be (point-wise) output controllable if, for initial condition x(0) = 0, any instant T > 0, and any point y T of the output space R p , there exists an input function u(t) such that y(T ) = y T .

It is easy to see that this output controllability can be tested via an extension of the Kalman controllability condition, i.e., the system is output controllable if and only if

rank(C[B, AB, . . . , A n-1 B]) = p, (3)
with p being the number of outputs.

Functional output controllability

In this paper, we will prefer a refined notion of output controllability. Instead of looking for the possibility to reach any point in the output space, we will ask for the possibility to follow any output trajectory. The notion of functional output controllability was introduced first in [START_REF] Brockett | The reproducibility of multivariable systems[END_REF], where it was called functional reproducibility. In the latter paper, functional reproducibility was also characterised for linear systems. This characterisation makes more precise the intuition which relates the possibility of finding an input producing a given output to some form of invertibility of the system. Several papers, see for example [START_REF] Silverman | Inversion of multivariable linear systems[END_REF], [START_REF] Sain | Invertibility of linear time-invariant dynamical systems[END_REF], brought additional contributions in this area and discussed the relations between point-wise and functional output controllability.

In order to define it rigorously, we recall that a function

f (t) is said to be C ∞ [t 1 , t 2 ] if it is differentiable on the interval [t 1 , t 2 ]
for any order of differentiation.

Definition 2 (Functional controllability). The system (2) is said to be functional output controllable if, for initial condition x(0) = 0, any instant T > 0, and any C ∞ [0, T ] trajectory ỹ(t) in the output space R p , there exists an input function

u(t) ∈ C ∞ [0, T ], such that the output of (2) satisfies y(t) = ỹ(t) for all t ∈ [0, T ].
From classical linear system theory, we recall that the transfer matrix of the system (2) is the rational matrix

T (s) = C(sI n -A) -1 B
, where I n is the identity matrix of size n. If we denote by ū(s) and ȳ(s), the Laplace transforms of the vector time functions u(t) and y(t), respectively, we have that ȳ(s) = T (s)ū(s), when assuming zero initial conditions. A transfer matrix is a matrix over the field of rational functions and as such all classical properties (rank, invertibility,...) of real matrices are applicable to matrix transfer functions. For a system of type (2), the rank of the transfer matrix T (s), sometimes called its normal rank, is defined as the rank of the matrix for almost any value of the variable s, with the finite number of singularities coming from the poles and the zeros of T (s) [START_REF] Kailath | Linear systems[END_REF]. From basic results on control, the functional output controllability can be characterised as follows.

Proposition 1 (Output controllability and transfer matrix [START_REF] Brockett | The reproducibility of multivariable systems[END_REF]). The system (2) is functional output controllable if and only if the transfer matrix T (s) has rank p (the number of outputs).

The systems whose transfer matrix is such that rank T (s) = p are called right invertible systems. Proposition 1 means that, for right invertible systems, given an objective output function ỹ(t) (or its Laplace Transform), it is possible to find an input function ũ(t) which can produce this output. This assertion assumes some smoothness of the function ỹ(t), when the input needs to remain in some physically feasible function class. This is why we restrict here the output trajectories to be C ∞ . This notion of functional controllability is more powerful and implies the classical (pointwise) controllability, but it is of course more demanding in terms of conditions on the system. A discussion on these two points of view on output controllability appeared in [START_REF] Hautus | Linear feedback decoupling, transfer function analysis[END_REF] in the context of non-interacting control.

Formulation of the output controllability problem

We are given a dynamic system, as in (1), representing the network, so that the matrix A is given. The designer has decided that a certain number of state variables T ⊂ X, called target variables, are of importance. The set of target variables induces in one-to-one correspondence an output set Y T and therefore the C T matrix. We have now to choose a minimum number of steering nodes S, which will define an input set U S , and therefore the B S matrix, such that the system (2) is functionally output controllable. Moreover, for physical or technological reasons, there may exist some variables which cannot be directly controlled, in such a way that the steering variables must belong to a restricted set, called the available set, A ⊂ X .

Problem 1. Given a system of type (1) with a set T of target variables, characterise, within the set of available variables A, the sets of steering variables S such that the system (A, B S , C T ) is functional output controllable. This characterisation includes:

• The determination of the minimum size of an admissible set of steering variables. • An evaluation of the importance of each available steering variable for functional output controllability.

In order to fit this problem with the network paradigm, the systems will be studied in the structured system framework which has a natural graph interpretation.

LINEAR STRUCTURED SYSTEMS AND FUNC-TIONAL OUTPUT CONTROLLABILITY

In this section we will recall first the main notions and graph tools for structured systems. We will then recall the well-known result on structural controllability and finally present our main result on functional output controllability. The concepts and results will be illustrated and compared via two examples.

Structured systems and structural controllability

We consider a linear system with parametrized entries denoted by Σ Λ .

Σ Λ : ẋ(t) = A Λ x(t) + B Λ u(t), y(t) = C Λ x(t), (4)
where x(t) ∈ R n is the state vector, u(t) ∈ R m the input signal, and y(t) ∈ R p the output signal. Further, A Λ , B Λ and C Λ are matrices of appropriate dimensions in which the non-zero entries are each replaced by a parameter, and where all parameters are collected in a parameter vector Λ ∈ R k . The system is called a linear structured system. Clearly, the entries of the composite matrix

J Λ = A Λ B Λ C Λ 0 , (5)
are either fixed zeros or independent parameters (not related by algebraic equations) [START_REF] Lin | Structural controllability[END_REF], [START_REF] Murota | Systems Analysis by Graphs and Matroids, ser. Algorithms and Combinatorics[END_REF], [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF]. Occasionally, we will use the system without explicit inputs and outputs as in (1): the structured system will then be

ẋ(t) = A Λ x(t). (6)
For linear structured systems one can study generic properties, i.e., properties which are true for almost all values of the k parameters collected in Λ. More precisely, a property is said to be generic (or structural) if it is true for all values of the parameter vector Λ outside a proper algebraic variety in the parameter space R k . Recall that a proper algebraic variety is the intersection of the zero set of some non-trivial polynomials with real coefficients in the k parameters of the system. A proper algebraic variety has Lebesgue measure zero. A directed graph G(Σ Λ ) = (Z, W ) can be associated with a structured system Σ Λ of type (4).

• The node set is Z = X ∪ U ∪ Y ,
= {(x i , x j )|a Λji = 0} ∪ {(u i , x j )| b Λji = 0} ∪{(x i , y j )|c Λji = 0}
, where a Λji denotes the (j, i)th entry of A Λ and (x i , x j ) denotes an edge from node x i to node x j , and similarly for b Λji and (u i , x j ), and c Λji and (x i , y j ). In the particular case ( 6), the graph is denoted G(A Λ ).

A path in G(Σ Λ ) from a node v 0 to a node v q is a sequence of edges, (v 0 , v 1 ), (v 1 , v 2 ), . . . , (v q-1 , v q ), such that v t ∈ Z for t = 0, 1, . . . , q, and (v t-1 , v t ) ∈ W for t = 1, 2, . . . , q. The nodes v 0 , . . . , v q are then said to be covered by the path. A path which does not meet the same node twice is called a simple path. If v 0 ∈ U and v q ∈ X, the path is called an input-state path. A path for which v 0 = v q is called a circuit. A stem is a simple input-state path. A system is said to be input-connected if any state node is the end node of a stem. A cycle is a circuit which does not meet the same node twice, except for the initial/end node. Two paths are disjoint when they cover disjoint sets of nodes. When some stems and cycles are mutually disjoint, they constitute a disjoint set of stems and cycles. The following result characterises structural controllability [START_REF] Lin | Structural controllability[END_REF], [START_REF] Reinschke | Multivariable control: a graph-theoretic approach[END_REF], [START_REF] Shields | Structural controllability of multiinput linear systems[END_REF].

Theorem 1 (Structural characterisation of point-wise controllability). Let Σ Λ be the linear structured system defined by (4) with associated graph G(Σ Λ ). System Σ Λ is structurally controllable if and only if

• the graph G(Σ Λ ) is input-connected,

and

• the state nodes of G(Σ Λ ) can be covered by a disjoint set of stems and cycles.

Linkings

Before moving on to characterise functional output controllability, we need to recall some additional graph notions.

Let us start with some graph G = (V, E), with two possibly intersecting node subsets

V 1 and V 2 of V . A path with initial node v 1 ∈ V 1 and terminal node v 2 ∈ V 2 is called a (V 1 -V 2 )- path. This path is said to be direct if v 1 (resp. v 2 ) is the only node of the path in V 1 (resp. V 2 ). A (V 1 -V 2 )-linking is a set of disjoint simple direct (V 1 -V 2 )-paths (with no nodes in common). For consistency, for v ∈ V 1 ∩ V 2 , it is assumed that there is a (V 1 -V 2 )-path of length 0 from v to itself. The size of a linking is the number of paths it is composed of. A maximum (V 1 -V 2 )
-linking is a linking of maximum size.

Finding a maximum linking in the graph G = (V, E) can be performed by using maximum flow techniques, and is then a problem with polynomial complexity [START_REF] Murota | Systems Analysis by Graphs and Matroids, ser. Algorithms and Combinatorics[END_REF], [START_REF] Yamada | A network flow algorithm to find an elementary I/O matching[END_REF]. This point will be treated in more detail in Section 6.

When dealing with the graph G(Σ Λ ) of a structured system, if we choose V 1 = U and V 2 = Y , we will speak about input-output paths and input-output linkings. Note that in this case, nodes of U (resp. nodes of Y ) having no incoming edge (resp. no outgoing edge), any input-output path is necessarily direct. Input-output linkings have been a very convenient tool for the study of generic properties and control of structured systems, see for example [START_REF] Commault | Disturbance rejection for structured systems[END_REF], [START_REF] Van Der Woude | A graph theoretic characterization for the rank of the transfer matrix of a structured system[END_REF], [START_REF]On the structure at infinity of a structured system[END_REF], [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF].

Structural rank of the transfer matrix and functional output controllability

When dealing with a structured system of type (4), the transfer matrix is

T Λ (s) = C Λ (sI n -A Λ ) -1 B Λ .
The generic rank of T Λ (s) depends, in a very complex way, on the parameter vector Λ. However, it has been understood since the eighties [START_REF] Commault | Disturbance rejection for structured systems[END_REF], [START_REF] Ohta | Structural invertibility of transfer functions[END_REF], [START_REF] Van Der Woude | A graph theoretic characterization for the rank of the transfer matrix of a structured system[END_REF], [START_REF]On the structure at infinity of a structured system[END_REF] that the generic rank can be simply obtained from the graph G(Σ Λ ).

Theorem 2 (Rank of transfer matrix [START_REF] Ohta | Structural invertibility of transfer functions[END_REF]). Let Σ Λ be the linear structured system defined by ( 4) with associated graph G(Σ Λ ). The generic rank of the corresponding transfer matrix T Λ (s) is the size of a maximum input-output linking in G(Σ Λ ). This result is not only remarkably simple, it is also rather intuitive. The maximum linking is indeed the maximum number of independent ways that the inputs may use to act on outputs. Notice that this result can also be seen as a generalisation of the characterisation of the rank of a structured matrix by means of the size of a maximum matching in the associated bipartite graph [START_REF] Murota | Systems Analysis by Graphs and Matroids, ser. Algorithms and Combinatorics[END_REF].

Example 1. Let us consider the structured system with 9 states, 2 inputs and 2 outputs defined by the following matrices:

A Λ =               0 0 0 0 0 0 0 0 λ 1 λ 2 0 0 0 0 0 0 0 0 0 λ 3 0 λ 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 λ 5 0 λ 6 0 0 0 0 0 λ 7 0 0 0 λ 8 0 0 0 0 0 0 0 0 λ 9 0 0 0 0 0 0 0 0 λ 10 λ 11 λ 12 0 0 0 0 0 0 λ 13 λ 14 0 0 0               , B Λ =               0 0 0 0 0 0 λ 15 0 0 0 0 λ 16 λ 17 0 0 0 0 λ 18               , C Λ = 0 0 0 0 0 0 0 λ 19 0 0 0 0 0 0 0 0 λ 20 λ 21 .
The corresponding graph is given in Figure 1.

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 9 From Theorem 2, it can be seen that the generic rank of the transfer matrix T Λ (s) is two. This follows from the fact that a maximal input-output linking in G(Σ Λ ) has size two. One can choose, for instance, the linking composed of the input-output paths (u 1 , x 4 , x 5 , x 8 , y 1 ) and (u 2 , x 6 , x 9 , y 2 ).

u 1 u 2 y 1 y 2 Fig. 1. Graph G(Σ Λ ) of
Proposition 1 and Theorem 2 can be combined to characterise the generic functional output controllability.

Corollary 1 (Structural characterisation of functional output controllability)

. Let Σ Λ be the linear structured system defined by (4) with associated graph G(Σ Λ ). The system Σ Λ is generically functional output controllable if and only if the size of a maximum input-output linking in G(Σ Λ ) is p, being the number of outputs.

From Corollary 1, the structured system of Example 1 is functional output controllable. Notice that by Theorem 1 this Example is also structurally controllable in the usual sense, since all the state nodes can be covered by the disjoint stems (u 1 , x 4 , x 5 , x 7 , x 8 ) and (u 2 , x 6 , x 9 , x 1 , x 2 , x 3 ).

On the difference between point-wise output controllability and functional output controllability

Consider a structured system whose graph is given in Figure 2, and whose matrices (A Λ , B Λ ) are

A Λ =     0 0 0 0 λ 2 0 0 0 0 λ 3 0 0 λ 4 0 0 0     , B Λ =     λ 1 0 0 0     . (7)
The corresponding controllability matrix is

K Λ =     λ 1 0 0 0 0 λ 1 λ 2 0 0 0 0 λ 1 λ 2 λ 3 0 0 λ 1 λ 4 0 0     . (8)
By Theorem 1 this system is not structurally controllable, because the state nodes cannot be covered disjointly by stems and cycles. The controllability matrix K Λ has clearly generic rank three. It can be checked that we have target point-wise controllability for the target sets {x 1 , x 2 , x 3 } and {x 1 , x 3 , x 4 } (and their subsets, like for instance {x 3 , x 4 }). This fact1 follows from the generic independence of the corresponding rows in K Λ . Since the system has only one input, the maximal size of an input-output linking is one, and therefore the system is functionally controllable only for target sets composed of a unique variable. This shows that, strictly speaking, the values of output variables can be driven to any value for target sets as {x 1 , x 2 , x 3 } or {x 1 , x 4 }. But, clearly, with a unique input one cannot hope to follow any time profile for two or more target variables simultaneously.

Remark 1 (On self-loops and functional controllability).

An important feature of the graph characterisation of functional controllability in Corollary 1 is that it only relies on inputoutput linkings, in which self-loops never appear. In other words, functional controllability is not dependent on the existence of selfloops, in contrast with point-wise controllability where they play a crucial role [START_REF] Liu | Controllability of complex networks[END_REF], [START_REF] Cowan | Nodal degree, not degree distributions, determine the structural controllability of complex networks[END_REF].

THE MINIMAL TARGET CONTROLLABILITY PROBLEM (MTCP) FOR COMPLEX NETWORKS

Let us now come to the problem as it appears in complex networks literature [START_REF] Liu | Controllability of complex networks[END_REF], [START_REF] Ruths | Control profiles of complex networks[END_REF], [START_REF] Olshevsky | Minimum input selection for structural controllability[END_REF], [START_REF] Commault | Input addition and leader selection for the controllability of graph-based systems[END_REF], [START_REF]The single-input minimal controllability problem for structured systems[END_REF], [START_REF] Pequito | A framework for structural input/output and control configuration selection in large-scale systems[END_REF].

Statement of the MTCP

As in Problem (1), we are given a dynamic system, representing the network, with target set of variables T ⊂ X. We have now to choose a minimum number of steering nodes S, which will define an input set U S , and therefore the B S matrix, such that the system (2) is functionally output controllable. When tackling this problem in the structured system framework, we have to find a minimum number of steering nodes such that the condition of Corollary 1 is satisfied. Since we are looking for a set of p non intersecting paths from inputs nodes to outputs nodes, it is clear that we must have at least p steering nodes. On another hand, taking the target nodes as steering nodes gives a trivial minimal solution. The problem is in general more difficult, and also more interesting, because, due to physical considerations, not all nodes may be chosen as steering nodes [START_REF] Olshevsky | Minimum input selection for structural controllability[END_REF], [START_REF] Commault | A classification of nodes for structural controllability[END_REF]. The Minimal Target Controllability Problem (MTCP) can then be stated as follows.

Definition 3 (Minimal Target Controllability Problem (MTCP))

. Given a structured system defined by matrices A Λ and C T ,Λ related with a target node set T , find a minimum number of steering nodes S, taken from a given set of available nodes A = {x i1 , . . . , x i k }, such that the corresponding system of type ( 4) is generically functional target controllable.

Existence of a solution

As mentioned previously, if there is no restriction on the possible steering nodes, i.e., A = X , then the MTCP has a trivial solution. Instead, when A = X , the existence of such a solution is not always guaranteed. The conditions are detailed in the following proposition.

Proposition 2 (Existence of a MTCP solution). Let Σ Λ be the linear structured system defined by ( 4) with associated graph G(Σ Λ ), where the input matrix B A,Λ is related with the available node set A, and the output matrix C T ,Λ is related with the target node set T of size p. The Minimal Target Controllability Problem (MTCP) is solvable if and only if there exists an (A-T )-linking of size p in the graph G(Σ Λ ). When a solution exists, the MTCP can be solved with a set of p steering nodes.

Proof. ⇒ If the MTCP has a solution, there exists a set of steering nodes S ⊂ A such that the condition of Corollary 1 is satisfied, i.e., there exists a (U S -Y T )-linking of size p in G(Σ Λ ). This linking induces an (A-T )-linking of size p, therefore the condition is necessary. ⇐ If there exists a (A-T )-linking of size p in G(Σ Λ ), the condition of Corollary 1 is satisfied by using A as the set of steering nodes. We can also choose as steering node set, the starting nodes of the p paths of the previous linking, which provides a size p solution to the MTCP.

We emphasize that this proof of existence is constructive, in the sense that it describes a way to select the steering nodes that solve the MTCP (provided a solution exists). Since this solution is in general not unique, in the following section we shall have a closer look at the set of solutions.

IMPORTANCE OF STEERING NODES

We have seen in the previous section that solutions to the MTCP are in general not unique. Given a system Σ Λ and a set of available nodes A that satisfy the condition of Proposition 2, in general there can exist several sets of steering nodes that provide a so-called admissible solution to the target controllability problem (minimal or not). It is therefore interesting to study what are the relations between such solution sets (for instance, whether there are nodes that necessarily belong to all solutions). Hence, the purpose of this section will be to classify the importance of nodes of A with respect to the target controllability problem.

Definition 4 (Classes of nodes for functional controllability).

Let x i ∈ A.

• Node x i is said to be essential if x i ∈ D for every admissible solution D.

• Node x i is said to be useless if for any admissible solution D containing x i , also D/{x i } is an admissible solution.

Otherwise, node x i is said to be useful.

Essential nodes are then particular useful nodes. The classification of nodes in A will need the introduction of some new graph concepts. These concepts and results complete those of Subsection 3.2.

Separators

Consider again a graph G = (V, E), with two possibly intersecting node subsets

V 1 and V 2 of V . A (V 1 , V 2 )-separator is a set of nodes S such that every path from V 1 to V 2 covers a node in S. The dependency on V 1 and V 2 is expressed by writing S(V 1 , V 2 ). The separator S(V 1 , V 2 ) is said to be minimal if any proper subset of S(V 1 , V 2 ) is not a separator between V 1 and V 2 .
It is a classical result of combinatorial optimisation that all minimal (V 1 , V 2 )-separators have the same size (cardinality) and that this size is equal to the size of a maximum linking between V 1 and V 2 . The minimal (V 1 , V 2 )-separator is generally not unique. In this paper, a particular uniquely defined (V 1 , V 2 )-separator, called the minimal left separator, and denoted by S * (V 1 , V 2 ), will be used extensively. The set of minimal separators may be endowed with a partial ordering. Indeed, if S and T are minimal separators between V 1 and V 2 , then S is said to precede T , denoted S ≺ T , when every direct path from V 1 to V 2 first passes through S and next passes through T . The minimal left separator is the infimal minimal separator with respect to this order. It is the (V 1 , V 2 )-separator of minimal size that is as close as possible to the node set V 1 . In simple words, the minimal left separator S * (V 1 , V 2 ) is the first smallest bottleneck that is met when we travel from V 1 to V 2 . We collect in the following proposition some of the properties of S * (V 1 , V 2 ), which will be of interest for our purpose.

Proposition 3 (Minimal left separator). Consider a graph

G = (V, E), with two node subsets V 1 and V 2 of V . Assume that every node of G is contained in a direct (V 1 -V 2 )-path.
Then the following facts hold true.

1) The minimal left separator S * (V 1 , V 2 ) is uniquely defined and can be computed in polynomial time.

2) If a node v i ∈ V 1 does not belong to S * (V 1 , V 2 ), then there exists a maximal (V 1 -V 2 )-linking that covers v i . 3) If a node v i ∈ V 1 does not belong to S * (V 1 , V 2 ), then there exists a maximal (V 1 -V 2 )-linking that does not cover v i .
Proof. 1) The result follows from [START_REF] Van Der Woude | The generic number of invariant zeros of a structured linear system[END_REF], and computational details will be given in Section 6. 2) Assume that we are given a maximal

(V 1 -V 2 )-linking that does not cover v i . Consider a (V 1 -V 2 )
direct path P with initial node v i . Let x j be the first node at the intersection of P and of a path, denoted by P k , in the considered

(V 1 -V 2 )-linking. A new (V 1 -V 2 )
-linking of the same size can be constructed by replacing the part from a node of V 1 to x j in the path P k , by the part from v i to x j in P.

3) The result follows from [START_REF] Van Der Woude | The generic number of invariant zeros of a structured linear system[END_REF]. A sketch of the proof is as follows. If every maximal

(V 1 -V 2 )-linking contains a path that covers node v i , then v i must be contained in every (minimal) (V 1 -V 2 )-separator. In particular, v i is in the minimal (V 1 -V 2 )-separator that is closest to V 1 , i.e., v i ∈ S * (V 1 , V 2 ).

Classification of available nodes

Proposition 3 allows to give the complete classification of the nodes of the available set A with respect to the target set T . This is simply obtained by choosing V 1 = A and V 2 = T .

Theorem 3 (Classification of nodes). Consider the linear structured system defined by ( 6) with associated graph G(A Λ ).

Let A be the set of available steering nodes and T be the target set.

With respect to the Minimal Target Controllability Problem, the nodes of A can be classified as follows. Considering node x i ∈ A, there holds the following.

1) Node x i is an essential steering node if and only if x i ∈ A ∩ S * (A, T ). 2) Node x i is a useless steering node if and only if there is no path from x i to a node in T .

Proof. 1) ⇐ If x i is in S * (A, T ), which is a minimal separator, by definition removing x i will decrease the size of a maximum input-output linking, therefore the MTCP has no solution, this implies that x i is essential. ⇒ If x i is not in S * (A, T ), either it is not covered by a (A-T )-path and therefore does not belong to a maximal input-output linking, or, by point 2 of Proposition 3, there exists a maximal input-output linking which does not contain x i . Hence, in both cases x i is not essential. 2) ⇐ If x i belongs to a solution, but is not covered by a (A-T )-path, there exists a maximal (A -T )-linking which does not cover x i . Discarding x i will leave this maximal (A -T )-linking unchanged, therefore the steering node set remains a solution without x i , which is then useless. ⇒ If x i belongs to a solution and is covered by a (A-T )path, from point 3 of Proposition 3, there exists a maximal (A -T )-linking containing x i . This linking provides a solution to the MTCP from which discarding x i would lead to a steering node set which is not a solution. Then x i is not useless.

Example 2.

Let us consider a network with the same dynamics as in Example 1, with target nodes T = {x 8 , x 9 } and whose steering nodes have to be determined among the nodes of the available set A = {x 1 , x 2 , x 3 , x 4 }. The corresponding graph is given in Figure 3.

From Proposition 2, it is clear that the MTCP has a solution. For example, we have the size two linking {(x 1 , x 6 , x 9 ), (x 2 , x 5 , x 8 )}. Therefore, the nodes x 1 and x 2 can be chosen as steering nodes for a minimal solution.

Let us now examine the importance of the different nodes of A with respect to the target controllability problem. The minimum input separator S * (A, T ) can shown to be equal to {x 1 , x 5 }. Then from Theorem 3, node x 1 is essential for the target controllability problem, i.e., it belongs to all the solutions of the problem. On the contrary, since node x 3 belongs to no (A, T )-path, it is useless for the target controllability problem. Finally, nodes x 2 and x 4 are simply useful steering nodes.

Remark 2 (Extension to functional output controllability).

Both the characterisation of a solution in Proposition 2 and the classification of Theorem 3 were stated with respect to a particular target set T . However, in the proofs, no use was made of the particular form of the corresponding matrix C T ,Λ . Therefore, all these results remain valid for a general output matrix C Λ and could be stated in terms of functional output controllability instead of functional target controllability.

ALGORITHMIC AND COMPLEXITY ASPECTS

In this section, we seek to exploit the structural results of Section 5 to propose efficient algorithms to solve the MTCP and to classify the available nodes. From Theorem 3 item 2, we know that the useless nodes in A are the nodes which are not the initial node of a (A -T )-path. This property can be checked with a depth first algorithm whose complexity is linear in the number of edges of the graph. At the same time, from Theorem 3 item 1, we know that the determination of the essential nodes requires the computation of the minimal left separator (A -T ). We will prove that this set can be obtained from the application of the Ford-Fulkerson algorithm on an auxiliary graph. Preliminarily to showing this fact, we observe that since S * (A, T ) is only related to direct (A -T )-paths, w.l.o.g. we can delete all the incoming edges in A and all the outgoing edges from T .

Separators and cuts for the essential nodes

Let us briefly recall some basics of flow theory [START_REF] Ford | Flows in networks[END_REF]. Consider first a graph G(V, E) with two distinguished vertices, a source s with no incoming edge and a sink t with no outgoing edge. A flow is a real number f (e) associated with each edge e of the graph, which satisfies the balance equation (i.e., for each node, except for the source and the sink, the incoming flow equals the outgoing flow). A nonnegative integer capacity c(e) is associated with each edge and a flow is said to be feasible if for each edge e of the graph, 0 ≤ f (e) ≤ c(e). Notice that a flow 0 on each edge is feasible. For a graph with a feasible flow, an augmenting path is defined as an undirected path from s to t (i.e., a path containing forward and backward edges) which is such that for each forward edge e, we have f (e) < c(e) and for each backward edge e , we have f (e ) > 0. The existence of an augmenting path gives the possibility to obtain a new feasible flow which is greater than the previous one. A source set is a set of vertices V such that s ∈ V and t / ∈ V . The cut associated with the source set V is the set of edges (v, v ) ∈ E such that the initial node v is in V and the terminal node v is not in V . The capacity c( V ) of the cut is defined as the sum of the capacities of the edges it is composed of. The famous Max-flow Min-cut Theorem [START_REF] Ford | Flows in networks[END_REF], [START_REF] Murota | Systems Analysis by Graphs and Matroids, ser. Algorithms and Combinatorics[END_REF] states that the maximal flow from s to t in the graph G(V, E) is equal to the minimal capacity of a cut.

We are now ready to bear on these notions and algorithms from flow theory to state and prove our final result. Our key instrument will be the following definition of auxiliary graph. Definition 5 (Auxiliary graph). Consider a system A Λ with available set A and target set T and its graph G(A Λ ). We define an associated auxiliary graph G aux (A Λ ) as follows:

• Split each state node x i of G(A Λ ) into two nodes x - i and x + i , and add an edge

(x - i , x + i ). • Transform each edge of G(A Λ ) of the form (x i , x j ) into an associated edge of G aux (A Λ ) of the form (x + i , x - j ). • Create in G aux (A Λ )
a dummy source node s and a dummy sink node t, add an edge from s to all the available nodes {x - i1 , x - i2 , . . . , x - im }, and an edge from all target nodes {x + j1 , x + j2 , . . . , x + jp } to the sink node t. • Give to all the edges (x - i , x + i ), for i = 1, . . . , n, a capacity one, and to all other edges of G aux (A Λ ) an infinite capacity.

This definition allows us to state the following result.

Proposition 4 (Max flow and Min cut in MTCP). Consider a structured system A Λ with available set A and target set T with its graph G(A Λ ), and the associated auxiliary graph G aux (A Λ ). The following two facts hold.

• The size of a maximal (A, T )-linking in G(A Λ ) is the value F of a maximal flow on G aux (A Λ ). • The minimal left separator S * (A, T ) of G(A Λ ) is in one-toone correspondence with the minimal cut in G aux (A Λ ) that is produced by the Ford-Fulkerson algorithm.

Proof. From the construction of the auxiliary graph G aux (A Λ ), every separator of G(A Λ ) induces a cut in G aux (A Λ ) whose capacity is the size of the separator. Moreover, a cut in G aux (A Λ ) has a finite capacity only if it corresponds with a separator of G(A Λ ), otherwise the cut would contain an edge with an infinite capacity. Therefore, there is a one-to-one correspondence between separators in G(A Λ ) and finite cuts in G aux (A Λ ), the size of the separator being equal to the capacity of the cut. As a consequence, any minimum separator of G(A Λ ) is in a one-to-one correspondence with a minimum cut of G aux (A Λ ). The first item of Proposition 4 then follows from the Max-Flow Min-Cut Theorem, see also [START_REF] Yamada | A network flow algorithm to find an elementary I/O matching[END_REF], [START_REF] Hovelaque | Analysis of linear structured systems using a primal-dual algorithm[END_REF]. We now prove the second item. Starting from an initial null flow on each edge, the Ford-Fulkerson algorithm [START_REF] Ford | Flows in networks[END_REF] is iteratively composed of two phases. In the first phase, a labelling procedure, starting in s, looks for an augmenting path. If no augmenting path is found, the algorithm stops and the actual flow is indeed maximum. If an augmenting path is found, the flow is increased along this path. The algorithm stops when the flow is maximum and when the set of labelled nodes is the source set associated with the minimal cut, which is the closest to the source [START_REF] Picard | On the structure of all minimum cuts in a network and applications[END_REF]. From the previous observation on the correspondence between minimum cuts in G aux (A Λ ) and the minimum (A, T )-separators in G aux (A Λ ), the second item of Proposition 4 follows.

The auxiliary graph associated to our Example of Figure 3 is given in Figure 4. In Figure 4, it appears that starting from a zero flow, a first augmenting path (s, x - 2 , x + 2 , x - 5 , x + 5 , x - 8 , x + 8 , t) composed only of forward edges allows to convey a unit flow from s to t. Similarly, a second path (s, x - 1 , x + 1 , x - 6 , x + 6 , x - 9 , x + 9 , t) allows to convey a supplementary unit flow from s to t. When this flow is installed on the graph, the labelling procedure allows to reach the node set L = {s, x - 4 , x + 4 , x - 5 , x - 3 , x + 3 , x - 2 , x - 1 , x + 2 }. This source set is associated to a minimal cut and the corresponding flow is a maximum one. This induces that

• the minimum number of steering nodes for target controllability is two, and that {x 1 , x 2 } is a possible solution, • the set S * (A, T ) is equal to {x 1 , x 5 } which implies that x 1 is an essential node.

Complexity of finding the essential nodes

The complexity of the Ford-Fulkerson algorithm with integer capacities is of order O(N e •f M ), where N e is the number of edges of the graph, and f M is the value of the maximum flow. The number of edges in G aux (A Λ ) being bounded by (2n + 2) 2 , and the flow being bounded by p, we finally get a complexity of order O(n 2 p). There are certainly better performing maximum flow algorithms, but it is important to note that the Ford-Fulkerson algorithm also provides the minimal left separator S * (A, T ) [START_REF] Picard | On the structure of all minimum cuts in a network and applications[END_REF].

CONCLUSION

In this paper we have introduced the notion of functional target controllability. This notion is a relevant alternative to the classical point-wise target controllability. We think that this notion is justified by the fact that the importance of target variables needs a refined type of controllability. It happens that this new approach induces a simpler characterisation of target controllability in graph terms for structured systems than the classical point of view. This opens the possibility to revisit some problems as the robustness of target controllability against edge deletions [START_REF] Fardad | On optimal link removals for controllability degradation in dynamical networks[END_REF], or the opposite problem of finding necessary edge additions to reach target controllability [START_REF] Chen | Minimal edge addition for network controllability[END_REF].

x - 1

x - 2

x - 3

x - 4

x - 5

x - 6

x - 7

x - Edges with infinite capacity are drawn as solid lines, edges with capacity one are drawn as dashed lines. A red dashed box encloses the source set associated to the minimal cut that is identified by the Ford-Fulkerson algorithm.

x 1 x 2 x 3 x 4 u 1 Fig. 2 .

 3412 Fig. 2. Example illustrating the difference between point-wise controllability and functional controllability, as discussed in Section 3.4.

Fig. 3 .

 3 Fig. 3. Steering node selection for target controllability of Example 2 with target set T highlighted by a blue diamond. Within set A (green rectangle), node x 1 is essential, node x 3 is useless, nodes x 2 and x 4 are useful.

Fig. 4 .

 4 Fig.4. Auxiliary graph associated to the graph of Figure3. Dummy source node s has rectangle shape, dummy sink node t has diamond shape. Edges with infinite capacity are drawn as solid lines, edges with capacity one are drawn as dashed lines. A red dashed box encloses the source set associated to the minimal cut that is identified by the Ford-Fulkerson algorithm.

  where X, U and Y are the state node set, input node set and output node set, given by {x 1 , x 2 , . . . , x n }, {u 1 , u 2 , . . . , u m } and {y 1 , u 2 , . . . , y p }, respectively.

• The edge set is W

  Example 1. Input nodes u 1 and u 2 have rectangle shapes, output nodes y 1 and y 2 have diamond shapes.

This observation incidentally shows that the condition of Theorem 12 in[START_REF] Blackhall | On the structural controllability of networks of linear systems[END_REF] is not necessary, because the nodes corresponding with the target set {x 3 , x 4 } do not belong to a cactus in the graph.