An Open-loop criterion for the solvability of a closed-loop guidance problem with incomplete information: Linear control systems

The method of open-loop control packages is a tool for stating the solvability of guaranteed closed-loop control problems under incomplete information on the observed states. In this paper, a solution method is specified for the problem of guaranteed closed-loop guidance of a linear control system to a convex target set at a prescribed point in time. It is assumed that the observed signal on the system’s states is linear and the set of its admissible initial states is finite. It is proved that the problem under consideration is equivalent to the problem of open-loop guidance of an extended linear control system to an extended convex target set. Using a separation theorem for convex sets, we derive a solvability criterion, which reduces to solving a finite-dimensional optimization problem. An illustrative example is considered.     

Continuity in the parameter of the minimum value of an integral functional over the solutions of an evolution control system

The problem of minimization of an integral functional with an integrand that is nonconvex with respect to the control is considered. We minimize our functional over the solution set of a nonlinear evolution control system with a time-dependent subdifferential operator in a Hilbert space. The control constraint is given by a nonconvex closed bounded set. The integrand, the control constraint, the initial conditions and the operators in the equation describing the control system all depend on a parameter. We consider, along with the original problem, the problem of minimizing an integral functional with an integrand convexified with respect to the control over the solution set of the same system, but now subject to the convexified control constraint. By a solution of the control system we mean a “trajectory–control” pair. We prove that for each value of the parameter the convexified problem has a solution, which is the limit of a minimizing sequence of the original problem, and the minimum value of the functional of the convexified problem is a continuous function of the parameter.     

An extension of set partitioning with application to scheduling problems

The well known problems of set covering, set partitioning and set packing are defined and their interrelationship is considered. A natural generalisation called the extended set partitioning model is presented and the three standard models are shown to be special cases of this generalisation. In addition, the extended model includes another type of set problem which can be of greater use in certain applications. The model forms the basis of a computer assisted bus crew scheduling system developed by the authors. The system is in regular use by Dublin City Services in the Republic of Ireland. Finally, the equivalence between a special case of the set partitioning problem and the shortest route problem is considered and it is shown that this equivalence also applies to the extended model.     

Coincidence criteria for maximal stable bridges in two game problems of approach

We consider a finite-dimensional conflict-controlled system whose behavior on a finite time interval is described by a vector differential equation. We analyze two game problems of approach in the phase space. In both problems the same terminal set is considered: in the first case, one should guarantee that the phase vector of the system reaches the terminal set at the final instant of time; in the second case, the phase vector should reach the terminal set no later than the final time instant. It is natural to assume that the construction of a solution to the first problem is much simpler than the construction of a solution to the second problem; this fact is confirmed by available experience. The paper is devoted to finding conditions on the system and the terminal set under which the solutions to the above problems coincide. Using these conditions, one can replace the solution of the second problem by the simpler solution of the first problem.     

Power domination in graphs

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. In 1998, Haynes et al. considered the graph theoretical representation of this problem as a variation of the domination problem. They defined a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The power domination number γ_P(G) of a graph G is the minimum cardinality of a power dominating set of G. In this paper, we present upper bounds on the power domination number for a connected graph with at least three vertices and a connected claw-free cubic graph in terms of their order. The extremal graphs attaining the upper bounds are also characterized.     

Guidance problem for a distributed system with incomplete information on the state coordinates and an unknown initial state

We study the problem of guaranteed positional guidance of a linear partially observable control system with distributed parameters to a convex target set at a given time. The problem is considered under incomplete information. More precisely, we assume that the system is subjected to an unknown disturbance; in addition, the initial state is assumed to be unknown as well. Further, the sets of admissible disturbances and the set of admissible initial states, which is assumed to be finite, are known. An algorithm for solving the problem is suggested.     

On the problem of output feedback control synthesis under uncertainty and finite-time observers

