Fuzzy Systems : agreement and modeling : with applications to Critical Infrastructure Protection problems.

(1)

UNIVERSITÀ DEGLI STUDI

ROMA

TRE

Roma Tre University

Ph.D. in Computer Science and Engineering

Fuzzy Systems: Agreement and Modeling

with Applications to Critical Infrastructure Protection Problems.

(2)

(3)

Fuzzy Systems: Agreement and Modeling

with Applications to Critical Infrastructure Protection Problems

A thesis presented by Gabriele Oliva

in partial fulfillment of the requirements for the degree of Doctor of Philosophy

in Computer Science and Engineering Roma Tre University

Dept. of Informatics and Automation February 28, 2012

(4)

Coordinator: Prof. Stefano Panzieri

Advisor:

Prof. Stefano Panzieri

Reviewers: Prof. Sujeet Shenoi

(5)

(6)

(7)

vii

Abstract

Protecting Critical Infrastructures is a hard task, since these systems are becoming more and more interdependent for many reasons, while the knowledge on their behavior is becoming more and more sector specific. In order to provide instruments for their protection, a first step is to define convincing frameworks able to assess and predict the evolution of their working condition by sharing information among infrastructures on a real-time basis.

Moreover, due to the lack of adequate quantitative data about the interac-tion among infrastructures and their subsystems, there is the need to provide formalisms able to handle the information elicited by experts and stakeholders, which typically express in a linguistic and vague way. This was the aim of MICIE European project, where a distributed real-time framework based on a fuzzy interdependency model was adopted.

This Thesis is aimed to summarize the efforts done within such a project, following three main directions. First of all, a formal framework for the analysis of systems characterized by vagueness and ambiguity is provided; some of the most studied distributed agreement problems are then addressed in the fuzzy fashion, thus providing a theoretical justification of the MICIE project; finally, some modeling methodologies, aimed to account for vagueness and fuzziness, are finally discussed, along with the online approach implemented within the MICIE project.

(8)

(9)

Acknowledgments

I would like to thank my advisor, professor Stefano Panzieri, for the opportu-nity to face the challenging problem of Critical Infrastructure Protection, for the high degree of freedom and autonomy he accorded me while performing my research, and for sharing with me the responsibilities and the decisions under-taken within the MICIE project. I will never forget the experience acquired under his inspiring guide.

I would also like to thank professor Roberto Setola for his precious support, for his restless involvement in my research and, in general, for believing in me. Finally, I would like to spend few words to kindly thank Chiara Foglietta, for her precious help in many situations, for leveraging me from many coding issues related to CISIA simulator and, last but not least, for accepting my odd launch schedules.

(10)

Introduction

It is a fact that Critical Infrastructures are becoming more and more complex, tightly interconnected and mutually dependent, according to many dimensions, such as geographic proximity, cyber connection (i.e., reachability via the web) or resource exchange dependencies [99]. For the United States, the general definition of Critical Infrastructure is:

Systems and assets, whether physical or virtual, so vital to the United States that the incapacity or destruction of such systems and assets would have a debilitating impact on security, national economic security, national public health or safety, or any combi-nation of those matters [108].

The protection (safety and security) of such systems is a nontrivial task, mainly due to the exponential relevance of web based technologies used to control the infrastructures. Indeed, such systems proved to be weak with re-spect to cyber attacks; e.g., Denial of Service or attacks aimed to override the commands sent from the SCADA (Supervisory Control and Data Acquisi-tion) systems to the actuators with fake ones, leading to dangerous situations. Among the others, the STUXNET worm infection [74] perfectly represents the frailty of the regulatory systems devoted to control Critical Infrastructures. First isolated in mid-June 2010, STUXNET is a computer virus specifically designed for attacking Windows based industrial computers and taking control of PLCs (Programmable Logic Controllers), influencing the behavior of remote actuators and leading to instability phenomena or even worse. The paradox is that Critical Infrastructures massively rely on newest ICT (Information and Communication Technologies), while the control equipment are typically old, legacy software/hardware. Such a combination of factors may lead to very dan-gerous situations, exposing the systems to a wide variety of attacks. In fact, while the high degree of interconnection of modern ICT equipment as well as the use of public networks represent a vulnerability, the devices used to control Critical Infrastructures were not designed to be accessed from public networks and hence may be prone even to relatively simple cyber attacks.

(14)

2 CHAPTER 1. INTRODUCTION

Hence, these systems are becoming more and more interoperable; con-versely, due to their complexity, the knowledge of human technicians is be-coming more and more sector-specific. Another important aspect is that, very often, Critical Infrastructures and their subsystems interact in ways that are hidden and not well understood by the single infrastructures’ experts, while such a hidden interaction represents one of the main causes of coupling among these systems, often leading to cascading failures and domino effects. This is the reason why sector-specific simulators and monitoring systems, although being very sophisticated, fail to capture the behavior of the infrastructures in critical situations, when domino effects arise.

In order to address the complexity of the interdependency phenomena that exist among Critical Infrastructures, a mandatory step is to model and quantify their interaction, assessing the evolution of the resulting System of Systems.

In the literature many approaches have been proposed to represent interde-pendency among infrastructures and their elements [39, 38, 94, 45, ES-1, IJ-3, IJ-2]; however, these models are mostly aimed to perform off-line evaluations, in order to identify the structural vulnerabilities of infrastructures by means of simulations. Besides simulation-based impact and risk analyses, there is the need to provide systems able to evaluate at real time the disruptive events that may affect Critical Infrastructures in a global perspective.

Notice that, typically, each infrastructure has its own SCADA or monitoring system; however such system only allows to have a partial, although detailed, perspective on the overall system of systems (e.g., on the isolated behavior of the single infrastructures). There is then the need to provide a framework able to merge these partial observations at real time into a global and unified perspective, thus providing previsions based on the actual state with a wider point of view; however the idea to merge all the information directly is not viable, for many reasons:

• Disclosure: the complete exchange of information is not feasible, since the different infrastructures’ owners are typically concurrent, and such an information may expose the infrastructures to commercial issues. In-frastructures should exchange only a subset of aggregate and abstract information.

• Security: the information to be exchanged is typically sensitive; there-fore the leak of such an information may have serious consequences, being the base for malicious attacks (e.g., if the state of a telecommunication network is disclosed to a terroristic group, it may concentrate an attack on the more congested nodes, leading to a denial of service).

• Authority: the idea to merge the information in a centralized way (i.e., to provide vital information to a central authority) is not feasible, both from a commercial and security point of view. Indeed, merging such an information should be done in a distributed manner, and the infrastruc-tures should be considered as peers.

(15)

3

A feasible on-line approach should be based on a de-centralized framework; from such a perspective the control room of each infrastructure should be equipped with an although abstract global model of the overall System of Systems, while only data originated within its own field should be directly available to each control room (i.e., only the data available by means of the SCADA/control system of the single infrastructures). Different tools, then, should be interconnected and synchronized: this is the underlying idea of On-line Distributed Interdependency Estimation [PR-2, PR-6, PR-7, PR-8, IT-2, IJ-1].

This is also the goal of EU FP7 Project MICIE [91, TR-5], which recently showed the potentialities of interconnecting interdependency models and recon-structing the global state (as well as a shared forecast) of the overall System of Systems via partial observations. The project considered a real case study com-posed of a medium voltage power distribution grid, a SCADA infrastructure and a fiber optic telecommunication infrastructure.

When dealing with complex and large scale systems, however, there is the need to properly set-up the models, since in many cases only very general and abstract information is available; for instance interdependency is often assumed to be proportional to economic interaction [39, 38]. To overcome the problem of model tuning, in [64] it is suggested to complement the data obtained by the stakeholders with information about the operational consequences of a failure in the different infrastructures provided by sector specific experts, by means of suitable questionnaires. Obviously in this way the degree of dependency among the infrastructures is expressed via vague linguistic expressions, such as “strong”, “limited”, etc.

