Necessary first-order conditions for optimal crossing of a given region

We consider a nonlinear optimal control problem with an integral functional in which the integrand is the characteristic function of a closed set in the phase space. An approximation method is applied to prove the necessary conditions of optimality in the form of a Pontryagin maximum principle without any prior assumptions on the behavior of the optimal trajectory. Similarly to phase-constrained problems, we derive conditions of nondegeneracy and pointwise nontriviality of the maximum principle. __________ Translated from Nelineinaya Dinamika i Upravlenie, No. 4, pp. 179–204, 2004.     

Quadratic convergence algorithms for the problem of capture of a point by a family of convex bodies

We consider the nonlinear optimal control problem with an integral functional in which the integrand function is the characteristic function of a given closed set in the phase space. The approximation method is applied to prove the necessary conditions of optimality in the form of the Pontryagin maximum principle without any prior assumptions on the behavior of the optimal trajectory. Similarly to the case of phase-constrained problems, we derive conditions of nondegeneracy and pointwise nontriviality of the maximum principle. __________ Translated from Nelineinaya Dinamika i Upravlenie, No. 4, pp. 241–256, 2004.     

Partial Differential Equation for Evolution of Star-Shaped Reachability Domains of Differential Inclusions

The problem of reachability for differential inclusions is an active topic in the recent control theory. Its solution provides an insight into the dynamics of an investigated system and also enables one to design synthesizing control strategies under a given optimality criterion. The primary results on reachability were mostly applicable to convex sets, whose dynamics is described through that of their support functions. Those results were further extended to the viability problem and some types of nonlinear systems. However, non-convex sets can arise even in simple bilinear systems. Hence, the issue of nonconvexity in reachability problems requires a more detailed investigation. The present article follows an alternative approach for this cause. It deals with star-shaped reachability sets, describing the evolution of these sets in terms of radial (Minkowski gauge) functions. The derived partial differential equation is then modified to cope with additional state constraints due to on-line measurement observations. Finally, the last section is on designing optimal closed-loop control strategies using radial functions.     

Global reachability results for systems with constrained controllers

The global reachability problem is to determine if, given a specified initial state, the state of a system can be steered via an admissible control to every point in the state space. This paper addresses the problem of global reachability when there are magnitude constraints on the controls. Necessary conditions and sufficient conditions for a system to be globally reachable are presented. The results are compared with those available for the global controllability problem.Dedicated to G. LeitmannThe research of the first author was supported by the National Science Foundation under Grant No. ECS-82-10284.     

Falsification of hybrid systems with symbolic reachability analysis and trajectory splicing

The falsification of a hybrid system aims at finding trajectories that violate a given safety property. This is a challenging problem, and the practical applicability of current falsification algorithms still suffers from their high time complexity. In contrast to falsification, verification algorithms aim at providing guarantees that no such trajectories exist. Recent symbolic reachability techniques are capable of efficiently computing linear constraints that enclose all trajectories of the system with reasonable precision. In this paper, we leverage the power of symbolic reachability algorithms to improve the scalability of falsification techniques. Recent approaches to falsification reduce the problem to a nonlinear optimization problem. We propose to reduce the search space of the optimization problem by adding linear state constraints obtained with a reachability algorithm. An empirical study of how varying abstractions during symbolic reachability analysis affect the performance of solving a falsification problem is presented. In addition, for solving a falsification problem, we propose an alternating minimization algorithm that solves a linear programming problem and a non-linear programming problem in alternation finitely many times. We showcase the efficacy of our algorithms on a number of standard hybrid systems benchmarks demonstrating the performance increase and number of falsifyable instances.     

On the construction of direct and reverse relations of linear control systems

We suggest a constructive method for finding controls D(x) that take zero of the phase space of a complete reachable linear control system with constant coefficients and with a conical set of control constraints to each point x of the phase space. The method is based on the idea of successive reduction of the problem dimension.     

Compactifiers in extension constructions for reachability problems with constraints of asymptotic nature

A reachability problem with constraints of asymptotic nature is considered in a topological space. The properties of a rather general procedure that defines an extension of the problem are studied. In particular, we specify a rule that transforms an arbitrary extension scheme (a compactifier) into a similar scheme with the property that the continuous extension of the objective operator of the reachability problem is homeomorphic. We show how to use this rule in the case when the extension is realized in the ultrafilter space of a broadly understood measurable space. This version is then made more specific for the case of an objective operator defined on a nondegenerate interval of the real line.     

