Sufficiency theorems for target capture

A dynamical system is assumed to be governed by a set of ordinary differential equations subject to control. The set of points in state space from which there exist permissible controls that can transfer these points to a prescribed target set in a finite time interval is called a capture set. The task of determining the capture set is studied in two contexts. first, in the case of the system subject to a single control vector; and second, in the case of the system subject to two control vectors each operated independently. In the latter case, it is assumed that one controller's aim is to cause the system to attain the target, and the other's is to prevent that from occurring.Sufficient conditions are developed that, when satisfied everywhere on the interior of some subset of the state space, ensure that this subset is truly a capture set. A candidate capture set is assumed to have already been predetermined by independent methods. The sufficient conditions developed herein require the use of an auxiliary scalar function of the state, similar to a Lyapunov function.To ensure capture, five conditions must be satisfied. Four of these constrain the auxiliary state function. Basically, these four conditions require that the boundary of the controllable set be an envelope of the auxiliary state function and that that function be positive inside the capture set, approaching zero value as the target set is approached. The final condition tests the inner product of the gradient of the auxiliary state function with the system state velocity vector. If the sign of that inner product can be made negative everywhere within the test subset, then that subset is a capture set.Dedicated to Professor A. BusemannThe authors are indebted to Professors G. Leitmann and J. M. Skowronskii for their useful comments and discussion.     

Complex differential games of pursuit-evasion type with state constraints,part 2: Numerical computation of optimal open-loop strategies

In Part 1 of this paper (Ref. 1), necessary conditions for optimal open-loop strategies in differential games of pursuit-evasion type have been developed for problems which involve state variable inequality constraints and nonsmooth data. These necessary conditions lead to multipoint boundary-value problems with jump conditions. These problems can be solved very efficiently and accurately by the well-known multiple-shooting method. By this approach, optimal open-loop strategies and their associated saddle-point trajectories can be computed for the entire capture zone of the game. This also includes the computation of optimal open-loop strategies and saddle-point trajectories on the barrier of the pursuit-evasion game. The open-loop strategies provide an open-loop representation of the optimal feedback strategies. Numerical results are obtained for a special air combat scenario between one medium-range air-to-air missile and one high-performance aircraft in a vertical plane. A dynamic pressure limit for the aircraft imposes a state variable inequality constraint of the first order. Special emphasis is laid on realistic approximations of the lift, drag, and thrust of both vehicles and the atmospheric data. In particular, saddle-point trajectories on the barrier are computed and discussed. Submanifolds of the barrier which separate the initial values of the capture zone from those of the escape zone are computed for two representative launch positions of the missible. By this way, the firing range of the pursuing missile is determined and visualized.This paper is dedicated to the memory of Professor John V. Breakwell.The authors would like to express their sincere and grateful appreciation to Professors R. Bulirsch and K. H. Well for their encouraging interest in this work.     

On the theory of three-person differential games

A differential game of three players with dynamics described by linear differential equations under geometric constraints on the control parameters is considered. Sufficient conditions are obtained for the existence of the first player’s strategy guaranteeing that the trajectory of the game reaches a given target set for any admissible control of the second player and avoids the terminal set of the third player. An algorithm of constructing the first player’s strategy guaranteeing the game’s termination in finite time is suggested. A solution of a model example is given.     

Characterization of Barriers of Differential Games

In pursuit-evasion games, when a barrier occurs, splitting the state space into capture and evasion areas, in order to characterize this manifold, the study of the minimum time function requires discontinuous generalized solutions of the Isaacs equation. Thanks to the minimal oriented distance from the target, we obtain a characterization by approximation with continuous functions. The barrier is characterized by the largest upper semicontinuous viscosity subsolution of a variational inequality. This result extends the Isaacs semipermeability property.     

Quasilinear Pursuit Differential Game with a Simple Dynamics under Phase Constraints

On a fixed closed time interval we consider a quasilinear pursuit differential game with a convex compact target set under a phase constraint in the form of a convex closed set. We construct a convex compact guaranteed capture set similar to an alternating Pontryagin sum and define the guaranteed piecewise-programmed strategy of the pursuer ensuring the hitting of the target set by the phase vector satisfying the phase constraint in finite time. Under certain conditions, we prove the convergence of the constructed alternating sum in the Hausdorff metric to a convex compact set, which is an analog of the alternating Pontryagin integral for the differential game.     

Construction of a maximal stable bridge in games with simple motions on the plane

It is known that the solvability set (the maximal stable bridge) in a zero-sum differential game with simple motions, fixed terminal time, geometric constraints on the controls of the first and second players, and convex terminal set can be constructed by means of a program absorption operator. In this case, a backward procedure for the construction of t-sections of the solvability set does not need any additional partition times. We establish the same property for a game with simple motions, polygonal terminal set (which is generally nonconvex), and polygonal constraints on the players’ controls on the plane. In the particular case of a convex terminal set, the operator used in the paper coincides with the program absorption operator.     

On a Multiperson Pursuit Problem with Integral Constraints on the Controls of the Players

