# Kleene Algebra to Compute Invariant Sets of Dynamical Systems
###### Abstract  
In this paper, we show that a basic fixed point method used to enclose the greatest fixed point in a Kleene algebra will allow us to compute inner and outer approximations of invariant-based sets for continuous-time nonlinear dynamical systems. Our contribution is to provide the definitions and theorems that will allow us to make the link between the theory of invariant sets and the Kleene algebra. This link has never be done before and will allow us to compute rigorously sets that can be defined as a combination of positive invariant sets. Some illustrating examples show the nice properties of the approach. invariant sets; Kleene algebra; nonlinear dynamical systems; path planning +
Footnote †: journal: _Algorithms_  
0000-0001-5000-0000-0000-0000-0000-0000-0000-00000-0000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-000000-00000-00000-00  
The set of all positive invariant sets is a complete lattice; i.e., the union and the intersection of two positive invariant sets is positive invariant. A consequence is that given a set \(\mathbb{A}\), the notion of the _greatest positive invariant set_ contained in \(\mathbb{X}\) and _smallest positive invariant set_ enclosing \(\mathbb{A}\) can be defined. For instance, the greatest positive invariant set for (1) included in \(\mathbb{A}\) is given by  
\[\mathrm{Inv}^{+}(\boldsymbol{\gamma},\mathbb{A})=\Big{\{}\mathbf{a}|\forall t \geq 0,\boldsymbol{\varphi}_{\boldsymbol{\gamma}}(t,\mathbf{a})\in\mathbb{A} \Big{\}}. \tag{3}\]  
Methods exist to characterize positive invariant sets for specific cases such as for instance when \(\boldsymbol{\gamma}\) is linear [11; 12; 13] or discrete time [14]. Outer approximation can be computed by providing a model for approximation [15] or support functions [16]. Moreover, most approximations correspond to convex sets such as ellipsoids, zonotopes [17], or polytopes. These linear-based approaches can be extended to hybrid linear systems [18; 19; 20]. For continuous-time nonlinear systems, computing invariant sets is much more difficult, and different types of approaches can be extracted from the literature. * The first approach is based on sampling. It has been used for instance by [PERSON] [21] to rigorously compute viability kernel, which is a specific type of controlled invariant set. [PERSON] and [PERSON] [22] also used a sampling-based method for stability verification of both continuous and discrete-time nonlinear systems. To get guaranteed results, an interval integration is often needed (see e.g., [23; 24; 25]). * The second approach is based on Lyapunov theory [3; 26] and is convenient for proving asymptotic stability of problems with an infinite time horizon. The principle is to find a parameter vector \(\mathbf{p}\) or a Lyapunov-like function \(V(\mathbf{p},\mathbf{x})\) such that the set \[\{\mathbf{x}|V(\mathbf{p},\mathbf{x})=0\text{ and }\dot{V}(\mathbf{p}, \mathbf{x})\geq 0\}\] is empty. In such a case, the set \(\mathbb{S}(\mathbf{p})=\{\mathbf{x}|V(\mathbf{p},\mathbf{x})\leq 0\}\) defines a positive invariant set. The function that is generally chosen for \(V(\mathbf{p},\mathbf{x})\) is polynomial in the \(x_{i}\)'s and linear in the \(p_{i}\)'s. When \(\boldsymbol{\gamma}\) is polynomial, this choice for \(V(\mathbf{p},\mathbf{x})\) makes it possible to use LMI/SOS/interval resolution techniques, which can be efficient when a low-dimensional approximation exists. This approach relies on assumptions such as the knowledge of an equilibrium point [27] or the polynomial property of the dynamics of the system [28], which is not always realistic. * The third approach is based is based on _occupation measures_, which are adapted to a finite time horizon [27]. Now, it can also consider problems with infinite time horizon at the price of technical difficulties [29]. * The fourth approach is based a polygonal decomposition of the state space [30; 31] and corresponds to the approach we will consider in the paper.