A scenario-based stochastic programming model for water supplies from the highland lakes

A scenario-based, multistage stochastic programming model is developed for the management of the Highland Lakes by the Lower Colorado River Authority (LCRA) in Central Texas. The model explicitly considers two objectives: (1) maximize the expected revenue from the sale of interruptible water while reliably maintaining firm water supply, and (2) maximize recreational benefits. Input data can be represented by a scenario tree, built empirically from a segment of the historical flow record. Thirty-scenario instances of the model are solved using both a primal simplex method and Benders decomposition, and results show that the first-stage ('here and now') decision of how much interruptible water to contract for the coming year is highly dependent on the initial (current) reservoir storage levels. Sensitivity analysis indicates that model results can be improved by using a scenario generation technique which better preserves the serial correlation of flows. Ultimately, it is hoped that use of the model will improve the LCRA's operational practices by helping to identify flexible policies that appropriately hedge against unfavorable inflow scenarios.     

Distributed dynamic programming for discrete-time stochastic control, and idempotent algorithms

Idempotent methods have been found to be extremely fast for the solution of dynamic programming equations associated with deterministic control problems. The original methods exploited the idempotent (e.g., max-plus) linearity of the associated semigroup operator. It is now known that curse-of-dimensionality-free idempotent methods do not require this linearity. Instead, it is sufficient that certain solution forms are retained through application of the associated semigroup operator. Here, we see that idempotent methods may be used to solve some classes of stochastic control problems. The key is the use of the idempotent distributive property. We demonstrate this approach for a class of nonlinear, discrete-time stochastic control problems.     

Solution time reduction techniques of a stochastic dynamic programming approach for hazardous material route selection problem

We use a stochastic dynamic programming (SDP) approach to solve the problem of determining the optimal routing policies in a stochastic dynamic network. Due to its long time for solving SDP, we propose three techniques for pruning stochastic dynamic networks to expedite the process of obtaining optimal routing policies. The techniques include: (1) use of static upper/lower bounds, (2) pre-processing the stochastic dynamic networks by using the start time and origin location of the vehicle, and (3) a mix of pre-processing and upper/lower bounds. Our experiments show that while finding optimal routing policies in stochastic dynamic networks, the last two of the three strategies have a significant computational advantage over conventional SDP. Our main observation from these experiments was that the computational advantage of the pruning strategies that depend on the start time of the vehicle varies according to the time input to the problem. We present the results of this variation in the experiments section. We recommend that while comparing the computational performances of time-dependent techniques, it is very important to test the performance of such strategies at various time inputs.     

On stochastic dynamic programming for solving large-scale planning problems under uncertainty

The stochastic dynamic programming approach outlined here, makes use of the scenario tree in a back-to-front scheme. The multi-period stochastic problems, related to the subtrees whose root nodes are the starting nodes (i.e., scenario groups), are solved at each given stage along the time horizon. Each subproblem considers the effect of the stochasticity of the uncertain parameters from the periods of the given stage, by using curves that estimate the expected future value (EFV) of the objective function. Each subproblem is solved for a set of reference levels of the variables that also have nonzero elements in any of the previous stages besides the given stage. An appropriate sensitivity analysis of the objective function for each reference level of the linking variables allows us to estimate the EFV curves applicable to the scenario groups from the previous stages, until the curves for the first stage have been computed. An application of the scheme to the problem of production planning with logical constraints is presented. The aim of the problem consists of obtaining the planning of tactical production over the scenarios along the time horizon. The expected total cost is minimized to satisfy the product demand. Some computational experience is reported. The proposed approach compares favorably with a state-of-the-art optimization engine in instances on a very large scale.     

Approximate stochastic dynamic programming for sensor scheduling to track multiple targets

The problem of sensor scheduling is to select the number and combination of sensors to activate over time. The goal is usually to trade off tracking performance and sensor usage. We formulate a version of this problem involving multiple targets as a partially observable Markov decision process, and use this formulation to develop a nonmyopic sensor-scheduling scheme. Our scheme integrates sequential multisensor joint probabilistic data association and particle filtering for belief-state estimation, and use a simulation-based Q-value approximation method called completely observable rollout for decision making. We illustrate the effectiveness of our approach by an example with multiple sensors activated simultaneously to track multiple targets. We also explore the trade-off between tracking error and sensor cost using our nonmyopic scheme.     

A simulation-and-regression approach for stochastic dynamic programs with endogenous state variables

We investigate the optimum control of a stochastic system, in the presence of both exogenous (control-independent) stochastic state variables and endogenous (control-dependent) state variables. Our solution approach relies on simulations and regressions with respect to the state variables, but also grafts the endogenous state variable into the simulation paths. That is, unlike most other simulation approaches found in the literature, no discretization of the endogenous variable is required. The approach is meant to handle several stochastic variables, offers a high level of flexibility in their modeling, and should be at its best in non time-homogenous cases, when the optimal policy structure changes with time. We provide numerical results for a dam-based hydropower application, where the exogenous variable is the stochastic spot price of power, and the endogenous variable is the water level in the reservoir.     