We consider the problem of controlling a linear system of ordinary differential equations with a linear observable output. The system contains uncertain items (disturbances), for which we know only “hard” pointwise constraints. The problem of synthesizing a control that brings the trajectories of the system into a given target set in finite time is solved under weakened conditions without assuming that the control and the disturbance are of the same type. To this end, we suggest an approach that amounts to constructing an information set and a weakly invariant set with subsequent “aiming” of the first set at the second. Both stages are carried out in a finite-dimensional space, which permits one to use an efficient algorithm for solving the synthesis problem approximately on the basis of the ellipsoidal calculus technique. The results are illustrated by an example in which the control of a linear oscillation system is constructed.     

Differential guidance game with incomplete information on the state coordinates and unknown initial state

We study the problem of guaranteed positional guidance of a linear partially observable control system to a convex target set at a given time. The problem is considered in the case of incomplete information. More precisely, it is assumed that the system is subjected to some unknown disturbance; in addition, the initial state is unknown as well. But the sets of admissible disturbances and the set of admissible initial states are known. The latter is assumed to be finite. We construct an algorithm for solving this problem.     

One control problem of a pencil of trajectories

A linear control problemwith a nonsingleton initial set is dealt with. For this problem,we consider the problem of transforming this initial set along trajectories of a linear controlled system into some fixed terminal set in a finite time using a single control. Various aspects of this control problem are studied using the machinery of support functions.     

On the solution of the trajectory survival problem for a nonlinear dynamical system

Nonlinear control systems possessing the flatness property are encountered in many applied mathematical models. In this paper, a trajectory survival problem is considered for a specific nonlinear system that possesses the above property. A method based on the properties of the system is proposed for constructing a control that solves the trajectory survival problem when the controlled object moves to the goal set within a bounding set containing an obstacle. Results of numerical calculations of the control and the trajectory of a system with a given initial position are presented.     

Asymptotic stabilization of a class of bilinear systems by a variable structure feedback

We consider the problem of stabilization of a homogeneous bilinear system at zero. We assume that the system can be reduced to a form that admits feedback linearization at all points of the phase space outside a set N of measure zero. For such systems, we construct a variable structure feedback solving the stabilization problem under the condition that N is not an invariant set of the closed system.     

Projective-Dual Method for Solving Systems of Linear Equations with Nonnegative Variables

In order to solve an underdetermined system of linear equations with nonnegative variables, the projection of a given point onto its solutions set is sought. The dual of this problem—the problem of unconstrained maximization of a piecewise-quadratic function—is solved by Newton’s method. The problem of unconstrained optimization dual of the regularized problem of finding the projection onto the solution set of the system is considered. A connection of duality theory and Newton’s method with some known algorithms of projecting onto a standard simplex is shown. On the example of taking into account the specifics of the constraints of the transport linear programming problem, the possibility to increase the efficiency of calculating the generalized Hessian matrix is demonstrated. Some examples of numerical calculations using MATLAB are presented.     

Weak Invariance of a Cylindrical Set with Smooth Boundary with Respect to a Control System

We consider the problem of constructing resolving sets for a differential game or an optimal control problem based on information on the dynamics of the system, control resources, and boundary conditions. The construction of largest possible sets with such properties (the maximal stable bridge in a differential game or the controllability set in a control problem) is a nontrivial problem due to their complicated geometry; in particular, the boundaries may be nonconvex and nonsmooth. In practical engineering tasks, which permit some tolerance and deviations, it is often admissible to construct a resolving set that is not maximal. The constructed set may possess certain characteristics that would make the formation of control actions easier. For example, the set may have convex sections or a smooth boundary. In this context, we study the property of stability (weak invariance) for one class of sets in the space of positions of a differential game. Using the notion of stability defect of a set introduced by V.N. Ushakov, we derive a criterion of weak invariance with respect to a conflict control dynamic system for cylindrical sets. In a particular case of a linear control system, we obtain easily verified sufficient conditions of weak invariance for cylindrical sets with ellipsoidal sections. The proof of the conditions is based on constructions and facts of subdifferential calculation. An illustrating example is given.     

An interactive approach to bicriterion loading of a flexible assembly system

