Programmed Iteration Method in Differential Games with a Functional Target Set

A variant of the programmed iteration method is developed for solving game problems of realizing trajectories of a nonlinear conflict controlled system in a given set of functions. Solving these open-loop control problems yields an iterative process in a space of sets whose elements are functional positions, and the corresponding limit determines the set of successful solvability of the original problem in the class of set-valued quasi-strategies (nonanticipating responses to disturbances). For the conflict controlled system, the conditions of generalized uniqueness and uniform boundedness of programmed motions are assumed to hold. The use of an infinite-dimensional space of functional positions is essential, since the arising differential game generally does not satisfy the alternative solvability conditions in classes of feedback strategies.     

On the Optimal Stabilisation for a set of Programmed Motions of the Bilinear Control System

During recent years there has been considerable interest in using bilinear systems [1, 2] as mathematical models to represent the dynamic behavior of a wide class of engineering, biological and economic systems. Moreover, there are some methods [3] which may approximate nonlinear control systems by bilinear systems. For the first time Zubov has proposed a method of stabilization control synthesis for a set of programmed motions in linear systems [4]. In papers [5, 6] this method has been developed and used to solve the same problem for bilinear systems. In the present paper the following problems are considered. First, synthesis of nonlinear control as feedback under which the bilinear control system has a given set of programmed and asymptotic stable motions. Because this control is not unique, the second problem concerns optimal stabilization. In this paper a method for the design of nonlinear optimal control is suggested. This control is constructed in the form of a convergent series. The theorem on the sufficient conditions to solve this problem is represented.     

Modelling of the controlled motion ofa point on a plane

A solution of the problem of feedback control of the motion of a point on a plane is presented. The equations of the controlprogramme (the objective) are set up as a system of differential equations with a given set of singular trajectories in the domain of admissible positions of the controlled point, as well as a given topological structure of the partition into trajectories. These equations define the vector field of velocities of the programmed motions of the point and are used to find the corresponding control forces.     

Programmed iteration method in packages of spaces

An abstract version of the programmed iteration method (used in the theory of differential games) is considered that is intended for the problem of observing phase constraints on a nonempty subset of the real line. It is assumed that trajectories and uncontrolled disturbances are realized in packages of mutually inconsistent spaces. This consistency is postulated to investigate solvability conditions for the problem in the class of quasi-strategies. As a result, the set of successful solvability is constructed and the structure of resolving strategies is determined.     

Two evasion problems in a plane with separate controls and non-convex terminal sets

Two different pursuit-evasion games are considered from the evader's point of view. The phase space is a plane, each of the two players controlling the motion of a point only along its own coordinate. The terminal sets are not convex; in the first problem, the set is an arc of a circle, in the second, the union of tow segments. In both games evasion cannot the achieved by means of programmed controls, but it can be achieved using feedback control. However, the strategies, which are continuous functions of the phase vector, have different properties in each problem. In the first, they cannot guarantee evasion (which is typical for the linear-convex case as well), but in the second they can (which is impossible in linear-convex games with a fixed final time). Verification that evasion is unachievable using such strategies reduces here to proving the solvability of a certain initial-value problem for an advanced differential equation, to which the Schauder principle is applicable.     

A Decision Model for a Sequential Testing Problem in civil Engineering

A sequential decision problem in civil engineering is formulatedas a dynamic programming model. A set of theorems lead to amore efficient formulation, permitting the solution routineto be programmed on a microcomputer. The solution is printedin table fonn, directly providing a decision rule usable bythe foreman in the field. The paper illustrates a point whichis becoming increasingly apparent: the power and availabilityof portable computer systems are making many decision problemsamenable to on-site analysis using models based upon rigoroustheory.     

Construction of Programmed Controls for a Dynamic System Based on the Set of its First Integrals

Based on the set of first integrals, we solve a programmed control problem for a nonlinear dynamic system with a random noise.     

The synthesis of multi-programme controls in bilinear systems

The problem of synthesizing multi-programme controls is considered for a bilinear time-dependent control system with mutli-dimensional input. An existence and representation theorem is proved for a control under which the initial system is capable of performing a given set of programmed motions, each of which is asymptotically stable in Lyapunov's sense.     

New computational results on the discrete time/cost trade-off problem in project networks

