A unified approach to controllability analysis for hybrid control systems

A unified approach is proposed for controllability analysis of a class of hybrid control systems, employing the controllability concept defined in [M. Tittus, B. Egardt, Control design for integrator hybrid systems, IEEE Transactions on Automatic Control 43 (4) (1998) 491–500; J.H. van Schuppen, A Sufficient Condition for Controllability of a Class of Hybrid Systems, in: LNCS, vol. 1386, Springer, 1998, pp. 374–383; Z. Yang, M. Verhaegen, Y.J. Wang, Z.J. Chen, Hybrid controllability of linear switched systems, in: Proceedings of 37th Control and Decision Conference, Tampa, FL, USA, December 1998, pp. 3920–3925]. The unified approach comprises global reachability analysis at the discrete event system level, local reachability analysis at the continuous-time dynamical system level and a merging of the results of these two methods using a discrete-path search algorithm. The proposed method is demonstrated useful for controllability analysis of complex hybrid control systems. The method is illustrated by analyzing the controllability of a linear switched system.     

Attack on Han et al.’s ID-based confirmer (undeniable) signature at ACM-EC’03

In ACM conference on electronic commerce (EC’03), Han et al. [Identity-based confirmer signatures from pairings over elliptic curves, in: Proceedings of ACM Conference on Electronic Commerce Citation 2003, San Diego, CA, USA, June 09–12, 2003, pp. 262–263] proposed an ID-based confirmer signature scheme using pairings (the scheme is in fact an ID-based undeniable signature scheme). In this paper, we show that this signature scheme is not secure and the signer can deny any signature, even if it is a valid signature, and any one can forge a valid confirmer signature of a signer with identity ID on an arbitrary message and confirm this signature to the verifier.     

Solution of a Differential Game Formulation of Military Air Operations by the Method of Characteristics

In this paper, we describe a zero-sum differential game formulation for the control of military air operations. The model consists of a system of nonlinear ordinary differential equations for the dynamics of the operations and a suitably chosen quadratic payoff function. The control variables are the engagement intensities and velocities, and there are constraints on the controls. The method of characteristics (based on the Pontryagin maximum principle) is used to solve the associated Hamilton-Jacobi equation. In this nonlinear formulation, the Hamiltonian can be optimized explicity with respect to the controls. Numerical simulations study the enforcement of constraints (a) by means of penalties in the payoff function or (b) explicitly. The numerical results show robustness with respect to various parameters.Effort sponsored by the Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory, Air Force Material Command, USAF, under Agreement F30602-99-2-0551. A shorter version of this paper appeared in the Proceedings of the 2001 American Control Conference, pp. 168--175, 2001.     

Robustness of minimax controllers to nonlinear perturbations

We study the robustness of minimax controllers, originally designed for nominal linear or nonlinear systems, to unknown static nonlinear perturbations in the state dynamics, measurement equation, and performance index. When the nominal system is linear, we consider both perfect state measurements and general imperfect state measurements; in the case of nominally nonlinear systems, we consider perfect state measurements only. Using a differential game theoretic approach, we show for the former class that, as the perturbation parameter (say, >0) approaches zero, the optimal disturbance attenuation level for the overall system converges to the optimal disturbance attenuation level for the nominal system if the nonlinear structural uncertainties satisfy certain prescribed growth conditions. We also show that anH -controller, designed based on a chosen performance level for the nominal linear system, achieves the same performance level when the parameter is smaller than a computable threshold, except for the finite-horizon imperfect state measurements case. For that case, we show that the design of the nominal controller must be based on a decreased confidence level of the initial data, and a controller thus designed again achieves a desired performance level in the face of nonlinear perturbations satisfying a computable norm bound. In the case of nominally nonlinear systems, and assuming that the nominal system is solvable, we obtain sufficient conditions such that the nominal controller achieves a desired performance in the face of perturbations satisfying computable norm bounds. In this way, we provide a characterization of the class of uncertainties that are tolerable for a controller designed based on the nominal system. The paper also presents two numerical examples; in one of these, the nominal system is linear; in the other one, it is nonlinear.This research was supported in part by the US Department of Energy, Grant DE-FG-02-88-ER-13939 and in part by the National Science Foundation, Grant ECS-91-13153.An abridged version was presented at the 32nd IEEE Conference on Decision and Control, San Antonio, Texas, December 15–17, 1993, and it appeared in the Conference Proceedings.     

