Printer Friendly

Uncertainty, dualism and inverse reachable sets.

1. INTRODUCTION

While constructing models, the uncertainty is being treated in many different ways. Roughly speaking, by uncertainty we understand a lack of exact information about some model parameters, or even about the model structure. Mostly, the uncertain parameters are represented in the model as random variables, which add the stochastic properties to the model. As there is a huge research on stochastic systems already done, this approach works well, provided the specification of the randomness is known. In general, to use a random variable we must know something about the basic parameters of the corresponding probability distribution. Unfortunately, this is not always the case. The mean value is frequently a confusing and little informative, and the standard deviation does not describe the random variable sufficiently enough. The density function is rarely known, and it may be inexistent at all. This is, for example, the case when the uncertain parameter represents false information intentionally inserted into the modelled system (as in stock market models).

There is no room here to mention a huge number of publications on uncertainty problems. See Bargiela and Hainsworth (1) or Bargiela (2) for an example of a quite different approach to the uncertainty management in water distribution systems, for example.

If we construct a continuous ODE (Ordinary Differential Equations) model, then the general description of its dynamics is, in most cases, given by the equation:

dx/dt = f(x(t),t), x(0) = [x.sub.0] (1)

where x(t) is the system state (a scalar, a point of the [R.sup.n] or a more abstract state space), and [x.sub.0] is the initial condition. Now, suppose that the value of f is charged with some uncertainty. Our, non-stochastic approach to the uncertainty problem is to replace (1) with a differential inclusion:

dx/dt [member of] F(x(t),t), x(0) [member of] [X.sub.0] (2)

where F is a set-valued function that maps (x, t) into a subset of the corresponding state space, and [X.sub.0] is the initial set. Note that the inclusion (2) has nothing random and that the whole model is deterministic. The solution to the equation (1) is a function of time. In turn, the solution to a differential inclusion (2) is the reachable set of the inclusion, and not a particular model trajectory.

In the section 3 of this paper we try to generalize the model specification by using the language of the theory of categories. The main purpose of this theory is abstraction and generalization of the concepts being considered. In our case, for example, the model is continuous and described by the differential inclusion. The categorical language, however, makes no use of this continuous nature of the model. So, it can describe the uncertainty and the reachable sets of any other model, even a discrete event one. This generalization should be exploited with more detail and more possible applications in the future. Now let us recall some definitions.

2. DIFFERENTIAL INCLUSION

A differential inclusion (DI) is defined by the formula (2). Early works on the DIs in the finite-dimensional case were published by Marchaud (3) and Zaremba (4). The terminology used in those papers was slightly different from later works. Zaremba uses the term paratingent equation and Marchaud calls the same a contingent equation. Their research was criticized by contemporary mathematicians and physicists as an abstract and useless work. In fact, Zaremba and Marchaud had already described the main properties of trajectories and reachable sets of control systems many years before those problems have been treated by the Control Theory. The later works of Turowicz and Wazewski provided more important results. Wazewski (5-7), Turowicz (8), (9) and Plis (10) gave the generalization of the basic results to the case of non convex sets of admissible directions (the set F in (2)). This is frequently the case in control systems, in particular when the "bang-bang" type of control is used. In the terminology used by Wazewski the right-hand side of the differential inclusion is called orientor field, and (2) is called orientor condition.

Recall some definitions. Let I be a time interval ([t.sub.0], [t.sub.1]), [t.sub.0] called the initial time and [t.sub.1] the final time, [t.sub.0] < t, and let x be a point in the model state space X.

A trajectory of a DI over I with the initial condition [x.sub.0] is a function of time such that:

dx/dt [member of] F(x(t), t), x([t.sub.0]) = [x.sub.0], t [member of] I

The solution to a DI with initial condition Y([t.sub.0]) [subset] X is the union of graphs of all trajectories going out of each point of Y([t.sub.0]) (with initial conditions belonging to Y([t.sub.0])). The solution to the DI is called reachable set (RS) of the DI.

Note that, at least in this paper, the trajectories are not solutions to the DI, they are just trajectories. The solution to the DI is given by its reachable set. For more precise definitions see (14). The above definitions are simplified; we do not treat here with such terms as absolutely continuous functions, Hausdorff distance and similar, explained in (11).