In [94] a methodology is proposed to collect such type of information, cod-ifying it by means of Fuzzy Numbers (FN) [26, 41]. Such a work emphasized that, especially in the presence of extended outage periods, the experts pro-vide data with significant degree of vagueness, ambiguity and/or uncertainty. Hence, in order to quantify interdependency, a good choice is to rely on the experience of the different stakeholders, technicians, experts and final users. Such an approach has two main positive consequences:

1. The interaction among infrastructures can be inferred with respect to multiple dimensions (e.g., economic, social, functional, etc.), relying on the experience of the actors involved.

2. The knowledge coming from multiple sources, each with its experience and its unique point of view is taken into account. Such an approach, besides leading to a systematization and formalization of the knowledge, may help to discover complex interactions by rebuilding the puzzle.

The main drawback of such an approach, however, is that the knowledge of experts might be affected by uncertainty, might be incomplete or contradictory. Moreover it is often expressed in a linguistic way and there is the need to identify a formalism for the quantification of such an information. To this

(16)

end some approaches aimed to provide a stakeholder-oriented interdependency models have been proposed in [ES-1, IJ-3, IJ-2, IJ-4].

Within MICIE Project, an on-line strategy for the analysis of interdepen-dency at real time has been proposed [91, TR-5, IJ-1], considering multiple, interconnected interdependency estimators, each attested in a given infrastruc-ture.

Moreover, in order to face the complexity of tightly interconnected infras-tructures, a methodology able to take into account multiple levels of abstrac-tion, namely Mixed Holistic Reductionistic Model (MHR) [ES-1], has been provided. Such an approach is able to represent the System of Systems, at the same time, as a set of physical equipment, as a set of functional high level entities (i.e., services) and as a whole. Moreover, due to the structural lack of adequate quantitative data, the interdependency model adopted is based on fuzzy numbers, and is tune-able with linguistic information obtained from stakeholders and experts of the different infrastructures.

There is, therefore, the need to provide a convincing approach for the dis-tributed synchronization of dynamic systems with fuzzy evolution and partial information sharing. To this end, a formal mathematical framework for the analysis of fuzzy systems [SJ-1, SC-2] as well as an approach for the agreement [IJ-1, SJ-2, PR-1] of distributed systems has been provided.

The result is an On-line Distributed Interdependency Estimation (ODIE) framework that operates as an on-line risk assessment able to provide Critical Infrastructures’ operators with useful information, in order to understand the actual situation of the other infrastructures and the implications for their own operational capability.

1.1 Scope of the Thesis

As stated above, the present work is strongly motivated by the lack of for-mal methodologies for the representation of ambiguity and fuzzyness within traditional interdependency models for Critical Infrastructures, as well as the need to provide a convincing framework for the distributed agreement of fuzzy systems. The need for such a work has become more and more mandatory during the research activities performed within the MICIE project [91]. In fact, being the MICIE project tailored on a real case study composed of mul-tiple infrastructures, the need for a methodology able to take into account the experience of different stakeholders and operators in order to correctly set up interdependency models became paramount.

In order to address such issues the present Thesis follows three main research directions:

1. Theory of Fuzzy Systems: a formal characterization [SJ-1, SC-2] of fuzzy systems has been carried out, based on the work in the literature [58, 84, 104, 51, 46, 23, 59], with the aim to provide a framework for the analysis of systems with fuzzy state variables and fuzzy parameters. Specifically, two main approaches have been followed:

(17)

1.1. SCOPE OF THE THESIS 5

• Systems with fuzzy state: the properties of systems with state vari-ables described by fuzzy numbers have been inspected, with par-ticular reference to the stability properties [SJ-1]. The research ac-tivities encompassed different typologies of systems, such as linear, time varying and non-linear systems.

• Systems with fuzzy state and fuzzy parameters: In order to suit-ably manage the ambiguity on both the state and the parameters, a framework based on Fuzzy Difference Inclusions has been set up [SC-2], with particular reference to the stability of linear systems. Note that most fuzzy approaches are typically empiric and rule-based [71, 82, 111]; in this work, however, a formal extension of the state space Rnhas been considered, defining adequate metrics and convergence prop-erties in the resulting space of fuzzy state variables En _[58].

2. Agreement of Fuzzy Systems: Based on the proposed fuzzy formal-ism, different agreement problems [SJ-2, IJ-1, IT-2, PR-1] have been ad-dressed from a fuzzy perspective, providing, where possible, formal proofs of convergence (e.g., the existence of an agreement among the systems). Specifically, three problems with increasing degree of complexity have been inspected and extended in the fuzzy fashion:

• Consensus: different agents with very simple dynamics and fuzzy initial values that converge to a function of their initial conditions (e.g., the average) in a distributed manner [SJ-2, IT-2];

• Opinion Dynamics: a set of experts, each having a fuzzy opinion, interact only with experts having similar opinions, and therefore the reach of an agreement is not granted [PR-1].

• Synchronization: an array of agents with nontrivial dynamics and with different fuzzy initial conditions have to reach a common evo-lution by communicating in a distributed way [IJ-1, IT-2].

Such a contribution represents a first step for the theoretical justification of the MICIE approach, where different nonlinear fuzzy models have to be synchronized in a distributed perspective.

3. Fuzzy Interdependency Modeling: The fuzzy formalism is applied in order to provide convincing frameworks for the representation of the interdependency among Critical Infrastructures. To this end a discussion on how to enhance traditional interdependency models, such as the Input-Output Inoperability Model (IIM) [38], is carried out, providing some extensions of the IIM approach [IJ-3, IJ-2, IJ-4]. Specifically three main directions were followed:

• Consider the interaction among infrastructures’ subsystems in terms of resource exchange [IJ-3];

(18)

• Represent the coupling among infrastructures as a function of the time duration and severity of failures [IJ-4];

• Model the interaction based on uncertainty and vague information [IJ-2].

Based on such results, the MHR interdependency model [ES-1] and the CISIA software platform [89], adopted within the MICIE project, are de-scribed as a complex framework for the modeling and real time evaluation of the actual and near future working condition of multiple interconnected Critical Infrastructures.

1.2 Organization of the Thesis

The present Thesis is structured into three parts, each devoted to report the results achieved in the aforementioned research directions. Specifically, Part I is aimed to provide a thorough discussion on fuzzy systems: Chapter 2 is devoted to introduce discrete-time fuzzy systems, thoroughly discussing their stability and numerical representation, as well as some clarifying numerical examples; such a fuzzy theory is then exploited in Part II, providing a framework to solve three different typologies of agreement problems in the fuzzy fashion; Chapter 3 further extends the framework by considering systems with both fuzzy state and fuzzy parameters, thus providing the basis for the formal introduction of Fuzzy interdependency models in Part III.

Part II is aimed to introduce the fuzzy extension of some distributed agree-ment problems: Chapter 4 analyzes the Consensus of distributed agents, pro-viding also a case study related to crisis management; Chapter 5 addresses a complementary problem, the Hegelsmann-Krause Opinion Dynamics model; Chapter 6 addresses the general Synchronization problem of arrays of identical and distributed systems, providing also a case study in the field of Critical Infrastructures.

Part III addresses the problem of introducing ambiguity and fuzziness while modeling interdependency among Critical Infrastructures, as well as the online approach implemented within the EU MICIE project. Specifically the structure of Part III is as follows: Chapter 7 describes the state of the art in interdepen-dency modeling for Critical Infrastructures; Chapter 8 suggests some research directions on how to provide a modeling methodology oriented to stakeholders and experts, while Chapter 9 is devoted to extend IIM model in the fuzzy fash-ion; then, Chapter 10 introduces the MHR framework and the CISIA software platform, and Chapter 11 describes MICIE project.

Finally, some conclusive remarks and future work directions are collected in Chapter 12.

(19)

1.3. CONTRIBUTION AND ACHIEVEMENTS OF THE THESIS 7

1.3 Contribution and Achievements of the Thesis

Let us now discuss in details the achievements and the contribution of the present Thesis with respect to the state of art.

