On Reachability Under Uncertainty.
The paper studies the problem of reachability for linear systems in the presence of uncertain (unknown but bounded) input disturbances that may also be interpreted as the action of an adversary in a game-theoretic setting.     It defines possible notions of reachability under uncertainty emphasizing the differences between reachability under open-loop and closed-loop control. Solution schemes for calculating reachability sets are then indicated. The situation when observations arrive at given isolated instances of time leads to problems of anticipative (maxmin) or nonanticipative (minmax) piecewise open-loop control with corrections and to the respective notions of reachability. As the number of corrections tends to infinity, one comes in both cases to reachability under nonanticipative feedback control. It is shown that the closed-loop reach sets under uncertainty may be found through a solution of the forward Hamilton--Jacobi--Bellman--Isaacs (HJBI) equation.     The basic relations are derived through the investigation of superpositions of value functions for appropriate sequential maxmin or minmax problems of control.
Introduction
Recent developments in real-time automation have promoted new interest in the reachability
problem-the computation of the set of states reachable by a controlled process through
available controls. Being one of the basic problems of control theory, it was studied from
the very begining of investigations in this field (see [18]). The problem was usually studied
in the absence of disturbances, under complete information on the system equations and
the constraints on the control variables. It was shown, in particular, that the set of states
Research supported by National Science Foundation Grant ECS 9725148. We thank Oleg Botchkarev
for the figures.
reachable at given time t under bounded controls is one and the same, whether one uses
open-loop or closed-loop (feedback) controls. It was also indicated that these "reachability
sets" could be calculated as level sets for the (perhaps generalized) solutions to a "forward"
Hamilton- Jacobi-Bellman equation [18], [19], [3], [15], [17].
However, in reality the situation may be more complicated. Namely, if the system is subject
to unknown but bounded disturbances, it may become necessary to compute the set of states
reachable despite the disturbances or, if exact reachability is impossible, to find guaranteed
errors for reachability.
These questions have implicitly been present in traditional studies on feedback control under
uncertainty for continuous-time systems, [10], [28], [4], [9], [12]. They have also appeared
in studies on hybrid and other types of transition systems [1], [29], [21], [5].
This leads us to the topic of the present paper which is the investigation of reachability
under uncertainty for continuous-time linear control systems subjected to unknown input
disturbances, with prespecified geometric (hard) bounds on the controls and the unknowns.
The paper indicates various notions of reachability, studies the properties of respective reach
sets and indicates routes for calculating them.
The first question here is to distinguish, whether reachability under open-loop and closed-loop
controls yield the same reach sets. Indeed, since closed-loop control is based on better
information, namely, on the possibility of continuous on-line observations of the state space
variable (with no knowledge of the disturbance), it must produce, generally speaking, a
result which is at least "not worse," for example, than the one by an open-loop control
which allows no such observations, but only the knowledge of the initial state, with no
knowledge of the disturbance. An open-loop control of the latter type is further referred to
as "nonanticipative."
However, there are many other possibilities of introducing open-loop or piecewise open-loop
controls, with or without the availability of some type of isolated on-line measurements
of the state space variable, as well as with or without an "a priori" knowledge of the
disturbance. Thus, in order to study the reachability problem in detail, we introduce a
hierarchy of reachability problems formulated under an array of different "intermediate"
information conditions. These are formulated in terms of some auxiliary extremal problems
of the maxmin or minmax type.
Starting with open-loop controls, we first distinguish the case of anticipative control from
nonanticipative control. The former, for example, is when a reachable set, from a given
initial state x 0 , at given time  , is defined as the set
of such states
x, that for any admissible disturbance given in advance, for the whole interval under con-
sideration, there exists an admissible control that steers the system to a -neighborhood
g. Here the respective auxiliary extremal problem is of the
maxmin type.(Maximum in the disturbance and minimum in the control). On the other
hand, for the latter the disturbance is not known in advance. Then the reachability set
from a given initial state is defined as the set X
of such states x whose
-neighborhoods B  (x) may be reached with some admissible control, one and the same for
all admissible disturbances, whatever they be. Now the respective auxiliary problem is of
the minmax type.
It is shown that always X
and that the closed-loop reach set X
attained under nonanticipative, but feedback control lies in between, namely,
There also are some intermediate situations when the observations of the state space variable
arrive at given N isolated instants of time. In that case one has to deal with reachability
under possible corrections of the control at these N time instants. Here again we distinguish
between corrections implemented through anticipative control (when the future disturbance
is known for each time interval in between the corrections) and nonanticipative control,
when it is unknown. The respective extremal problems are of sequential maxmin and
types accordingly and the controls are piecewise open-loop: at isolated time instants
of correction comes information on the state space variable, while in between these the
control is open-loop (either anticipative or not). Both cases produce respective sequences
reach sets". The
relative positions of the reach sets in the hierarchical scheme are as follows
Finally, in the limit, as the number of corrections N tends to infinity, both sequences of
reachability sets converge to the closed-loop reach set 1 .
The adopted scheme is based on constructing superpositions of value functions for open-loop
control problems. In the limit these relations reflect the Priciple of Optimality under
set-membership uncertainty. This principle then allows one to describe the closed loop reach
set as a level set for the solution to the forward HJBI (Hamilton-Jacobi-Bellman-Isaacs)
equation. The final results are then presented either in terms of value functions for this
equation or in terms of set-valued relations.
Schemes of such type have been used in synthesizing solution strategies for differential games
and related problems, and were constructed in backward time, [23], [11], [27], [28].
The topics of this paper were motivated by applied problems and also by the need for a
theoretical basis for further algorithmic schemes.
As indicated in the sequel, this is true when all the sets involved are nonempty and when the problems
satisfy some regularity conditions.
dynamics. Reachability under open loop
controls
In this section we introduce the system under consideration and define two types of open-loop
reachability sets. Namely, we discuss reachability under unknown but bounded disturbances
for the system
with continuous matrix coefficients A(t); B(t); C(t). Here x 2 IR n is the state and u 2 IR p is
the control that may be selected either as an open loop control OLC-a Lebesgue-measurable
function of time t, restricted by the inclusion
or as a closed-loop control CLC-a set-valued strategy
Here v 2 IR q is the unknown input disturbance with values
P(t); Q(t) are set-valued continuous functions with convex compact values.
The class of OLC's u(\Delta) bounded by inclusion (2) is denoted by UO and the class of input
disturbances v(\Delta) bounded by (4) as VO . The strategies U are taken to be in U C -the
class U C of CLC's that are multivalued maps U(t; x) bounded by the inclusion (3), which
guarantee the solutions to equation (1), (which now turns into a differential
inclusion), for any Lebesgue-measurable function v(\Delta). 2
We distinguish two types of open loop reach sets-the maxmin type and the minmax type.
As we will see in the next Section, the names maxmin and minmax assigned to these sets
are due to the underlying optimization problems used for their calculation.
Definition 1.1 An open loop reach set (OLRS) of the maxmin type (from set X
is the set vectors x such that for every disturbance
there exist an initial state x 0 2 X 0 and an OLC u(t) 2 P(t) which steer the
trajectory , from state x
The set X 0 is assumed convex and compact (X
2 For example, the class of set-valued functions with values in compIR n , upper semicontinuous in x and
continuous in t.
turns to be empty, one may introduce the open loop -reachable set
as in Definition 1.1 except that (5) is replaced by
Here
is the ball of radius  with center x.
Thus the OLRS of the maxmin type is the set of points x 2 IR n that can be
reached, for any disturbance v(t) 2 Q(t) given in advance, for the whole interval t 0  t   ,
from some point x(t
The open loop -reach set is the set of points x 2 IR n whose -neighborhood
may be reached, for any disturbance v(t) given in advance, through some x(t 0
By taking   0 large enough, we may assume
to be the unique trajectory corresponding to x(t 0
u(\Delta) and disturbance v(\Delta). Then
is the reach set in the variable u(\Delta) 2 UO (at time t from set X 0 ) with fixed disturbance
input v(\Delta).
Lemma 1.1
This formula follows from Definition 1.1. Recall the definition of the geometrical
difference P
\GammaQ of sets
Then directly from (1) one gets
Z
S(s; )P(s)ds
Z
S(s; )(\GammaQ(s))ds: (7)
Here S(s; t) stands for the matrix solution of the adjoint equation
In other words the set
is the geometric difference of two "ordinary" reach sets, namely, the set X(t; t
taken from X(t 0 calculated in the variable u, with v(t) j 0, and the set
taken from x(t 0 calculated in the variable v, with u(\Delta) j 0.
This simple geometrical interpretation is of course due to the linearity of (1).
For the -reachable set, we have the following lemma.
Lemma 1.2 The set may be expressed as
also
Remark 1.1. Definition (8) of may also be rewritten as
We now define another class of open-loop reach sets under uncertainty-the OLRS of the
Definition 1.2 An open loop -reach set (OLRS) of the minmax type (from set
is the set X for each of which there
exists a control u(t) 2 P(t) that assigns to each v(t) 2 Q(t) a vector x such that the
respective trajectory ends in x[
Thus the -OLRS of minmax type consists of all x whose -neighborhood B  (x) contains
the states x[ ] generated by system (1) under some control u(t) 2 P(t) and all fv(t) 2
selected depending on u; v. 3
A reasoning similar to the above leads to the following lemma.
Lemma 1.3 The set X may be expressed as
and
usually turns out that X
Remark 1.2. Definition may be rewritten as
Direct calculation, based on the properties of set-valued operations, allows to conclude the
following.
Lemma are both nonempty for some  ? 0,
we have
We shall now calculate the open-loop reach sets defined above, using the techniques of
convex analysis ([25], [12], [15]).
2 The calculation of open-loop reach sets
Here we shall calculate the two basic types of open-loop reach sets. The relations of this
section will also serve as the basic elements further constructions which will be produced
as some superposititions of the relations of this section.
The calculations of this section and especially of later sections related to reachability under
feedback control require a number of rather cumbersome calculations of geometrical
(Minkowski) differences and their support functions. In order to simplify these calculations
we transform system (1) to a simpler form. Taking the transformation
gets
Keeping the previous notations loss of generality,
to the system
with the same constraints on u; v as before. For equation (10) consider the following two
problems:
Problem (I) Given a set X 0 and x 2 IR n , find
min u
min
under conditions
Problem (II) Given a set X 0 and x 2 IR n , find
min
under conditions
Here
and G is a closed set in IR n . Thus
where h+ (Q; G) is the the Hausdorff semidistance between compact sets Q; G; defined as
min z
The Hausdorff distance is h(Q; Q)g.
In order to calculate the function explicitly, we use the relations
and (see [10], [15] for the next formula)
where
is the support function of G [15]. (For compact G, sup may be substituted by max.)
We thus need to calculate
min u
min
which gives, after an application of (11), and an interchange of min u ; min x() and max l (see
Z
Due to (11), the last formula says simply that V \Gamma is given by
where
Z
B(t)P(s)ds
Z
(\GammaC(s))Q(s)ds;
It then follows that
and so (12) implies that x 2
Z
This gives, from the definitions of support function and geometrical difference,
ae
l
Z
B(s)P(s)ds
Z
(\GammaC(s)Q(s))ds
which, interpreted as integrals of multivalued functions, again results in (14).
Theorem 2.1 The set its support function
It is clear that if the difference
Z
B(t)P(s)ds
Z
C(s)(\GammaQ(s))ds 6= ;;
Note that function may be also defined as the solution to
Problem
min u
min
Direct calculations then produce the formula
which gives the same result as Problem (I).
Similarly, we may calculate
min
Taking into account the minimax theorem of [7] and the fact that
l
l
we come to
l
Z
ae(ljB(s)P(s))ds
Z
ae(\GammaljC(s)Q(s))ds:
Here (conc h)(l) is the closed concave hull of h(l). Note that
where (conv (l) is the closed convex hull and also the Fenchel second conjugate
h    (l) of h(l) (see [25], [12] for the definitions).
Therefore
where
Z
(\GammaC(s))Q(s)ds
Z
B(s)P(s)ds:
It then follows that
Similarly, (18) implies that
Z
so that the support function
l
Z
B(s)P(s)ds
l
Z
(\GammaC(s))Q(s)ds
Theorem 2.2 The set X by (20) and its support function
It can be seen from (22) that X may be empty. At the same time, in order
that it is sufficient that
Z
(\GammaC(s))Q(s)ds 6= ;;
which holds for  ? 0 sufficiently large.
It is worth mentioning that a minmax OLRS may be also be specified through an alternative
definition.
Definition 2.1 An open loop -reach set (OLRS) of the minmax type (from set X 0 ,
at time   t 0 ) is the union
where
for some u(\Delta) 2 UP with   0 given and each set X
This leads to Problem (II   ). Given set X 0 , and vector x 2 IR n , find
min
under conditions x(t 0
Direct calculations here lead to the formula
the same result as Problem II .
The equivalence of Problems II ; II   means that definitions 1.2 and 2.1 both lead to the
same set X As we shall see, this is not so for the problem of reachability with
corrections. A similar observation holds for problems I ; I   .
Remark 2.1. For the case that X is a singleton, one should recognize the following.
The OLRS of the maxmin type is the set of points reachable at time  from a given point
x 0 for any disturbance v(\Delta) 2 VO , provided function v(t); t 0  t   is communicated to the
controller in advance, before the selection of control u(t). As mentioned above, the control
u(\Delta) is then selected through an anticipative control procedure.
On the other hand, for the construction of the the \Gammareach set of the minmax type there is no
information provided in advance on the realization of v(\Delta), which becomes known only after
the selection of u. Indeed, given point one has to select the control u(t) for the
whole time interval t 0  t   , whatever be the unknown v(t) over the same interval. The
control u(\Delta) is then selected through a nonanticipative control procedure. Such a definition
allows to specify an OLRS as consisting of points x each of which is complemented by a
neighborhood B  (x) so that
for a certain control u(\Delta) 2 UO . This requires  ? 0 to be sufficiently large.
As a first step towards reachability under feedback, we consider piecewise open-loop controls
with possibility of corrections at fixed instants of time.
3 Piecewise open-loop controls: reachability with
corrections
Here we define and calculate reachability sets under a finite number of corrections. This is
done either through the solution of problems sequential maxmin and minmax or through
operations on set-valued integrals.
Taking a given instant of time t  that divides the interval T in two, namely,
consider the following sequential maxmin problem.
Problem
min u
min
and then find
min u
min
The latter is a problem on finding a sequential maxmin with one "point of correction"
. Using the notation [1;
Let us find
using the technique of convex analysis. According
to section 2, (see (11)), we have
(ae(ljB(s)P(s))\Gammaae(\GammaljC(s)Q(s))dsj(l; l)  1g
where
B(s)P(s)ds
(\GammaC(s))Q(s))ds:
Substituting this in (24), we have
min u
min
l
Z
Continuing the calculation, we come to
l
Z
(ae(ljB(s)P(s))ds
Z
where
(ae(ljB(s)P(s))ds \Gamma ae(\GammaljC(s)Q(s)))ds:
is the support function of the set
B(s)P(s)ds
(\GammaC(s)Q(s))ds:
Together with (25) this allows us as in Section 2, to express V \Gamma(; x; [1; 2]) as
where
"'
B(s)P(s)ds
(\GammaC(s))Q(s)ds
Z
B(s)P(s)ds
Z
(\GammaC(s))Q(s))ds:
Formula (26) shows that
(defined as the level set of
1 ) is also the
reach set with one correction. In particular, X \Gamma(; t consists of all states x that
may be reached for any function v(\Delta) 2 VP , whose values are communicated in two stages,
through two consecutive selections of some open-loop control u(t) according to the following
scheme.
Stage (1): given at time t 0 are the initial state x 0 and function v(t) for ,-select at
time t 0 the control u(t) for
Then at instant of correction t  additional information for stage (2).
Stage (2): given at time t   are the state x(t   ) and function v(t) for ,-select at time
the control u(t) for
This proves Theorem 3.1.
Theorem 3.1 The set
is the maxmin OLRS with one correction at instant t oe and is given by formula (26).
We refer to
as the maxmin OLRS with one correction at instant
The two-stage scheme may be further propagated to the class of piecewise open-loop controls
with k corrections. Taking the interval, introduce a partition
so that the interval T is now divided into k
where
are the points of correction.
Consider also a nondecreasing continuous function (t)  0; denoting
and also
Problem
Solve the following consecutive optimization problems.
Find
min u
min
then find
min u
min
then consecutively, for
min u
min
and finally
min u
min
Direct calculation gives
with
B(s)P(s)ds
(\GammaC(s))Q(s)ds;
then
with
"'
B(s)P(s)ds
(\GammaC(s)Q(s)ds
B(s)P(s)ds
(\GammaC(s)Q(s)ds;
then consecutively
with
B(s)P(s)ds
(\GammaC(s))Q(s))ds
B(s)P(s)ds
(\GammaC(s))Q(s)ds
and finally
where
(0)+
B(s)P(s)ds
(\GammaC(s))Q(s))ds
B(s)P(s)ds
(\GammaC(s))Q(s)ds
Z
B(s)P(s)ds
Z
(\GammaC(s))Q(s)ds
We refer to
as the maxmin OLRS with k corrections at points
Theorem 3.2 The set
is given by formula (29).
We denote
and also introduce additional notations for the functions
emphasizing the dependence of
on the initial condition
We further assume
Note that the number of nodes  j in any partition \Sigma k is k 1. The
partition applied to a function V k is precisely \Sigma k . Consequently, the increment
is presented as a sum of k once it is applied to a function V k with
index k.
A sequence of partitions \Sigma k is monotone in k if for every
contains all
the nodes  j of partition \Sigma k 1
Theorem 3.3 Given are a monotone sequence of partitions \Sigma
continuous nondecreasing function (t)  0; that generates for any partition \Sigma k
a sequence of numbers
Given also are a sequence of value functions
each of which is formed by
the partition \Sigma k and a sequence  is the index of
Then the following relations are true.
(i) For any fixed ; x, one has
(ii) For any fixed ; x and index i 2 [1; k] one has
(iii) The following inclusions are true for
where the sets
are defined by (30).
The proofs are based on the following properties of the geometrical (Minkowski) sums and
differences of sets
and the fact that in general a maxmin does not exceed a min max. Direct calculations
indicate that the following superpositions will also be true.
Lemma 3.1 The functions
k satisfy the following property
This follows from Theorem 3.2 and the definitions of the respective functions
Remark 3.1 Formula (34) reflects a semigroup property, but only for the selected points of
correction
The reasoning above indicates, for example, that
is the set of states that
may be reached for any function v(\Delta) 2 VO , whose values are communicated in advance in
stages, through k consecutive selections of some open-loop control u(t) according to
the following scheme.
Stage (1): given at time t 0 are initial state x 0 and function v(t) for select at time
Then at instant of correction  j comes additional information for stage (j 1).
Stage (j), (j = 2; :::; k): given at time  j are state x( j ) and function v(t) for
select at time  control u(t) for t 2 T j+1 .
Remark 3.2. There is a case when all the functions
taken for all the integers
coincide. This is when system (10) satisfies the so-called matching conditions:
We now pass to the problem of sequential minmax, with one correction at instant t 0
using the notations for Problem (I 1 ). This is
Problem
min
then find
min
The latter is a problem of finding a sequential minmax with one point of correction
Denoting
let us find X +(; t using the techniques of convex analysis (as
above, with obvious changes).
This gives
where
(\GammaC(s))Q(s)ds
B(s)P(s)ds:
Continuing the calculations, we have
min
where
Z
(\GammaC(s))Q(s)ds
Z
B(s)P(s)ds:
This proves Theorem 3.4
Theorem 3.4 The set
is the minmax OLRS with one correction at instant
Here the problem is again solved in two stages, according to the following scheme.
Stage (1): given at time t 0 are set X 0 and x 2 IR n . Select control u(t) (one and the same
for all v) and for each v(t); t 2 T 1 , assign a vector x(t 0 that jointly with u; v produces
Then at instant of correction t  additional information for stage (2).
Stage (2): given at time t   are x(t   ) and vector x 2 IR n . Select control u(t); t 2 T 2 (one
and the same for all v) and for each v(t); t 2 T 2 assign a vector x(t
that jointly with u; v steers the system to state x() 2 B  2
(x).
We now propagate this minmax procedure to a sequential minmax problem in the class of
piecewise open-loop controls with k corrections, using the notations of Problem (I k ).
Problem (II k ).
Solve the following consecutive optimization problems.
Find
min
then consecutively, for
min u
min
and finally
min u
This time direct calculation gives
where
(\GammaC(s))Q(s)ds
\Gamma:::
(\GammaC(s))Q(s)ds
\Gamma:::
Z
(\GammaC(s))Q(s)ds
Z
B(s)P(s)ds
We refer to X
as the maxmin OLRS with k corrections at points  k .
Theorem 3.5 The set
is then the mimax OLRS with one corection and is given by formula (38).
Denote
assuming
Under the assumptions and notations of Theorem 3.3, the last results may be summarized
in the following proposition.
Theorem 3.6 (i) For any fixed values ; x one has
(ii) For any fixed ; x and index i 2 [1; k] one has
(iii) The following inclusions are true for
(iv) The following superpositions will also be true
In this section we have considered problems with finite number of possible corrections and
additional information coming at fixed instants of time, having presented a hierarchy of
piecewise open-loop reach sets of the anticipative (maxmin) or of the nonanticipative type.
These were presented as level sets for value functions which are superpositions of "one-
stage" value functions calculated in Section 2. A semigroup-type property (34) for these
value functions was indicated which is true only for the points of correction (Remark 3.1).
In the continuous case, however, we shall need this property to be true for any points. Then
it would be possible to formulate the Principle of Optimality under uncertainty for our class
of problems.
We shall therefore investigate some limit transitions with number of corrections tending to
infinity. This will allow a further possibility of continuous corrections of the control under
unknown disturbances.
4 The alternated integrals and the value functions
We observed above that the open-loop reach sets of both types (maxmin and minmax) are
described as the level sets of some value functions, namely 4
We now propagate this approach, based on using value functions, to systems with continuous
measurements of the state to allow continuous corrections of the control.
First note that inequality
is always true with equality attained, for example, under the following assumption.
Assumption 4.1 There exists a scalar function ffl(t) ? 0 such that
for all
In order to simplify the further explanations, we shall further deal in this section with the
case omitting the last symbol 0 in the notations for
Now note that Lemmas 3.1, 3.2 indicate that each of the functions
may be determined through a sequential procedure,
and a similar one for
. How could one express this procedure in terms of set-valued
For a given partition \Sigma k we have (j  i)
in view of the previous relations (see (27)
-(29)), we may formulate a set-valued analogy of Lemma 3.1.
4 Here, without abuse of notation for
, we shall use symbol (\Delta) rather than the earlier
emphasizing the function (t); used in the respective constructions.
5 The case (\Delta) 6= 0 would add to the length of the expressions, but not to the essence of the scheme. This
case could be treated similarly, with obvious complements.
Lemma 4.1 The following relations are true
In terms of set-valued integrals (43) is precisely the equivalent of (29).
Moreover,
min u
min u
oe l
Similarly, for the sequential minmax, we have
Using notations identical to (42),(43), but with minus changed to plus in the symbols for
k , we have Lemma 4.2.
Lemma 4.2 The following relations are true
In terms of set-valued integrals, formula (46) is precisely the equivalent of (38), provided
Moreover,
min u
oe l
0g.
It is important to emphasize that until now all the relations were derived for a fixed partition
6 Also note that under Assumption 4.1, with X 0 single-valued, one may treat the sets X
as the
Hausdorff limits
What would happen, however, if k increases to infinity with
and would the result depend on the type of partition?
Our further discussion will require an important nondegeneracy assumption.
Assumption 4.2 There exist continuous vector functions
and a number ffl ? 0 such that
(a)
for all the sets
and
for all the sets
whatever be the partition \Sigma k .
This last assumption is further taken to be true without further notice. 7
Observing that (29), (38) have the form of certain set-valued integral sums, ("the alternated
sums"), we introduce the additional notation
Let us now proceed with the limit operation. Take a monotone sequence of partitions
1. Due to inclusions (33) and the boundedness of the sequence
from below by any of the sets X
the sequence I \Gamma (; t
a set-valued limit. Similarly, the inclusions (40) and the boundedness of the sequence
above ensure that it also has a set-valued limit. A more detailed
investigation of this scheme along the lines of [23] would indicate that under assumption
4.2 (a); (b) these set-valued limits do not depend on the type of partition \Sigma k . This leads to
Theorem 4.1.
7 If at some stage this assumption is not fulfilled, it may be applied to sets of type
sufficiently large.
Theorem 4.1 There exist Hausdorff limits I \Gamma (; t
with
These limits do not depend on the type of partition \Sigma k .
Morerover,
so that
We refer to I(; t as the alternated reach set. 8
The proofs of the convergence of the alternated integral sums to their Hausdorff limits and
of the equalities (52) are not given here. They follow the lines of those given in detail in
[14] for problems on sequential maxmimin and minmax considered in backward time (see
also [23], [22], [13]).
Let us now study the behavior of the function
According to (38), (31) the sequence
increasing in i with i !1. This sequence
is pointwise bounded in x by any solution of Problem (II k ) and therefore has a pointwise
limit. Due to (29), Theorem 4.1, and the continuity of the distance function d(x; M) in
lim
and therefore we may conclude that
under condition (48). This yields Theorem 4.2.
Theorem 4.2 Under condition (48) there exists a pointwise limit
lim
limit does not depend on the type of partititon
The alternated integral is the level set of the function
8 A maxmin construction of the indicated type had been introduced in detail in [23], where it was constructed
in backward time, becoming known as the alternated integral of Pontryagin.
does not depend on the partition \Sigma k and due to the properties of minmax
we also come to the following conclusion.
Theorem 4.3 The function satisfies the semigroup property:
for The following inequality is true
min u
Similarly, for the decreasing sequence of functions
we have Theorem 4.4.
Theorem 4.4 (i) Under condition (48) there exists a pointwise limit
lim
limit does not depend on the type of partititon
(ii) The alternated integral is the level set of the function V
I
(iii) The function satisfies the semigroup property:
for
(iv) The following inequality is true
A consequence of (52) is the basic assertion, Theorem 4.5.
Theorem 4.5 With the initial condition the
following equality is true
The function V(; x) satisfies the semigroup property
The last relation follows from (59), (54), (57).
Thus, under the nondegeneracy Assumption 4.2 the two forward alternated integrals I
coincide and so do the value functions
Relations (55), (58), (59) allow us to construct a partial differential equation for the function
V(t; x)-the so-called HJBI (Hamilton-Jacobi-Bellman-Isaacs) equation.
We now investigate the existence of the total derivative dV(t; x)=dt along the trajectories
of system (10). Due to (59), (13), we have
Observing that for d(x; X(t; t of (61) is unique and
taking l 0 (t; may apply the rules for differentiating a
"maximum"-type function [6], to get
Direct calculations indicate that the respective partials exist and are continuous in the
domain D[intD 0 , where
and intD 0 stands for the interior of the respective set.
To find the value of the total derivative take inequalities (58), (55), which may be rewritten
as
and
min u
Dividing both relations by oe ? 0 and passing to the limit with oe ! 0, we get
Since in Theorem 4.5 we had for the linear system (10) we
have
which results in the next proposition.
Theorem 4.6 In the domain D [ intD 0 the value function V(t; x) satisfies the "forward"
equation
over
Equation (63) may be rewritten as
The last theorem indicates that the HJBI equation (63) is satisfied everywhere in the open
domain D [ intD 0 . However, the continuity of the partials @V=@x; @V=@t on the boundary
of the domains D; D 0 was not investigated and in fact may not hold. But it is not difficult
to check that with boundary condition (65) the function V(t; x) will be a minmax solution
to equation (66) in the sense of [26], which is equivalent to the statement that V(t; x) is
a viscosity solution ([3], [20]) to (66), (67). This particularly follows from the fact that
function V(t; x) is convex, being a pointwise limit of convex functions
Let us note here that the problem under discussion may be treated not only as above but
also within the notion of classical solutions to equation (66), (65). Indeed, although all
the results above were proved for the criterion d(x(t in the respective problems, the
following assertion is also true.
Assertion 4.1 Theorems 3.1-3.6, 4.1-4.6, are all true with the criterion d(x(t in the
respective problems substituted by d 2 (x(t
This assertion follows from direct calculations, as in paper [13], with formula (11) substituted
by
The respective value function similar to V(t; x), denoted further as V 1 (t; x), will now be a
solution to (66) with boundary condition
together with its first partials, turns out to be continuous in t; x 2 D[D 0 .
Thus we come to
Theorem 4.7 The function V 1 (t; x)-a classical solution to (66), (67)-satisfies the relation

We have constructed the set X(t; t as the limit of OLRS and the level set of function
V(t; x), (or function V 1 (t; x))-the sequential maxmin or minmax of function d(t;
function d 2 (t; X 0 restriction It remains to show that X(t; t
precisely the set of points that may be reached from X 0 with a certain feedback control
strategy U(t; x), whatever be the function v(t).
Prior to the next section, we wish to note the following. Function V(t;
may be interpreted as the value function for the following
Problem (IV): find the value function
U
x(\Delta)
is a CLC (see Section 1) and X U (\Delta) is the set of all solutions to the
differential inclusion
generated by taken within the interval
Its level set
is precisely the closed-loop reach set. It is the set of such points x 2 IR n that there exists
a strategy U 2 U C which for any solution x(t) of (69), ensures the
inequality . Due to the structure of (69), (A(t) j 0), this is equivalent to
the following definition of closed-loop reachability sets.
Definition 4.1 A closed-loop reachability set X  () is the set of such points x 2 IR n for
each of which there exists a strategy U 2 U C that for every v(\Delta) 2 VO assigns a point x
such that every solution x[t] of the differential inclusion
satifies the inequality d(x[ ]; x)  .
Once the Principle of Optimality (60) is true, it may also be used directly to derive equation
- the HJBI equation for the function V(t; x). Therefore, set X  () (if nonempty), will
be nothing else than the set X(; t defined earlier as the limit of open-loop reach sets.
5 Closed loop reachability under uncertainty
We shall now show that each point of X(t; t may be reached from X 0 with a certain
feedback control strategy U(t; x), whatever be the function v(t).
In order to do this, we shall need the notion of solvability set, (or, in other terms, "the
backward reachability set", see [11], [27], [15]) - a set similar to X(t; t
in backward time. We first recall from [13] some properties of these sets. Consider
Problem find the value function
U
x(\Delta)
where M is a given convex compact set (M 2 convIR n ) and X U is the variety of all trajectories
x(\Delta) of the differential inclusion (69), generated by a given
strategy U 2 U C .
The formal HJBI equation for the value V   (t; x) is
@t
@x
with boundary condition
Equation (71) may be rewritten as
@t
@x
@x
0: (73)
An important feature is that function V   (t; x) may be interpreted as a sequential maxmin
similar to the one in section 3. Namely, taking the interval   t  t 1 , introduce a partition
similar to that of Section 3. For the given partition, consider the recurrence relations
min u
min u
min u
almost everywhere in the respective intervals.
Lemma 5.1 ([13]) With
there exists a pointwise limit
that does not depend upon the type of partition \Sigma k .
The function
We shall refer to
as the sequential maxmin. This function enjoys
properties similar to those of its "forward time" counterpart, the function of section
3. A similar construction is possible for a "backward" version of the sequential minmax.
The level set
is referred to as the closed loop solvability set CLSS at time t, from set M. It may be
presented as an alternated integral of Pontryagin, - the Hausdorff limit of the sequence
I   (t;
Z
Z
Z
under conditions (74). Also presumed is a nondegeneracy assumption similar to Assumption
4.2.
Assumption 5.1 For a given set M 2 convIR n there exists a continuous function fi 3 (t) 2
and a number ffl ? 0, such that
for any whatever be the partition \Sigma k .
This assumption is presumed in the next lemma.
Lemma 5.2 Under condition (76) there exists a Hausdorff limit I   (t;
I   (t;
0:
This limit does not depend on the type of partition \Sigma k and coincides with the CLSS,
I   (t;
From the theory of control under uncertainty and differential games it is known that if
there exists a feedback strategy U(t; x) 2 U C that steers system (10)
from state x(t) = x to set M whatever be the unknown disturbance v(\Delta) ([11], [29], [15]).
Therefore, assuming our assumptions, we just have to prove the
inclusion
or, in view the properties of V(t; x); V   (t; x), that
is the solution to equation (71) with boundary condition
(Recall that V(t 1
Due to the definition of the geometrical difference and of the integral I
check that
We thus have to prove the inclusion
Under assumptions 4.2 (a) taken for 0, or under assumption 4.2,
it is possible to observe, through direct calculation, using the properties of integrals I
(see formulas (29),(75)), that the following holds:
I   (t;
where
and we arrive at Lemma 5.3.
Lemma 5.3 The following inclusion is true
moreover,
Inclusion (79) implies the existence of a feedback strategy U   (t; x) that brings system (10)
from x
Theorem 5.1 Under assumptions 4.1(a), there exists a closed-loop
strategy U   (t; x) ' U C that steers system (10) from x
The strategy U   (t; x) may be found through the solution V(t; x) of equation (71), with boundary
condition (78), as
U   (t;
(if the gradient @V   (t; x)=@x does exist at ft; xg), or, more generally, as
U   (t;
0g.
This is verified by differentiating V(t; x) with respect to t and checking that a.e.
dV
dt
(see [10], [15]).
The previous theorem ensures merely that some point of may be reached from
x   . In order to demonstrate that any point x may be reached from position
ft; x   g, we have to prove the inclusion
for any x ?
is a solution to (66) with boundary condition
But inclusions (82), (83) again follow from the properties of I assuming
both of these set-valued integrals are nonempty. The latter, in its turn, is again ensured
by either assumptions 4.2(a), Assumption 4.1. This leads to
Theorem 5.2.
Theorem 5.2 Under either Assumptions 4.1(a), or 4.1 there
exists a closed-loop strategy U ? (t; x) ' U C that steers system (10) from x  to point
The strategy U ? (t; x) may be found through the solution V ? (t; x) of equation (71), with boundary
condition (84), as
(if the gradient @V ? (t; x)=@x does exist at ft; xg), or, more generally, as
0g.
Remark 5.1. Assumptions 4.1(a), are ensured by Assumption 4.1.
If this does not hold, it is possible to go through all the procedures taking  \Gamma neighborhoods
of sets X(\Delta); W (\Delta) rather than the sets themselves. Then one has to look for the (\Delta)-reach
sets -solvability sets W (t; sufficiently large, so
that X(t; t would surely be nonempty.
Remark 5.2. The emphasis of this paper is to discuss the issue of reachability under uncertainty
governed by unknown but bounded disturbances. This topic was studied here
through a reduction to the calculation of value functions for a successive problems on sequential
and maxmin of certain distance functions or their squares. The latter
problems were dealt with via techniques of convex analysis and set-valued calculus. However
the solution schemes of this paper naturally allow a more general situation which is to
substitute the distance function d(x; M) by any proper convex function OE(x), for example,
with similar results passing through. The more general problems then reduce to those of
this paper.
Thus, given terminal cost function OE(x), it may readily generate a terminal set M as a level
set some ff, with support function ([25])
The given formalisms for decribing reachability are not the only ones available. We further
indicate yet another formal scheme.
6 Reachability and the funnel equations
In this section we briefly indicate some connections between the previous results and those
that can be obtained through evolution equations of the "funnel type" [2], [15].
Consider the evolution equations
lim
oe
with initial condition
and
lim
oe
with
Under some regularity assumptions (similar to Assumption 4.1) which ensure that all the
sets that appear in (87), (88) are nonempty, these equations have solutions which turn to
be set-valued. The solutions almost everywhere. But they
need not be unique. However, the property of uniqueness may be restored if we presume
that are the (inclusion) maximal solutions, (see [15], Sections 1.3, 1.7).
solution X 0 (t) to a funnel equation of type (87), (88) is maximal if it satisfies the inclusion
other solution X (t) to the respective equation with the same initial
condition).
Equations (87), (88) may be interpreted as some limit form of the recurrence equations
\Gammaoe(\GammaC
and
\Gammaoe(\GammaC (t)Q(t) 6= ;:
Indeed, taking, for example solving the recurrence equation (89) for
values of time
oe (0j) to
oe (kj ), we observe that
oe (kj) is similar to I \Gamma (; t
selected with constant oe
\Gamma(\GammaC
is similar to (29)(when and to (43).
Under Assumtion 4.1 a direct calculation leads to the next conclusions.
Lemma 6.1 The following relations are true with
oe
oe
is a maximal solution
to equation (87) with
Therefore, the closed-loop reach set X (; t may be also calculated through the funnel
equation (87) which therefore also describes the dynamics of the level sets of the value
function V(; x) -the solution to the forward HJBI equation (66).
Remark 6.1. As we have seen, equation (87) describes the evolution of the alternated integral
Similarly to that, equation (88) describes the evolution of the alternated
recurrence equations (89), (90) may then serve to be the basis
of numerical schemes for calculating the reach sets.
7 Example
Consider the system
defined on the interval [0;  ], with hard bounds
on the control u and the uncertain disturbance v.
As is known (see, for example, [16]), a parametric representation of the boundary of the
reach set X(; t of system (91) without uncertainty (v(t) j 0) is given by two
curves (see external set in fig.1, generated for x
and where oe  0 is the parameter, (the values oe ? 0 correspond to the vertices of
Similarly, the reach set X(; t in the variable v is given by the curves
According to (7) , the set
which leads to a parametrization of the boundary of this set in the form
(see internal set in fig.1, generated for
so that the OLRS under uncertainty is smaller than X(; 0; x 0 jP(\Delta); f0g)-the
reach set without uncertainty.
Let us now look for the OLRS one correction at time Taking
may figure out that set has to be
bounded by two curves (fig.2)
which gives
we come to intX
Continuing with r
We also observe that with r 2 ! 1=2 we have sufficiently
large.
As indicated above, sets X turn to be empty unless  is sufficiently large.
Continuing our example further, for
\GammaX (2; 0; 0jf0g; Q(\Delta))g;
and
The last set is nonvoid if  is such that B  (0)
\GammaX (2; 0; 0; jf0g; ;. The
smallest value  0 of all such  ensures
For all    0 it is then possible to compare sets
that the latter is smaller than the former (see fig.3, where X shown by the
internal continuous curve, by the external continuous curve and
by the dashed curve).
Fig.1
xFig.2
-226
xFig.3
8 Conclusion
In this paper we deal with one of the recent problems in reachability analysis which is to
specify the sets of points that can be reached by a controlled system despite the unknown
but bounded disturbances in the system inputs. The paper gives a description of several notions
of such reachability and indicates schemes to calculate various types of reach sets. We
consider systems with linear structure and closed-loop controls that are generally nonlinear.
In particular, we emphasize the difference between reachability under open-loop and closed-loop
controls. We distinguish open-loop controls of the anticipative type, which presume
the disturbances to be known in advance, and of the nonanticipative type, which presume
no such knowledge. The nonanticipative open-loop reach set is smaller than the one for anticipative
open-loop controls and the closed loop reach set (which is always nonanticipative)
lies in between. Intermediate reach sets are those generated by piecewise closed-loop controls
that allow on-line measurements of the state space variable at isolated instants of time
- the points of correction. Increasing the number of corrections to infinity and keeping them
dense within the interval under consideration, we came to the case of continuous corrections
- the solution to the problem of reachability under closed-loop (feedback control).
The various types of reach sets introduced here were calculated through two alternative
presentations, namely, either through operations on set-valued integrals or as level sets for
value functions in sequential problems on maxmin or minmax for certain distance functions.
For the closed-loop reachability problem the corresponding value function defines a mapping
that satifies the semigroup property. This property allowed us to formulate the Principle of
Optimality under Uncertainty for the class of problems considered here. The last Principle
allowed to demonstrate that the closed-loop reach set under uncertainty is the level set for
the solution to a forward HJBI equation. On the other hand, the feedback control strategy
that steers a point to its closed-loop reach set (whatever be the disturbance) may be found
from the solution to a backward HJBI equation whose boundary condition is taken from the
solution of the earlier mentioned forward HJBI equation.
This paper leaves many issues for further investigation. For example, there is a strong
demand from many applied areas to calculate reach sets under uncertainty. However, the
given solutions to the problem are not simple to calculate. Among the nearest issues may
be the calculation of the reach sets of this paper through ellipsoidal approximations along
the schemes of [15], [16]. Then, of course, comes the propagation of the results to nonlinear
systems. Here the application of the HJBI technique seems to allow some progress. Needless
to say, similar problems could also be posed for systems with uncertainty in its parameters
or in the model itself, as well as for other types of controlled transition systems.



--R

KUPFERMAN O.

Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations
Optimal Control and Related Minimax Design Prob- lems
Stochastic Transition Systems.
RUBINOV A.

Topics in Control Theory.

SUBBOTIN A.
Control and Observation Under Uncertainty.
Pontryagin's alternated integral in the theory of control synthesis.
N.



MARKUS L.
Optimality and reachability with feedback controls.
SOUGANIDIS P.
Controllers for reachability specifications for hybrid systems.
IVANOV G.


WETS R.
Generalized Solutions of First Order PDE's: the Dynamic Optimization Perspective.
On the Existence of Solutions to a Differential Game.
Existence of Saddle Points in Differential Games.
Reach set Computation Using Optimal Control.
--TR
uncertainty;differential games;reach sets;alternated integral;funnel equations;differential inclusions;closed-loop control;HJBI equation;open-loop control;reachability;dynamic programming