Performance bounds and suboptimal policies for linear stochastic control via LMIs

In a recent paper, the authors showed how to compute performance bounds for infinite‐horizon stochastic control problems with linear system dynamics and arbitrary constraints, objective, and noise distribution. In this paper, we extend these results to the finite‐horizon case, with asymmetric costs and constraint sets. In addition, we derive our bounds using a new method, where we relax the Bellman equation to an inequality. The method is based on bounding the objective with a general quadratic function, and using linear matrix inequalities (LMIs) and semidefinite programming (SDP) to optimize the bound. The resulting LMIs are more complicated than in the previous paper (which only used quadratic forms) but this extension allows us to obtain good bounds for problems with substantial asymmetry, such as supply chain problems. The method also yields very good suboptimal control policies, using control‐Lyapunov methods. Copyright © 2010 John Wiley & Sons, Ltd.     

动态规划-粒子群算法在水库优化调度中的应用

水库优化调度是一个典型的具有多约束条件的、动态的、非线性的优化问题。针对这些问题,利用动态规划-粒子群(DP-PSO)算法加以求解。利用动态规划中的多阶段最优策略原理,将水库优化调度问题转化为多阶段决策子问题,各个子问题采用粒子群算法优化求解。数值实验表明,在计算时段较多时,DP-PSO算法计算的可靠性明显优于一般的动态规划(DP)算法,在计算时间上,DP-PSO算法用时较动态规划-遗传算法(DP-GA)少。     

On the existence of stationary optimal policies for partially observed MDPs under the long-run average cost criterion

This paper studies the problem of the existence of stationary optimal policies for finite state controlled Markov chains, with compact action space and imperfect observations, under the long-run average cost criterion. It presents sufficient conditions for existence of solutions to the associated dynamic programming equation, that strengthen past results. There is a detailed discussion comparing the different assumptions commonly found in the literature.     

Adaptive dynamic programming and optimal control of nonlinear nonaffine systems

In this paper, a novel optimal control design scheme is proposed for continuous-time nonaffine nonlinear dynamic systems with unknown dynamics by adaptive dynamic programming (ADP). The proposed methodology iteratively updates the control policy online by using the state and input information without identifying the system dynamics. An ADP algorithm is developed, and can be applied to a general class of nonlinear control design problems. The convergence analysis for the designed control scheme is presented, along with rigorous stability analysis for the closed-loop system. The effectiveness of this new algorithm is illustrated by two simulation examples.     

非线性零和微分对策的事件触发自适应动态规划算法

针对一类非线性零和微分对策问题,本文提出了一种事件触发自适应动态规划(event-triggered adaptive dynamic programming,ET--ADP)算法在线求解其鞍点.首先,提出一个新的自适应事件触发条件.然后,利用一个输入为采样数据的神经网络(评价网络)近似最优值函数,并设计了新型的神经网络权值更新律使得值函数、控制策略及扰动策略仅在事件触发时刻同步更新.进一步地,利用Lyapunov稳定性理论证明了所提出的算法能够在线获得非线性零和微分对策的鞍点且不会引起Zeno行为.所提出的ET--ADP算法仅在事件触发条件满足时才更新值函数、控制策略和扰动策略,因而可有效减少计算量和降低网络负荷.最后,两个仿真例子验证了所提出的ET--ADP算法的有效性.     

信号灯控制的多阶段决策模型及其前向动态规划算法

为研究路口交通信号灯的实时最优控制问题,提出一种以最小化等待时间为目标的多阶段决策模型.该模型利用最短绿灯和红灯时间的结构特征,通过合理选择系统状态和控制变量压缩了模型规模,进而提出了前向动态规划算法以高效得到最优解.数值实验显示,对比于固定时长的周期性控制可以节省路口车辆的等待时间;对比基于混合整数规划的求解方法,可以提高求解效率,满足实时控制的要求.     

Neural network and regression spline value function approximations for stochastic dynamic programming

Dynamic programming is a multi-stage optimization method that is applicable to many problems in engineering. A statistical perspective of value function approximation in high-dimensional, continuous-state stochastic dynamic programming (SDP) was first presented using orthogonal array (OA) experimental designs and multivariate adaptive regression splines (MARS). Given the popularity of artificial neural networks (ANNs) for high-dimensional modeling in engineering, this paper presents an implementation of ANNs as an alternative to MARS. Comparisons consider the differences in methodological objectives, computational complexity, model accuracy, and numerical SDP solutions. Two applications are presented: a nine-dimensional inventory forecasting problem and an eight-dimensional water reservoir problem. Both OAs and OA-based Latin hypercube experimental designs are explored, and OA space-filling quality is considered.     

Remarks on the application of dynamic programming to the optimal path timing of robot manipulators

