Separable Dynamic Programming and Approximate Decomposition Methods

We consider control, planning, and resource allocation problems involving several independent subsystems that are coupled through a control/decision constraint. We discuss one-step lookahead methods that use an approximate cost-to-go function derived from the solution of single subsystem problems. We propose a new method for constructing such approximations, and derive bounds on the performance of the associated suboptimal policies. We then specialize this method to problems of reachability of target tubes that have the form of a box (a Cartesian product of subsystem tubes). We thus obtain inner approximating tubes, which are the union of a finite number of boxes, each involving single subsystem calculations     

Approximate Dynamic Programming for Self-Learning Control

This paper introduces a self-learning control approach based on approximate dynamic programming. Dynamic programming was introduced by Bellman in the 1950’s for solving optimal control problems of nonlinear dynamical systems. Due to its high computational complexity, the applications of dynamic programming have been limited to simple and small problems. The key step in finding approximate solutions to dynamic programming is to estimate the performance index in dynamic programming. The optimal control signal can then be determined by minimizing (or maximizing) the performance index. Artificial neural networks are very efficient tools in representing the performance index in dynamic programming. This paper assumes the use of neural networks for estimating the performance index in dynamic programming and for generating optimal control signals, thus to achieve optimal control through self-learning.     

Bayesian Methods for Efficient Genetic Programming

A Bayesian framework for genetic programming (GP) is presented. This is motivated by the observation that genetic programming iteratively searches populations of fitter programs and thus the information gained in the previous generation can be used in the next generation. The Bayesian GP makes use of Bayes theorem to estimate the posterior distribution of programs from their prior distribution and likelihood for the fitness data observed. Offspring programs are then generated by sampling from the posterior distribution by genetic variation operators. We present two GP algorithms derived from the Bayesian GP framework. One is the genetic programming with the adaptive Occam's razor (AOR) designed to evolve parsimonious programs. The other is the genetic programming with incremental data inheritance (IDI) designed to accelerate evolution by active selection of fitness cases. A multiagent learning task is used to demonstrate the effectiveness of the presented methods. In a series of experiments, AOR reduced solution complexity by 20% and IDI doubled evolution speed, both without loss of solution accuracy.     

Adaptive Feedback Control by Constrained Approximate Dynamic Programming

A constrained approximate dynamic programming (ADP) approach is presented for designing adaptive neural network (NN) controllers with closed-loop stability and performance guarantees. Prior knowledge of the linearized equations of motion is used to guarantee that the closed-loop system meets performance and stability objectives when the plant operates in a linear parameter-varying (LPV) regime. In the presence of unmodeled dynamics or failures, the NN controller adapts to optimize its performance online, whereas constrained ADP guarantees that the LPV baseline performance is preserved at all times. The effectiveness of an adaptive NN flight controller is demonstrated for simulated control failures, parameter variations, and near-stall dynamics.      

Approximate Dynamic Programming for Stochastic Resource Allocation Problems

A stochastic resource allocation model, based on the principles of Markov decision processes (MDPs), is proposed in this paper. In particular, a general-purpose framework is developed, which takes into account resource requests for both instant and future needs. The considered framework can handle two types of reservations (i.e., specified and unspecified time interval reservation requests), and implement an overbooking business strategy to further increase business revenues. The resulting dynamic pricing problems can be regarded as sequential decision-making problems under uncertainty, which is solved by means of stochastic dynamic programming (DP) based algorithms. In this regard, Bellman’s backward principle of optimality is exploited in order to provide all the implementation mechanisms for the proposed reservation pricing algorithm. The curse of dimensionality, as the inevitable issue of the DP both for instant resource requests and future resource reservations, occurs. In particular, an approximate dynamic programming (ADP) technique based on linear function approximations is applied to solve such scalability issues. Several examples are provided to show the effectiveness of the proposed approach.      

基于近似动态规划的微粒群系统参数优化研究

从系统最优控制的角度对微粒群参数的动态优化问题进行探讨. 针对离散动态规划的``维数灾"问题, 将群体启发式随机搜索机制引入动态规划的最优策略求解, 提出了一种群体智能近似动态规划模式; 基于该模式给出简化的确定型微粒群反馈控制系统参数优化的近似计算方法, 并扩展应用于具有随机变量的微粒群系统; 仿真计算得到了微粒群加速因子的近似最优动态规律, 并将所得策略与一种时变加速因子(Time-varying acceleration coefficients, TVAC)策略进行了函数优化性能的比较与分析, 初步实验结果表明该近似动态规划模式可有效地用于微粒群系统参数的动态优化设置.     

Multibody Dynamic Response Optimization with ALM and Approximate Line Search

This paper presents an efficient approach for dynamic responseoptimization based on the ALM method. In this approach, an approximateaugmented Lagrangian is employed for line searches while an exactaugmented Lagrangian is used for finding search directions. An importantfeature of this study is that the approximate augmented Lagrangian forline search is composed of the linearized cost and constraint functionsprojected on the search direction. The quality of this approximationshould be good since an approximate penalty term is found to have almostsecond-order accuracy near the optimum. Quasi-Newton and conjugategradient algorithms are used to find exact search directions and a goldensection method followed by a cubic polynomial approximation is employedfor line search. The numerical performance of the proposed approach isinvestigated by solving eight typical dynamic response optimizationproblems and comparing the results with those in the literature. Thiscomparison shows that the suggested approach is robust and efficient.     

Feature-Based Methods for Large Scale Dynamic Programming

We develop a methodological framework and present a few different ways in which dynamic programming and compact representations can be combined to solve large scale stochastic control problems. In particular, we develop algorithms that employ two types of feature-based compact representations; that is, representations that involve feature extraction and a relatively simple approximation architecture. We prove the convergence of these algorithms and provide bounds on the approximation error. As an example, one of these algorithms is used to generate a strategy for the game of Tetris. Furthermore, we provide a counter-example illustrating the difficulties of integrating compact representations with dynamic programming, which exemplifies the shortcomings of certain simple approaches.     

Model-free Adaptive Dynamic Programming Based Near-optimal Decentralized Tracking Control of Reconfigurable Manipulators

In this paper, a model-free near-optimal decentralized tracking control (DTC) scheme is developed for reconfigurable manipulators via adaptive dynamic programming algorithm. The proposed controller can be divided into two parts, namely local desired controller and local tracking error controller. In order to remove the normboundedness assumption of interconnections, desired states of coupled subsystems are employed to substitute their actual states. Using the local input/output data, the unknown subsystem dynamics of reconfigurable manipulators can be identified by constructing local neural network (NN) identifiers. With the help of the identified dynamics, the local desired control can be derived directly with corresponding desired states. Then, for tracking error subsystems, the local tracking error control is investigated by the approximate improved local cost function via local critic NN and the identified input gain matrix. To overcome the overall error caused by the substitution, identification and critic NN approximation, a robust compensation is added to construct the improved local cost function that reflects the overall error, regulation and control simultaneously. Therefore, the closed-loop tracking system can be guaranteed to be asymptotically stable via Lyapunov stability theorem. Two 2-degree of freedom reconfigurable manipulators with different configurations are employed to demonstrate the effectiveness of the proposed modelfree near-optimal DTC scheme.     

Decentralized Bayesian detection with feedback

A decentralized detection system with feedback and memory using the Bayesian formulation is investigated. The optimization of this system results in a likelihood ratio test at the local detectors for statistically independent observations. In addition, local detector thresholds and the system probability of error are shown to be a function of the fed back global decision. The issue of data transmission between local detectors and the fusion center is addressed. Two protocols are proposed and studied to reduce data transmissions. Numerical examples are also presented for illustration     

利用面向对象的技术扩展ActiveX控件

利用ＡｃｔｉｖｅＸ控件开发应用系统是广泛使用的软件开发技术。研究用面向对象和事件反射技术扩展Ｗａｎｇ图象控件的方法,设计和实现了能完成特定功能、具有新的事件处理的扩展图象控件类。这种方法同样适用其它的控件,为使用ＡｃｔｉｖｅＸ控件提供了新的思路。     

Using an Approximate Bayesian Bootstrap to multiply impute nonignorable missing data

An Approximate Bayesian Bootstrap (ABB) offers advantages in incorporating appropriate uncertainty when imputing missing data, but most implementations of the ABB have lacked the ability to handle nonignorable missing data where the probability of missingness depends on unobserved values. This paper outlines a strategy for using an ABB to multiply impute nonignorable missing data. The method allows the user to draw inferences and perform sensitivity analyses when the missing data mechanism cannot automatically be assumed to be ignorable. Results from imputing missing values in a longitudinal depression treatment trial as well as a simulation study are presented to demonstrate the method’s performance. We show that a procedure that uses a different type of ABB for each imputed data set accounts for appropriate uncertainty and provides nominal coverage.     

动态规划法构建最优二叉查找树的研究

提出动态规划法构建最优二叉查找树的算法模型,并对其进行改进,构造实例表明算法的有效性。     

最优二叉搜索树的动态规划算法研究

动态规划算法的有效性依赖于问题本身具有最优子结构性质和子问题重叠性质。该文给出了用动态规划算法构造最优二叉搜索树的详细步骤,并用C 语言具体实现了该算法。用一定的空间换取时间,提高了解决本问题的效率。     

Approximate Bayesian multibody tracking

Visual tracking of multiple targets is a challenging problem, especially when efficiency is an issue. Occlusions, if not properly handled, are a major source of failure. Solutions supporting principled occlusion reasoning have been proposed but are yet unpractical for online applications. This paper presents a new solution which effectively manages the trade-off between reliable modeling and computational efficiency. The hybrid joint-separable (HJS) filter is derived from a joint Bayesian formulation of the problem, and shown to be efficient while optimal in terms of compact belief representation. Computational efficiency is achieved by employing a Markov random field approximation to joint dynamics and an incremental algorithm for posterior update with an appearance likelihood that implements a physically-based model of the occlusion process. A particle filter implementation is proposed which achieves accurate tracking during partial occlusions, while in cases of complete occlusion, tracking hypotheses are bound to estimated occlusion volumes. Experiments show that the proposed algorithm is efficient, robust, and able to resolve long-term occlusions between targets with identical appearance.     

Using an Approximate Bayesian Bootstrap to multiply impute nonignorable missing data

An Approximate Bayesian Bootstrap (ABB) offers advantages in incorporating appropriate uncertainty when imputing missing data, but most implementations of the ABB have lacked the ability to handle nonignorable missing data where the probability of missingness depends on unobserved values. This paper outlines a strategy for using an ABB to multiply impute nonignorable missing data. The method allows the user to draw inferences and perform sensitivity analyses when the missing data mechanism cannot automatically be assumed to be ignorable. Results from imputing missing values in a longitudinal depression treatment trial as well as a simulation study are presented to demonstrate the method’s performance. We show that a procedure that uses a different type of ABB for each imputed data set accounts for appropriate uncertainty and provides nominal coverage.     

Applying Dynamic Training‐Subset Selection Methods Using Genetic Programming for Forecasting Implied Volatility

Volatility is a key variable in option pricing, trading, and hedging strategies. The purpose of this article is to improve the accuracy of forecasting implied volatility using an extension of genetic programming (GP) by means of dynamic training‐subset selection methods. These methods manipulate the training data in order to improve the out‐of‐sample patterns fitting. When applied with the static subset selection method using a single training data sample, GP could generate forecasting models, which are not adapted to some out‐of‐sample fitness cases. In order to improve the predictive accuracy of generated GP patterns, dynamic subset selection methods are introduced to the GP algorithm allowing a regular change of the training sample during evolution. Four dynamic training‐subset selection methods are proposed based on random, sequential, or adaptive subset selection. The latest approach uses an adaptive subset weight measuring the sample difficulty according to the fitness cases' errors. Using real data from S&P500 index options, these techniques are compared with the static subset selection method. Based on mean squared error total and percentage of non‐fitted observations, results show that the dynamic approach improves the forecasting performance of the generated GP models, especially those obtained from the adaptive‐random training‐subset selection method applied to the whole set of training samples.     

近似动态规划在双容水箱预测控制中的应用

在双容水箱液位优化控制的研究中,由于双容水箱液位控制系统是一个典型的具有大滞后、非线性特征的难控系统,造成系统液位控制不稳定.为解决上述问题,提出一种近似动态规划的预测控制算法,建立反映系统预测时域内参考轨迹与预测输出偏差的性能指标函数J.将函数J的优化问题看作动态规划问题,为了避免“维数灾”,采用近似动态规划求解J的近似值,获得最(次)优控制策略.算法包括评价网络、模型网络和执行网络三部分.评价网络近似性能指标函数,模型网络近似系统输入输出关系,执行网络给出相应控制策略.通过不断在线调整各网络参数,使系统输出逼近参考液位.仿真结果表明,与经典PID算法相比,改进算法表现出更好的控制效果.