Search

Sample complexity bounds are a common performance metric in the reinforcement learning literature. In the discounted cost, infinite horizon setting, all of the known bounds can be arbitrarily large, as the discount factor approaches unity. These results seem to imply that a very large number of samples is required to achieve an epsilon-optimal policy. The objective of the present work is to introduce a new class of algorithms that have sample complexity uniformly bounded over all discount factors. One may argue that this is impossible, due to a recent min–max lower bound. The explanation is that these prior bounds concern value function approximation and not policy approximation. We show that the asymptotic covariance of the tabular Q-learning algorithm with an optimized step-size sequence is a quadratic function of a factor that goes to infinity, as discount factor approaches 1; an essentially known result. The new relative Q-learning algorithm proposed here is shown to have asymptotic covariance that is uniformly bounded over all discount factors. [ABSTRACT FROM AUTHOR]

Stochastic dynamic teams and games are rich models for decentralized systems and challenging testing grounds for multiagent learning. Previous work that guaranteed team optimality assumed stateless dynamics, or an explicit coordination mechanism, or joint-control sharing. In this article, we present an algorithm with guarantees of convergence to team optimal policies in teams and common interest games. The algorithm is a two-timescale method that uses a variant of Q-learning on the finer timescale to perform policy evaluation while exploring the policy space on the coarser timescale. Agents following this algorithm are “independent learners”: they use only local controls, local cost realizations, and global state information, without access to controls of other agents. The results presented here are the first, to the best of our knowledge, to give formal guarantees of convergence to team optimality using independent learners in stochastic dynamic teams and common interest games. [ABSTRACT FROM AUTHOR]

This article adopts a reinforcement learning (RL) method to solve infinite horizon continuous-time stochastic linear quadratic problems, where the drift and diffusion terms in the dynamics may depend on both the state and control. Based on the Bellman’s dynamic programming principle, we presented an online RL algorithm to attain optimal control with partial system information. This algorithm computes the optimal control, rather than estimates the system coefficients, and solves the related Riccati equation. It only requires local trajectory information, which significantly simplifies the calculation process. We shed light on our theoretical findings using two numerical examples. [ABSTRACT FROM AUTHOR]

We analyze a tree search problem with an underlying Markov decision process, in which the goal is to identify the best action at the root that achieves the highest cumulative reward. We present a new tree policy that optimally allocates a limited computing budget to maximize a lower bound on the probability of correctly selecting the best action at each node. Compared to widely used upper confidence bound (UCB) tree policies, the new tree policy presents a more balanced approach to manage the exploration and exploitation tradeoff when the sampling budget is limited. Furthermore, UCB assumes that the support of reward distribution is known, whereas our algorithm relaxes this assumption. Numerical experiments demonstrate the efficiency of our algorithm in selecting the best action at the root. [ABSTRACT FROM AUTHOR]

In this article, we study the problem of information sharing among rational self-interested agents as a dynamic game of asymmetric information. We assume that the agents imperfectly observe a Markov chain, and they are called to decide whether they will share their noisy observations or not at each time instant. We utilize the notion of conditional mutual information to evaluate the information being shared among the agents. The challenges that arise due to the interdependence of agents’ information structure and decision making are exhibited. For the finite horizon game, we prove that agents do not have incentive to share information. In contrast, we show that cooperation can be sustained in the infinite-horizon case by devising appropriate punishment strategies, which are defined over the agents’ beliefs on the system state. We show that these strategies are closed under the best-response mapping and that cooperation can be the optimal choice in some subsets of the state belief simplex. We characterize these equilibrium regions, prove uniqueness of a maximal equilibrium region, and devise an algorithm for its approximate computation. [ABSTRACT FROM AUTHOR]