Obviously, the model (1) is a special case of a DI, where F is a one point set for all t. Fig. 1 shows a possible reachable set for a differential inclusion with initial set A. We will always consider the time interval I = ([t.sub.0], [t.sub.1]). So, for a given DI, its reachable set depends only on A and will be denoted as RS(A). The time-section of the RS will be denoted in the similar way, with extra parameter representing the time instant.

[FIGURE 1 OMITTED]

So, The term RS(A, [t.sub.x]) means the intersection of RS(A) with the plane t = [t.sub.x]. Clearly A = RS(A, [t.sub.0]).

Example. Consider a second order system described by the following equations:

[dx.sub.1] / dt = [x.sub.2]

[dx.sub.2] / dt = [u.sub.1] - [u.sub.2]. [x.sub.2] - [x.sub.1]

where -1 < [u.sub.1] < 1 and 0.5 < [u.sub.2] < 1.5. The right-hand side of the second equation represents a set, parameterized by two parameters [u.sub.1] and [u.sub.2]. Fig. 2 shows the 3D image of the RS in coordinates [x.sub.1] (upwards), [x.sub.2] (to the right) and t. The RS was generated by the Differential Inclusion Solver (DIS), described in (12). The DIS algorithm is somewhat complicated. It calculates the trajectories that scan the boundary of the RS, using some concepts from the Optimal Control Theory. One could suppose that the RS can be obtained by a "random shooting", generating trajectories that correspond to selectors generated randomly. This is, however not the case. Such random shooting can provide very confusing results, detecting only a small region inside the RS (see (12-16) for more detail).

[FIGURE 2 OMITTED]

3. DYNAMIC SYSTEM AS A CATEGORY

In 1942-45, Samuel Eilenberg (17) and Saunders Mac Lane introduced categories, as part of their work in topology, especially algebraic topology (see also (18-20)). As the concepts of the theory of categories provide a high level of abstracting, the language of the theory may be useful while constructing models and examine their properties.

As for the other works that can be found in this and similar fields of Model Theory and Category Theory, the reader can consult the works of Serge P. Kovalyov (21-23), but these works are rather focused on applications in software development. An application in brain modelling can be found in Gomez and Sanz (24). However.

The problem discussed in this paper is mainly the time-inverse problem in models with uncertainty. The model is given in the form of a differential inclusion, but, as mentioned in the sequel, the categorical model description is valid for any other model (may be also discrete event), where a reachable set is defined.

Following Fokkinga (20) recall the some definitions.

A category is defined by its data and the axioms the data must satisfy. The data are the following.

1. A collection of things called objects. By default, A, B, C, ... vary over objects.

2. A collection of things called morphisms, sometimes called arrows.

By default, f, g, h,. ... , vary over morphisms.

3. A relation on morphisms and pairs of objects, called typing of the morphisms.

By default, the relation is denoted f: A [right arrow] B, for morphism f and objects A, B. In this case we also say that A [right arrow] B is the type of f, and that f is a morphism from A to B. Object A is called the source of f, and the object b is its target. In other words, src f = A and tgt f = B.

4. A binary partial operation on morphisms, called composition.

By default, f; g is the notation of the composition of morphisms f and g.

5. For each object A a distinguished morphism, called identity on A. By default, idA, or id when A is clear from the context, denotes the identity on object A.

The morphisms must satisfy the following axioms.

A3.1 f: A [right arrow] B and f: [A.sub.0] [right arrow] [B.sub.0] [??] A = [A.sub.0] and B = [B.sub.0] (unique-Type)

A3.2 f: A [right arrow] B and g: B [right arrow] C [??] f; g: A [right arrow] C (composition-Type)

A3.3 idA: A [right arrow] A (identity-type)

A3.4 ( f; g ); h = f; ( g; h ) (composition)

A3.5 id; f = f = f; id (identity)

Note that f: A [right arrow] A does not mean that f is an identity (it is an endomorphism). For example, if X is the space of reals, the function y(x) = [x.sup.3] maps X to itself, but it is not an identity. Also f: A [right arrow] B and g: A [right arrow] B does not mean that f = g.

Let A and B be categories; then a functor from A to B is: a mapping F that sends objects of A to objects of B, and morphisms of A to morphisms of B in such a way that

A3.6 F f: FA [right arrow] [.sub.B]FB whenever f: A [right arrow] [.sub.A]B

A3.7 [Fid.sub.A] = [id.sub.FA] for each object A in A