1. Theory of Fuzzy Systems. As stated before, in this Thesis a formal analysis of fuzzy system has been carried out, focusing on the stability and on the level wise representation of such systems. Such a research is mainly based on the results in [58, 84, 104, 51, 46, 23, 59]. In particular the results for fuzzy systems with crisp dynamics are mainly based on the work of Lakshmikantham and Mohapatra [58]. With respect to [58], here the focus is on discrete time systems and it is proven that the stability of positive systems is independent on the fuzziness of the state. Moreover, based on the work in [84, 104, 51] on the level-wise representation of fuzzy systems, here a finer analysis is carried out, inspecting the structure of the α-levels under different conditions along with the relations between stability and level-wise stability. Nevertheless, in this Thesis an analysis of fuzzy systems with both fuzzy dynamics and fuzzy state has been carried out; such a work is mainly based on the results in [58, 51, 46, 23]. Again, the focus here is on discrete-time systems and to this end the theory of difference inclusions [51, 46] has been exploited, obtaining results similar to those available in the continuous case [58], under the strong assumption of systems with nonnegative dynamics. The effort done in this direction is supported by several publications: in particular in [IJ-1, PR-1, SC-1, IT-2] for what regards fuzzy systems with crisp dynamics and in [IJ-2, IT-2] for what concerns fuzzy difference inclusions. 2. Agreement of Fuzzy Systems. The above theoretical framework has been exploited in order to provide a methodology for the analysis of dis-tributed agreement problems when the state of the involved agents is de-scribed as a fuzzy set. To this end the problems of consensus [SC-2, SJ-2], opinion dynamics [PR-1] and synchronization [IJ-1] have been analyzed. One of the main advantages of such an approach is the increased expres-sivity of the framework: in fact, besides providing distributed averages [80] of the evolution of the agents, here more sophisticated analyses can be carried out. For instance it is now possible to evaluate the uncertainty associated to the final estimate or to the asymptotic value reached. More-over the choice of fuzzy sets allows to model in a very sophisticated way the preferences over a set of values. For instance, in the case of trian-gular fuzzy numbers an asymmetry may indicate different beliefs for the extremal cases, while a plateau may indicate the inability to express a clear choice among a set of values. Hence the proposed approach is more than just an extension of interval arithmetics. These frameworks can be applied in the field of Critical Infrastructure Protection, by providing a methodology for the distributed aggregation of clashing observations (e.g., performed by experts and technicians) or for merging real time data into online interdependency models [BC-2, 91, PR-2].

(20)

3. Fuzzy Interdependency Modeling. Another interesting application of fuzzy systems is the modeling and simulation of interdependent Crit-ical Infrastructures. Here the idea is to tune the models based on the experience of human technicians and stakeholders, by converting their linguistic expressions into fuzzy numbers. In this Thesis the problem is tackled from many perspectives, providing a discussion on how to de-fine interdependency models aimed to be easily tunable with linguistic data. To this end many extension of the Input-Output Interdependency Model (IIM) [39] have been provided [IJ-3, IJ-2, IJ-4]. Note that, also in this field, the theory of fuzzy numbers and systems provides a rele-vant enhancement in the descriptiveness of interdependency models for Critical Infrastructures. This Thesis, finally, provides a description of the online approach used within the MICIE european project [91] for the real time assessment of Critical Infrastructure interdependencies. Such an approach is based on a set of methodologies, namely Mixed-Holistic Reductionistic Model [ES-1] and CISIA simulator [89], and is intended as a synthesis of the different aspects discussed in this Thesis.

Let us now provide some notation and definitions that will be used along this work.

1.4 Notation and Preliminary Definitions

General Notation In the following, x will denote a vector with fuzzy entries, while crisp (i.e., non-fuzzy) vectors will be denoted by z.

Let Ipbe the p × p identity matrix and let cp be a vector of p components,

each equal to c.

Let A ⊗ B denote the Kronecker product of two square matrices A (n × n) and B (m × m), that is the nm × nm matrix:

A ⊗ B =    a11B · · · a1nB .. . . .. ... an1B · · · annB    (1.1)

Spaces, Sets and Metrics _{Let R, N be the set of reals and integers,} re-spectively and R+

, N+ _{be the set of nonnegative real and integer numbers,}

respectively. Let Kn

C be the space of nonempty compact convex subsets of Rn.

Let Bn

be the open unit ball in Rn_.

Given a space X and a particular distance dXdefined over such a space, the

Hausdorff separation and the Hausdorff metric for two sets A, B ⊂ X are given by:

ρ∗_d,X(A, B) = sup{d_X(a, b) : a ∈ A, b ∈ B} (1.2) ρ_d,X(A, B) = max{ρ∗_d,X(A, B), ρ∗_d,X(B, A)} (1.3)

(21)

1.4. NOTATION AND PRELIMINARY DEFINITIONS 9

Stability of Crisp Systems. Consider the following discrete-time crisp (i.e., non-fuzzy) system:

z(k + 1) = G(z(k), k), z(0) = z0 (1.4)

where k ∈ N+

represents the discrete time step, G : Rn_×N+_{→ R}n_{is continuous}

and z, z0∈ Rn.

Let 0n = [0, . . . , 0]T ∈ Rn; 0n is a stable solution for System (1.4) if, for

each > 0 there exists a positive function δ() such that

d_Rn(z0, 0n) < δ() implies d_Rn(z(k), 0n) < , ∀k ≥ 0 (1.5)

Moreover if further than (1.5) it is also verified that lim

k→+∞dR

n(z(k), 0) = 0 (1.6)

then 0n is said to be a asymptotically stable solution of (1.4).

Monotonicity Definitions. If a matrix M is non-negative (non-positive), i.e., it has only non-negative (non-positive) entries, write M ≥ 0 (M ≤ 0). If B − A is a nonnegative matrix, write B ≥ A.

Let gi(z(k), k) : Rn× N+ → R be the i-th component of G(z(k), k) (i.e.,

G(z(k), k) is the column-wise concatenation of the gi(z(k), k), for all i =

1, . . . n).

Let za, zb∈ Rn; define the partial orderings ≥ as follows

za ≥ zb ⇔ zai≥ zbi, ∀i = 1, . . . , n (1.7)

The definition of ≤ is analogous.

A continuous function gi(z, k) : Rn × N+ → R is said to be monotone

nondecreasing in z if:

za≥ zb⇒ gi(za, k) ≥ gi(zb, k) ∀k ∈ N+, ∀za, zb∈ Rn (1.8)

Conversely, it is monotone nonincreasing if:

za≤ zb⇒ gi(za, k) ≤ gi(zb, k) (1.9)

or in other terms if gi(·, k) preserves the partial ordering ≤ (or ≥).

The above definition can be easily extended to G(z, k) if it preserves the partial ordering ≤ (≥) defined in (1.7).

Notice that the monotone nondecreasing assumption for system (1.4) is equivalent to require that the system is non-negative, that is, its state z(k) remains nonnegative for each k ∈ N+if the initial conditions z0are nonnegative

[67].

Let us define a system (1.4) to be separable if G(·, k) is such that ∀i = 1, . . . , n gi(z, k) = n X j=1 gij(zj, k) (1.10)

(22)

Moreover, if ∀i = 1, . . . , n, ∀j = 1, . . . , n, gij(zj, k) is continuous and is

either monotone nondecreasing or monotone nonincreasing let us define the system (1.4) to be monotonically separable.

Let us define the monotonicization G∗(·, k) of a monotonically separable system with dynamics G(·, k) to be a system such that, ∀i = 1, . . . , n

