CiteULike: jford Mceneaney

Some Classes of Imperfect Information Finite State-Space Stochastic Games with Finite-Dimensional Solutions

William Mceneaney — 2008-05-28T01:43:00-00:00

Applied Mathematics and Optimization, Vol. 50, No. 2. (2004), pp. 87-118.

Stochastic games under imperfect information are typically computationally intractable even in the discrete-time/discrete-state case considered here. We consider a problem where one player has perfect information. A function of a conditional probability distribution is proposed as an information state. In the problem form here, the payoff is only a function of the terminal state of the system, and the initial information state is either linear or a sum of max-plus delta functions. When the initial information state belongs to these classes, its propagation is finite-dimensional. The state feedback value function is also finite-dimensional, and obtained via dynamic programming, but has a nonstandard form due to the necessity of an expanded state variable. Under a saddle point assumption, Certainty Equivalence is obtained and the proposed function is indeed an information state.

Stochastic game approach to air operations

WM Mceneaney — 2008-05-28T01:40:37-00:00

Aerospace and Electronic Systems, IEEE Transactions on, Vol. 40, No. 4. (2004), pp. 1191-1216.

A command and control (C/sup 2/) problem for military air operations is addressed. Specifically, we consider C/sup 2/ problems for air vehicles against ground-based targets and defensive systems. The problem is viewed as a stochastic game. We restrict our attention to the C/sup 2/ level where the problem may consist of a few unmanned combat air vehicles (UCAVs) or aircraft (or possibly teams of vehicles), less than say, a half-dozen enemy surface-to-air missile air defense units (SAMs), a few enemy assets (viewed as targets from our standpoint), and some enemy decoys (assumed to mimic SAM radar signatures). At this low level, some targets are mapped out and possible SAM sites that are unavoidably part of the situation are known. One may then employ a discrete stochastic game problem formulation to determine which of these SAMs should optimally be engaged (if any), and by what series of air vehicle operations. We provide analysis, numerical implementation, and simulation for full state-feedback and measurement feedback control within this C/sup 2/ context. Sensitivity to parameter uncertainty is discussed. Some insight into the structure of optimal and near-optimal strategies for C/sup 2/ is obtained. The analysis is extended to the case of observations which may be affected by adversarial inputs. A heuristic based on risk-sensitive control is applied, and it is found that this produces improved results over more standard approaches.

Robust control and differential games on a finite time horizon

William Mceneaney — 2008-05-28T01:40:10-00:00

Mathematics of Control, Signals, and Systems (MCSS), Vol. 8, No. 2. (21 June 1995), pp. 138-166.

It is well known that theH8 control problem has a state space formulation in terms of differential games. For a finite time horizon control problem, the analogous differential game is considered. The disturbance is the control for the maximizing player. In order to allow forL2 disturbances, the controls for at least one player must be allowed to be unbounded. It is shown that the value of the game is the viscosity solution of the corresponding Isaacs equation under rather general conditions.

Exploitation of an opponent's imperfect information in a stochastic game with autonomous vehicle application

WM Mceneaney — 2008-05-28T01:31:21-00:00

Decision and Control, 2004. CDC. 43rd IEEE Conference on, Vol. 5 (2004), pp. 4839-4843 Vol.5.

We consider a finite state space, discrete stochastic game problem where only one player has perfect information. In the notation employed here only the "red" player has the perfect state information. The "blue" player only has access to observation-based information. To some degree the observations may be influenced by the controls of both players. A Markov chain model is used where the transition probabilities depend on the controls of the players. The game is zero-sum. It is known that application of the optimal control at a maximum likelihood estimate by the blue player is not optimal; under a saddle point condition, a form of certainty equivalence does exist for the blue player, but the structure is more complex than the above approach. In this work, the point of view of the red player is considered. Simulation is used to demonstrate that the optimal state feedback control for red is not the optimal control (even with perfect information for red). This is a significantly stronger statement than that certainty equivalence does not hold when the red player has imperfect information. A theory for the development of red control is presented. This yields "deceptive" controls in the presence of the simpler blue approach above, which provide superior performance in this case. An open question is whether (and under what conditions), this approach yields superior performance for red as compared with slate feedback when blue is allowed strategies including the more complex one above. Experimentation and theory are employed to answer this question.

Max-plus eigenvector representations for solution of nonlinear H/sub /spl infin// problems: basic concepts

WM Mceneaney — 2008-04-30T01:15:36-00:00

Automatic Control, IEEE Transactions on, Vol. 48, No. 7. (2003), pp. 1150-1163.