We consider a linear multiperson differential game with integral constraints on the control of the players. The pursuit is assumed terminated if the solution of at least one of the equations describing the game reaches the origin at some instant of time.In the case of one pursuer, we obtain a necessary and sufficient condition for terminating pursuit from all points of space. In the case of many pursuers, we obtain a sufficient condition for terminating pursuit from all points of space.     

Patrolling a perimeter

In this paper we study the problem of patrolling a perimeter. The general situation considered here can correspond to different tactical problems and it is studied from the point of view of game theory. To put the ideas in a context we describe it as follows. An intruder seeks to carry out a sabotage on the perimeter of a protected zone. He has to perform the action along n consecutive days and has to position himself each day at one of m strategic points placed on this border. The first day he can take his place at any of the m points, but on successive days he can move only to adjacent points. Furthermore, the perimeter is protected by a patroller, who will select each day one of the m points to inspect. The strategic situation is modeled as a two-person zero-sum game, which is developed on a cyclic set of m points over n time units. We prove some interesting properties of the strategies, solve the game in closed form under certain constraints and obtain bounds for the value of the game in several non-solved cases.     

Algorithm for constructing an optimal control strategy in a nonlinear differential game with Lipschitz compactly supported payoff

For a zero-sum differential game, we consider an algorithm for constructing optimal control strategies with the use of backward minimax constructions. The dynamics of the game is not necessarily linear, the players’ controls satisfy geometric constraints, and the terminal payoff function satisfies the Lipschitz condition and is compactly supported. The game value function is computed by multilinear interpolation of grid functions. We show that the algorithm error can be arbitrarily small if the discretization step in time is sufficiently small and the discretization step in the state space has a higher smallness order than the time discretization step. We show that the algorithm can be used for differential games with a terminal set. We present the results of computations for a problem of conflict control of a nonlinear pendulum.     

A differential game of surveillance evasion of two identical cars

A partial solution of a differential game of surveillance evasion is presented. The dynamics is that of two identical cars, with constant speeds and bounded turn rates. The pursuer's surveillance zone is circular. The game of kind and the game of degree are solved for ratios of the surveillance radius to the minimal turn radius equal to or greater than +2. A barrier is constructed, and regions of strategies are separated through the use of dispersal and universal surfaces. A synthesis of a composite game of two identical cars is outlined, covering the space outside the surveillance zone as well as that inside it.Part of this research (the game of kind, Ref. 1) was carried out in the Faculty of Mechanical Engineering in the Technion, Haifa under the supervision of J. Lewin. The author is indebted to J. Lewin for his guidance.     

Robust State-Feedback Controllability of Linear Systems to a Hyperplane in a Class of Bounded Controls

The paper deals with a linear time-dependent dynamic system with scalar control and input uncertainty (disturbance). Two admissible classes of input uncertainty realizations are considered: the class of measurable bounded functions and the class of measurable quadratically integrable functions. The problem to be studied is the existence of a state feedback control with measurable bounded time realizations transferring the system to a given hyperplane (a target set) from any initial position in a prescribed time for any admissible input uncertainty realization. Necessary and sufficient conditions for the existence of such a control are derived, based on the explicit construction of this control by using an auxilary zero-sum linear-quadratic differential game with a cheap control for the minimizing player. Examples illustrting the theoritical results are presented.     

On the restricted cores and the bounded core of games on distributive lattices

A game with precedence constraints is a TU game with restricted cooperation, where the set of feasible coalitions is a distributive lattice, hence generated by a partial order on the set of players. Its core may be unbounded, and the bounded core, which is the union of all bounded faces of the core, proves to be a useful solution concept in the framework of games with precedence constraints. Replacing the inequalities that define the core by equations for a collection of coalitions results in a face of the core. A collection of coalitions is called normal if its resulting face is bounded. The bounded core is the union of all faces corresponding to minimal normal collections. We show that two faces corresponding to distinct normal collections may be distinct. Moreover, we prove that for superadditive games and convex games only intersecting and nested minimal collection, respectively, are necessary. Finally, it is shown that the faces corresponding to pairwise distinct nested normal collections may be pairwise distinct, and we provide a means to generate all such collections.     

On intersections of abelian and nilpotent subgroups in finite groups. I

We consider Pontryagin’s generalized nonstationary example with identical dynamic and inertial capabilities of the players under phase constraints on the evader’s states. The boundary of the phase constraints is not a “death line” for the evader. The set of admissible controls is a ball centered at the origin, and the terminal sets are the origin. We obtain sufficient conditions for a multiple capture of one evader by a group of pursuers in the case when some functions corresponding to the initial data and to the parameters of the game are recurrent.     

Impulse capture basins of sets under impulse control systems

Given a target contained in a constrained set and an impulse control system governing the evolutions of runs or executions, that are hybrids of continuous and discrete evolutions, this paper studies and provides several characterizations of the capture basin of the target viable in the constrained set. It is the subset of initial runs from which start at least one run viable in the constrained set until it reaches the target in finite time. It also provides algorithms and regulation rules governing the runs that reach the targets while obeying state constraints.     

Informational Sets in a Model Problem of Homing