g∗_i(z, k) = n X j=1 g∗_ij(zj, k) (1.11) where g∗_ij(zj, k) = ( gij(zj, k) if gij(zj, k) monotone nondecreasing −gij(zj, k) if g∗ij(zj, k) monotone nonincreasing (1.12)

Graphs Let G = {V, E , Γ} be a weighted graph with p nodes, where the set V denotes the nodes v1, . . . , vp; E is the set of edges (vi, vj). Matrix Γ = {γij} is

the weighted adjacency matrix describing the network topology; it is composed of non-negative entries and γij > 0 ⇔ (vi, vj) ∈ E , i.e., there exists an arc that

starts form node viand reaches node vj. The value of γij represents the weight

of the arc (vi, vj).

The graph G is said to be undirected if (vj, vi) ∈ E whenever (vi, vj) ∈ E

(the weights are γij = γji in this case); otherwise the graph G is said to be

directed.

An undirected graph G contains a spanning tree if there is a tree composed of a subset of the edges that connects each node vi to each node vj; in this

case the undirected graph is said to be connected. A directed graph G contains a directed spanning tree for a node vi if there is a tree composed of a subset

of the (oriented) edges that connects vi to each other node vj; in this case the

directed graph is said to be simply connected.

A directed graph G is strongly connected if for each couple of nodes viand vj

there is a path composed of edges in E that connects vi and vj, respecting the

orientation of the edges. Clearly a connected undirected graph is also strongly connected.

The set of the neighbors of a node vi is denoted by Ni= {vj∈ V : (vi, vj) ∈

E}.

Let degout_i = Pp

j=1γij be the out-degree of node vi (i.e., the number of

outgoing links, weighted by the γ coefficients) and let degini =

Pp

j=1γjibe the

in-degree of node vi (i.e., the number of incoming links, again, weighted by

the γ coefficients). Clearly, if the graph G is undirected the in-degree and the out-degree coincide for each node. Generally speaking, if the in-degree equals the out-degree, the graph G is said to be balanced.

(23)

1.4. NOTATION AND PRELIMINARY DEFINITIONS 11

Laplacian Matrix Let L be the Laplacian matrix induced by the adjacency matrix Γ of a graph G, whose elements {lij} are in the form:

lij= ( Pp k=1γik, j = i −γij, j 6= i (1.13)

From this definition, it follows that L = D − Γ, where D is a diagonal matrix containing the out-degrees of each node. Note that, by construction, L has zero row-sum, i.e.,Pp

j=1lij = 0 for all i = 1, . . . , p. It is a well known result

[80, 122] that the eigenvalues of L are all non-negative, λ = 0 being its smallest eigenvalue, whose multiplicity is equal to the number of connected components of the corresponding graph. Moreover if the graph is strongly connected, λ = 0 is a simple eigenvalue of L with eigenvector 1p (i.e., L1p = 0). Moreover, if

the graph is also balanced (or undirected), then 1T

pL = 0 (i.e., L has also zero

(24)

(25)

Part I

Fuzzy Systems

(26)

(27)

Chapter 2

Discrete-Time Fuzzy Systems

Modeling real systems often represents an hard challenge and is generally sub-ject to non trivial issues; in fact in many situations the system to be modeled is very complex, or the model may be affected by subjective choices. This is particularly true when humans are directly involved in the functioning of the system (i.e., when linguistic opinions have to be handled quantitatively [30, 92]). Fuzzy theory, [22, 26, 58], appears a quite natural choice to address the problem of modeling complex systems affected by vagueness.

In the literature many approaches have been introduced: in [26, 41] fuzzy numbers are used to model uncertain quantities (e.g., different beliefs or opin-ions [69]), considering also the fuzzy extension of traditional arithmetic oper-ations; a different approach is to use controllers based on fuzzy rules [71, 82, 111, 48] to control real-world systems that are hard to handle using traditional approaches, but such that they are feasibly manageable by human operators (e.g., a parking system [1] or the navigation [34] of a wheeled mobile robot); a more formal approach is to consider a dynamic fuzzy equation or system, both in the continuous [60, 58, 84, 104, 51] and discrete-time [58].

In this Chapter a framework for the analysis of Discrete-time Fuzzy sys-tems is provided, focusing on the stability and on the level-wise representation of such systems [SJ-1]. Exploiting the richness of the fuzzy theory, the pro-posed framework allows to the ambiguity and vagueness associated to the state of dynamical systems; hence it has both the advantages of handling vague information and of modeling human opinions and beliefs.

The Chapter is mainly based on the scalar stability results in [58], where a comparison theorem has first been proved and on the results in [84, 104, 51] related to the level-wise representation of scalar fuzzy differential equations. The main theoretical contribution of this Chapter, besides the extension of the comparison principle [58] to the vectorial case and the general simplification and systematization of the theory, is the proof that the stability of a positive system is an intrinsic property of the dynamics, regardless the or crispness of the initial conditions. However in the general case, according to [58], the fuzzy system is required to be bounded by a positive crisp system, and in this

(28)

16 CHAPTER 2. DISCRETE-TIME FUZZY SYSTEMS

Chapter some conditions to overcome such a limitation are given.

2.1 Definitions

The key idea of Fuzzy Theory is to extend traditional Set Theory by allowing an element to partially belong to a set.

Definition 2.1.1. (Fuzzy Set) Let us define a fuzzy subset of R through a membership function x : R → [0, 1] which assigns to each point p ∈ R a grade of membership in the fuzzy set [22].

Let us define the p-membership x(p) as the grade of membership of p ∈ R in the set x. In the following, the value assumed by a given fuzzy variable at time instant k will be denoted by x(k); in this case the p-membership of the set x(k) is denoted by x(p, k). Note that, when dealing with fuzzy sets, it is very common to denote with the same symbol the fuzzy sets itself and the membership function that defines the set, since the membership function univocally determines the set and vice-versa.

Definition 2.1.2. (α-level) Let us define an α-level set [x]α _{of a fuzzy set x}

as

[x]α_{= {p ∈ R|x(p) ≥ α}} (2.1)

where x(p) is the p-membership and α ∈ [0, 1].

The level set [x]0 _{is often referred to as the support of x.}

Figure 2.1: Different α-levels of a triangular-shaped fuzzy membership func-tion.

The α-levels, as shown in Figure 2.1, allow to treat a fuzzy sets as a collec-tion of nested real intervals. In the following the evolucollec-tion of a fuzzy dynamic

(29)

2.1. DEFINITIONS 17

system will be evaluated level-wise by considering for each α, the evolution of a system whose state is described by the endpoints of the interval that represents the α-level.

According to [58], let us now introduce the space E of Fuzzy Numbers (FN) [26, 41].

Definition 2.1.3. (Fuzzy Numbers) Let us define the space E of Fuzzy Numbers as the space of fuzzy subsets x of R such that:

1. x maps R onto [0, 1]; 2. [x]0

is a bounded subset of R; 3. [x]α

is a compact subset of R for all α ∈ (0, 1]; 4. x is fuzzy convex, that is:

x(φp + (1 − φ)q) ≥ min[x(p), x(q)] for all p, q ∈ R

A few remarks are now in order:

Remark 2.1.4. These above conditions are equivalent to require that: • the membership functions are compact;

• their shape is composed of a monotone nondecreasing and a monotone non increasing part (e.g., a triangle);

• the α-levels are nested, i.e., those with greater values of α are contained into those with smaller α (all the intervals are contained in the support).

Let us now introduce a particular subclass of FNs denoted as Triangular Fuzzy Numbers (TFN).

Definition 2.1.5. (Triangular Fuzzy Numbers) A triangular fuzzy number x ∈ E is described by an ordered triple {xl, xc, xr} ∈ R3with xl≤ xc≤ xrand such

that [x]0 = [xl, xr] and [x]1 = {xc}, while in general the α-level set is given,

for any α ∈ [0, 1] by:

[x]α= [xc− (1 − α)(xc− xl), xc+ (1 − α)(xr− xc)] (2.2)

An illustrative example of triangular fuzzy numbers is reported in Figure 2.2; the Figure shows two triangular fuzzy numbers with different levels of am-biguity, representing for example the codification of the statement “an high wall”. Specifically, the interior triangle represents the fuzzy number corre-sponding to the measure of 4 meters with a given degree of ambiguity (i.e., the width of the base of the triangle); the exterior triangle still represents the same fuzzy number 4, but with a greater ambiguity.

(30)

Triangular Fuzzy Numbers are widely used in many applications, due to their compact representation. In fact they can be described by the triple of the abscissae of their vertices (e.g., {2, 4, 6} and {3, 4, 5} in the case of the Triangular FNs in Figure 2.2). Moreover, as shown in Figure 2.1, a singleton is obtained for α = 1. Hence the α-level with the strongest belief collapses into a crisp point.

However, the triangular representation is not the sole available alternative. As depicted in Figure 2.3 many other shapes are possible, and more complex is the shape, more descriptive is the resulting fuzzy number (i.e., the vagueness is better characterized). For instance the existence of a plateau for a given interval represents complete indeterminacy for that interval, or an asymmetry with respect to the peak may represents different beliefs in the entity of the values that are smaller or bigger than the “nominal” value (e.g., the best and worst cases).

Indeed complex shapes, as shown in Figure 2.3, allow to better character-ize the uncertainty: the leftmost Fuzzy Number represents a situation where uncertainty rapidly decreases while approaching the peak value; the rightmost Fuzzy Number, due to its trapezoidal shape, models the case where multiple values are associated to the maximum belief.

Note further that, as stated before, the shape of a FN needs not to be symmetric (see the central TFN in Figure 2.3), thus allowing to represents different beliefs on the left and right spread of uncertainty with respect to the value associated with the maximum belief.

0 1 2 3 4 5 6 7 8 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Figure 2.2: Two triangular fuzzy numbers representing the same value “about 4”, although with different uncertainty.

Let us now endow the space of fuzzy sets with a metric [58].

(31)

2.1. DEFINITIONS 19 0 2 4 6 8 10 12 0 0.2 0.4 0.6 0.8 1

Figure 2.3: Examples of fuzzy numbers in the space E.

metric d_E(·, ·) is defined: d_E(x1, x2) = sup α>0 {ρdR,R([x1] α_{, [x} 2]α)}, x1, x2∈ E (2.3)

This metric correlates the distance with the α-sets [58], considering the sup(·) of the Hausdorff distances of the α-levels in Rn_.

Let us now define the level-wise convergence of a sequence of fuzzy numbers, that is, for a fixed α ∈ [0, 1], the convergence of the α-levels of the FNs in the sequence.

Definition 2.1.7. (Level-wise convergence in R) Let {xn} be a sequence in E,

then {xn} converges level-wise to x ∈ E if, for all α ∈ (0, 1]:

ρdR,R([xn]

α_{, [x]}α_{) → 0} _as _{n → ∞} _(2.4)

Let us define the set of concave fuzzy sets:

Ψ = {x ∈ E : x(φp + (1 − φ)q) ≥ φx(p) + (1 − φ)x(q)} (2.5)

for each p, q ∈ [x]0, φ ∈ [0, 1].

In [58] it is proved that convergence in (E, dE) implies level-wise

conver-gence. Moreover, limiting to sequences in Ψ, the implication between con-vergence in (E, dE) and level-wise convergence can be revised. Note that the

concavity of the fuzzy number is not always verified. This is the case, for instance, of the leftmost FN in Figure 2.3 (e.g., for p = 0 and q = 0.6).

(32)

Lemma 2.1.8. The set Ψ is closed under monotone nondecreasing transfor-mations.

Proof Let x ∈ Ψ and let f : En _{→ E}n _{be a monotone nondecreasing}

function. Then for any p, q ∈ [x]0, due to the nondecreasing monotonicity of f and to the concavity of x it is verified that

y = f (x(φp+(1−φ)q)) ≥ f (φx(p)+(1−φ)q) ≥ φf (x(p))+(1−φ)f (x(q)) (2.6)

therefore y ∈ E belongs to Ψ.

The above lemma requires the nondecreasing monotonicity property that, as stated before, holds true for positive systems. The class of positive linear systems is therefore included, and it is indeed a well known result that a linear combination of concave functions with positive coefficients is again concave. However the property is not generally true for any level wise representation of a DFS.

Let us now provide the following result in the case of TFNs.

Theorem 2.1.9. Limiting to sequences in the set of TFNs, level-wise conver-gence implies converconver-gence in (E, dE).

Proof It is sufficient to show that the set of TFNs is a subset of Ψ. Let a TFN x = {xl, xc, xr} and consider two real numbers p, q ∈ [xl, xr], with p ≤ q

and let h = φp + (1 − φ)q, φ ∈ [0, 1]. First of all consider the case in which p ≤ q ≤ xc or xc ≤ p ≤ q, that is x(p) and x(q) are on the same edge of the

TFN. The value of x(h) is given by:

x(h) =x(q) − x(p)

q − p (h − p) + x(p) (2.7)

which, just as expected, satisfies condition (2.5) as an equivalence.

Consider the case in which p ≤ xc ≤ q and x(p) ≤ x(q). In this case it

is true that if q = xc the condition (2.5) is satisfied as an equivalence and if

q > xc then x(q) < x(xc) = 1, meaning that condition (2.5) is satisfied. A

similar result holds in the case in which p ≤ xc ≤ q and x(p) > x(q), proving

the statement.

In the case of linear systems with triangular initial conditions, let us now relax the nondecreasing monotonicity assumption.

Corollary 2.1.10. In the case of linear systems with triangular initial condi-tions level-wise convergence implies convergence in (E, dE)

Proof Since TFNs are closed with respect to linear transformations [26, 41], the sequences of FNs generated by a dynamic system are all triangular and remain in Ψ.

In order to consider vectors of n components, each being a FN, the space En has to be characterized; to this end let us endow En with the following

(33)

2.2. STABILITY 21 metric [58]: d_En(x, y) = n X i=1 d_E(xi, yi) (2.8)

where x = [x1, . . . , xn]T and y = [y1, . . . , yn]T, x, y ∈ En, while ∀i = 1, . . . , n

xi, yi∈ E.

Let us define the α-level of a vector of FNs x ∈ En _{as the set of vectors}

z ∈ Rn such that, zibelongs to the α-level of i-th component xi, ∀i = 1, . . . , n.

Let us now extend level wise convergence in the case of vectors of FNs. Let {xn} be a sequence on En, then {xn} converges level-wise to x ∈ En if, for all

α ∈ (0, 1]:

ρdRn,Rn([xn]

α_{, [x]}α_{) → 0} _as _{n → ∞} _(2.9)

Let us now extend the set Ψ of concave fuzzy sets to the vectorial case as follows:

Ψn_{= {x ∈ E}n: xi(φp + (1 − φ)q) ≥ φxi(p) + (1 − φ)xi(q)} (2.10)

for each p, q ∈ [xi]0, φ ∈ [0, 1] and ∀i = 1, . . . , n. Note that, with the above

definition of α-level of a vector of FNs, it follows that

lim n→∞ρdRn,Rn([xn] α_{, [x]}α_{) = 0 ⇔ lim} n→∞ρdR,R([xni] α_{, [x} i]α) = 0 (2.11)

∀i = 1, . . . , n, where xniis the i-th component of xn; therefore the scalar results

on level-wise convergence apply to the vectorial case.

In the following the stability and level-wise representation of systems with fuzzy initial conditions will be characterized; within this setting, therefore, the state variables are defined for each time instant as a FN, hence by a set of values, each with a specific level of believeness. Such an extension is of great interest in all those situations where there is the need to operate with dynamic systems in the presence of ambiguities and vagueness, and, as will be clarified later in the text, when humans are involved or when there is the need to represent vague and linguistic opinions.

2.2 Stability

Let us now introduce the definition of discrete-time Fuzzy Systems (DFS).

Definition 2.2.1. (Discrete-time Fuzzy Systems) A discrete-time Fuzzy Sys-tem is a sysSys-tem in the form:

x(k + 1) = F (x(k), k); x(0) = x0 (2.12)

(34)

Analogously to the crisp case, let ˆ_{0 ∈ E}n _{denote the trivial solution of Eq.}

(2.12), which is assumed to exist. Note that such a trivial solution coincides with the crisp zero or, in other terms, the i-th component ˆ0ican be seen as the

TFN {0, 0, 0}.

Definition 2.2.2. The trivial solution ˆ0 of System (2.12) is a stable solution of (2.12) if, for each > 0 there exists a positive function δ() such that

d_En(x₀, ˆ0) < δ() ⇒ d_En(x(k), ˆ0) < , ∀k ≥ 0 (2.13)

Similarly, the trivial solution ˆ0 of System (2.12) is said to be asymptotically stable if the condition given in eq. (2.13) is fulfilled and:

d_En(x(k), ˆ0) → 0, as k → +∞ (2.14)

The following result, based on the work in [60, 58], characterizes the stability of a fuzzy system (2.12) in terms of the stability of a suitable bounding crisp system (2.15) in the form

z(k + 1) = G(z(k), k), z(0) = z0 (2.15)

where z, z0∈ Rn and G : Rn× N+→ Rn is continuous.

The proof is mainly based on a defuzzyfication function, that is used to project the fuzzy state space into a crisp one; then the fuzzy stability definition (2.13) is derived thanks to the non-decreasing monotonicity assumption made for the bounding dynamic system.

Theorem 2.2.3. Let a DFS (2.12) and let a crisp system (2.15) where G(z(k), k) is a continuous function, monotone nondecreasing with respect to z(k) for k ≥ 0.

Suppose that there is a continuous and positive valued defuzzyfication func-tion V (x(k), k) : En× N+→ Rn+ such that, posing z(0) = V (x(0), 0), for each

k ≥ 0

V (x(k + 1), k + 1) ≤ G(V (x(k), k), k) (2.16) Suppose further that there exists a continuous, monotone non-decreasing func-tion a : R → R+ such that

a(d_En(x(k), ˆ0)) ≤ V0(x(k), k) (2.17)

where d_En is the distance in En defined in (2.8) and V₀(x(k), k) is defined as

V0(x(k), k) = n

X

j=1

Vi(x(k), k), ∀k ≥ 0 (2.18)

Then the stability properties of the trivial solution of Eq.(2.15) implies the corresponding stability properties of the trivial solution of Eq.(2.12).

(35)

2.2. STABILITY 23

Proof First, there is the need to prove that, under the hypotheses

V (x(0), 0) ≤ z(0) ⇒ V (x(k + 1), k + 1) ≤ z(k + 1); ∀k ≥ 0 (2.19) In [58], Theorem 5.2.1, it is proven that, given a scalar function g(r, k), nonde-creasing in r for each k ≥ 0, k ∈ N+ _{and given two sequences of real numbers}

{ck}, {dk} such that c0 ≤ d0 and such that the following inequality holds for

all k ≥ 0

ck+1≤ g(ck, k) (2.20)

dk+1≥ g(dk, k) (2.21)

then ck≤ dk, for all k ≥ 0.

Such a Theorem trivially extends to the vectorial case, therefore, consid-ering a vectorial G(r, k) : Rn_{× N}+ _{→ R}n _{and setting {c}

k} as the sequence

of defuzzyfied values {V (x(k), k)} and {dk} equal to the sequence of values

assumed by system (2.12) {z(k)}, implication (2.20) holds because of impli-cation (2.16) and impliimpli-cation (2.21) is true due to the monotonicity of G(·, ·); therefore implication (2.19) is proved.

Suppose that the trivial solution of (2.15) is stable. Then, for each a() > 0 there exists a positive δ1() such that

d_Rn(z(0), 0_n) =Pn_j=1z_j(0) < δ₁() (2.22)

implies

d_Rn(z(k + 1), 0_n) =Pn_j=1z_j(k + 1) < a() (2.23)

where d_Rn(·, ·) is the distance in Rn defined in (??).

To prove the stability of Sytem (2.12) there is the need to show that, for any ≥ 0 there exists a positive δ() such that if d_En(x(0), ˆ0) ≤ δ() then

d_En(x(k), ˆ0) < , for each k ≥ 0.

Since z(0) = V (x(0), 0), on the base of the Implication (2.19), it follows that V0(x(k + 1), k + 1) ≤ P

n

j=1z(k + 1); therefore, according to Inequality

(2.17): a(d_En(x(k + 1), ˆ0)) ≤ V₀(x(k + 1), k + 1) ≤ n X j=1 zj(k + 1) < a() (2.24)

Due to the continuity and monotonicity of a(·), it follows that

a(d_En(x(k + 1), ˆ0)) < a() ⇒ d_En(x(k + 1), ˆ0) < (2.25)

and the stability of system (2.12) is proved. For asymptotic stability note that

0 ≤ a(d_En(x(k + 1), ˆ0)) ≤ V₀(x(k + 1), k + 1) ≤

n

X

j=1

(36)

If System (2.15) is asymptotically stable, then zj(k + 1) → 0 as k → ∞, for

each j = 1, . . . , m, and it follows that d_En(x(k + 1), ˆ0) → 0 as k → ∞, too.

The above comparison theorem, therefore, allows to derive the stability of a fuzzy system from the stability of suitable non-fuzzy system. Note that the crisp system (2.15) has to be a bound for the defuzzyfication of the fuzzy system (2.12) only for non-negative values. In fact, since z(0) = V (x(0), 0) ≥ 0 and the bounding crisp system has monotone non-decreasing dynamics, condition (2.16) has to be verified only for non-negative values.

Indeed the choice of such a bounding system, as well as the choice of the correct defuzzyfication function can be quite hard. However, since the dynamics of the DFS is itself crisp (i.e., there are no fuzzy parameters, but only fuzzy state variables), it is interesting to see what happens when the dynamics of the fuzzy system and of the crisp bounding system coincide.

The following Corollary, hence, provides a useful parallelism between the stability of a fuzzy system and the stability of a crisp system obtained by defuzzyfication (i.e., the case in which G(z(k), k) = F (z(k), k)); the key aspect of the proof is the choice of a particular defuzzyfication function.

Corollary 2.2.4. Let the assumptions of Theorem (2.2.3) hold. Let a DFS in the form of Eq. (2.12) where F (·, k) is monotone nondecreasing, and let the following crisp system

z(k + 1) = F (z(k), k) z(0) = V (x(0), 0) (2.26)

The stability properties of crisp system (2.26) imply the corresponding sta-bility properties of the DFS (2.12).

Proof It will be shown that, choosing Vi(x(k), k) = dE(xi(k), ˆ0i) the

con-ditions required by Theorem 2.2.3 are verified.

Inequality (2.17) is satisfied if it is true component-wise, that is, if:

a(d_En(x(k), ˆ0)) ≤

n

X

i=1

d_E(xi(k), ˆ0i) = dEn(x(k), ˆ0) (2.27)

Since d_En(x(k), ˆ0) ≥ 0, the inequality is verified choosing a(r) = ψr, with

ψ ∈ [0, 1]. In this case a(·) is continuous and monotone non-decreasing. It remains to prove inequality (2.16).

Note that V (x(k), k) = [d_E(x1(k), ˆ01), . . . , dE(xn(k), ˆ0n)]T. There is the

need to prove that, for all i = 1, . . . , n

d_E(fi(x(k), k), ˆ0i) ≤ fi(V (x(k), k), k) (2.28)

Note that [ˆ0i]α= {0} for all α, hence:

d_E(w, ˆ0i) = supα>0{ρdR,R([w]

α_{, {0})} =}

= max{d_R([w]0_{, {0})} = max{||z|| : z ∈ [w]}0_}

(37)

2.2. STABILITY 25

that is to say that the distance of a given fuzzy set from zero is the maximum value of the norm of its support (i.e., the absolute value of one of the endpoints of the support). Analogously we have that

Vi(x(k), k) = max{||z|| : z ∈ [xi(k)]0} (2.30)

Note that fi(·, k) is monotone nondecreasing and that in the left term of

inequality (2.28) the max{|| · ||} are taken component-wise; therefore inequality (2.28) is always verified.

Hence the requirements of Theorem 2.2.3 are fulfilled and the proof is com-plete.

The above corollary proves that, under the non-decreasing monotonicity as-sumption made, the stability is an intrinsic property of the dynamics, regardless the fact that the state is fuzzy or crisp. In other terms, the fuzzyfication of a particular class of crisp systems (i.e., the class of stable systems with monotone nondecreasing dynamics) preserves the stability properties. The role of such a monotonicity assumption in the stability will be better clarified while analyzing the level wise representation of a DFS. Note that the chosen defuzzyfication function, being equal to the distance from the origin, corresponds to the norm of each state variable.

However, when the monotonicity assumption is not satisfied, there is the need to find a stable crisp system with monotone nondecreasing dynamics that bounds the fuzzy system that is, generally speaking, quite hard to be found. Under the hypothesis of monotonically separable dynamics, however, it is easy to find such a bounding system.

Corollary 2.2.5. Let a monotonically separable DFS (2.12), such that the terms fij(xj, k) are zero at zero. The monotonicization of the defuzzyfied crisp

system (2.26), defined as

z∗(k + 1) = F∗(z∗(k), k) z∗(0) = V (x(0), 0) (2.31) is a bound for system (2.12) according to Theorem 2.2.3.

Proof Note that, under the hypotheses F∗(z∗(k), k) is continuous and is monotone nondecreasing in z∗ for each k.

There is the need to show that system (2.31) satisfies inequality (2.16). Inequality (2.16) is true if it holds component by component, i.e., if

Vi(x(k + 1), k + 1) ≤ f gi(V (x(k), k), k) = n

X

j=1

fij(Vj(x(k), k), k) (2.32)

Since Vj(x(k), k) is always non-negative and fij∗(·, k) (i.e., the

monotoni-cization of fij(xj, k)) is monotone nondecreasing and zero at zero, it follows

that

fij(Vj(x(k), k), k) ≤ fij∗(Vj(x(k), k), k) (2.33)

(38)

The requirement that the terms fij(zj∗, k) are zero at zero follows from the

consideration that, in this case, due to the monotonicity (either non-increasing or non-decreasing) and due to the continuity, the terms f_ij∗(z_j∗, k) are monotone non-decreasing and assume non-negative values for z_j∗≥ 0, thus bounding the terms fij(zj∗, k) for non-negative values of z∗j.

The above corollary, therefore, provides a useful criterion for the identifica-tion of a bounding crisp system for a subset of the DFS that are not monotone nondecreasing. If the dynamics is monotonically separable, therefore, the sta-bility of the monotonicization of the defuzzyfied system is sufficient to prove the stability of the original fuzzy system.

2.3 Levelwise Representation

In this Section the numerical representation of DFS is addressed, considering the evolution of its α-levels. Note that each state variable xi is such that, at

any time k its α-level is given by

[xi(k)]α= [xαi(k), ¯x α

i(k)], ∀i = 1, . . . , n (2.34)

In [84, 104, 51], it is shown that, for each time k and for each α-level , the evolution of the system can be described by 2n crisp difference equations for the endpoints of the intervals of eq. (2.34). Hence with reference to the generic DFS (2.12), for each i = 1, . . . , n these equations are:

xα i(k + 1) ¯ xα i(k + 1) = = min{fi(u(k), k) : uj(k) ∈ [xαj(k), ¯x α j(k)], ∀j = 1, . . . , n} max{fi(v(k), k) : vj(k) ∈ [xαj(k), ¯xαj(k)], ∀j = 1, . . . , n} (2.35)

where the in initial conditions are given by:

xα_i(0) ¯ xα_i(0) = = xα_i0 ¯ xα_i0 (2.36)

Based on the results on level-wise convergence, it is possible to provide the following stability results.

Lemma 2.3.1. If the dynamics of a DFS (2.12) is monotone nondecreasing and the initial conditions x0∈ Ψn, then the stability of all the α-levels (2.35)

for α ∈ [0, 1] imply the stability of the DFS (2.12)

Proof From lemma 2.1.8, Ψ is closed to monotone nondecreasing transfor-mations, and the result trivially extends to Ψn, proving the statement.

Lemma 2.3.2. If the dynamics of a DFS (2.12) is linear and the initial con-ditions x0 are such that x0i is a TFN for each i = 1, . . . , n, then the stability

(39)

2.3. LEVELWISE REPRESENTATION 27

Number Assumptions Notes

Theorem 2.2.3 Defuzzyfication function; stable

monotone nondecreasing bound-ing crisp system

Applies to any DFS

Corollary 2.2.4 Monotone nondecreasing DFS The stability of a monotone

non-decreasing system is an intrinsic property of the dynamics

Corollary 2.2.5 Stable monotonically separable

DFS, zero at zero

Applies to linear systems and to a subset of nonlinear systems, e.g., with separable variables.

Lemma 2.3.1 Monotone nondecreasing DFS;

concave initial conditions; stable levelwise representation

Applies to the levelwise represen-tation of a DFS

Lemma 2.3.2 Linear DFS; triangular initial

conditions; stable levelwise rep-resentation

Applies to the levelwise represen-tation of a DFS

Table 2.1: Stability conditions for a DFS

Proof From theorem 2.1.9, the set of TFNs is contained in Ψ; moreover it is closed to linear transformations [26, 41], and the results trivially extend to Ψn_{, proving the statement.}

Therefore the stability of a linear fuzzy system can be evaluated directly by evaluating the stability of its α-level, while for other shapes of the initial conditions in Ψn _{the nondecreasing monotonicity is required; otherwise there}

is in general no guarantee. In order to summarize the stability results for a DFS, Table 2.3 provides a synoptic view.

Proposition 2.3.3. If F (·, k) is monotone nondecreasing, then, for each α-level xα_i(k + 1) ¯ xα i(k + 1) = = fi(xα(k), k) fi(¯xα(k), k) (2.37) where xα_{(k) = [x}α 1(k), . . . , xαn(k)]T and ¯xα(k) = [¯xα1(k), . . . , ¯xαn(k)]T.

Proof Since fi(·) is monotone nondecreasing for each i, it commutes with

the max{·} and with the min{·} (i.e. max[a,b]{fi(·)} = fi(max[a,b]{·})), and

the statement is proved.

The above proposition proves that, under the non-decreasing monotonicity assumption made for F (·, k) the system can be represented, for each α-level, by two isolated replica of the original system, one for each endpoint of the interval that represents the α-level.

If the monotonicity assumption is not verified, there is the need to compute each α-level according to (2.35); in the linear case, however, the evolution for each α-level is given by [84]:

xα_{(k + 1)} ¯ xα_{(k + 1)} = F + _F− F− F+ xα_(k) ¯ xα_(k) (2.38)

where matrix F is decomposed into a monotone non-decreasing n × n matrix F+ _{such that f}+

(40)

non-increasing n × n matrix F− such that f_ij− = fij if fij < 0 and is zero

otherwise.

The above equation may help understand why, removing the non-decreasing monotonicity assumption for the defuzzyfied crisp system, the stability of the monotonicization implies the stability of the DFS.

Let the transform matrix T =In −In In In

; changing coordinates by means of this transformation it follows that

TF + _F− F− F+ T−1=F +_{− F}− ₀ 0 F+_{+ F}− =|F | 0 0 F (2.39)

Since the transformed matrix is block diagonal, the stability, for each α-level is obtained if both F and |F | are stable in the discrete-time sense. In other terms, the stability of the monotonicization is required to assure the stability of the fuzzy system.

Note that, in the general (non-linear) case the computation of the α-level is quite complex; however, in the case of monotonically separable systems, such a computation can be simplified.

Proposition 2.3.4. If F (·, k) is monotonically separable, then xα_i =Pn j=1hij ¯ xα_i =Pn j=1rij (2.40) where hij = ( fij(xαj, k) if fij(zj, k) is monotone-nondecreasing fij(¯xαj, k) if fij(zj, k) is monotone-nonincreasing (2.41) and rij = ( fij(¯xαj, k) if fij(zj, k) is monotone-nondecreasing fij(xαj, k) if fij(zj, k) is monotone-nonincreasing (2.42)

Proof Since fi(z, k) is composed of independent terms (i.e., fij(zj, k)

de-pends only on the choice of zj), the following equality holds

xα

i = maxu{fi(u(k), k)} = maxu{P n j=1fij(uj, k)} = =Pn j=1maxuj{fij(uj, k)} = Pn j=1hij (2.43)

The proof for ¯xα_i is analogous.

2.4 Examples

In this Section some examples are given as a simple instrument to understand the potentialities of the proposed framework.

(41)

2.4. EXAMPLES 29

Example 2.4.1. The linear and stationary DFS ( x1(k + 1) = 0.5x1(k) − 0.1x2(k) x2(k + 1) = −0.3x1(k) + 0.1x2(k) (2.44) is asymptotically stable. Let M = 0.5 −0.1 −0.3 0.1

be the dynamic matrix of the above linear and stationary system; in this case the monotonicized dynamic matrix is given by:

|M | =0.5 0.1 0.3 0.1

From Gershgorin circle theorem [116], the matrices M and |M | are both asymptotically stable in the discrete time sense, hence by Corollary 2.2.5 the DFS (2.44) is asymptotically stable.

In the first case the evolution of the generic α-level is given by xα_{(k + 1)} ¯ xα(k + 1) = M + _M− M− M+ xα_(k) ¯ xα(k) (2.45) where M+=0.5 0 0 0.1 , M−= 0 −0.1 −0.3 0 and where ¯ xα= [¯xα₁, ¯xα₂]T , xα= [xα₁, xα₂]T Let us consider the following triangular initial conditions:

x1= {−10, −20, −30}

x2= {50, 70, 90}

Figure 2.4 shows the plot of the evolution of the α-levels of the system for a sampling of α ranging from 0 to 1 with step size 0.1 where the red and the blue curves represent the left and right extrema of the α-level, respectively, and the more external pairs of curves correspond to lower α-levels, while the extrema collapse into a single trajectory for α = 1. Just as expected, the different α-levels converge to 0. Note that it is also possible to represent the evolution of the whole fuzzy sets representing the state variables of the systems; as shown by Figure 2.5, the triangular-shaped initial conditions tend to zero and the shape remains triangular during the evolution of the system, due to linearity. Example 2.4.2. The nonlinear DFS

(

x1(k + 1) = − sinh−1(x2(k))

x2(k + 1) = cosh−1(x1(k))

(2.46)

(42)

30 CHAPTER 2. DISCRETE-TIME FUZZY SYSTEMS 0 1 2 3 4 5 6 7 8 9 10 ï30 ï25 ï20 ï15 ï10 ï5 0 steps x1 0 1 2 3 4 5 6 7 8 9 10 0 10 20 30 40 50 60 70 80 90 steps x2

Figure 2.4: Evolution of the α-levels of linear system introduced in the example 2.4.1: the red and blue curves represent the evolution of left and right endpoint of the α-levels, respectively, for α sampled with step size 0.1.

ï300 ï25 ï20 ï15 ï10 ï5 0.2 0.4 0.6 0.8 1 x1 0 10 20 30 40 50 60 70 80 90 0 0.2 0.4 0.6 0.8 1 x2 Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Step 8 Step 9 Step 10 Step 11

Figure 2.5: Evolution of fuzzy system introduced in the example 2.4.1.

According to Corollary 2.2.5, there is the need to prove that the monotoni-cized bounding system

(

z₁∗(k + 1) = sinh−1(z∗₂(k))

z₂∗(k + 1) = cosh−1(z₁∗(k)) (2.47) is stable.

Recall that a crisp discrete-time system is stable if it is possible to find a positive-definite Lyapunov function W (k) such that W (k + 1) − W (k) is semi-definite negative. Therefore, choosing W (k) = zT_{(k)z(k), which is positive}

definite, it follows that

W (k + 1) − W (k) = sinh−2(z2(k)) + cosh−2(z1(k)) − z12(k) − z 2

(43)

2.4. EXAMPLES 31 0 1 2 3 4 5 ï3 ï2 ï1 0 1 2 3 x1 steps 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 1 2 3 4 5 6 7 x2 steps

Figure 2.6: Evolution of the α-levels of the system introduced in the example 2.4.2: the red and blue curves represent the evolution of left and right endpoint of the α-levels, respectively, for α sampled with step size 0.1.

which is semidefinite negative. Note that the value assumed by W (k+1)−W (k) for the defuzzyfication of system (2.46) and for system (2.47) is the same, hence the stability of the two crisp systems hold simultaneously.

Figure 2.7: Evolution of fuzzy system introduced in the example 2.4.2.

Therefore the crisp version of system (2.46) is stable and, by Corollary 2.2.5 the DFS (2.46) is stable.

(44)

According to Proposition 2.3.4, the evolution of the generic α-level is given by          xα₁(k + 1) = − sinh−1(¯xα₂(k)) xα 2(k + 1) = cosh −1_(xα 1(k)) ¯ xα 1(k + 1) = − sinh −1_(xα 2(k)) ¯ xα 2(k + 1) = cosh −1_(¯_xα 1(k)) (2.49)

The following triangular initial conditions were chosen: x1= {1, 2, 3}, x2=

{5, 6, 7}.

Figure 2.6 shows the plot of the evolution of the α-levels of the system for a sampling of α ranging from 0 to 1 with step size 0.1: as expected, the different α-levels do not diverge nor tend to zero (i.e., they remain in a bounded region of the origin), as shown also by Figure 2.7, where the evolution of the fuzzy system is plotted.

Note that, in general, when the system is non-linear the shape of the fuzzy sets is not triangular, even if the initial conditions were triangular; for instance Figure 2.8 shows the evolution of the scalar system

x1(k + 1) = − sinh−1(x1(k)) (2.50)

with triangular initial condition {1, 2, 3}.

−2 −1.5 −1 −0.5 0 0.5 1 1.5 2 2.5 3 0 0.2 0.4 0.6 0.8 1 x1 0 1 2 3 4 5 6 7 0 0.2 0.4 0.6 0.8 1 x2 Step 0 Step1 Step 10 step 500

Figure 2.8: Evolution of fuzzy system (2.50)

In the following Chapter the proposed fuzzy framework will be extended, considering systems with fuzzy initial conditions and fuzzy dynamics, thus obtaining a Fuzzy Difference Inclusion.

To conclude this Chapter, let us give a last example, where the system is nonlinear nor monotonically separable.

Fuzzy Logistic Map

In order to show the potentialities of the framework, in the following a fuzzy extension of a chaotic system will be considered [SC-1].

In the literature the relations between chaotic and fuzzy systems have been deeply inspected, with the aim to provide more insights on the relation between

(45)

2.4. EXAMPLES 33

these two branches. However the focus of such researches is mainly on the approximation or control of chaotic behaviors by means of fuzzy rule-based systems.

Indeed the proposed framework allows to capture how the fuzziness further increases the chaotic behavior of the system under analysis, since such a for-malism highlights that close points in the membership function representing the state of the system evolve in significantly different ways.

Chaotic systems gained large attention in the scientific community (see [123] and its references) as systems with rather unpredictable behavior due to inadequate feature of measurement methodology (e.g. weather evolution).

The question then arises wether it is possible or not to establish a bridge between these two fields. In the literature the interactions between fuzzy and chaos theories have been inspected according to 4 main perspectives:

1. fuzzy control of chaotic systems [119, 13];

2. fuzzy model identification based on the evolution of chaotic systems [43]; 3. theoretical relations between fuzzy logic and chaos [54];

4. approximation a chaotic system by means of fuzzy rule-based systems [90, 107].

In this Section a different path will be followed by resorting to the DFS formalism.

The proposed approach, besides providing a formal representation, allows to handle non-triangular shapes for the state of the system. Indeed chaotic systems are highly nonlinear, hence approximating their behavior by means of triangular shapes [90, 107] is a very rough assumption, that does not account for the complexity of the problem at hand.

In order to show the potentialities of the proposed framework, let us focus on the extension of the chaotic logistic map in the fuzzy fashion, letting the initial condition (i.e., the initial population) be defined by a fuzzy set.

The proposed extension allows to exploit the complexity and the richness of fuzzy sets, hence providing a sophisticated description of the population at each time step. Moreover, such an extension successfully captures and further amplifies the underlying chaotic behavior of the logistic map, since the evolu-tion of the fuzzy set representing the populaevolu-tion is not uniform, in the sense that the membership grade of close points in the fuzzy set show significant differences.

The logistic map [73, 6] is the discrete-time version of the logistic equation [117, 118], a demographic model that captures the aspects of reproduction and starvation in a population. Such a model is described by the following equation:

z(k + 1) = rz(k)(1 − z(k) (2.51)

where z(k) ∈ [0, 1] represents the ratio of existing population with respect to the maximum population at year k and r, chosen in the range [0, 4], represents