Reachability under uncertainty and measurement noise

Abstract

This paper deals with the problem of reachability under unknown but bounded disturbances and piecewise open-loop controls which may be feedback-corrected at isolated ‘points of correction’. It is presumed that there are hard bounds on the controls and the unknown but bounded items. The open-loop controls are reassigned at prespecified points of correction on the basis of additional information on the state space variable which arrives at these points. Such information typically comes through a given noisy instantaneous measurement of the state space variable which sometimes may or may not be complemented by information on the forthcoming disturbance. Thus the process is ‘piecewise feedback’ with feedback introduced at points of correction. The described situation is intermediate relative to purely open-loop control and continuous measurement feedback control under uncertainty. The novelty of this paper lies in considering incomplete noisy measurements of the state space variable at points of correction rather than exact complete measurements of these. The paper also describes some numerical algorithms relevant for computer modelling. It is emphasized that effective computational results may be obtained if one relies on ellipsoidal techniques as given by Kurzhanski et al.

Keywords:

• Reachability
• measurement feedback
• set-membership estimation
• open-loop control
• feedback control
• set-valued analysis
• ellipsoidal calculus

1. Introduction

The standard reachability problem is one of the essential topics in control theory [1 –  6]. However, recent applications require the treatment of this problem in a more complicated setting, presuming that the system is subjected to unknown but bounded disturbances ([7 –  10]). The reach set is then taken as the variety of such points that these or their neighbourhoods could be reached despite the unknown disturbances. The notion of such ‘reachability under uncertainty’ is relevant primarily for systems subjected to feedback controls. The respective notions were introduced and thoroughly explained in [10,11]. In these papers it was assumed that the respective feedback control strategies are based on complete and noise-free measurements of the state space variable.

In the present paper we discuss computation of domains reachable by a controlled process through available piecewise open-loop controls, despite the unknown input disturbances, with feedback control corrections allowed at isolated instants of time. If exact reachability is impossible, we introduce the notion of approximate reachability and indicate guaranteed error bounds for such approximations. The additional information for feedback control correction here again arrives at prespecified instants of time – ‘the points of correction’. But this information is now confined to incomplete noisy measurements of the phase space variable at such points. All the uncertain items are taken to be unknown but bounded. The total process is therefore a combination of piecewise open-loop control and guaranteed (‘set-membership’) estimation as introduced in [10,13]. The final reach sets then turn out to be set-valued and ensure guaranteed estimates.

Here the controls, the unknown inputs and measurement noise are subjected to geometrical ‘hard’ bounds which are presumed ellipsoidal. However, the suggested computational schemes also allow original box-valued constraints or a combination of both options (see [11]). Efficient numerical solutions through external and internal ellipsoidal-valued approximations of reach sets and their elements are then available.

2. The system

Consider the system

with continuous matrix coefficients A(t), B(t), C(t) and x∈ℝ ⁿ . Here u = u(t)∈ℝ ^p is an open-loop control which may be corrected at prespecified instants of correction thus allowing us to introduce elements of feedback control; v(t)∈ℝ ^q is the unknown input disturbance and x(t ₀) is the initial value for the trajectory x(t,t ₀,x(t ₀)).

The control u and the uncertain items v, x(t ₀) are subjected to hard bounds t ⩾ t ₀

where 𝒫(t), 𝒬(t) are given set-valued functions with convex compact values, continuous in time in the Hausdorff metric, 𝒳⁰ is a convex compact set in ℝ ⁿ . The classes of open-loop controls u(t) and unknown disturbances v(t) subjected to hard bounds of the above will be further denoted as 𝒫_O, 𝒬_O, respectively.

In this paper we consider hard bounds of specific ellipsoidal-valued type, with

where p(t) is the centre and P(t) = P′(t) > 0 is the ‘shape’ matrix of the ellipsoid, so that the support function is ρ(l|ℰ(p,P)) = max{(l,x)|x∈ℰ(p,P)} = (l,p) + (l,Pl)^1/2. The restrictions 𝒬(t), 𝒳⁰ are of similar ellipsoidal type.

The problems considered in the sequel deal with reachability under open-loop or piecewise open-loop controls. Such problems will be further reduced to those of optimization. We first start with open-loop control under uncertainty.

3. Reachability under open-loop controls

The problem of open-loop control under uncertain inputs allows several interpretations. Here we shall introduce two basic types of open-loop reach sets which are different from those introduced earlier in [10]. The relations for these sets will be important for further constructions which will be a superposition of such relations.

In order to simplify the formal calculations, we transform system (1) without loss of generality, to system