This paper presents integer programming formulations and an interactive solution procedure for a bicriterion loading problem in a flexible assembly system. The system is made up of a set of assembly stations linked with an automated material handling system. In the system, several different product types can be assembled simultaneously. The problem objective is to assign assembly tasks and products to stations with limited working space, so as to balance the station workloads and to minimize station-to-station product transfer time, subject to precedence relations among the tasks for a mix of product types. The solution procedure proposed is based on the weighting method and the interactive search for a set of weights which would produce the most preferred nondominated solution. Numerical examples are included to illustrate possible applications of the interactive approach for various problem formulations proposed.     

Suboptimal target control for hybrid automata using model predictive control

In this paper, a computationally efficient controller is proposed for the target control problem when the system is modelled by hybrid automata. The design is carried out in two stages. First, we compute off-line the shortest switching path which has the minimum discrete cost from an initial set to the given target set. Next, a controller is derived which successfully drives the system from any given initial state in the initial set to the target set while minimizing a cost function. The model predictive control (MPC) technique is used when the current state is not within a guard set, otherwise the mixed-integer predictive control (MIPC) technique is employed. An on-line, semi-explicit control algorithm is derived by combining these two techniques. When the system is subject to additive bounded disturbance, it is shown that the proposed on-line control algorithm holds if tighter constraints on the original nominal state and controller are imposed. Finally, as an application of the proposed control procedure, the high-speed and energy-saving control problem of the CPU processing is considered.     

On Generalizations of the Frank-Wolfe Theorem to Convex and Quasi-Convex Programmes

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or a quasi-convex polynomial function over the feasible set defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities, where the faithfully convex functions satisfy some mild assumption. The conditions are provided in the form of an algorithm, terminating after a finite number of iterations, the implementation of which requires the identification of implicit equality constraints in a homogeneous linear system. We prove that the optimal solution set of the considered problem is nonempty, this way extending the attainability result well known as the so-called Frank-Wolfe theorem. Finally we show that our extension of the Frank-Wolfe theorem immediately implies continuity of the solution set defined by the considered system of (quasi)convex inequalities.     

Feedback Stabilization Methods for the Solution of Nonlinear Programming Problems

In this work, we show that, given a nonlinear programming problem, it is possible to construct a family of dynamical systems, defined on the feasible set of the given problem, so that: (a) the equilibrium points are the unknown critical points of the problem, which are asymptotically stable, (b) each dynamical system admits the objective function of the problem as a Lyapunov function, and (c) explicit formulas are available without involving the unknown critical points of the problem. The construction of the family of dynamical systems is based on the Control Lyapunov Function methodology, which is used in mathematical control theory for the construction of stabilizing feedback. The knowledge of a dynamical system with the previously mentioned properties allows the construction of algorithms, which guarantee the global convergence to the set of the critical points.     

Multistate components assignment problem with optimal network reliability subject to assignment budget

The typical assignment problem for finding the optimal assignment of a set of components to a set of locations in a system has been widely studied in practical applications. However, this problem mainly focuses on maximizing the total profit or minimizing the total cost without considering component’s failure. In practice, each component should be multistate due to failure, partially failure, or maintenance. That is, each component has several capacities with a probability distribution and may fail. When a set of multistate components is assigned to a system, the system can be treated as a stochastic-flow network. The network reliability is the probability that d units of homogenous commodity can be transmitted through the network successfully. The multistate components assignment problem to maximize the network reliability is never discussed. Therefore, this paper focuses on solving this problem under an assignment budget constraint, in which each component has an assignment cost. The network reliability under a components assignment can be evaluated in terms of minimal paths and state-space decomposition. Subsequently an optimization method based on genetic algorithm is proposed. The experimental results show that the proposed algorithm can be executed in a reasonable time.     

Small Motions of a Partially Dissipative Hydrodynamic System

A new problem is discussed: small motions of the hydrodynamic system {viscous fluid + set of ideal fluids}. The conditions are determined for the existence of a strong solution of the initial/boundary-value problem corresponding to small motions of the investigated hydrodynamic system, subject to the condition that the system is statically stable in the linear approximation.