The H/sub /spl infin// problem for a nonlinear system is considered. The corresponding dynamic programming equation is a fully nonlinear, first-order, steady-state partial differential equation (PDE), possessing a term which is quadratic in the gradient. The solutions are typically nonsmooth, and further, there is nonuniqueness among the class of viscosity solutions. In the case where one tests a feedback control to see if it yields an H/sub /spl infin// controller, the PDE is a Hamilton-Jacobi-Bellman equation. In the case where the "optimal" feedback control is being determined as well, the problem takes the form of a differential game, and the PDE is, in general, an Isaacs equation. The computation of the solution of a nonlinear, steady-state, first-order PDE is typically quite difficult. In this paper, we develop an entirely new class of methods for obtaining the "correct" solution of such PDEs. These methods are based on the linearity of the associated semigroup over the max-plus (or, in some cases, min-plus) algebra. In particular, solution of the PDE is reduced to solution of a max-plus (or min-plus) eigenvector problem for known unique eigenvalue 0 (the max-plus multiplicative identity). It is demonstrated that the eigenvector is unique, and that the power method converges to it. An example is included.

A risk-sensitive escape criterion and robust limit

WM Mceneaney — 2008-04-30T01:15:09-00:00

Decision and Control, 1994., Proceedings of the 33rd IEEE Conference on, Vol. 4 (1994), pp. 4195-4197 vol.4.

A common problem of interest is that of controlling a stochastic process so as to keep the state in some fixed set G. The two optimization criteria which are most often used are the escape probability over a fixed time interval and the mean escape time. We apply a risk-sensitive criterion to the escape problem which avoids certain difficulties associated with the above two criteria. Further, in the risk-averse limit the value function converges to the value of a deterministic differential game where an opposing player attempts to push the process out of G. In analogy with H<sup>∞</sup> disturbance rejection bounds, this yields a lower bound on the escape time as a (nonlinear) function of the L<sup>2</sup> norm of the opposing player's control

Risk sensitive control with ergodic cost criteria

WH Fleming — 2008-04-30T01:07:07-00:00

Decision and Control, 1992., Proceedings of the 31st IEEE Conference on (1992), pp. 2048-2052 vol.2.

Stochastic control problems on an infinite time horizon with exponential cost criteria are considered. The Donsker-Varadhan large deviation rate (1975, 1976) is used as a criterion to be optimized. The optimum rate is characterized as the value of an associated stochastic differential game, with an ergodic (expected average cost per unit time) cost criterion. By taking a small-noise limit a deterministic differential game with an average cost per unit time cost criterion is obtained. This differential game is related to robust control of nonlinear systems

Risk sensitive and robust nonlinear filtering

WH Fleming — 2008-04-30T01:06:45-00:00

Decision and Control, 1997., Proceedings of the 36th IEEE Conference on, Vol. 2 (1997), pp. 1088-1093 vol.2.

A risk sensitive approach to nonlinear filtering is considered. In this case, the traditional expected mean squared error is replaced by an expected exponential-of-mean squared error. A pathwise filtering equation is used to take the risk averse limit. This leads to a robust filtering estimator. The robust estimator yields a bound on the estimate error in terms of (finite) disturbance energy

A Curse-of-Dimensionality-Free Numerical Method for Solution of Certain HJB PDEs

William Mceneaney — 2007-09-13T00:45:26-00:00

SIAM Journal on Control and Optimization, Vol. 46, No. 4. (2007), pp. 1239-1276.

In previous works of the author and others, max-plus methods have been explored for the solution of first-order, nonlinear Hamilton–Jacobi–Bellman partial differential equations (HJB PDEs) and corresponding nonlinear control problems. These methods exploit the max-plus linearity of the associated semigroups. In particular, although the problems are nonlinear, the semigroups are linear in the max-plus sense. These methods have been used successfully to compute solutions. Although they provide certain computational-speed advantages, they still generally suffer from the curse of dimensionality. Here we consider HJB PDEs in which the Hamiltonian takes the form of a (pointwise) maximum of linear/quadratic forms. The approach to the solution will be rather general, but in order to ground the work, we consider only constituent Hamiltonians corresponding to long-run average-cost-per-unit-time optimal control problems for the development. We obtain a numerical method not subject to the curse of dimensionality. The method is based on construction of the dual-space semigroup corresponding to the HJB PDE. This dual-space semigroup is constructed from the dual-space semigroups corresponding to the constituent linear/quadratic Hamiltonians. The dual-space semigroup is particularly useful due to its form as a max-plus integral operator with a kernel obtained from the originating semigroup. One considers repeated application of the dual-space semigroup to obtain the solution.