This article presents ConVex optimization-based Stochastic steady-state Tracking Error Minimization (CV-STEM), a new state feedback control framework for a class of Itô stochastic nonlinear systems and Lagrangian systems. Its innovation lies in computing the control input by an optimal contraction metric, which greedily minimizes an upper bound of the steady-state mean squared tracking error of the system trajectories. Although the problem of minimizing the bound is nonconvex, its equivalent convex formulation is proposed utilizing SDC parameterizations of the nonlinear system equation. It is shown using stochastic incremental contraction analysis that the CV-STEM provides a sufficient guarantee for exponential boundedness of the error for all time with ${\bf \mathcal {L}_2}$ -robustness properties. For the sake of its sampling-based implementation, we present discrete-time stochastic contraction analysis with respect to a state- and time-dependent metric along with its explicit connection to continuous-time cases. We validate the superiority of the CV-STEM to PID, $\mathcal {H}_\infty$ , and baseline nonlinear controllers for spacecraft attitude control and synchronization problems. [ABSTRACT FROM AUTHOR]

Value functions derived from Markov decision processes arise as a central component of algorithms as well as performance metrics in many statistics and engineering applications of machine learning. Computation of the solution to the associated Bellman equations is challenging in most practical cases of interest. A popular class of approximation techniques, known as temporal difference (TD) learning algorithms, are an important subclass of general reinforcement learning methods. The algorithms introduced in this article are intended to resolve two well-known issues with TD-learning algorithms. Their slow convergence due to very high central limit theorem variance, and the fact that, for the problem of computing the relative value function, consistent algorithms exist only in special cases. First we show that the gradients of these value functions admit a representation that lends itself to algorithm design. Based on this result, a new class of differential TD-learning algorithms is introduced. For Markovian models on Euclidean space with smooth dynamics, the algorithms are shown to be consistent under general conditions. Numerical results show dramatic variance reduction in comparison to standard methods. [ABSTRACT FROM AUTHOR]

Probabilistic occupancy, the likelihood that the state at a known future time lies in a given set, is important in a variety of stochastic motion planning problems. We provide efficient computational techniques, based in Fourier transforms, to characterize the stochasticity of the future state for Markov jump affine systems. This class of systems captures a variety of important dynamics in planning problems, including the Dubins’ vehicle. We employ convex optimization to compute outer approximations of the superlevel sets of the probabilistic occupancy function, which is a key for preserving the safety guarantees sought in collision-avoidance problems. In contrast to traditional approaches, our approach does not rely on gridding, recursion, or sampling, accommodates non-Gaussian perturbed dynamics, and affords outer-approximation guarantees. We demonstrate our methods on the target pursuit problem with multiple robots pursuing a nonadversarial target with stochastic dynamics, and on the problem of computing keep-out regions for stochastic collision avoidance of a Dubins’ vehicle. [ABSTRACT FROM AUTHOR]

We consider a class of dynamic collective choice models with social interactions, whereby a large number of nonuniform agents have to individually settle on one of multiple discrete alternative choices, with the relevance of their would-be choices continuously impacted by noise and the unfolding group behavior. This class of problems is modeled here as a so-called min-LQG game, i.e., a linear quadratic Gaussian dynamic and noncooperative game, with an additional combinatorial aspect in that it includes a final choice-related minimization in its terminal cost. The presence of this minimization term is key to enforcing some specific discrete choice by each individual agent. The theory of mean field games is invoked to generate a class of decentralized agent feedback control strategies, which are then shown to converge to an exact Nash equilibrium of the game as the number of players increases to infinity. A key building block in our approach is an explicit solution to the problem of computing the best response of a generic agent to some arbitrarily posited smooth mean field trajectory. Ultimately, an agent is shown to face a continuously revised discrete choice problem, where greedy choices dictated by current conditions must be constantly balanced against the risk of the future process noise upsetting the wisdom of such decisions. We show that any Nash equilibrium of the game is defined by an a priori computable probability matrix, which describes the distribution of the players’ choices over the alternatives. The results are illustrated through simulations. [ABSTRACT FROM AUTHOR]

