Lie symmetries for guaranteed integration
In the paper Lie symmetries applied to interval integration (download preprint), a new approach has been proposed for improving significantly existing guaranteed integration methods for state equations under the form \(\dot{\mathbf{x}}=\mathbf{f}(\mathbf{x})\), with uncertain initial conditions, when symmetries can be found in the vector field of \(\mathbf{f}\).
First, a tube is computed for enclosing the solution of the differential equation assuming that the initial state is known. Then, using Lie symmetries, the tube is inflated in order to contain the uncertainty associated with the initial state.
The method is shown to be efficient on examples coming from reachability analysis and robotics.
Method
Given a box \(\left[\mathbf{x}_0\right]\) containing the initial state \(\mathbf{x}_{0}\), the approach aims at characterizing the set of all feasible trajectories of the system. More precisely, if \(\boldsymbol{\Phi}_{t}\) is the flow associated to \(\mathbf{f}\), then the guaranteed integration consists in computing the sets \(\mathbb{X}_{t}=\boldsymbol{\Phi}_{-t}^{-1}([\mathbf{x}_{0}])\).
To get the set \(\mathbb{X}_{t_{i}}\) of all feasible states at time \(t_{i}\), the following method is applied:
Step 1. Define a reference \(\mathbf{a}(\cdot)\) and enclose it in a thin tube \([\mathbf{a}](\cdot)\). The initial vector \(\mathbf{a}_{0}\) is exactly known. In order to generate a precise tube \([\mathbf{a}](\cdot)\) for \(\mathbf{a}(\cdot)\), one can use the CAPD library, or the CtcLohner algorithm.
Step 2. Find a Lie group of symmetries \(G_{\mathbf{p}}\) and give an expression for the transport function \(\mathbf{h}(\mathbf{x},\mathbf{a})\).
Step 3. Solve the resulting set inversion problem related to \(\boldsymbol{\Phi}_{-t}^{-1}\) with SIVIA.
This method is illustrated on four examples. For each of these, the set \(\underset{t\in\mathbb{T}}{\bigcup}\mathbb{X}_{t} = \underset{t\in\mathbb{T}}{\bigcup}\boldsymbol{\Phi}_{-t}^{-1}([\mathbf{x}_{0}])\) is computed, where \(\boldsymbol{\Phi}_{t}(\mathbf{x})=\mathbf{g}{}_{\mathbf{h}\left(\mathbf{x},\mathbf{a}_{0}\right)}\circ\mathbf{a}(t)\), and where \(\mathbb{T}\) is either
a discrete set \(\mathbb{T}=\{1,\dots,m\}\), which allows us to draw different non-overlapping sets \(\mathbb{X}_{t_{i}}\) on the same picture;
an interval \(\mathbb{T}=[0,t_{\max}]\), in order to approximate forward reach sets.
Note that the unions of sets, as well as other set-theoretical operators such as the projection, can easily be done using separator algebra.
More details about this method can be found in the related paper (download preprint) and in Julien Damers’s thesis.
Test-case 1
We consider the system:
where the mirror-symmetry w.r.t the abscissa axis \(Ox_1\) is a stabiliser for the system.
Results are provided below.
Fig. 53 Guaranteed integration of Test-case 1: computing the set \(\bigcup_{t\in\{1,2,3,4,5\}}\mathbb{X}_t\), based on the initial condition \(\mathbb{X}_0\) in green.
Try this example TC1-discrete on Repl.it.
Fig. 54 Guaranteed integration of Test-case 1: computing the set \(\bigcup_{t\in[0,5]}\mathbb{X}_t\), based on the initial condition \(\mathbb{X}_0\) in green.
Try this example TC1-continuous on Repl.it.
Test-case 2
We consider the system:
where the translation symmetry along the \(Ox_2\) axis is a stabiliser for the system. The translation of \(p_2 = \pm k2\pi\) along \(Ox_1\) is another stabiliser.
Results are provided below.
Fig. 55 Guaranteed integration of Test-case 2: computing the set \(\bigcup_{t\in\{2,4,6,8\}}\mathbb{X}_t\), based on the initial condition \(\mathbb{X}_0\) in green.
Try this example TC2-discrete on Repl.it.
Fig. 56 Guaranteed integration of Test-case 2: computing the set \(\bigcup_{t\in[0,8]}\mathbb{X}_t\), based on the initial condition \(\mathbb{X}_0\) in green.
Try this example TC2-continuous on Repl.it.
Test-case 3
We consider the system:
Results are provided below.
Fig. 57 Guaranteed integration of Test-case 3: computing the set \(\bigcup_{t\in\{0.1,\dots,6\}}\mathbb{X}_t\), based on the initial condition \(\mathbb{X}_0\) in green.
Try this example TC3-discrete on Repl.it.
Fig. 58 Guaranteed integration of Test-case 3: computing the set \(\bigcup_{t\in[0,6]}\mathbb{X}_t\), based on the initial condition \(\mathbb{X}_0\) in green.
Try this example TC3-continuous on Repl.it.
Test-case 4
We consider the system of a Dubins car:
where \(u_1\), \(u_2\) are time dependent inputs. To avoid the time dependency in \(\mathbf{u}\), we rewrite the system into
where \(x_4\) is the clock variable. Two transformations exist: a translation symmetry related to \((x_1,x_2)\) and a rotation linked to \(x_3\).
Results are provided below.
Fig. 59 Guaranteed integration of Test-case 4: computing the set \(\underset{(x_{1},x_{2})}{\text{Proj}}\bigcup_{t\in\{1,\dots,14\}}\mathbb{X}_t\), based on the initial condition \(\mathbb{X}_0\) projected in green.
Try this example TC4-discrete on Repl.it.
Fig. 60 Guaranteed integration of Test-case 4: computing the set \(\underset{(x_{1},x_{2})}{\text{Proj}}\bigcup_{t\in[0,14]}\mathbb{X}_t\), based on the initial condition \(\mathbb{X}_0\) projected in green.
Try this example TC4-continuous on Repl.it.
Note
All the examples can be found in the ‘examples’ folder of the library in the directory ‘lie-symmetries’ in both Python and C++