We consider the following question: given a continuous-time non-deterministic (not necessarily time-invariant) dynamical system, is it true that for each initial condition there exists a global-in-time trajectory. We study this question for a large class of systems, namely the class of complete non-deterministic Markovian systems. We show that for this class of systems, the question can be answered using analysis of existence of locally defined trajectories in a neighborhood of each time.
In this paper we consider the following question: given a continuous-time nondeterministic (not necessarily time-invariant) dynamical system Σ, is it true that for any time moment t0 and initial state x0 there exists a global-in-time trajectory t 7→ s(t) such that s(t0) = x0.
Some related problems, e.g. global existence of solutions of initial value
problems for various classes of diferential equations [
For deterministic systems the existence of a global trajectory for each initial condition implies that each partial trajectory (e.g. defined on a proper open interval of the real time scale) can be extended to a global trajectory. But this is not necessary for non-deterministic systems. For example, for each initial condition x(t0) = x0 the diferential inclusion ddxt ∈ [0, x2] has both a globally defined constant trajectory x(t) = x0 and a trajectory of the equation ddxt = x2 which escapes to infinity in finite time. Thus it is not true that any (locally defined) solution extends infinitely into future.
We will study our existence question for a large class of systems, namely the class of complete non-deterministic Markovian systems. We will show that for this class of systems, the question can be answered using analysis of existence of locally defined trajectories in a neighborhood of each time.
Note that in this paper we use the term Markovian in the context of purely non-deterministic (i.e. non-stochastic) systems. The formal definition will be given below. Also note that many well-known classes of continuous-time systems either belong to this class of can be represented by systems of this class. We will give examples later in the paper. 2
Non-deterministic Complete Markovian Systems
The notions of a Markov process or system [
General definitions of continuous-time Markovian systems of such kind have
appeared in the literature [
Below we define the notion of a non-deterministic (complete) Markovian
system in spirit of, but not exactly as in [
We will use the following notation: N = {1, 2, 3, ...}, N0 = N ∪ {0}, f : A → B is a total function from A to B, f : A →˜B is a partial function from A to B, f |X is the restriction of a function f to a set X, 2A is the power set of a set A. The notation f (x) ↓ (f (x) ↑) means that f (x) is defined (resp. undefined) on the argument x, dom(f ) = {x | f (x) ↓}. Also, ¬, ∨, ∧, ⇒, ⇔ denote the logical operations of negation, disjunction, conjunction, implication and equivalence correspondingly. Let us denote: – T = [0, +∞) is the (real) time scale. We assume that T is equipped with a topology induced by the standard topology on R – T is the set of all connected subsets of T with cardinality greater than one.
For the purpose of this paper, we will use the following definition of a dynamical system on the time scale T .
Definition 1. A dynamical system on T is as an abstract object M (a mathematical model; in applications this may be an equation, inclusion, switched system, etc.) together with the associated time scale T (this scale will be the same throughout the paper), the set of states Q, and the set of (partial) trajectories T r. A trajectory is a function s : A → Q, where A ∈ T (note that trivial trajectories defined on singleton or empty time sets are excluded). The set T r satisfies the property: if s : A → Q ∈ T r, B ∈ T, and B ⊆ A, then s|B ∈ T r. We will refer to this property as ”Tr is closed under proper restrictions (CPR)”.
We will say that a trajectory s1 ∈ T r is a subtrajectory of s2 ∈ T r (denoted as s1 v s2), if s1 = s2|A for some A ∈ T. The trajectories s1 and s2 are incomparable, if s1 is not a subtrajectory of s2 and vice versa.
According to the definition given above, for a time t0 ∈ T and q0 ∈ Q there may exist multiple incomparable trajectories s such that s(t0) = q0 (as well as one or none). In this sense a dynamical system can be non-deterministic.
It is easy to see that (T r, v) is a partially ordered set (poset).
Definition 2.
A set T r (which is CPR) is s2(t), t ∈ dom(B)
.
s(t) = – complete, if (T r, v) is a chain-complete poset (every chain has a supremum) – Markovian, if s ∈ T r for each s1, s2 ∈ T r and t ∈ T such that t = sup dom(s1) = inf dom(s2), s1(t) ↓, s2(t) ↓, and s1(t) = s2(t), where (s1(t), t ∈ dom(A)
Note that because T r is closed under restrictions to sets A ∈ T, the supremum of a chain c in poset (T r, v) exists if s∗ ∈ T r, where s∗ : Ss∈c dom(s) → Q is defined as follows: s∗(t) = s(t), if s ∈ c and t ∈ dom(s) (this definition is correct, because c is a chain with respect to subtrajectory relation).
The notions of complete and Markovian sets of trajectories are illustrated in Fig. 1 and 2.
The following proposition gives some examples of sets of trajectories. Proposition 1. Let Q = R. Consider the following sets of trajectories: – T rall is the set of all functions s : A → Q, A ∈ T. – T rcont is the set of all continuous functions s ∈ T rall (on their domains) – T rdiff is the set of all diferentiable functions s ∈ T rall (on their domains) – T rbnd is the set of all bounded functions s ∈ T rall (on their domains).
(1) ∅, T rall, T rcont, T rdiff , T rbnd, T rdiff ∩ T rbnd are CPR (2) ∅, T rall, T rcont are complete and Markovian (3) T rdiff is complete, but is not Markovian (4) T rbnd is Markovian, but is not complete (5) T rdiff ∩ T rbnd is neither complete, nor Markovian.
Definition 3. A non-deterministic complete Markovian system (NCMS) is dynamical system is (M, T, Q, T r) such that T r is complete and Markovian.
The following propositions 2-4 give some examples of NCMS.
Proposition 2. Let Q = Rd (d ∈ N) and M be a diferential equation ddyt = f (t, y), where f : R × Rd → Rd is a given total function. Let T r be the set of all functions s : A → Q, A ∈ T such that s is diferentiable on A and satisfies M on A. Then (M, T, Q, T r) is a NCMS.
Proposition 3. Let M be a diferential inclusion ddyt = F (t, y), where F : R × Rd → 2Rd is a given (total) function. This is not necessarily a NCMS, but it can be converted to a NCMS as follows. Let M 0 be the system y ∈ F (t, x) where x is a new variable. Let Q = Rd × Rd and T r be the set of all s : A → Q, A ∈ T such that s is locally absolutely continuous on A and satisfies M 0 almost everywhere on A (w.r.t. Lebesgue’s measure). Then (M, T, Q, T r) is a NCMS. ( ddyt = x Proposition 4. Let Q be a set equipped with discrete topology. Let r ⊆ Q × Q be (y(t+) = y(t), a relation on Q. Let M be a system t ∈/ N0 , where y denotes (y(t), y(t+)) ∈ r, t ∈ N0 an unknown function, y(t+) denotes the right limit at t. Let T r be the set of all piecewise-constant left-continuous functions s : A → Q (w.r.t. discrete topology on Q) which satisfy M on A (see Fig. 3). Then (M, T, Q, T r) is a NCMS.
A predicate p : ST (Q) → Bool (Bool = {true, f alse}) is called . – left-local, if p(s1, t) ⇔ p(s2, t) whenever (s1, t), (s2, t) ∈ ST (Q) and s1 =t− s2, and moreover, p(s, t) whenever t is the least element of dom(s) . – right-local, if p(s1, t) ⇔ p(s2, t) whenever (s1, t), (s2, t) ∈ ST (Q), s1 =t+ s2, and moreover, p(s, t) whenever t is the greatest element of dom(s) – left-stable, if whenever t is not the least element of dom(s), p(s, t) implies that there exists t0 ∈ [0, t) such that p(s, τ ) for all t0 ∈ [t0, t] ∩ dom(s) – right-stable, if whenever t is not the greatest element of dom(s), p(s, t) implies that there exists t0 > t such that p(s, τ ) for all τ ∈ [t, t0] ∩ dom(s).
The theorems given below show how left- and right-local predicates can be used to specify/represent a complete Markovian set of trajectories (or system). Theorem 1. Let l : ST (Q) → Bool be a left-local predicate and r : ST (Q) → Bool be a right-local predicate. Then the set
T r = {s : A → Q | A ∈ T ∧ (∀t ∈ A l(s, t) ∧ r(s, t))}. is CPR, complete, and Markovian.
Theorem 2. Let T r be a CPR complete Markovian set of trajectories which take values in the set of states Q. Then there exist unique predicates l, r : ST (Q) → Bool such that l is left-local and left-sable, r is right-local and right-stable, and
T r = {s : A → Q | A ∈ T ∧ (∀t ∈ A l(s, t) ∧ r(s, t))}.
Let us consider an example which illustrates these theorems. Let Q = Rd and T r be the set of all functions s : A → Q, A ∈ T such that s is diferentiable on A and satisfies a diferential equation ddyt = f (t, y) on A, where f : R × Rd → Rd is a given function. Then T r is complete and Markovian by Proposition 2.
Let us show how T r can be represented using left- and right-local predicates. Let l, r : ST (Q) → Bool be predicates such that – l(s, t) if either t is the least element of dom(s), or ∂−s(t) ↓= f (t, s(t)), – r(s, t) if either t is the greatest element of dom(s), or ∂+s(t) ↓= f (t, s(t)), where ∂−s(t) and ∂+s(t) denote the left- and right- derivative of s at t (the symbol ↓ indicates that the left hand side of the equality is defined). It is not dificult to check that l is left-local, r is right-local, and T r = {s : A → Q | A ∈ T ∧ (∀t ∈ A l(s, t) ∧ r(s, t))}. In general case, l and r are not necessarily (respectively) leftand right-stable. But we can define another predicates l∗, r∗ on ST (Q) such that – l∗(s, t) if either t is the least element of dom(s), or there exists t0 < t such that s is diferentiable on ( t0, t] and satisfies diferential equation ddyt = f (t, y) on (t0, t] (at the time t the derivative is understood as left-derivative). – r∗(s, t) if either t is the greatest element of dom(s), or there exists t0 > t such that s is diferentiable on [ t, t0) and satisfies ddyt = f (t, y) on [t, t0). Then it is not dificult to see that l∗ is left-local and left-stable, and r∗ is rightlocal and right-stable, and T r = {s : A → Q | A ∈ T ∧ (∀t ∈ A l(s, t) ∧ r(s, t))}.
Existence of Global-in-Time Trajectories Let us recall our original question about global-in-time trajectories and formulate it for non-deterministic complete Markovian systems.
Let (M, T, Q, T r) be a NCMS. Our question (let us denote it as Q0) is whether it is true that for each t0 ∈ T , q0 ∈ Q there exists a trajectory s : T → Q (i.e. global-in-time) such that s(t0) = q0.
Note that we ask about existence of a trajectory defined in both time directions relative to t0. The case when we are interested in existence of a trajectory defined in one direction (e.g s : [t0, +∞) → Q) is not considered in this paper, but can be studied analogously.
Let us decompose Q0 into the following two questions:
Q1: Is it true that for each t0 ∈ T , q0 ∈ Q there exists a (partial) trajectory
s : A → Q such that t0 is an interior point of A (relative to the topology on
T , e.g. 0 is considered an interior point of [
The question Q1 is about existence of a local-in-time trajectories. We will not study it in this paper and assume that it can be answered using domain-specific methods. Our aim is to answer Q2 using only information about existence of locally defined trajectories in the neighborhood of each time moment.
Let us introduce several definitions. Let Σ = (M, T, Q, T r) be a fixed NCMS. Definition 6. – A right dead-end path (in Σ) is a trajectory s : A → Q such that A has a form [a, b), where a, b ∈ T . and there is no s0 : [a, b] → Q ∈ T r such that s = s0|dom(s) (i.e. s cannot be extended to a trajectory on [a, b]).
The value b is called the end of this path. – A left dead-end path (in Σ) is a trajectory s : A → Q such that A has a form (a, b], where a, b ∈ T . and there is no s0 : [a, b] → Q ∈ T r such that s = s0|dom(s). The value a is called the end of this path. – A dead-end path is either a right dead-end path, or a left dead-end path.
Let f : [0, +∞) → [0, +∞) be a positive-definite (i.e. f (0) = 0, f (x) > 0 when x > 0), monotonously non-decreasing, and continuous function (e.g. f (x) = x). Definition 7. – A right dead-end path s : [a, b) → Q is called f -Ob-escapable, where Ob is a connected neighborhood of b, if there exists c ∈ (a, b) ∩ Ob, d ∈ [b + f (b − c), +∞), and a trajectory s0 : [c, d] ∩ Ob → Q such that s(c) = s0(c). – A left dead-end path s : (a, b] → Q is called f -Ob-escapable, where Ob is a connected neighborhood of b, if there exists c ∈ (a, b) ∩ Ob, d ∈ [0, max{a − f (c − a), 0}], and a trajectory s0 : [d, c] ∩ Ob → Q such that s(c) = s0(c). – A right- or left- dead-end path is called f -escapable, if it is f -T -escapable. This definition is illustrated in Fig. 4. Note that a sufix of a right dead-end path s : [a, b) → Q (i.e. a restriction of the form s|[a0,b), where a0 ∈ [a, b)) is a right dead-end path. Analogously, a prefix of a left dead-end path s : (a, b] → Q (i.e. a restriction of the form s|(a,b0], where b0 ∈ (a, b]) is a left dead-end path.
Let Σ = (M, T, Q, T r) be a NCMS. For each t ∈ T let Ot ⊆ T be some connected neighborhood of t and Dt be the set of all dead-end paths s (in Σ) such that t is the end of s and dom(s) ⊆ Ot.
(1) for each partial trajectory s : A → Q such that A is a compact segment there exists a trajectory s0 : T → Q such that s = s0|A (2) each dead-end path (in Σ) is f -escapable (3) for each t ∈ T and s ∈ Dt, s is f -Ot-escapable.
Note that this theorem holds for an arbitrary fixed f and arbitrary fixed choice of neighborhoods Ot, t ∈ T .
This theorem gives an answer to the question Q2. The condition 3 of this theorem shows in which sense Theorem 3 reduces the question of global-in-time existence of trajectories to the analysis of local existence of trajectories in the neighborhood of each time moment. We have studied the question of existence of global-in-time trajectories for each initial condition of a (non-time-invariant) non-deterministic complete Markovian system. We have shown that this question can be answered using analysis of existence of locally defined trajectories in a neighborhood of each time. The results can be useful for studying the problems of well-posedness and reachability for continuous and discrete-continuous (hybrid) dynamical systems.