This brief studies controllability for probabilistic Boolean control network (PBCN) with time-varying feedback control laws. The concept of feedback controllability with an arbitrary probability for PBCNs is formulated first, and a control problem to maximize the probability of time-varying feedback controllability is investigated afterward. By introducing semitensor product (STP) technique, an equivalent multistage decision problem is deduced, and then a novel optimization algorithm is proposed to obtain the maximum probability of controllability and the corresponding optimal feedback law simultaneously. The advantages of the time-varying optimal controller obtained by the proposed algorithm, compared to the time-invariant one, are illustrated by numerical simulations. [ABSTRACT FROM AUTHOR]

This paper considers the quadratic control problem of discrete-time Markov jump linear systems with constraints on the norm of the state and control variables. We assume that the Markov chain parameter is not available, and instead, there is a detector, which emits signals providing information on this parameter. It is desired to derive a feedback linear control using the information provided by this detector in order to stochastically stabilize the closed-loop system, satisfy the constraints whenever the initial conditions belong to an invariant set, and minimize an upper bound for the quadratic cost. We show that a linear matrix inequality (LMI) optimization problem can be formulated in order to obtain a solution for this problem. Two other related problems, one for minimizing the guaranteed quadratic cost considering fixed initial conditions and the other for maximizing an estimate of the domain of an invariant set, can also be formulated using our LMI approach. This paper is concluded with some numerical simulations. [ABSTRACT FROM AUTHOR]

We consider a general sequential team problem based on Witsenhausen's intrinsic model. Our formulation encompasses all teams in which the uncontrolled inputs can be viewed as random variables on a finite probability space, the number of control inputs/decisions is finite and the decisions take values in finite spaces. We define the concept of common knowledge in such teams and use it to construct a sequential decomposition of the problem of optimizing the team strategy profile. If the information structure is classical, our common knowledge based decomposition is identical to classical dynamic program. If the information structure is such that the common knowledge is trivial, our decomposition is similar in spirit to Witsenhausen's standard form based decomposition. In this case, the sequential decomposition is essentially a sequential reformulation of the strategy optimization problem and appears to have limited value. For information structures with nontrivial common knowledge, our sequential decomposition differs from Witsenhausen's standard form based decomposition because of its dependence on common knowledge. Our common knowledge based approach generalizes the common information based methods of –. [ABSTRACT FROM AUTHOR]

This paper is concerned with learning and stochastic control in physical systems that contain unknown input signals. These unknown signals are modeled as Gaussian processes (GP) with certain parameterized covariance structures. The resulting latent force models can be seen as hybrid models that contain a first-principle physical model part and a nonparametric GP model part. We briefly review the statistical inference and learning methods for this kind of models, introduce stochastic control methodology for these models, and provide new theoretical observability and controllability results for them. [ABSTRACT FROM AUTHOR]

A novel risk-sensitive (RS) control law is proposed for linear systems with stochastic system parameters. RS control laws are efficient means of handling risk in various failures in control caused by stochastic disturbances. However, stochastic parameters invoke problems, resulting controllers may become nonlinear in the state variable and incompatible with linear systems, cannot be obtained in an exact sense, and are defined only on a bounded state region. To solve these problems, this paper presents a risk-sensitive linear (RSL) control method. The important idea is that a standard RS-type cost function is converted to an expectation of a weighted cost function such that the resulting optimal controller is linear in the state. The weight is designed such that the weighted cost function preserves the characteristics of the original RS control. The designed weight allows one to derive the proposed RSL controller whose exact solution is obtained as a linear feedback law for all states. Furthermore, the RSL control law over an infinite horizon guarantees stochastic stability of the feedback system with the control law. The effectiveness of the proposed RSL control law is demonstrated by a numerical simulation. [ABSTRACT FROM AUTHOR]