A3.8 F ( f; g ) = F f; F g

In this, as in some other articles (24) the operation of modelling is represented as a functor in the categorical language.

A useful concept in the category theory is dualism.

The dual of a term in the categorical language is defined by:

dual A = A for object term A

dual x = x for morphism variable x

dual(f: A [right arrow] B) = dual f: B [right arrow] A (note the swap of A and B)

dual(f; g) = dual g; dual f (note the swap of f and g)

dual(idA) = idA.

Clearly, dualising is its own inverse, that is, dual(dual t) = t for each term t.

For each definition expressed in the categorical language, of a concept or construction xxx, you obtain another concept, often called co-xxx if no better name suggests itself, by dualising each term in the definition (Fokkinga (20)). Also, for each equation f = g provable from the axioms of category theory (hence valid for all categories), the equation dual f = dual g is provable too. Thus dualisation cuts work in half, and gives each time two concepts or theorems for the price of one.

Now, consider the ODE model (1). To use the categorical language, let define the category object as a pair (x(t), t), where x( t) is the system state. Let suppose that a morphism exists between two objects (x([t.sub.a]), [t.sub.a]) and (x([t.sub.b]), [t.sub.b]) if and only if [t.sub.a] [t.sub.b]. The morphism g between the two objects can be defined as "solve the equation (1) over [[t.sub.a], [t.sub.b]] with the initial condition x([t.sub.a])". Note that this means that in the model (1) the time cannot go backwards. It is rather a philosophical question if the real world is reversible in this sense. The common believe is that it is not. Moreover, while in the model (1) we can integrate the equations backwards to restore the previous states, we will see that this is not so simple in the case of the model (2) (with uncertainty).

What is important that the morphism g may be defined as any other well defined state transition algorithm, not necessarily a differential equation. This may be some logical procedure with discrete state and discrete time. In other words, this categorical specification can also be applied to discrete event models.

4. THE INVERSE PROBLEM

The problem for an ODE model is: Given the final state of a dynamic system, what was the initial state that originated it?

For the ODE model (1) we can simply go backwards in time, from [t.sub.1] to [t.sub.0]. This means that we resolve the equation:

dx/ds = -f (x(s),s) (3)

with initial condition x([t.sub.1]), over [J=[t.sub.1], [t.sub.0]], being ds = -dt. In this case the inverse problem is trivial. In the categorical language, model (3) is the dual of model (1) (check it using the definition of the dual category).

Now consider a similar inverse problem for the model (2) (a dynamic system with uncertainty): Given the final reachable set, what was the initial set that originated it?

In this case we cannot just go backwards in time. Indeed, consider, for example, the inclusion:

dx/ds [member of] [-1,1], x [member of] R

Starting from the initial point x = 0, t = 0 and calculating the RS at t = 1 we get RS(0, 1) = [-1, 1]. Now, if we start from t = 1 and from the final set [-1, 1], and go backwards (inverting the sign of the derivative), we get the set (interval) [-2, 2] instead of the original set (point) (0, 0). It is clear that the RS must grow, because the uncertainty remains the same for the inverse problem. Fig. 3 illustrates this in 2-dimensional case. The reachable set obtained by inverting the sign of the derivatives (going backwards in time) is denoted as BRS.

[FIGURE 3 OMITTED]

In the general case of the differential inclusion (2) over a fixed time interval, the solution to the inverse problem should result in the initial set A (see Fig. 3). Denote this solution by IRS. So, it should be IRS(RS(A, [t.sub.1]), [t.sub.0]) = A. In other words, we must express the set A in terms of the reachable set at t = [t.sub.1]. The second parameter of IRS (as well as of BRS) is the target time instant.

Corollary 1. The IRS(B, [t.sub.0] ), denoted as E in the sequel, is the intersection of all the BRSs going out of the points of B as initial sets (at [t.sub.1], backwards in time).

To prove, observe that E is the set of points, from which at least one point inside the RS(A, [t.sub.1]) is reachable and no point outside RS(A, [t.sub.1]) is reachable. Consequently, it is the complement of the BRS set of D = RS [(A, [t.sub.1]).sup.C] (C means complement). But the BRS of D is the union of the BRSs of all points of D, namely:

BRS(D, [t.sub.1]) = [union] [{BRS(z, [t.sub.1]): z [??] RS( A, [t.sub.1])} = [union] {BRS(z, [t.sub.1]): z [member of] RS( A, [t.sub.1])}.sup.C]

So,

BRS(D, [t.sub.1]) = [([intersection] {BRS(z, [t.sub.1]): z [member of] RS(A, [t.sub.1])}).sup.C],

because the union of complements is equal to the complement of the intersection.

But IRS(B, [t.sub.0]) = E = BRS[(D, [t.sub.1]).sup.C], so:

IRS(B, [t.sub.0]) = [intersection] {BRS([z,t.sub.1]): z [member of] RS(A, [t.sub.1])}

Let M be the categorical representation of the model (2), the objects of M being pairs (RS(A, t), t). Here A is a set on the plane t = [t.sub.0]. A morphism g between two objects (RS(A, [t.sub.0]), [t.sub.0]) and (RS(A, [t.sub.1]), [t.sub.1]) exists if [t.sub.0] [less than or equal to] [t.sub.1]. The morphism maps the object (A, [t.sub.0]) into (RS(A, [t.sub.1]), [t.sub.1]). In other words, the morphism is defined as "find the reachable set RS(A, [t.sub.1]), given the initial condition (A, [t.sub.0])".

The dual category (or dual model) of M, denoted as [M.sup.op] can be constructed as follows: Object of [M.sup.op] = object of M, and morphism [g.sup.op] from (B, [t.sub.1]) to (A, [t.sub.0]) (note the swap of [t.sub.0] and [t.sub.1]) is an operation that converts (B, [t.sub.1]) into IRS(B, [t.sub.0]), where [t.sub.0] [less than or equal to] [t.sub.1] (see Fig. 3). The IRS is defined by the corollary 1.

Observe that in the proof of the corollary 1 we never used any particular property of differential inclusions. We only use the notion of reachable states and reachable sets. These concepts, as well as the construction of [M.sup.op] do not even require the model M being continuous. So, the time can also be a discrete variable, and the state space can also be discrete. This means, that all we are talking about is applicable to discrete event models as well. So, as an example, consider an electronic logical system where the erroneous states are grouped into a set in the system state space. The problem is, given some uncertainty in the switching operations, to determine the set of past system states that originated the failures.

5. CONCLUSIONS

We used a differential inclusion (DI) model to treat the dynamic uncertainty. Deterministic ODE models can be treated as special cases of the corresponding DI models (with zero uncertainty). While ODE models are reversible (can be integrated backwards in time), the DI models are not. We gave a possible generalization of the model in categorical language, which is much more abstract and can work for discrete events models also, though the categorical specification of both kinds of models is the same. Using the concept of dualism, we can construct the dual category in the way shown above, to solve the inverse problem. In the case of models with uncertainty (that always exists in the real world) the inverse problem cannot be solved by backward integration (in continuous case) of the model equations. The proposed procedure for the inverse problem (dualising the original morphisms) is not very complicated, but may be difficult while looking for numerical implementations.

DOI:10.2507/IJSIMM10(1)4.180

REFERENCES

(1.) Bargiela, A.; Hainsworth, G. (1989). Pressure and flow uncertainty in water systems, ASCE Journal of Water Resources Planning and Management, Vol. 115, No. 2, 212-229

(2.) Bargiela, A. (1993). Managing uncertainty in operational control of water distribution systems, Integrated Computer Applications, Vol. 2, (Ed. Coulbeck, B.), Wiley, ISBN 0 471 94232 2, 353-363

(3.) Marchaud, A. (1934). Sur les champs de demi-cones et les equations differielles du premier ordre, Bulletin de la Societe mathematique de France, Vol. 62

(4.) Zaremba, S. K. (1936). Sur les equations au paratingent, Bulletin des Sciences Mathematiques, Vol. 60

(5.) Wazewski, T. (1961). Sur une condition equivalente a l'equation au contingent, Bulletin de l'Academie Polonaise des Science--Serie des Sciences Mathematiques, Astronomiques et Physiques, Vol. 9, No. 12, Warszawa

(6.) Wazewski, T. (1962). Sur une genralisation de la notion des solutions d'une equation au contingent, Bulletin de l'Academie Polonaise des Science--Serie des Sciences Mathematiques, Astronomiques et Physiques, Vol. 10, No. 1, Warszawa

