In this paper, problem of reachable set computation of the linear discrete-time controlled system is considered. It is supposed that controlled plant dynamics is described by the vector recurrence equation. It is assumed that the plant initial condition and its control parameters are constrained by the sets, which are convex, closed and limited polyhedrons with final number of vertices. The description of the modified method of reachable set computation is provided and the comparative analysis of the received results with an initial general recurrent algebraic method is made.
Nowadays, a lot of attention is paid to the solution of optimal control problems of discrete-time dynamical systems with terminal functional of quality. From [Chernousko94, Krasovskii68, Tyulyukin93, Shorikov97] it is known that for solving problem of this kind it is rational to compute the reachable sets of all terminal (final) states. The availability of reachable set allows to significantly simplify the solution of a optimal open-loop control problem.
Reachable set computation methods can be divided into two main groups. The first group is creation of the exact reachable sets containing all admissible states of dynamical system to which it can be steered [Lasserre91, Tyulyukin93, Shorikov97]. The second group is approximating methods assuming considerable reduction of calculation time, however giving only an approximate estimation of reachable set [Girard05, Kurzhanski02, Chernousko94].
This paper offers the modified method of exact reachable set computation for discrete-time dynamical system, which is based on the general recurrent algebraic method described in work [Shorikov97].
Let us consider the given integer-valued period of time t ∈ 0, T = {0, 1, . . . , T }, T > 0, T ∈ N (N is the set of all natural numbers) the class of the linear controlled systems with dynamics that is described by the discrete-time vector-matrix recurrence equation: where x(·) ∈ Rn is the state vector (a phase vector); u(·) ∈ Rp is the control (input) vector; A(·) ∈ Rn×n is the state matrix; B(·) ∈ Rn×p is the input matrix.
Let us consider that the vector of the initial state and the vector of admissible controls satisfy the set geometric constraints x(0) ∈ X(0) ⊂ Rn; u(t) ∈ P(t) ⊂ Rp, where sets X(0) and P(t) are convex, closed and limited polyhedrons (i.e. convex polytopes) with final number of vertices in spaces Rn and Rp, respectively.
Thus, the problem is stated as the set constraints (2), (3) to define a set of all possible phase states G(0, X(0), T ) to which the controlled system (1) can be transferred [Krasovskii68, Tyulyukin93] at time T G(0, X(0), T ) = {x(T ) : x(T ) ∈ Rn, x(t + 1) = A(t)x(t) + B(t)u(t), t ∈ 0, T − 1, x(0) ∈ X(0), u(t) ∈ P(t)}. (1) (2) (3) (4)
Pair (X(0), 0) is understood as the a set of all admissible initial states of system at time t = 0. The reachable set (4) has the following main properties [Chernousko94, Shorikov97]: 1. Reachable set (4) is a convex polytope with the finite number of vertices for each time point t ∈ 0, T ; 2. Evolutionary (semi-group) property of reachable sets:
G(0, X(0), T ) = G(t, G(0, X(0), t); T ), where G(0, X(0), T ) – the reachable set at time point corresponding to pair (X(0), 0). 3
In the works [Tyulyukin93, Shorikov97] it is shown that the reachable set represents a convex polytope with the finite number of vertices in Rn. In this method reachable set computation leads to solving of the sequence of single-step reachable set computation
G (0, X(0); T ) = G(t, G+(t); T ), t ∈ 1, T − 1, (5) where G+(t) = G (0, X(0); t) is the reachable set at time t, corresponding to the pair (X(0), 0), which is a convex polytope with the finite number of vertices in Rn.
In this case if we can realize reachable set computation only on one step forward, it is possible to obtain the final reachable set (in terminal time point), which is only determined by reachable set on previous step:
G(0, X(0); T ) = G(T − 1, G+(T − 1); T ).
It is known that the representation of convex polytope can be carried out as the description of all his vertices on the one hand and as the description of basic hyperplanes (linear inequalities) on the other [Chernikov68, Shorikov97, Ziegler98].
Hence, for the solving of basic auxiliary problem we rely on the generalized recurrent algorithm [Shorikov97].
The set of the feasible states x(t+1) of the considered controlled system (1), comprising all vertices of reachable set G(t, G+(t); t + 1) at time (t + 1), t ∈ 0, T − 1, corresponding to the pair G+(t) ∈ 0, T − 1 × 2Rn , is defined according to the following algorithm.
Step 1. Forming of the set Γn(G+(t)) of all vertices of polytope G+(t).
Step 2. Forming of the set Γp(P(t)) of all vertices of polytope P(t).
Step 3. Defining the following sets characterizing free and controlled motion of the system (1) – (3). where Gb +(t + 1) is the Minkowski sum of the sets Gb x(t + 1) and Gb u(t + 1) [Ziegler98], which are the set of points, among which are both internal and extreme points.
Step 4. For the defined set we define the set of all its vertices
Gb +(t + 1) = v(i)(t + 1) i∈1,m⊂ G(t, G+(t), t + 1) b Γn(G+(t + 1)) = v(i)(t + 1) i∈1,k, (k ≤ m).
b In [Tyulyukin93] it is shown that the following statement holds:
conv Gb +(t + 1) = G(t, G+(t); t + 1) = G+(t + 1).
Thus, the vertices of the set G+(t + 1) define the reachable set of controlled system (1) – (3) at time (t + 1). That reachable set is the convex polytope in Rn. 4
In the works [Tyulyukin93, Shorikov97] it is shown that the set vertices search problem is reduced to the solution of m linear mathematical programming problems. In accordance with this fact, we are formulated the following statement of the optimization problem.
For fixed i = 1, m and a set of variables λj , j = 1, m, j 6= i, λj ∈ R, it is required to solve the following linear mathematical programming problem j f =
X λj → min (max )
j X λj vb(j)(t + 1) = v(i)(t + 1),
b X λj = 1, λj > 0.
j (6)
For the solving of linear mathematical programming problem we will use a simplex-method with inverse matrix [Yudin69]. It is known [Papadimitriou85, Chernikov68] that for check of consistency of system (6) it is enough to consider only the first stage of a simplex-method, that is to search the reference basis admissible decision if it exists. For finding of the reference basis admissible decision we will use artificial basis technique. It follows that the choice of cost function f in the problem (6) is of no importance as its choice does not affect at the search of the reference basis admissible decision in any way.
At the first stage of a simplex-method the simplex table is a matrix, the coefficients of which on the last row can be considered as assessment of substitution of the appropriate columns [Yudin69], i.e. has the form: n P bk + 1 . . . k=1 . . . . . . . . . . . . . . .
a1m a2m . . .
anm , n 1 P akm + 1 k=1
The column bk, k = 1, n in the matrix M corresponds to coordinates of the fixed checked point v(i)(t + 1), remaining columns v(j)(t + 1) correspond to coordinates of points akj , k = 1, n, j = 1, m, j 6= i. b b Further, there are two solutions of the linear mathematical programming problem: 1. The basis admissible solution is not found. It follows that the checked point corresponding to a vector v(j)(t+1) is the extreme point of set Gb +(t+1) and, therefore, is the vertex of reachable set G(t, G+(t); t+1). b 2. The basis admissible solution is found. In this case the checked point can be presented in the form of a convex combination of basis vectors Bi, i 6 n + 1, therefore, this point is not the vertex of reachable set G(t, G+(t); t + 1).
Thus, when the solutions of m linear mathematical programming problems are found, we computed set of all vertices Γn(G+(t + 1)) which will also be the reachable set G(t, G+(t); t + 1) of dynamical system (1) – (3). 5
Now we present a modified version of the initial general recurrent method that is often much faster. This modified algorithm of reachable set computation relies on the ideas of ”divide-and-conquer” algorithm, described in [Pardalos95, Preparata85]. This algorithm is often the main alternative to iterative algorithms, which example is the initial recurrent method.
”Divide-and-Conquer” is possible to present by means of the following consecutive steps: 1. Division of a problem into sub-problem, usually of a smaller size; 2. The solution of each of sub-problems (directly, if they are of rather small volume; differently if recursively breaking into smaller parts); 3. Combination of the received solutions of sub-problems.
For realization of this method in this paper the following step-by-step algorithm is offered. Using this algorithm it is possible to define all extreme points of reachable set:
The working set of points X = {x(i)}i∈1,m is formed from the considered initial set of reachable set points v(i)(t + 1)}i∈1,m ⊂ Rn.
Gb +(t + 1) = {b
Then, it is necessary to compute the smallest multidimensional parallelepiped with the side parallel to the coordinate axes, which contains this set. Points of the set are sorted as increase in their distance from the multidimensional parallelepiped center, based on following values δ(i) = maxn x(ki) − dk o , k ∈ 1, n, i ∈ 1, m.
rk where dk is a coordinates of the center R; r is a vector, which components are lengths of the parallelepiped R sides; k · k is a designation of Euclidean norm.
On the next stage of the algorithm we will assume that first k + 1 elements of sorted set Xs are extreme points of reachable set since these points have longest distance from center of parallelepiped R. Taking it into consideration we move these points to the set of pretender-points Xpr.
Then, for each point i = k + 2, . . . , n of sorted set it is necessary to find the solution of linear mathematical program (6). Thus, if the point x(si) is the vertex of polytope Xpr S x(si), it is moved to set of pretender-points Xpr, otherwise, it is excluded and does not participate in further work of an algorithm (in initial time point contains the two first points of the sorted set). Therefore, we solve the linear program of significantly smaller size than the algorithm presented in [Tyulyukin93, Shorikov97].
Since Xs becomes empty set, it is necessary to solve linear mathematical programming (6) for each pretenderpoint x(si) ∈ Xpr.
Algorithm action comes to the end after check of all points of the set Xpr.
For the description of the modified recurrent algorithm the reachable set computation of linear discrete-time dynamical systems modeling has been carried out in the software environment MATLAB 8.4 (R2014a). The linear discrete-time model has served as an example where state matrix and control matrix are and the vector of an initial states set and the vector of admissible controls are presented in the following form: x(t + 1) = Ax(t) + Bu(t), 0 A = −2 0
Modeling results of the reachable set computation for this system are presented in the Figure 1.
For the more complete quality assessment of convex hull computation problem we solved that problem for two typical sets of random points: 1. Type Normal is the random set of points with the normal law distribution (expected mean M1 = 0, rootmean-square deviation σ1 = 1); 2. Type Square is the random set of points normally distributed relation to the square surface with the side
L = 0.5 (expected mean M2 = 0, root-mean-square deviation σ2 = 0, 5); Type: Square
Type: Gaussian 1.5 1
Space dimension n = 3 n = 5 n = 7 −1 −0.5 0.5 1 1.5 −3 −2 −1 1 2 3
4 0 x1
From the given results it is clear that modification of the general recurrent algebraic method due to sorting of an initial set, solving of smaller dimensions linear mathematical programming problems, allows to significantly reduce calculations time. Especially, it is noticeable for high dimensionality of Euclidean vector spaces. In this paper, we described modification of the general recurrent algebraic method for reachable set computation of linear discrete-time dynamical systems [Tyulyukin93, Shorikov97]. This modification is based on use of the ideas of ”divide-and-conquer” algorithm [Pardalos95, Preparata85].
Also we provided the numerical simulation of exact reachable set computation for the dynamical systems of the 3rd order, described by linear discrete-time models. Let us note that the provided sorting algorithm is very effective. The best candidates for set extreme points are checked primarily, and the size of a set remains rather small throughout all computing process. As a result of application of the presented modification of a general recurrent algebraic method the goal was achieved and time spent for computing transactions was considerably reduced.
Program implementation of reachable set computation is performed by authors in the software environment MATLAB 8.4 (R2014a), where the modified recurrent algorithm of linear discrete-time dynamical systems was developed. 8
The research was supported by Russian Foundation for Basic Research (Project 15-01-02368). [Chernikov68] S.N. Chernikov. Linear Inequalities. Moscow, Nauka Publ., 1968. (in Russian) [Chernousko94] F.L. Chernousko. State Estimation for Dynamic Systems. Boca Raton: CRC Press, 1994.