We consider two-stage tandem queueing systems with one dedicated server in each station and a flexible server that can serve both stations. We assume exponential service times, linear holding costs accrued by jobs present in the system, and a collaborative work discipline. We seek optimal server allocation strategies for systems without external arrivals (clearing systems). When the combined rate of collaborating servers is less than the sum of their individual rates (partial collaboration), we identify conditions under which the optimal server allocation strategy is non-idling and has a threshold-type structure. Our results extend previous work on systems with additive service rates. When the aforementioned conditions are not satisfied we show by examples that the optimal policy may have counterintuitive properties, which is not the case when a fully collaborative service discipline is assumed. We also obtain novel results for any type of collaboration when idling policies may be optimal. [ABSTRACT FROM AUTHOR]

This paper considers a Markov decision process (MDP) model with safety state constraints, which specify polytopic invariance constraints on the state probability distribution (pd) for all time epochs. Typically, in the MDP framework, safety is addressed indirectly by penalizing failure states through the reward function. However, such an approach does not allow imposing hard constraints on the state pd, which could be an issue for practical applications where the chance of failure must be limited to prescribed bounds. In this paper, we explicitly separate state constraints from the reward function. We provide analysis and synthesis methods to impose generalized safety constraints at all time epochs, unlike current constrained MDP approaches where such constraints can only be imposed on the stationary distributions. We show that, contrary to the unconstrained MDP policies, optimal safe MDP policies depend on the initial state pd. We present novel algorithms for both finite- and infinite-horizon MDPs to synthesize feasible decision-making policies that satisfy safety constraints for all time epochs and ensure that the performance is above a computable lower bound. Linear programming implementations of the proposed algorithms are developed, which are formulated by using the duality theory of convex optimization. A swarm control simulation example is also provided to demonstrate the use of proposed algorithms. [ABSTRACT FROM AUTHOR]

In this paper, an improved approach for the solution of the regulator problem for linear discrete-time dynamical systems with non-Gaussian disturbances and quadratic cost functional is proposed. It is known that a suboptimal recursive control can be derived from the classical linear quadratic Gaussian (LQG) solution by substituting the linear filtering part with a quadratic, or in general polynomial, filter. However, we show that when the system is not asymptotically stable the polynomial control does not improve over the classical LQG solution, due to the lack of the internal stability of the polynomial filter. In order to enlarge the class of systems that can be controlled, we propose a new method based on a suitable rewriting of the system by means of an output injection term. We show that this allows us to overcome the problem and to design a polynomial optimal controller also for non asymptotically stable systems. Numerical results show the effectiveness of the method. [ABSTRACT FROM AUTHOR]

The topic of this paper is model predictive control (MPC) for max-plus linear systems with stochastic uncertainties the distribution of which is supposed to be known. We consider linear constraints on the inputs and the outputs. Due to the uncertainties, these linear constraints are formulated as probabilistic or chance constraints, i.e., the constraints are required to be satisfied with a predefined probability level. The proposed chance constraints can be equivalently rewritten into a max-affine (i.e., the maximum of affine terms) form if the linear constraints are monotonically nondecreasing as a function of the outputs. Based on the resulting max-affine form, two methods are developed for solving the chance-constrained MPC problem for stochastic max-plus linear systems. Method 1 uses Boole's inequality to convert the multivariate chance constraint into univariate chance constraints for which the probability can be computed more efficiently. Method 2 employs Chebyshev's inequality and transforms the chance constraint into linear constraints on the inputs. The simulation results for a production system example show that the two proposed methods are faster than the Monte Carlo simulation method and yield lower closed-loop costs than the nominal MPC method. [ABSTRACT FROM AUTHOR]

We consider stochastic shortest path problems with infinite state and control spaces, a nonnegative cost per stage, and a termination state. We extend the notion of a proper policy, a policy that terminates within a finite expected number of steps, from the context of finite state space to the context of infinite state space. We consider the optimal cost function $J^*$ , and the optimal cost function $\hat{J}$ over just the proper policies. We show that $J^*$ and $\hat{J}$ are the smallest and largest solutions of Bellman's equation, respectively, within a suitable class of Lyapounov-like functions. If the cost per stage is bounded, these functions are those that are bounded over the effective domain of $\hat{J}$. The standard value iteration algorithm may be attracted to either $J^*$ or $\hat{J}$ , depending on the initial condition. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of infinite horizon forward and backward stochastic difference equations (FBSDEs) that are fully coupled. The adapted solution is given by establishing an explicit relation between the forward and backward components in terms of a generalized algebraic Riccati equation. The equivalence between the exponential stabilizability of the stochastic control system and the infinite horizon FBSDEs is derived. As an application, the FBSDEs are used to characterize the maximum principle of the infinite horizon stochastic optimal control problem. [ABSTRACT FROM PUBLISHER]

This paper is concerned with controlling poorly known systems, for which only a simplified and rough model is available for control design. There are many systems that cannot be reasonably probed for the sake of identification, yet they are important for areas such as economy, populations, or medicine. The ideas are developed around an alternative way to account for the bare modeling in a stochastic-based setting, and to heighten the control features for such a modified model. The mathematical framework for the optimal control reveals important features such as the raising of a precautionary feedback policy of “keep the action unchanged” (inaction for short), on a certain state-space region. This feature is not seen in the robust approach, but has been pointed out and permeates part of the economics literature. The control problem relies on the viscosity solution for the Hamilton–Jacobi–Bellman equation, and the value of the problem is shown to be convex. When specialized to the quadratic problem with discounted cost, the exact solution inside the inaction region is given by a Lyapunov type of equation, and asymptotically, for large state values, by a Riccati-like equation. This scenario bridges to the stochastic stability analysis for the controlled model. The single control input is developed in full, part analytically, part numerically, for the scalar case, and an approximation is tested for the multidimensional case. The advantage of the precautionary policy is substantial in some situations. [ABSTRACT FROM AUTHOR]

Sequential rate-distortion (SRD) theory provides a framework for studying the fundamental trade-off between data-rate and data-quality in real-time communication systems. In this paper, we consider the SRD problem for multi-dimensional time-varying Gauss-Markov processes under mean-square distortion criteria. We first revisit the sensor-estimator separation principle, which asserts that considered SRD problem is equivalent to a joint sensor and estimator design problem in which data-rate of the sensor output is minimized while the estimator's performance satisfies the distortion criteria. We then show that the optimal joint design can be performed by semidefinite programming. A semidefinite representation of the corresponding SRD function is obtained. Implications of the obtained result in the context of zero-delay source coding theory and applications to networked control theory are also discussed. [ABSTRACT FROM AUTHOR]

In this paper, an offline approximate dynamic programming approach using neural networks is proposed for solving a class of finite horizon stochastic optimal control problems. There are two approaches available in the literature, one based on stochastic maximum principle (SMP) formalism and the other based on solving the stochastic Hamilton–Jacobi–Bellman (HJB) equation. However, in the presence of noise, the SMP formalism becomes complex and results in having to solve a couple of backward stochastic differential equations. Hence, current solution methodologies typically ignore the noise effect. On the other hand, the inclusion of noise in the HJB framework is very straightforward. Furthermore, the stochastic HJB equation of a control-affine nonlinear stochastic system with a quadratic control cost function and an arbitrary state cost function can be formulated as a path integral (PI) problem. However, due to curse of dimensionality, it might not be possible to utilize the PI formulation for obtaining comprehensive solutions over the entire operating domain. A neural network structure called the adaptive critic design paradigm is used to effectively handle this difficulty. In this paper, a novel adaptive critic approach using the PI formulation is proposed for solving stochastic optimal control problems. The potential of the algorithm is demonstrated through simulation results from a couple of benchmark problems. [ABSTRACT FROM PUBLISHER]

This paper proposes a new iterative solution method for nonlinear stochastic optimal control problems based on path integral analysis. First, we provide an iteration law for solving a stochastic Hamilton-Jacobi-Bellman (SHJB) equation associated to this problem, which is a nonlinear partial differential equation (PDE) of second order. Each iteration procedure of the proposed method is represented by a Cauchy problem for a linear parabolic PDE, and its explicit solution is given by the Feynman-Kac formula. Second, we derive a suboptimal feedback controller at each iteration by using the path integral analysis. Third, the convergence property of the proposed method is investigated. Here, some conditions are provided so that the sequence of solutions for the proposed iteration converges, and the SHJB equation is satisfied. Finally, numerical simulations demonstrate the effectiveness of the proposed method. [ABSTRACT FROM PUBLISHER]

We address the problem of minimizing the long-run expected average cost of a complex system consisting of interactive subsystems. We formulate a multiobjective optimization problem of the one-stage expected costs of the subsystems and provide a duality framework to prove that the control policy yielding the Pareto optimal solution minimizes the average cost criterion of the system. We provide the conditions of existence and a geometric interpretation of the solution. For practical situations with constraints consistent to those studied here, our results imply that the Pareto control policy may be of value when we seek to derive online the optimal control policy in complex systems. [ABSTRACT FROM AUTHOR]

We address the problem of steering the state of a linear stochastic system to a prescribed distribution over a finite horizon with minimum energy, and the problem to maintain the state at a stationary distribution over an infinite horizon with minimum power. For both problems the control and Gaussian noise channels are allowed to be distinct, thereby, placing the results of this paper outside of the scope of previous work both in probability and in control. The special case where the disturbance and control enter through the same channels has been addressed in the first part of this work that was presented as Part I. Herein, we present sufficient conditions for optimality in terms of a system of dynamically coupled Riccati equations in the finite horizon case and in terms of algebraic conditions for the stationary case. We then address the question of feasibility for both problems. For the finite-horizon case, provided the system is controllable, we prove that without any restriction on the directionality of the stochastic disturbance it is always possible to steer the state to any arbitrary Gaussian distribution over any specified finite time-interval. For the stationary infinite horizon case, it is not always possible to maintain the state at an arbitrary Gaussian distribution through constant state-feedback. It is shown that covariances of admissible stationary Gaussian distributions are characterized by a certain Lyapunov-like equation and, in fact, they coincide with the class of stationary state covariances that can be attained by a suitable stationary colored noise as input. We finally address the question of how to compute suitable controls numerically. We present an alternative to solving the system of coupled Riccati equations, by expressing the optimal controls in the form of solutions to (convex) semi-definite programs for both cases. We conclude with an example to steer the state covariance of the distribution of inertial particles to an admissible stationary Gaussian distribution over a finite interval, to be maintained at that stationary distribution thereafter by constant-gain state-feedback control. [ABSTRACT FROM PUBLISHER]

This paper examines stochastic optimal control problems in which the state is perfectly known, but the controller's measure of time is a stochastic process derived from a strictly increasing Lévy process. We provide dynamic programming results for continuous-time finite-horizon control and specialize these results to solve a noisy-time variant of the linear quadratic regulator problem and a portfolio optimization problem with random trade activity rates. For the linear quadratic case, the optimal controller is linear and can be computed from a generalization of the classical Riccati differential equation. [ABSTRACT FROM PUBLISHER]

We study Dynamic Games with randomly entering players, staying in the game for different lengths of time. Particularly, a class of Discrete Time Linear Quadratic (LQ) Games, involving a major player who has an infinite time horizon and a random number of minor players is considered. The number of the new minor players, entering at some instant of time, is random and it is described by a Markov chain. The problem of the characterization of a Nash equilibrium, consisting of Linear Feedback Strategies, is reformulated as a set of coupled finite and infinite horizon LQ optimal control problems for Markov Jump Linear Systems (MJLS). Sufficient conditions characterizing Nash equilibrium are then derived. The problem of Games involving a large number of minor players is then addressed using a Mean Field (MF) approach and asymptotic $\varepsilon$—Nash equilibrium results are derived. Sufficient conditions for the existence of a MF Nash equilibrium are finally stated. [ABSTRACT FROM AUTHOR]

The stochastic optimal control of nonlinear networked control systems (NNCSs) using neuro-dynamic programming (NDP) over a finite time horizon is a challenging problem due to terminal constraints, system uncertainties, and unknown network imperfections, such as network-induced delays and packet losses. Since the traditional iteration or time-based infinite horizon NDP schemes are unsuitable for NNCS with terminal constraints, a novel time-based NDP scheme is developed to solve finite horizon optimal control of NNCS by mitigating the above-mentioned challenges. First, an online neural network (NN) identifier is introduced to approximate the control coefficient matrix that is subsequently utilized in conjunction with the critic and actor NNs to determine a time-based stochastic optimal control input over finite horizon in a forward-in-time and online manner. Eventually, Lyapunov theory is used to show that all closed-loop signals and NN weights are uniformly ultimately bounded with ultimate bounds being a function of initial conditions and final time. Moreover, the approximated control input converges close to optimal value within finite time. The simulation results are included to show the effectiveness of the proposed scheme. [ABSTRACT FROM AUTHOR]

A class of stochastic processes characterized by rapid transitions in their structure is considered and the quickest detection of such transitions is studied in a Bayesian framework. The emphasis is on stochastic processes consisting of a randomly arrived causal pulse (possibly with a set of random parameters such as amplitude and duration) and an additive white Gaussian noise. In this model, the pulse shape and the prior joint density of the arrival time and other random parameters are assumed known. The task of quickest detection in this paper is described mathematically by minimizing the expected detection error. The detection error is represented by a nonlinear function of the distance between the actual transition time and its associated detection time. The assumptions on this function are fairly mild and allow to flexibly design its shape for a desired trade-off between the detection delay and the false alarm rate. Two special cases of such design are well known error measures: mean squared and mean absolute error. The quickest detection problem—a subclass of optimal stopping time problems—is formulated as a stochastic optimal control problem and is resolved using dynamic programming. The optimal detection rule is determined in terms of the solution of an integral equation that cannot be directly solved due to its complexity. This equation is later used to develop a class of suboptimal detection rules and a lower bound on the minimum error. Using this lower bound, it is shown for a numerical example that the suboptimal detector is nearly optimal. [ABSTRACT FROM PUBLISHER]

Optimal sensor scheduling with applications to networked estimation and control systems is considered. We model sensor measurement and transmission instances using jumps between states of a continuous-time Markov chain. We introduce a cost function for this Markov chain as the summation of terms depending on the average sampling frequencies of the subsystems and the effort needed for changing the parameters of the underlying Markov chain. By minimizing this cost function through extending Brockett's recent approach to optimal control of Markov chains, we extract an optimal scheduling policy to fairly allocate the network resources among the control loops. We study the statistical properties of this scheduling policy in order to compute upper bounds for the closed-loop performance of the networked system, where several decoupled scalar subsystems are connected to their corresponding estimator or controller through a shared communication medium. We generalize the estimation results to observable subsystems of arbitrary order. Finally, we illustrate the developed results numerically on a networked system composed of several decoupled water tanks. [ABSTRACT FROM PUBLISHER]

We derive an explicit characterization of the stability region of stationary multi-queue multi-server (MQMS) queueing system by means of a finite set of linear inequalities. More specifically, we explicitly determine the coefficients of the linear inequalities describing the facet-defining hyperplanes of the stability region polytope. Such a characterization is useful for performance evaluation of certain scheduling algorithms such as maximum weight (MW) policy. Our results can be used for studying the asymptotic behavior of the MW policy and computing bounds for the average queueing delay, as well as limiting moments of the queue sizes in heavy-traffic regime. Furthermore, it may be directly applied as the constraint set of network stochastic optimization problems to provide an offline computational solution for such problems. Finally, we use our methodology to characterize the stability region of a fluid model MQMS system which is described by an infinite number of linear inequalities. For such a model, we present an example and show that depending on the channel distribution, the stability region can be instead characterized by a finite set of non-linear inequalities. [ABSTRACT FROM AUTHOR]