with the same type of constraints on u,v as before (see [9]).

For equation (4) consider the following two problems:

Problem 1-1. Given an interval [t ₀, τ], a set 𝒳⁰ and a point x∈ℝ ⁿ , find

under the conditions

Here

We further assume 𝒳⁰ = ℰ(x ⁰,X ⁰), X ⁰ = X ^0′ > 0, so that in Problem 1-1 we have z∈ℰ(x ⁰,X ⁰), where x ⁰, X ⁰ are known.

Problem 2-1. Given an interval [t ₀, τ], a set 𝒳⁰, and x∈ℝ ⁿ , find

under the conditions

Note that d(x,𝒢) = min {d(x,z)|z∈𝒢} where 𝒢 is a closed set in ℝ ⁿ . Thus d(x,𝒢) = h ₊(x,𝒢), where h ₊(𝒬, 𝒢) is the Hausdorff semidistance between compact sets 𝒬, 𝒢 defined as

This is precisely the operation used in the above problems. The Hausdorff distance is then defined as h(𝒬, 𝒢) = max {h ₊(𝒬, 𝒢), h ₊(𝒢, 𝒬)}. We shall also need the geometric (Minkowski) difference of sets 𝒬, 𝒢 which is defined as

Direct calculations indicate that V – is given by

where

This yields

Lemma 3.1. The following equality is true:

Here 𝒳⁻(τ, t ₀, 𝒳⁰, μ) is the open loop reach set (OLRS) of maxmin type, namely, the set of points x∈ℝ ⁿ whose μ-neighbourhood ℬ_μ (x) may be reached at time τ by system (4) for any disturbance v(t) given in advance, through some u(·)∈U _O , whatever z∈𝒳⁰.

Assumption 3.1. The following relation is true for some γ > 0

This assumption ensures B(s)𝒫(s)

and is further presumed true. It is not seriously restrictive, however, since, by increasing the parameter μ we may always ensure the overall property 𝒳⁻ (τ,t ₀, 𝒳⁰, μ) ≠ ∅.

Similarly, we may calculate

under the conditions

Having in mind that again 𝒳⁰ = ℰ(x ⁰,X ⁰), we find

where

This yields

Lemma 3.2. The following equality is true

Here 𝒳⁺(τ, t ₀, 𝒳⁰, μ) is an open-loop reach set of minmax type. It consists of all x whose μ-neighbourhood ℬ_μ (τ) may be reached at time τ by system (4) under some control u(·)∈U _O , whatever v(t)∈𝒬(t), t ₀ ⩽ t ⩽ τ and z∈X ⁰. (With μ = 0 it turns out that

.)

Remark 3.1. With X ⁰ = {x ⁰} one should recognize that the OLRS of the maxmin type is the set of points reachable at time τ from a given point x ⁰ for any disturbance v(·)∈V _O , provided the function v(t), t ₀ ⩽ t ⩽ τ is communicated to the controller in advance, before the selection of control u(t). The control u(·) is then selected through an anticipative control procedure. On the other hand, for the μ-reach set of the minmax type there is no information provided in advance on the realization of v(·), which is realized only after the selection of μ. The control u(·) is then selected through a non-anticipative control procedure.

We now pass to the main point of this paper – the treatment of corrections under noisy measurement.

4. Reachability with correction and incomplete measurement

Let us start from the maxmin problem. Suppose a point of correction τ₁∈[t ₀,τ] is given. In the case of exact and complete measurements we could then consider (compare with [10]).

Problem 1-2. Given a set 𝒳⁰, a vector x∈ℝ ⁿ , numbers μ₁ > 0, μ₂ > 0 and an instant τ₁, find the sequential maxmin, namely, first consider Stage 1 (t∈[t ₀, τ₁]), which is to find

under the conditions z ∈ ℰ(x ⁰, X ⁰), x(τ₁) ∈ ℬ_μ1(x), u(·)∈U ₀, v(·)∈V ₀.

Then at Stage 2 find (t∈[τ₁, τ])

under the conditions

Here under complete measurements it is assumed that at time τ₁ one uses the additional information for Stage 2 which is the knowledge of the set

Namely, at Stage 2, one is to start from the set of initial points

where z∈𝒳⁻(τ₁, t ₀, 𝒳⁰, μ₁) is unknown.

Now, passing to the specifics of this paper, we suppose that the exact value of x(τ₁) is unavailable and only the measurement is given:

where H is a given matrix of dimension m × n and ξ∈ℛ(τ) = {ξ: ϕ(t,ξ) ⩽ 0}. Here ϕ(t,ξ) is continuous in both variables, convex in ξ and such that 0∈intD_ϕ* – the interior of the set D _ϕ* = {ξ*:ϕ*(t,ξ*)} < ∞. The function ϕ*(t,ξ*) is the Fenchel conjugate of ϕ(t,x) in the second variable. The last property ensures that ℛ is bounded.

Denote

where

.

Then

where

We now pass to Problem 1-1-N – the ‘noisy measurement’ variant of Problem 1-1. We observe that Stage 1 is the same as above, in Problem 1-1, while at instant τ₁ we assume that given, in addition to the set

, are also the value y ₁ = y(τ₁) and the parameters H, ℛ of the measurement equation (10). This allows us to presume that given instead of

is the information (consistency) set 𝒳⁻(τ₁, t ₀, 𝒳⁰, y ₁, μ₁, under measurement y ₁ (see [12], [9]). This information set is the level set of the information function V(τ₁,x,y ₁,μ₁).

In order to formulate Stage 2 one may observe that at time τ₁ one of the sets 𝒳⁻(τ₁,t ₀,𝒳⁰,y ₁,μ₁) is available depending on y ₁. In turn, the specific realization y ₁ = y*(τ₁) = Gx* + ξ* depends on the unknown actual values

.

We may now denote

At Stage 2 under incomplete measurement we have the next problem.

Problem 1-2-N: Find

under the conditions

Denote

This set was calculated for a given fixed measurement y ₁. Then the final reach set X ⁻(τ,t ₀,𝒳⁰,μ[1,2]) of maxmin type after one correction will be the union of sets 𝒳⁻(τ,t ₀,𝒳⁰,y ₁,μ[1,2]) over all admissible realizations of y ₁:

The following proposition is true.

Theorem 4.1. The reach set X ⁻(τ,t ₀,𝒳⁰,μ[1,2]) of maxmin type under one correction and incomplete measurement is the union (13) of sets 𝒳(τ,t ₀,𝒳⁰,y ₁,μ[1,2]) over all y ₁∈𝒴∈(τ₁).

This is the union of sets (the set of sets) whose (μ₁ + μ₂)-neighbourhoods may be reached for any disturbance v(t) through some piecewise open-loop control μ, whatever the unknown value x(t ₀)∈𝒳⁰. Here the control u is subject to one correction at time τ₁ and depends on the incomplete measurement y ₁ = y(τ₁).

In more detail we have:

Lemma 4.1 Each of the sets 𝒳⁻(τ,t ₀,𝒳⁰,y ₁,μ[1,2]) may be written as

If we introduce the mapping,

as given in (6), we come to the next statement.

Lemma 4.2

Suppose we now have several corrections at points τ₁, … τ _k , with t ₀ < τ₁,τ _k  < τ, and measurements

subjected to unknown noise ξ^{( i )} bounded due to the relation ϕ^{( i )}(τ_i,ξ^{( i )} ⩽ 0 with functions ϕ^{( i )} of the same class as ϕ and Y(τ _i ) defined as Y(τ₁).

Then the respective reach set of sequential maxmin type after k corrections and incomplete measurements may be presented as follows:

This set is defined for a fixed sequence of admissible measurements y[1, …., k]. Then the final reach set will be the union of such sets:

This is the set of sets whose (μ₁ + … + μ _k )-neighbourhoods may be reached for any disturbance v(t) through some piecewise open-loop control μ, whatever the unknown value x(t ₀)∈𝒳⁰. Here the control u is subject to k corrections at instants τ₁,i = 1, …, k, and depends on k incomplete measurements y_i  = y(τ_i).

The minmax problem is described similarly. But the basic operation will now consist of calculating the set 𝒳⁺(τ,t ₀,𝒳₀,μ) according to (8) instead of 𝒳 – (τ,t ₀,𝒳₀,μ) according to (6). The other parts of the procedure are mostly similar to the maxmin problem.

The analytical description of the problem is rather cumbersome, as we see. It is all the more true since here we have to deal with set-valued items. We further indicate a computation scheme based on ellipsoidal calculus [9, [11] which allows us to represent the given solutions in terms of ellipsoidal-valued relations.

5. Ellipsoidal representations

When observing the equations of Section 3, one may note that they require calculations of set-valued integrals with varying upper limit, as well as of geometric sums, differences and intersections of convex sets. To calculate such items is a difficult procedure. It would be easier to model such systems if the solution were rewritten in terms of the ellipsoidal approximations of such items. We shall therefore indicate ellipsoidal modules for such calculations, constructing the ellipsoidal representations along the lines of [9,11].

Let us calculate the sets 𝒳⁻(τ,t ₀,𝒳⁰,y,μ[1,2]) of Proposition 3.1, assuming 𝒫(t) = ℰ(p(t),P(t)) and 𝒳⁰ = ℰ(x ⁰,X ⁰), 𝒬(t) = ℰ(q(t),𝒬(t)) to be ellipsoidal-valued.

(i) At Stage 1 we first approximate

Denote

Following [13], we have

where,

Similarly,

where

(ii) The geometric differences of two ellipsoids ℰ(x ⁽¹⁾, X ⁽¹⁾), ℰ(x ⁽²⁾, X ⁽²⁾), X ⁽¹⁾ = X ⁽¹⁾′ ⩾ 0,X ⁽²⁾ = X ⁽²⁾′ ⩾ 0 are approximated as

where

,

(iii) The intersection ℰ(x ⁽¹⁾, X ⁽¹⁾) ∩ ℰ(x ⁽²⁾, X ⁽²⁾) = 𝒳 _I is approximated as

The internal and external ellipsoids of (17) will be sought for as

where α _i  > 0, so that

with x(α) = α₁ x ⁽¹⁾ + α₂ x ⁽²⁾.

Denote f_i (l) = (l,x ⁽ⁱ⁾) + (l,X ⁽ⁱ⁾ l)^1/2, l∈ℝ ⁿ . The coefficients α_i define an internal ellipsoid

if they satisfy the inequalities

with i = 1,2.

The coefficients α _i define an external ellipsoid

iff they satisfy the inequalities

with i = 1,2.

It is possible to retain one external and one internal ellipsoid respectively minimalizing or maximizing a positive measure of the set ℰ(x(α), X(α)) over the solutions to inequalities (18) or (19) (see [9] for such measures).

(iii-a) The possibly unbounded set

may be approximated by a parametrized family of ellipsoids. Thus, for example, assuming H = {D_m ,0}, x_m  = (m,0}, with D_m  > 0 diagonal, we may replace 𝒳 _R by

, where

Then the intersection

converges to ℰ(x ⁽¹⁾,X ⁽¹⁾ ∩ 𝒳 _M  = Z internally, namely,

and

Substituting M for M + ε ^k I_m for some k ⩾ 2 and repeating the procedure, we will obtain an external estimate

with convergence

(I_m is a unit m × m matrix).

(iv) We finally remark that the integrals

are approximated similarly to those of (16).

The sequence of calculations (algorithmic scheme) may now be described as follows.

(1) Following (i), calculate the external and internal approximations

(2) Following (ii), calculate the external and internal ellipsoidal approximations

for

, then similar approximations

that ensure

(3) Following (iii-a), find external and internal approximations for 𝒳 _R .

(4) Following (11), (iii), (iii-a), calculate for a given vector y ₁∈𝒴 the approximations

that ensure

(5) As in points (1), (2), following remark (iv) and Lemma 4.1, calculate final ellipsoids ℰ⁺(y ₁), ℰ – (y ₁) that ensure the approximations

Then the final set-valued reach set X(τ,t ₀, 𝒳⁰, μ[1,2]) is a union of sets and satisfies the inclusions

In each of the approximations indicated in the above the relations depend on the parameters γ(t), π(t), S(t), S_i (t), λ _i , K_i , α _i , etc. These parameters may be ‘tuned’ for each direction l∈ℝ ⁿ along which the approximations would be tight. An array of directions is then selected so as to ensure tight approximations by a family of ellipsoids that envelopes the exact items from above and produces unions of ellipsoids which approximate these items internally. (This may be done through identical parallel calculations.) A detailed treatment of tight ellipsoidal approximations is given in [9,11,13]. The case of k > 1 corrections is dealt with by sequentially applying the present scheme.

6. Conclusion

1.	In this paper we have treated the problem of reachability under piecewise open-loop control and set-membership uncertainty with a finite number of corrections, emphasizing the difference between problems of minmax and maxmin type.
2.	We discussed the specific problem when the information at the points of corrections is incomplete and subjected to measurement noise.
3.	We treated the maxmin problem in detail and showed that in the latter case (as also in the minmax case) the reach set has to be treated as consisting of set-valued elements.
4.	We indicated an array of ellipsoidal-valued operations whose combination allows us to solve the problem numerically with the techniques of finite-dimensional calculus and also allows computer animation.
5.	The schemes of this paper may be used as prototypes for treating hybrid systems with resets governed by enabling zones (‘guards’) given by ellipsoids or ellipsoidal cylinders similar to 𝒳 R of the above.