Some topological structures of extensions of abstract reachability problems

We consider the problem of the reachability of states that are elements of a topological space under constraints of asymptotic nature on the choice of an argument of a given objective mapping. We study constructions that have the sense of extensions of the original space and are implemented with the use of methods that are natural for applied mathematics but employ elements of extensions used in general topology. The study is oriented towards the application in the problem on the construction and investigation of properties of reachability sets for control systems.Constructions involving an approximate observation of constraints in control problems, as well as various generalized regimes, were widely used by N.N. Krasovskii and his students. In particular, this approach was applied in the proof of N.N. Krasovskii and A.I. Subbotin’s fundamental theorem of the alternative, which made it possible to establish the existence of a saddle point in a nonlinear differential game. In the investigation of impulse control problems, Krasovskii used techniques from the theory of generalized functions, which formed the basis for many studies in this direction. A number of A.B. Kurzhanski’s papers are devoted to the solution of control problems related in one way or another to the construction of reachability sets. Control problems with incomplete information, duality issues for control and observation problems, and team control problems constitute a far from exhaustive list of research areas where Kurzhanskii obtained profound results. These studies are characterized by the use of a wide range of tools and methods from applied mathematics and various constructions as well as by the combination of theoretical investigations and procedures related to the possibility of computer modeling.The research direction developed in the present paper mainly concerns the problem of constraint observation (including “asymptotic” constraints) and involves other issues. Nevertheless, the idea of constructing generalized elements of various nature (in particular, generalized controls) seems to be useful for the purpose of asymptotic analysis of control problems that do not possess stability as well as problems on the comparison of different tendencies in the choice of control in the form of dependences on a complex of factors inherent in the original real-life problem. The use of such tools as the Stone–?ech compactification and Wallman’s extension is, of course, oriented toward the study of qualitative issues. In the authors’ opinion, the combined application of the approaches to the construction of extensions used in control theory and in general topology holds promise from the point of view of both pure and applied mathematics. Apparently, the present paper can be considered as a certain step in this direction.     

Barbashin and krasovskii’s asymptotic stability theorem in application to control systems on smooth manifolds

We introduce the notion of so-called standard control system, whose phase space is a finite-dimensional smooth manifold satisfying a number of conditions; in particular, it is supposed to be connected, orientable, and having a countable atlas. For a given standard control system, we consider a set of time translations and construct the closure of this set in the topology of uniform convergence on compact sets. In these terms, we study the conditions of uniform local reachability of a given trajectory. The main result is formulated in terms of a modified Lyapunov function. A simple example is considered.     

A STOCHASTIC REPRESENTATION FOR THE LEVEL SET EQUATIONS

ABSTRACT

A Feynman-Kac representation is proved for geometric partial differential equations. This representation is in terms of a stochastic target problem. In this problem the controller tries to steer a controlled process into a given target by judicial choices of controls. The sublevel sets of the unique level set solution of the geometric equation is shown to coincide with the reachability sets of the target problem whose target is the sublevel set of the final data.     

Stabilization by a linear feedback under phase constraints

We suggest a new method for solving the stabilization problem under phase constraints with the use of linear matrix inequalities. We consider the cases of complete and incomplete state measurements and the presence of nonstationary parametric perturbations. In the synthesis of linear control laws, the suggested method permits one to cover all possible quadratic Lyapunov functions and indicate a set of initial values for trajectories satisfying the phase constraints.     

Algorithm for determining the reachability set of a linear control system

We present in this paper algorithms for calculating the reachability set of a linear control system with a bounded closed control set and a finite time interval. We also present algorithms for the time-optimal problem of the linear control that yields an approximation to the optimal time and the corresponding control function. We give numerical examples of the computer implementation of these algorithms.This research was supported by the National Science Foundation of China.The authors are grateful to an anonymous referee for constructive suggestions that greatly helped to improve the presentation.     

Liapunov reachability and optimization in control