Topology of rearrangements of non-smoothness sets of minimum functions in variational problems

Control Problems Institute. Translated from Funktsional'nyi Analiz i Ego Prilozheniya, Vol. 24, No. 3, pp. 62–63, July–September, 1990.     

Ashby relation and control of the qualitative behavior of dynamical systems

Institute of Control Problems, Moscow. Translated from Funktsional'nyi Analiz i Ego Prilozheniya, Vol. 24, No. 2, pp. 93–94, April–June, 1990.     

Fast reconstruction of Delaunay triangulations

We present a new linear time algorithm to compute a good order for the point set of a Delaunay triangulation in the plane. Such a good order makes reconstruction in linear time with a simple algorithm possible. Similarly to the algorithm of Snoeyink and van Kreveld [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471], our algorithm constructs such orders in O(logn) phases by repeatedly removing a constant fraction of vertices from the current triangulation. Compared to [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471] we improve the guarantee on the number of removed vertices in each such phase. If we restrict the degree of the points (at the time they are removed) to 6, our algorithm removes at least 1/3 of the points while the algorithm from [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471] gives a guarantee of 1/10. We achieve this improvement by removing the points sequentially using a breadth first search (BFS) based procedure that—in contrast to [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471]—does not (necessarily) remove an independent set.

Besides speeding up the algorithm, removing more points in a single phase has the advantage that two consecutive points in the computed order are usually closer to each other. For this reason, we believe that our approach is better suited for vertex coordinate compression.

We implemented prototypes of both algorithms and compared their running time on point sets uniformly distributed in the unit cube. Our algorithm is slightly faster. To compare the vertex coordinate compression capabilities of both algorithms we round the resulting sequences of vertex coordinates to 16-bit integers and compress them with a simple variable length code. Our algorithm achieves about 14% better vertex data compression than the algorithm from [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471].     

Book Reviews

Methods of Intermediate Problems for Eigenvalues: Theory and Ramifications, by Alexander Weinstein and William Stenger. Academic Press, 1971. ($16.00)

Combinatorics, Proceedings of the British Combinatorial Conference 1973, Edited by T.P. McDnough and V.C. Mavron, London Mathematical Society Lecture Note Series 13, Cambridge University Press, London, New York, 1974. 204pp.($9.95)     

An averaging principle for a class of systems of differential equations with deviating argument

A theorem concerning the asymptotic stability of solutions of systems with deviating argument is formulated under the assumption that the averaged system has quasistatic solutions.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 42, No. 10, pp. 1363–1369, October, 1990.     

A Higher-Dimensional Version of the Brody Reparametrization Lemma

We prove a generalization of the Brody reparametrization lemma.__________Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 56, No. 10, pp. 1369 – 1377, October, 2004.     

Flexible composites, strength, deformation, and fracture processes. 1. Reinforcement structures and tensile strength

Fiber-reinforced flexible composites are extensively used for different kinds of applications, for example, tubes, drive belts, tires, and coated fabrics. Typical for these materials are matrix materials allowing large strain deformation and reinforcement structures allowing bending. Apart from the tensile strength and limited bending stiffness, damage resistance and ductile-brittle transition characteristics are discussed. The tensile strength usually follows the rule of mixture. The mode of fracture and damage resistance, however, strongly depend on penetration of the matrix into the fiber bundles, textile structure, and internal friction. Models for the work of fracture and the ductile-to-brittle fracture transition are discussed.Presented at the 10th International Conference on the Mechanics of Composite Materials (Riga, April 20–23, 1998).Published in Mekhanika Kompozitnykh Materialov, Vol. 34, No. 6, pp. 747–760, November–December, 1998.     