We describe a new exact procedure for the discrete time/cost trade-off problem in deterministic activity-on-the-arc networks of the CPM type, where the duration of each activity is a discrete, nonincreasing function of the amount of a single resource (money) committed to it. The objective is to construct the complete and efficient time/cost profile over the set of feasible project durations. The procedure uses a horizon-varying approach based on the iterative optimal solution of the problem of minimising the sum of the resource use over all activities subject to the activity precedence constraints and a project deadline. This optimal solution is derived using a branch-and-bound procedure which computes lower bounds by making convex piecewise linear underestimations of the discrete time/cost trade-off curves of the activities to be used as input for an adapted version of the Fulkerson labelling algorithm for the linear time/cost trade-off problem. Branching involves the selection of an activity in order to partition its set of execution modes into two subsets which are used to derive improved convex piecewise linear underestimations. The procedure has been programmed in Visual C ++ under Windows NT and has been validated using a factorial experiment on a large set of randomly generated problem instances.     

Integral estimation and adaptive stabilization of non-holonomic controlled systems

A method for the programmed stabilization of non-holonomic dynamic systems is proposed. The original problem is reduced to a constrained adaptive control problem with unknown perturbations, which are represented by the reactions of linear (not necessarily ideal) non-holonomic constraints. Effective control and parameter estimation algorithms are constructed for the exponential stabilization of the system. The method can be extended to non-holonomic systems whose parameters are not known in advance or undergo an unknown bounded drift with time.     

Programmed iteration method and sets of positional absorption

A pursuit–evasion differential game is considered, and the programmed iteration method is used to construct a set of positional absorption corresponding to the Krasovskii–Subbotin alternative theorem. The case is considered where the set of positions determining the state constraints may not be closed (in the position space), but has closed sections corresponding to fixed times. Properties are established that are interpreted as the (one-sided) continuity of the positional absorption set from above, and the relation to the solution of the game in the class of set-valued quasi-strategies is shown.     

Microcomputers and linear programming—Feedstock revisited

The paper describes the application of linear programming to the feedstock mix problem. The algorithm is programmed on a microcomputer. The study covers the formulation of the problem, its solution and successful implementation. System performance and cost are discussed and extensions to the work are suggested.     

On synthesis in a differential game

The control problem is considered with minimization of the guaranteed result for a system described by an ordinary differential equation in the presence of uncontrolled noise. The concepts and formulation of the problem in /1/ are used. It is shown that, when forming the optimal control by the method of programmed stochastic synthesis /1–3/, the extremal shift at the accompanying point /1, 4/ can be reduced to extremal shift agianst the gradient of the appropriate function. This explains the connection between the programmed stochastic synthesis and the generalized Hamilton-Jacobi equation /5, 6/ in the theory of differential games.     

Linear stabilization of the programmed motions of non-linear controlled dynamical systems under parametric perturbations

A non-linear controlled dynamical system that describes the dynamics of a broad class of non-linear mechanical and electromechanical systems (in particular, electromechanical robot manipulators) is considered. It is proposed that the real parameter vector of a non-linear controlled dynamical system belongs to an assigned (admissible) constrained closed set and is assumed to be unknown. The programmed motion of the non-linear controlled dynamical system and the programmed control that produces it are assigned (constructed) by using an estimate, that is, the nominal value of the parameter vector of the non-linear controlled dynamical system, which differs from its actual value. A procedure for synthesizing stabilizing control laws with linear feedback with respect to the state that ensure stabilization of the programmed motions of the non-linear controlled dynamical system under parametric perturbations is proposed. A non-singular linear transformation of the coordinates of the state space that transforms the original non-linear controlled dynamical system in deviations (from the programmed motion and programmed control) into a certain non-linear controlled dynamical system of special form, which is convenient for analysing and synthesizing laws for controlling the motion of the system, is constructed. A certain non-linear controlled dynamical system of canonical form is derived in the original non-linear controlled dynamical system in deviations. The transformation of the coordinates of the state space constructed and the Lyapunov function methodology are used to synthesize stabilizing control laws with linear feedback with respect to the state, which ensure asymptotic stability as a whole of the equilibrium position of the non-linear controlled dynamical system of canonical form and dissipativity “in the large” of the non-linear controlled dynamical system of special form and of the original non-linear controlled dynamical system in deviations. In the control laws synthesized, the formulae for the elements of their matrices of the feedback loop gains do not depend on the real parameter vector of the non-linear controlled dynamical system, and they depend solely on the constants from certain estimates that hold for all of its possible values from an assigned set. Estimates of the region of dissipativity “in the large” of the non-linear controlled dynamical system of special form and the original non-linear controlled dynamical system in deviations closed by the stabilizing control laws synthesized are given, and estimates for their limit sets and regions of attraction are presented.     

