Max-Plus (A, B)-Invariant Spaces and Control of Timed Discrete-Event Systems

Ricardo David KatzIEEE Trans. Automatic Control 2007 · OpenReview

TL;DR

This paper extends the concept of (A,B)-invariant subspaces, crucial for control theory in standard linear systems, to the max-plus algebra framework. This extension allows for the analysis and control of timed discrete-event systems, such as transportation networks, by providing tools to compute maximal invariant spaces and design state feedbacks.

What Problem Does This Paper Address?

Traditional control theory heavily relies on the geometric approach, particularly the concept of (A,B)-invariant subspaces, to solve complex control problems like disturbance decoupling. However, many real-world systems, such as manufacturing processes, computer networks, and transportation systems, exhibit discrete-event dynamics where events occur at specific times. These systems are often modeled using max-plus algebra, which naturally handles synchronization and timing constraints. The challenge addressed by this paper is to bridge the gap between the established geometric control theory and the max-plus algebraic framework, enabling the application of powerful invariant subspace concepts to these timed discrete-event systems.

Methods

The core of this paper is the generalization of the (A,B)-invariant subspace concept to semimodules over the max-plus semiring. This involves:

  • Defining (A,B)-invariant semimodules: Adapting the definition of (A,B)-invariance to the max-plus algebraic setting, where states and inputs are vectors over the max-plus semiring.
  • Generalizing the fixed-point algorithm: The paper adapts the classical Wonham fixed-point algorithm, used to compute maximal (A,B)-invariant subspaces, to the max-plus semiring. This involves defining a map $\phi(X) = X \cap A^{-1}(X \oplus B)$ and iterating it to find the maximal invariant semimodule.
  • Introducing the concept of "volume": To analyze the convergence of the fixed-point algorithm, a notion of "volume" for semimodules in the max-plus setting is introduced. This volume is related to the number of elements in a semimodule that satisfy a specific "zero sum" condition.
  • Developing conditions for stabilization: The paper provides sufficient conditions for the convergence of the fixed-point algorithm in a finite number of steps, particularly for semimodules with finite volume.
  • Addressing algebraic invariance and feedback: The paper extends the concept of algebraic (A,B)-invariance and proposes methods to determine the existence of linear state feedbacks that maintain this invariance. This involves solving max-plus linear systems of equations.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and uses illustrative examples rather than empirical datasets.

Key Insights and Ideas

  • Max-plus algebra as a powerful tool for timed systems: The paper reinforces the utility of max-plus algebra for modeling and controlling systems with synchronization and timing constraints, extending established control theory concepts to this domain.
  • Challenges in max-plus invariance: The generalization of (A,B)-invariance to max-plus algebra is not straightforward and presents difficulties similar to those encountered when extending to systems over rings (as opposed to fields). Notably, the convergence of the fixed-point algorithm is not guaranteed in a finite number of steps, unlike in the field case.
  • The role of "volume" in convergence: The introduction of the "volume" concept for semimodules is a key theoretical tool that helps establish conditions for the finite convergence of the iterative algorithm.
  • Distinction between geometric and algebraic invariance: For max-plus systems, geometric (A,B)-invariance does not necessarily imply algebraic (A,B)-invariance, a departure from the field case. This highlights the need for specific methods to address feedback synthesis.
  • Practical applicability to transportation networks: The paper demonstrates the practical relevance of its theoretical framework by applying it to the control of transportation networks, showing how to determine feasible timetables that satisfy desired performance criteria.

Key Results

  • The paper successfully extends the concept of (A,B)-invariant subspaces to the max-plus semiring, defining (geometrically) (A,B)-invariant semimodules.
  • A generalized fixed-point algorithm is presented for computing the maximal (geometrically) (A,B)-invariant semimodule contained within a given semimodule.
  • Sufficient conditions for the finite convergence of this algorithm are established, particularly for semimodules with finite volume.
  • The paper discusses the existence and computation of linear state feedbacks for achieving algebraic (A,B)-invariance.
  • An application to transportation networks demonstrates how the developed methods can be used to analyze and synthesize timetables that satisfy specific delay and connection constraints.

Limitations and Future Work

  • Convergence guarantee: While conditions for finite convergence of the fixed-point algorithm are provided, the algorithm is not guaranteed to converge in a finite number of steps for all semimodules. The paper notes that this is a known difficulty when working with rings and semirings.
  • Computational complexity: The paper mentions that some algorithms for solving max-plus linear systems, which are used in determining algebraic invariance, can have a priori doubly exponential complexity, although improvements are being worked on.
  • Open problem: The paper poses an open question: whether the maximal geometrically (A,B)-invariant semimodule $K^*$ is always equal to $X_\omega$ (the intersection of the sequence of semimodules).
  • Future work: The authors indicate ongoing work on improving the efficiency of algorithms for solving max-plus linear systems and further exploring the properties of max-plus invariant spaces. They also suggest that the developed framework can be applied to a wider range of control problems in discrete-event systems.

Summary updated

Abstract

The concept of (A,B)-invariant subspace (or controlled invariant) of a linear dynamical system is extended to linear systems over the max-plus semiring. Although this extension presents several difficulties, which are similar to those encountered in the same kind of extension to linear dynamical systems over rings, it appears capable of providing solutions to many control problems like in the cases of linear systems over fields or rings. Sufficient conditions are given for computing the maximal (A,B)-invariant subspace contained in a given space and the existence of linear state feedbacks is discussed. An application to the study of transportation networks which evolve according to a timetable is considered
BibTeX
@article{katz2007max,
  author = {Ricardo David Katz},
  title = {{Max-Plus (A, B)-Invariant Spaces and Control of Timed Discrete-Event Systems}},
  journal = {IEEE Trans. Automatic Control},
  year = {2007},
  url = {https://openreview.net/forum?id=zv0mXMAlwZ},
}
Figure