Conditions necessary for optimality in the convex Bolza problem with phase constraints of a general form

Institute of Control Problems. Translated from Funktsional'nyi Analiz i Ego Prilozheniya, Vol. 24, No. 1, pp. 92–93, January–March, 1990.     

Fuzzy stability and synchronization of hyperchaos systems

This paper studies stability and synchronization of hyperchaos systems via a fuzzy-model-based control design methodology. First, we utilize a Takagi–Sugeno fuzzy model to represent a hyperchaos system. Second, we design fuzzy-model-based controllers for stability and synchronization of the system, based on so-called “parallel distributed compensation (PDC)”. Third, we reduce a question of stabilizing and synchronizing hyperchaos systems to linear matrix inequalities (LMI) so that convex programming techniques can solve these LMIs efficiently. Finally, the generalized Lorenz hyperchaos system is employed to illustrate the effectiveness of our designing controller.     

Representation of consistent recursive rules

This paper develops the recursive model for connective rules (as proposed in V. Cutello, E. Molina, J. Montero, Associativeness versus recursiveness, in: Proceedings of the 26th IEEE International Symposium on Multiple-valued Logic, Santiago de Compostela, Spain, 29–31 May, 1996, pp. 154–159; V. Cutello, E. Molina, J. Montero, Binary operators and connective rules, in: M.H. Smith, M.A. Lee, J. Keller, J. Yen (Eds.), Proceedings of NAFIPS 96, North American Fuzzy Information Processing Society, IEEE Press, Piscataway, NJ, 1996, pp. 46–49), where a particular solution in the Ordered Weighted Averaging (OWA) context (see V. Cutello, J. Montero, Recursive families of OWA operators, in: P.P. Bonissone (Ed.), Proceedings of the Third IEEE Conference on Fuzzy Systems, IEEE Press, Piscataway, NJ, 1994, pp. 1137–1141; V. Cutello, J. Montero, Recursive connective rules, International Journal of Intelligent Systems, to appear) was translated into a more general framework. In this paper, some families of solutions for the key recursive equation are obtained, based upon the general associativity equation as solved by K. Mak (Coherent continuous systems and the generalized functional equation of associativity, Mathematics of Operations Research 12 (1987) 597–625). A context for the representation of families of binary connectives is given, allowing the characterization of key families of connective rules.     

Conservative perturbations of infinite-dimensional linear systems depending on a vector parameter

Control Problems Institute, Academy of Sciences of the USSR. Translated from Funktsional'nyi Analiz i Ego Prilozheniya, Vol. 23, No. 1, pp. 72–73, January–March, 1989.     

Book reviews

Desch, W.; F. Kappel; K. Kunisch: Estimation and Control of Distributed Parameter Systems. International Series of Numerical Mathematics. Vol. 100. Birkhauser Verlag AG Base1 1991, 396pp., DM 138, ISBN 3-7643-2676-X.

Klein, D. J.; M. RandiC: Mathematical Chemistry. Proceedings of the 3rd International Conference on Mathematical Chemistry, Galveston (USA) March 1989. VCH Weinheim 1990, 416pp., 59 fig., DM265,ISBN 3-527-28240-0.

Mezey, P. C.: Mathematical Modeling in Chemistry. VCH Weinheim 1991,416 pp., DM 265,ISBN 3-527-28292-0.

Lewandowski, A.; V. Volkovich (eds.): Multiobjective Problems of Mathematical Programming. Proceedings Yalta, USSR 1988. Lecture Notes in Economics and Mathematical Systems, Vol. 351. Springer-Verlag Berlin, Heidelberg, New York, London 1991, VII, 314 pp., Softcover, DM 61,- ISBN 3-540-532-6

Guddat, J.; F. Guerra Vasquez; H. Th. Jongen: Parametric Optimization: Singularities, Pathfollowing and Jumps. John Wiley & Sons Ltd. Baffins Lane, Chichester 1990, 216 pp., $80.40, ISBN 0-471-92807-0.

van der Geer, G.; F. Oort; J. Steenbrink (eds.): Arithmetic Algebraic Geometry. Progress in Mathematics, Vol. 89. Birkhauser Verlag Basel, Boston, Berlin l991, 446 pp., SFr. 78.-, ISBN 3-7643-3513-0.

Solomon, A.: PC Viruses-Detection, Analysis and Cure. Springer Verlag Berlin, Heidelberg, New York, Paris, London 1991, IX, 288 pp., DM 74,ISBN 3-540-19691-9.     

An optimal randomized algorithm for d-variate zonoid depth

A randomized linear expected-time algorithm for computing the zonoid depth [R. Dyckerhoff, G. Koshevoy, K. Mosler, Zonoid data depth: Theory and computation, in: A. Prat (Ed.), COMPSTAT 1996—Proceedings in Computational Statistics, Physica-Verlag, Heidelberg, 1996, pp. 235–240; K. Mosler, Multivariate Dispersion, Central Regions and Depth. The Lift Zonoid Approach, Lecture Notes in Statistics, vol. 165, Springer-Verlag, New York, 2002] of a point with respect to a fixed dimensional point set is presented.     

Superfast algorithms for Cauchy-like matrix computations and extensions

An effective algorithm of [M. Morf, Ph.D. Thesis, Department of Electrical Engineering, Stanford University, Stanford, CA, 1974; in: Proceedings of the IEEE International Conference on ASSP, IEEE Computer Society Press, Silver Spring, MD, 1980, pp. 954–959; R.R. Bitmead and B.D.O. Anderson, Linear Algebra Appl. 34 (1980) 103–116] computes the solution to a strongly nonsingular Toeplitz or Toeplitz-like linear system , a short displacement generator for the inverse T⁻¹ of T, and det T. We extend this algorithm to the similar computations with n×n Cauchy and Cauchy-like matrices. Recursive triangular factorization of such a matrix can be computed by our algorithm at the cost of executing O(nr²log³ n) arithmetic operations, where r is the scaling rank of the input Cauchy-like matrix C (r=1 if C is a Cauchy matrix). Consequently, the same cost bound applies to the computation of the determinant of C, a short scaling generator of C⁻¹, and the solution to a nonsingular linear system of n equations with such a matrix C. (Our algorithm does not use the reduction to Toeplitz-like computations.) We also relax the assumptions of strong nonsingularity and even nonsingularity of the input not only for the computations in the field of complex or real numbers, but even, where the algorithm runs in an arbitrary field. We achieve this by using randomization, and we also show a certain improvement of the respective algorithm by Kaltofen for Toeplitz-like computations in an arbitrary field. Our subject has close correlation to rational tangential (matrix) interpolation under passivity condition (e.g., to Nevanlinna–Pick tangential interpolation problems) and has further impact on the decoding of algebraic codes.     

A capacity scaling algorithm for M-convex submodular flow

This paper presents a faster algorithm for the M-convex submodular flow problem, which is a generalization of the minimum-cost flow problem with an M-convex cost function for the flow-boundary, where an M-convex function is a nonlinear nonseparable discrete convex function on integer points. The algorithm extends the capacity scaling approach for the submodular flow problem by Fleischer, Iwata and McCormick (2002) with the aid of a novel technique of changing the potential by solving maximum submodular flow problems.Mathematics Subject Classification (1991): 90C27A preliminary version of this paper has appeared in Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization (IPCO X), LNCS 3064, Springer-Verlag, 2004, pp. 352–367.