商人渡河问题的算法实现

"商人渡河问题"是一个传统的智力游戏问题,常常是作为数学模型、数据结构与智能算法分析等学科中很重要的教学或实验案例被引用.其求解算法尚未得到很好的解决,问题解的存在性等还缺少一般性和明确的结论.将首先从算法实现方面对这个问题进行深入地探讨.设计出思想方法较简单的、能在Matlab中编程实现的算法,且算法能求出问题的全部最少步数解.此外还报告了该类问题在各种情形下有趣的计算结果.     

Solution of a control problem for a nilpotent system

We consider a control problem for systems described by ordinary differential equations with linear controls. The solution of the control problem for a three-dimensional nilpotent system with two-dimensional control is presented in the classes of trigonometric controls, piecewise constant controls, and controls minimizing the sub-Riemannian length functional. The corresponding programmed controls and synthesis families are constructed.     

A new iterative algorithm for the variational inequality problem over the fixed point set of a firmly nonexpansive mapping

Many problems to appear in signal processing have been formulated as the variational inequality problem over the fixed point set of a nonexpansive mapping. In particular, convex optimization problems over the fixed point set are discussed, and operators which are considered to the problems satisfy the monotonicity. Hence, the uniqueness of the solution of the problem is not always guaranteed. In this article, we present the variational inequality problem for a monotone, hemicontinuous operator over the fixed point set of a firmly nonexpansive mapping. The main aim of the article is to solve the proposed problem by using an iterative algorithm. To this goal, we present a new iterative algorithm for the proposed problem and its convergence analysis. Numerical examples for the proposed algorithm for convex optimization problems over the fixed point set are provided in the final section.     

Optimal procedures for the discrete time/cost trade-off problem in project networks

We describe two algorithms, based on dynamic programming logic, for optimally solving the discrete time/cost trade-off problem (DTCTP) in deterministic activity-on-arc networks of the CPM type, where the duration of each activity is a discrete, nonincreasing function of the amount of a single nonrenewable resource committed to it. The first algorithm is based on a procedure proposed by Bein, Kamburowski and Stallmann for finding the minimal number of reductions necessary to transform a general network to a series-parallel network. The second algorithm minimizes the estimated number of possibilities that need to be considered during the solution procedure. Both procedures have been programmed in C and tested on a large set of representative networks to give a good indication of their performance, and indicate the circumstances in which either algorithm performs best.     

Outcome Space Partition of the Weight Set in Multiobjective Linear Programming

Approaches for generating the set of efficient extreme points of the decision set of a multiple-objective linear program (P) that are based upon decompositions of the weight set W⁰ suffer from one of two special drawbacks. Either the required computations are redundant, or not all of the efficient extreme point set is found. This article shows that the weight set for problem (P) can be decomposed into a partition based upon the outcome set Y of the problem, where the elements of the partition are in one-to-one correspondence with the efficient extreme points of Y. As a result, the drawbacks of the decompositions of W⁰ based upon the decision set of problem (P) disappear. The article explains also how this new partition offers the potential to construct algorithms for solving large-scale applications of problem (P) in the outcome space, rather than in the decision space.     

The Generic Stability and Existence of Essentially Connected Components of Solutions for Nonlinear Complementarity Problems

The aim of this paper is to develop the general generic stability theory for nonlinear complementarity problems in the setting of infinite dimensional Banach spaces. We first show that each nonlinear complementarity problem can be approximated arbitrarily by a nonlinear complementarity problem which is stable in the sense that the small change of the objective function results in the small change of its solution set; and thus we say that almost all complementarity problems are stable from viewpoint of Baire category. Secondly, we show that each nonlinear complementarity problem has, at least, one connected component of its solutions which is stable, though in general its solution set may not have good behaviour (i.e., not stable). Our results show that if a complementarity problem has only one connected solution set, it is then always stable without the assumption that the functions are either Lipschitz or differentiable.