In this paper, we investigate the use of the dynamic programming approach in the solution of the optimal path timing problem in robotics. This problem is computationally feasible because the path constraint reduces the dimension of the state in the problem to two. The Hamilton–Jacobi–Bellman equation of dynamic programming, a nonlinear first order partial differential equation, is presented and is solved approximately using finite difference methods. Numerical solution of this results in the optimal policy which can then be used to define the optimal path timing by numerical integration. Issues relating to the convergence of the numerical schemes are discussed, and the results are applied to an experimental SCARA manipulator. © 1998 John Wiley & Sons, Ltd.     

Convergence rate analysis of the state increment dynamic programming method

It is shown that if the discretization of the state space is sufficiently fine and if the limiting trajectory is an interior point of the admissible policies then the state increment dynamic programming technique (SIDP) has linear convergence, and the coefficient of convergence can be explicitly related to the control problem components. In the course of this analysis, it is seen that the SIDP method is, in essence, a nonlinear generalization of the block Gauss-Seidel algorithm for solving linear equations. Some consequences of this insight are suggested, and a computational example comparing SIDP with differential dynamic programming is offered.     

允许存储的变周期随机动态车队调度双层模型交替求解策略

针对一类允许存储的变周期随机动态车队调度问题进行研究.难点在于运输任务数量不确定、运输任务可存储、计划周期内各时段长度不同、车辆荷载不同.根据问题表述建立数学模型,进而设定新的决策向量和状态向量,对问题模型进行可分离形式改造.引入排队原理设计运输任务产生机制和模型分离参数拟合过程,在此基础上,建立由内层模型与外层模型共同构成的双层模型体系,并给出双层模型的交替求解算法. 通过仿真实验和数值分析验证了所提出算法的可行性和有效性.     

Finite-horizon neuro-optimal tracking control for a class of discrete-time nonlinear systems using adaptive dynamic programming approach

In this paper, a finite-horizon neuro-optimal tracking control strategy for a class of discrete-time nonlinear systems is proposed. Through system transformation, the optimal tracking problem is converted into designing a finite-horizon optimal regulator for the tracking error dynamics. Then, with convergence analysis in terms of cost function and control law, the iterative adaptive dynamic programming (ADP) algorithm via heuristic dynamic programming (HDP) technique is introduced to obtain the finite-horizon optimal tracking controller which makes the cost function close to its optimal value within an ?-error bound. Three neural networks are used as parametric structures to implement the algorithm, which aims at approximating the cost function, the control law, and the error dynamics, respectively. Two simulation examples are included to complement the theoretical discussions.     

Reclaimed water distribution network design under temporal and spatial growth and demand uncertainties

A significant—but underutilized—water resource is reclaimed water, i.e., treated wastewater that is reintroduced for various purposes. Especially in water scarce regions, reclaimed water is often the only remaining source of water to meet increasing population and water demands. In this paper, we develop a new model formulation for the cost-effective branched reclaimed water network design and solve it with an exact optimization method. We consider both construction and energy costs expended over a twenty-year period. Unlike other formulations, uncertain reclaimed water demands, temporal and spatial population changes are explicitly considered in our two-staged construction and expansion model. In order for the system to meet higher demands during the peak times and to evaluate energy use, we consider two pumping conditions: one with average demands, which is used to compute the average energy consumption, and the other with peak demands, which dominates pipe size and pump station capacity selection. By introducing binary variables that indicate discrete pipe and pump sizes, we linearize the nonlinear hydraulic equations and objective function terms. We develop methods to significantly reduce the problem dimension by exploiting the problem characteristics and network structure. Our computational results indicate that these methods are very effective. Finally, we apply our model to design a reclaimed water network for a realistic municipal system under estimated demand and population scenarios, and analyze the sensitivity of the system to model parameters.     

Choice of approximator and design of penalty function for an approximate dynamic programming based control approach

This paper investigates the choice of function approximator for an approximate dynamic programming (ADP) based control strategy. The ADP strategy allows the user to derive an improved control policy given a simulation model and some starting control policy (or alternatively, closed-loop identification data), while circumventing the ‘curse-of-dimensionality’ of the traditional dynamic programming approach. In ADP, one fits a function approximator to state vs. ‘cost-to-go’ data and solves the Bellman equation with the approximator in an iterative manner. A proper choice and design of function approximator is critical for convergence of the iteration and the quality of final learned control policy, because an approximation error can grow quickly in the loop of optimization and function approximation. Typical classes of approximators used in related approaches are parameterized global approximators (e.g. artificial neural networks) and nonparametric local averagers (e.g. k-nearest neighbor). In this paper, we assert on the basis of some case studies and a theoretical result that a certain type of local averagers should be preferred over global approximators as the former ensures monotonic convergence of the iteration. However, a converged cost-to-go function does not necessarily lead to a stable control policy on-line due to the problem of over-extrapolation. To cope with this difficulty, we propose that a penalty term be included in the objective function in each minimization to discourage the optimizer from finding a solution in the regions of state space where the local data density is inadequately low. A nonparametric density estimator, which can be naturally combined with a local averager, is employed for this purpose.