(7.) Wazewski, T. (1962). Sur les systemes de commande non lineaires dont le contredomaine de commande n'est pas forcement convexe, Bulletin de l'Academie Polonaise des Science--Serie des Sciences Mathematiques, Astronomiques et Physiques, Vol. 10, No. 1, Warszawa

(8.) Turowicz, A. (1962). Sur les trajectoires et quasitrajectoires des systemes de commande nonlineaires, Bulletin de l'Academie Polonaise des Science--Serie des Sciences Mathematiques, Astronomiques et Physiques, Vol. 10, No. 10, Warszawa

(9.) Turowicz, A. (1963). Sur les zones d'emision des trajectoires et des quasitrajectoires des systemes de commande nonlineaires, Bulletin de l'Academie Polonaise des Science--Serie des Sciences Mathematiques, Astronomiques et Physiques, Vol. 11, No. 2, Warszawa

(10.) Plis, A. (1961). Remark on measurable set-valued functions, Bulletin de l'Academie Polonaise des Science--Serie des Sciences Mathematiques, Astronomiques et Physiques, Vol. 9, No. 12, Warszawa

(11.) Hausdorff, F. (1919). Dimension und au[beta]res Ma[beta], Mathematische Annalen, Vol. 79, No. 1-2, 157-179

(12.) Raczynski, S. (2002). Differential Inclusion Solver, International Conference on Grand Challenges for Modeling and Simulation (The Society for Computer Simulation Int.), San Antonio, TX, USA

(13.) Raczynski, S. (2003). Are discrete models valid?, VIth Conference on Computer Simulation and Industry Applications (McLeod Institute for Simulation Sciences), Tijuana, BC, Mexico

(14.) Raczynski, S. (1996). Differential Inclusions in System Simulation, Transaction of the Society for Computer Simulation, Vol. 13, No. 1, 47-54

(15.) Raczynski, S. (2000). Alternative mathematical tools for modeling and simulation: Metric space of models, Uncertainty, Differential Inclusions and Semi-discrete Events, Proceeedings of the European Simulation Symposium ESS2000, Hamburg, Germany

(16.) Raczynski, S. (2006). Modeling and Simulation: The Computer Science of Illusion, Wiley, England

(17.) Eilenberg, S. (1974). Automata, Languages, and Machines (2 vols.), Academic Press, New York

(18.) Asperti, A.; Longo, G. (1991). Categories, Types and Structures, MIT Press, ISBN 0262011255, ftp://ftp.di.ens.fr/pub/users/longo/CategTypesStructures/book.pdf

(19.) Fokkinga, M. M. (1992). Law and Order in Algorithmics, PhD thesis, University of Twente, Dept Comp Sc, Enschede, The Netherlands

(20.) Fokkinga, M. M. A Gentle Introduction to Category Theory, from http://wwwhome.cs.utwente.nl/~fokkinga/mmf92b.pdf

(21.) Kovalyov, S. P. (2010). Modeling Aspects by Category Theory, http://www.eecs.ucf.edu/FOAL/papers-2010/Kovalyov.pdf

(22.) Kovalyov, S. P. (2002). Architecture of Time of Distributed Information Systems, J. Computational Technologies, Vol. 7, No. 6, 38-53 (In Russian.)

(23.) Kovalyov, S. P. (2008). Domain Engineering of Distributed Measurement Systems. Optoelectronics, Instrumentation and Data Processing, Vol. 44, No. 2, 125-130

(24.) Gomez, J.; Sanz, R. (2009). Modeling cognitive systems with Category Theory Subtitle: Towards rigor in cognitive sciences, Autonomous Systems Laboratory, Universidad Tecnica de Madrid (Spain), Reference: A-2009-014 v 1.0, http://tierra.aslab.upm.es/documents/controlled/ASLABA-2009-023.pdf

Raczynski, S.

Universidad Panamericana, Escuela de Ingenieria, 498 Augusto Rodin, 03920 Mexico DF, Mexico

E-Mail: stanracz@stanr.com
COPYRIGHT 2011 DAAAM International Vienna
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Raczynski, S.
Publication:International Journal of Simulation Modelling
Article Type:Report
Geographic Code:1MEX
Date:Mar 1, 2011
Words:3849
Previous Article:Disk array simulation model development.
Next Article:Reconfigurable modelling with deadlock avoidance for the clinical pathway based on MCPN-CS.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |