An actor-critic algorithm with function approximation for discounted cost constrained Markov decision processes

We develop in this article the first actor-critic reinforcement learning algorithm with function approximation for a problem of control under multiple inequality constraints. We consider the infinite horizon discounted cost framework in which both the objective and the constraint functions are suitable expected policy-dependent discounted sums of certain sample path functions. We apply the Lagrange multiplier method to handle the inequality constraints. Our algorithm makes use of multi-timescale stochastic approximation and incorporates a temporal difference (TD) critic and an actor that makes a gradient search in the space of policy parameters using efficient simultaneous perturbation stochastic approximation (SPSA) gradient estimates. We prove the asymptotic almost sure convergence of our algorithm to a locally optimal policy. (C) 2010 Elsevier B.V. All rights reserved.

Free vibration analysis Of stochastic strings

The free vibration of strings with randomly varying mass and stiffness is considered. The joint probability density functions of the eigenvalues and eigenfunctions are characterized in terms of the solution of a pair of stochastic non-linear initial value problems. Analytical solutions of these equations based on the method of stochastic averaging are obtained. The effects of the mean and autocorrelation of the mass process are included in the analysis. Numerical results for the marginal probability density functions of eigenvalues and eigenfunctions are obtained and are found to compare well with Monte Carlo simulation results. The random eigenvalues, when normalized with respect to their corresponding deterministic values, are observed to tend to become first order stochastically stationary with respect to the mode count.

Frontier Based Multiple Goal Search in Unknown Environments

We present a frontier based algorithm for searching multiple goals in a fully unknown environment, with only information about the regions where the goals are most likely to be located. Our algorithm chooses an ``active goal'' from the ``active goal list'' generated by running a Traveling Salesman Problem (Tsp) routine with the given centroid locations of the goal regions. We use the concept of ``goal switching'' which helps not only in reaching more number of goals in given time, but also prevents unnecessary search around the goals that are not accessible (surrounded by walls). The simulation study shows that our algorithm outperforms Multi-Heuristic LRTA* (MELRTA*) which is a significant representative of multiple goal search approaches in an unknown environment, especially in environments with wall like obstacles.

Layered Tabu Search Algorithm for Large-MIMO Detection and a Lower Bound on ML Performance

In this paper, we are concerned with low-complexity detection in large multiple-input multiple-output (MIMO) systems with tens of transmit/receive antennas. Our new contributions in this paper are two-fold. First, we propose a low-complexity algorithm for large-MIMO detection based on a layered low-complexity local neighborhood search. Second, we obtain a lower bound on the maximum-likelihood (ML) bit error performance using the local neighborhood search. The advantages of the proposed ML lower bound are i) it is easily obtained for MIMO systems with large number of antennas because of the inherent low complexity of the search algorithm, ii) it is tight at moderate-to-high SNRs, and iii) it can be tightened at low SNRs by increasing the number of symbols in the neighborhood definition. Interestingly, the proposed detection algorithm based on the layered local search achieves bit error performances which are quite close to this lower bound for large number of antennas and higher-order QAM. For e. g., in a 32 x 32 V-BLAST MIMO system, the proposed detection algorithm performs close to within 1.7 dB of the proposed ML lower bound at 10(-3) BER for 16-QAM (128 bps/Hz), and close to within 4.5 dB of the bound for 64-QAM (192 bps/Hz).

Precipitation in small systems-I. stochastic analysis

Precipitation in small droplets involving emulsions, microemulsions or vesicles is important for Producing multicomponent ceramics and nanoparticles. Because of the random nature of nucleation and the small number of particles in a droplet, the use of a deterministic population balance equation for predicting the number density of particles may lead to erroneous results even for evaluating the mean behavior of such systems. A comparison between the predictions made through stochastic simulation and deterministic population balance involving small droplets has been made for two simple systems, one involving crystallization and the other a single-component precipitation. The two approaches have been found to yield quite different results under a variety of conditions. Contrary to expectation, the smallness of the population alone does not cause these deviations. Thus, if fluctuation in supersaturation is negligible, the population balance and simulation predictions concur. However, for large fluctuations in supersaturation, the predictions differ significantly, indicating the need to take the stochastic nature of the phenomenon into account. This paper describes the stochastic treatment of populations, which involves a sequence of so-called product density equations and forms an appropriate framework for handling small systems.

Multiple UAV Coalitions for a Search and Prosecute Mission

Unmanned aerial vehicles (UAVs) have the potential to carry resources in support of search and prosecute operations. Often to completely prosecute a target, UAVs may have to simultaneously attack the target with various resources with different capacities. However, the UAVs are capable of carrying only limited resources in small quantities, hence, a group of UAVs (coalition) needs to be assigned that satisfies the target resource requirement. The assigned coalition must be such that it minimizes the target prosecution delay and the size of the coalition. The problem of forming coalitions is computationally intensive due to the combinatorial nature of the problem, but for real-time applications computationally cheap solutions are required. In this paper, we propose decentralized sub-optimal (polynomial time) and decentralized optimal coalition formation algorithms that generate coalitions for a single target with low computational complexity. We compare the performance of the proposed algorithms to that of a global optimal solution for which we need to solve a centralized combinatorial optimization problem. This problem is computationally intensive because the solution has to (a) provide a coalition for each target, (b) design a sequence in which targets need to be prosecuted, and (c) take into account reduction of UAV resources with usage. To solve this problem we use the Particle Swarm Optimization (PSO) technique. Through simulations, we study the performance of the proposed algorithms in terms of mission performance, complexity of the algorithms and the time taken to form the coalition. The simulation results show that the solution provided by the proposed algorithms is close to the global optimal solution and requires far less computational resources.

Automated Multi-Agent Search Using Centroidal Voronoi Configuration

This paper addresses the problem of automated multiagent search in an unknown environment. Autonomous agents equipped with sensors carry out a search operation in a search space, where the uncertainty, or lack of information about the environment, is known a priori as an uncertainty density distribution function. The agents are deployed in the search space to maximize single step search effectiveness. The centroidal Voronoi configuration, which achieves a locally optimal deployment, forms the basis for the proposed sequential deploy and search strategy. It is shown that with the proposed control law the agent trajectories converge in a globally asymptotic manner to the centroidal Voronoi configuration. Simulation experiments are provided to validate the strategy. Note to Practitioners-In this paper, searching an unknown region to gather information about it is modeled as a problem of using search as a means of reducing information uncertainty about the region. Moreover, multiple automated searchers or agents are used to carry out this operation optimally. This problem has many applications in search and surveillance operations using several autonomous UAVs or mobile robots. The concept of agents converging to the centroid of their Voronoi cells, weighted with the uncertainty density, is used to design a search strategy named as sequential deploy and search. Finally, the performance of the strategy is validated using simulations.

Genetic search: Analysis using fitness moments

Genetic Algorithms are efficient and robust search methods that are being employed in a plethora of applications with extremely large search spaces. The directed search mechanism employed in Genetic Algorithms performs a simultaneous and balanced, exploration of new regions in the search space and exploitation of already discovered regions.This paper introduces the notion of fitness moments for analyzing the working of Genetic Algorithms (GAs). We show that the fitness moments in any generation may be predicted from those of the initial population. Since a knowledge of the fitness moments allows us to estimate the fitness distribution of strings, this approach provides for a method of characterizing the dynamics of GAs. In particular the average fitness and fitness variance of the population in any generation may be predicted. We introduce the technique of fitness-based disruption of solutions for improving the performance of GAs. Using fitness moments, we demonstrate the advantages of using fitness-based disruption. We also present experimental results comparing the performance of a standard GA and GAs (CDGA and AGA) that incorporate the principle of fitness-based disruption. The experimental evidence clearly demonstrates the power of fitness based disruption.

Stability of stochastic Leipholz column with stochastic loading

The Leipholz column which is having the Young modulus and mass per unit length as stochastic processes and also the distributed tangential follower load behaving stochastically is considered. The non self-adjoint differential equation and boundary conditions are considered to have random field coefficients. The standard perturbation method is employed. The non self-adjoint operators are used within the regularity domain. Full covariance structure of the free vibration eigenvalues and critical loads is derived in terms of second order properties of input random fields characterizing the system parameter fluctuations. The mean value of critical load is calculated using the averaged problem and the corresponding eigenvalue statistics are sought. Through the frequency equation a transformation is done to yield load parameter statistics. A numerical study incorporating commonly observed correlation models is reported which illustrates the full potentials of the derived expressions.

Stochastic differential games: Occupation measure based approach

A new approach based on occupation measures is introduced for studying stochastic differential games. For two-person zero-sum games, the existence of values and optimal strategies for both players is established for various payoff criteria. ForN-person games, the existence of equilibria in Markov strategies is established for various cases.

Stochastic fluctuations of the solar dynamo

Attempts in the past to model the irregularities of the solar cycle (such as the Maunder minimum) were based on studies of the nonlinear feedback of magnetic fields on the dynamo source terms. Since the alpha-coefficient is obtained by averaging over the turbulence, it is expected to have stochastic fluctuations, and we show that these fluctuations can explain the irregularities of the solar cycle in a more satisfactory way. We solve the dynamo equations in a slab with a single mode, taking the alpha-coefficient to be constant in space but fluctuating stochastically in time with some given amplitude and given correlation time. The same level of percentile fluctuations (about 10 %) produces no effect on an alpha-omega dynamo, but makes an alpha-2 dynamo completely chaotic. The level of irregularities in an alpha-2-omega dynamo qualitatively agrees with the solar behavior, reinforcing the conclusion of Choudhuri (1990a) that the solar dynamo is of the alpha-2-omega-type. The irregularities are found to increase on increasing either the amplitude or the correlation time of the stochastic fluctuations. The alpha-quenching mechanism tends to make the system stable against the irregularities and hence it is inferred that the alpha-quenching should not be too strong so that the irregularities are not completely suppressed. We also present a simple-minded analysis to understand why the stochastic fluctuations in the alpha-omega, alpha-2-omega and alpha-2 regimes have such different outcomes.

Stochastic modelling of flexible manufacturing systems

Mathematical modelling plays a vital role in the design, planning and operation of flexible manufacturing systems (FMSs). In this paper, attention is focused on stochastic modelling of FMSs using Markov chains, queueing networks, and stochastic Petri nets. We bring out the role of these modelling tools in FMS performance evaluation through several illustrative examples and provide a critical comparative evaluation. We also include a discussion on the modelling of deadlocks which constitute an important source of performance degradation in fully automated FMSs.

Unwinding of heterologous DNA by RecA protein during the search for homologous sequences

The search for homologous sequences promoted by RecA protein in vitro involves a presynaptic filament and naked duplex DNA, the multiple contacts of which produce nucleoprotein networks or coaggregates. The single-stranded DNA within the presynaptic filaments, however, is extended to an axial spacing 1.5 times that of B-form DNA. To investigate this paradoxical difference between the spacing of bases in the RecA presynaptic filament versus the target duplex DNA, we explored the effect of heterologous contacts on the conformation of DNA, and vice versa. In the presence of wheat germ topoisomerase I, RecA presynaptic filaments induced a rapid, limited reduction in the linking number of heterologous circular duplex DNA. This limited unwinding of heterologous duplex DNA, termed heterologous unwinding, was detected within 30 seconds and reached a steady state within a few minutes. Presynaptic filaments that were formed in the presence of ATP?S and separated from free RecA protein by gel filtration also generated a ladder of topoisomers upon incubation with relaxed duplex DNA and topoisomerase. The inhibition of heterologous contacts by 60 mImage -NaCl or 5 mImage -ADP resulted in a corresponding decrease in heterologous unwinding. In reciprocal fashion, the stability or number of heterologous contacts with presynaptic filaments was inversely related to the linking number of circular duplex DNA. These observations show that heterologous contacts with the presynaptic filament cause a limited unwinding of the duplex DNA, and conversely that the ability of the DNA to unwind stabilizes transient heterologous contacts.

Variability of sif and cod of stochastic structural systems

Stochastic structural systems having a stochastic distribution of material properties and stochastic external loadings in space are analysed when a crack of deterministic size is present. The material properties and external loadings are considered to constitute independent, two-dimensional, univariate, real, homogeneous stochastic fields. The stochastic fields are characterized by their means, variances, autocorrelation functions or the equivalent power spectral density functions, and scale fluctuations. The Young's modulus and Poisson's ratio are treated to be stochastic quantities. The external loading is treated to be a stochastic field in space. The energy release rate is derived using the method of virtual crack extension. The deterministic relationship is derived to represent the sensitivities of energy release rate with respect to both virtual crack extension and real system parameter fluctuations. Taylor series expansion is used and truncation is made to the first order. This leads to the determination of second-order properties of the output quantities to the first order. Using the linear perturbations about the mean values of the output quantities, the statistical information about the energy release rates, SIF and crack opening displacements are obtained. Both plane stress and plane strain cases are considered. The general expressions for the SIF in all the three fracture modes are derived and a more detailed analysis is conducted for a mode I situation. A numerical example is given.

A two timescale stochastic approximation scheme for simulation-based parametric optimization

A two timescale stochastic approximation scheme which uses coupled iterations is used for simulation-based parametric optimization as an alternative to traditional "infinitesimal perturbation analysis" schemes, It avoids the aggregation of data present in many other schemes. Its convergence is analyzed, and a queueing example is presented.