In this paper, we find sufficient conditions that do not rely upon any Liapunov stability results for the reachability of the target set by an admissible control from ana priori specified set of states. The conditions found are less restrictive than those obtained by Sticht, Vincent, and Schultz in Ref. 1. For control problems with specific integral performance index, we also show that, if a quantitative Liapunov function for optimization exists, then it may also serve as a qualitative Liapunov function ensuring the reachability of the target. The results are illustrated by examples.     

Mathematical programming approach to the Petri nets reachability problem

This paper focuses on the resolution of the reachability problem in Petri nets, using the mathematical programming paradigm. The proposed approach is based on an implicit traversal of the Petri net reachability graph. This is done by constructing a unique sequence of Steps that represents exactly the total behaviour of the net. We propose several formulations based on integer and/or binary linear programming, and the corresponding sets of adjustments to the particular class of problem considered. Our models are validated on a set of benchmarks and compared with standard approaches from IA and Petri nets community.     

Fractional delay control problems: topological structure of solution sets and its applications

This paper deals with the control problems of semilinear fractional delay evolution equations. Under rather mild conditions, we study the topological structure of solution sets (compactness and R_δ-property). Then, the information about the structure is employed to show the invariance of a reachability set of the control problem under nonlinear perturbations. Finally, we present an example to illustrate the feasibility of the abstract results.     

Maximum principle in the problem of time optimal response with nonsmooth constraints : PMM vol. 40, n 6, 1976, pp. 1014–1023

The problem of optimal response [1, 2] with nonsmooth (generally speaking, nonfunctional) constraints imposed on the state variables is considered. This problem is used to illustrate the method of proving the necessary conditions of optimality in the problems of optimal control with phase constraints, based on constructive approximation of the initial problem with constraints by a sequence of problems of optimal control with constraint-free state variables. The variational analysis of the approximating problems is carried out by means of a purely algebraic method involving the formulas for the incremental growth of a functional [3, 4] and the theorems of separability of convex sets is not used.Using a passage to the limit, the convergence of the approximating problems to the initial problem with constraints is proved, and for general assumptions the necessary conditions of optimality resembling the Pontriagin maximum principle [1] are derived for the generalized solutions of the initial problem. The conditions of transversality are expressed, in the case of nonsmooth (nonfunctional) constraints by a novel concept of a cone conjugate to an arbitrary closed set of a finite-dimensional space. The concept generalizes the usual notions of the normal and the normal cone for the cases of smooth and convex manifolds.     

Stability analysis of probabilistic Boolean networks with switching topology

This paper investigates the set stability of probabilistic Boolean networks (PBNs) with switching topology. To deal with this problem, two novel concepts, set reachability and the largest invariant set family, are defined. By constructing an auxiliary system, the necessary and sufficient conditions for verifying set reachability are given and the calculation method for the largest invariant set family is obtained. Based on these two results, an equivalent condition of set stability is derived, which can be used to determine whether a PBN with switching topology can be stabilized to a given set. In addition, the design method of switching signal is proposed by combining the characteristic of the largest invariant set family, and a numerical example is reported to demonstrate the efficiency of presented approach.     

Dynamic programming for stochastic target problems and geometric flows

Given a controlled stochastic process, the reachability set is the collection of all initial data from which the state process can be driven into a target set at a specified time. Differential properties of these sets are studied by the dynamic programming principle which is proved by the Jankov-von Neumann measurable selection theorem. This principle implies that the reachability sets satisfy a geometric partial differential equation, which is the analogue of the Hamilton-Jacobi-Bellman equation for this problem. By appropriately choosing the controlled process, this connection provides a stochastic representation for mean curvature type geometric flows. Another application is the super-replication problem in financial mathematics. Several applications in this direction are also discussed. Received October 24, 2000 / final version received July 24, 2001?Published online November 27, 2001     

Local convexity conditions for reachability tubes of distributed control systems

For a nonlinear functional operator equation describing a wide class of controlled initial boundary-value problems we introduce the notion of an abstract reachability set analogous to the notion of a reachability tube. We obtain local sufficient conditions for the convexity of such a set. We consider a mixed boundary-value problem associated with a semilinear hyperbolic equation of the second order in a rather general form as an example illustrating the reduction of a controlled initial boundary-value problem to the studied equation, as well as the verification of the stated assumptions.