A linear pursuit problem in the plane under incomplete pursuer information about the evader is investigated. At discrete time instants, the pursuer measures with errors the angle of vision to the evader, the angular velocity of the line of sight, and the relative distance. Other combinations of measurable parameters are possible (for example, angle of vision and relative distance or angle of vision only). The measurements errors obey certain geometric constraints. The initial uncertainties on the evader coordinates and velocities are given in advance. Having a resource of impulse control, the pursuer tries to minimize the miss distance. The evader control is bounded in modulus.The problem is formulated as an auxiliary differential game. Here, the notion of informational set is central. The informational set is the totality of pointwise phase states consistent with the history of the observation-control process. The informational set depends on the current measurements; it changes in time and plays the role of a generalized state, which is used for constructing the pursuer control.A control method designed for the linear pursuit problem is used in the planar problem of a vehicle homing toward a dangerous space object. The nonlinear dynamics is described by the Kepler equations. Nonlinear terms of the equations in relative coordinates are small and are replaced by an uncertain vector parameter, which is bounded in modulus and is regarded as an evader control. As a result, we obtain the mentioned control problem in the plane.The final part of the paper is devoted to the simulation of a space vehicle homing toward a dangerous space object. In testing the control method developed, two variants are considered: random measurement errors and game method of constructing the measurements; the latter is also described in the paper.     

Robust Transferable Sets of Linear Transferring Strategies

The problem of transferring a controlled linear system with a disturbance to a prescribed target set (a hyperplane at a prescribed time instant) is considered. The control and disturbance are subject to geometrical constraints. The original transfer problem is reduced to a scalar one. Then, for a given transferring linear feedback strategy, the respective transferable set is studied, i.e. the set of all the initial positions in the time/state plane, from which the target set is reached, respecting the control constraints, against any admissible disturbance. Necessary and sufficient conditions for the existence of the transferable set are derived, its set-theoretical properties are established, the algorithm of its boundary construction is proposed, the boundary smoothness is studied. Illustrative examples are presented.     

ɛ-Subdifferentials of Set-valued Maps and ɛ-Weak Pareto Optimality for Multiobjective Optimization

In this paper we consider vector optimization problems where objective and constraints are set-valued maps. Optimality conditions in terms of Lagrange-multipliers for an ɛ-weak Pareto minimal point are established in the general case and in the case with nearly subconvexlike data. A comparison with existing results is also given. Our method used a special scalarization function, introduced in optimization by Hiriart-Urruty. Necessary and sufficient conditions for the existence of an ɛ-weak Pareto minimal point are obtained. The relation between the set of all ɛ-weak Pareto minimal points and the set of all weak Pareto minimal points is established. The ɛ-subdifferential formula of the sum of two convex functions is also extended to set-valued maps via well known results of scalar optimization. This result is applied to obtain the Karush–Kuhn–Tucker necessary conditions, for ɛ-weak Pareto minimal points     

Characterization of the Darboux point for particular classes of problems

A minimal sufficient condition for global optimality involving the Darboux point, analogous to the minimal sufficient condition of local optimality involving the conjugate point, is presented. The Darboux point is then characterized for optimal control problems with linear dynamics, cost functionals with a general terminal state term and an integrand quadratic in the state and control, and general terminal conditions. The Darboux point is shown to be the supremum of a sequence of conjugate points. If the terminal state term is quadratic, along with a scalar quadratic boundary condition, then the Darboux point is also the time at which the Riccati matrix becomes unbounded, giving a characterization of the unboundedness of the Riccati matrix at points which are not in general conjugate points.This research was supported by the National Science Foundation under Grant No. GK-30115.This is Definition 2.1 of Ref. 1.     

Structure of equilibria inN-person non-cooperative games

Here we study the structure of Nash equilibrium points forN-person games. For two-person games we observe that exchangeability and convexity of the set of equilibrium points are synonymous. This is shown to be false even for three-person games. For completely mixed games we get the necessary inequality constraints on the number of pure strategies for the players. Whereas the equilibrium point is unique for completely mixed two-person games, we show that it is not true for three-person completely mixed game without some side conditions such as convexity on the equilibrium set. It is a curious fact that for the special three-person completely mixed game with two pure strategies for each player, the equilibrium point is unique; the proof of this involves some combinatorial arguments.     

On Implicit Active Constraints in Linear Semi-Infinite Programs with Unbounded Coefficients

The concept of implicit active constraints at a given point provides useful local information about the solution set of linear semi-infinite systems and about the optimal set in linear semi-infinite programming provided the set of gradient vectors of the constraints is bounded, commonly under the additional assumption that there exists some strong Slater point. This paper shows that the mentioned global boundedness condition can be replaced by a weaker local condition (LUB) based on locally active constraints (active in a ball of small radius whose center is some nominal point), providing geometric information about the solution set and Karush-Kuhn-Tucker type conditions for the optimal solution to be strongly unique. The maintaining of the latter property under sufficiently small perturbations of all the data is also analyzed, giving a characterization of its stability with respect to these perturbations in terms of the strong Slater condition, the so-called Extended-Nürnberger condition, and the LUB condition.