skip to main content

Title: Gradient Flow Algorithms for Density Propagation in Stochastic Systems
We develop a new computational framework to solve the partial differential equations (PDEs) governing the flow of the joint probability density functions (PDFs) in continuous-time stochastic nonlinear systems. The need for computing the transient joint PDFs subject to prior dynamics arises in uncertainty propagation, nonlinear filtering and stochastic control. Our methodology breaks away from the traditional approach of spatial discretization or function approximation – both of which, in general, suffer from the “curse-of-dimensionality”. In the proposed framework, we discretize time but not the state space. We solve infinite dimensional proximal recursions in the manifold of joint PDFs, which in the small time-step limit, is theoretically equivalent to solving the underlying transport PDEs. The resulting computation has the geometric interpretation of gradient flow of certain free energy functional with respect to the Wasserstein metric arising from the theory of optimal mass transport. We show that dualization along with an entropic regularization, leads to a cone-preserving fixed point recursion that is proved to be contractive in Thompson metric. A block co-ordinate iteration scheme is proposed to solve the resulting nonlinear recursions with guaranteed convergence. This approach enables remarkably fast computation for non-parametric transient joint PDF propagation. Numerical examples and various extensions are provided to illustrate the scope and efficacy of the proposed approach.  more » « less
Award ID(s):
Author(s) / Creator(s):
Date Published:
Journal Name:
IEEE Transactions on Automatic Control
Page Range / eLocation ID:
1 to 1
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    We study the Schr{\"o}dinger bridge problem (SBP) with nonlinear prior dynamics. In control-theoretic language, this is a problem of minimum effort steering of a given joint state probability density function (PDF) to another over a finite time horizon, subject to a controlled stochastic differential evolution of the state vector. For generic nonlinear drift, we reduce the SBP to solving a system of forward and backward Kolmogorov partial differential equations (PDEs) that are coupled through the boundary conditions, with unknowns being the ``Schr\"{o}dinger factors". We show that if the drift is a gradient vector field, or is of mixed conservative-dissipative nature, then it is possible to transform these PDEs into a pair of initial value problems (IVPs) involving the same forward Kolmogorov operator. We employ a proximal algorithm developed in our prior work to solve these IVPs and compute the Schr\"{o}dinger factors via weighted scattered point cloud evolution in the state space. We provide the algorithmic details and illustrate the proposed framework of solving the SBPs with nonlinear prior dynamics by numerical examples. 
    more » « less
  2. How to steer a given joint state probability density function to another over finite horizon subject to a controlled stochastic dynamics with hard state (sample path) constraints? In applications, state constraints may encode safety requirements such as obstacle avoidance. In this paper, we perform the feedback synthesis for minimum control effort density steering (a.k.a. Schrödinger bridge) problem subject to state constraints. We extend the theory of Schrödinger bridges to account the reflecting boundary conditions for the sample paths, and provide a computational framework building on our previous work on proximal recursions, to solve the same. 
    more » « less
  3. This paper contributes to the emerging viewpoint that governing equations for dynamic state estimation, conditioned on the history of noisy measurements, can be viewed as gradient flow on the manifold of joint probability density functions with respect to suitable metrics. Herein, we focus on the Wonham filter where the prior dynamics is given by a continuous time Markov chain on a finite state space; the measurement model includes noisy observation of the (possibly nonlinear function of) state. We establish that the posterior flow given by the Wonham filter can be viewed as the small time-step limit of proximal recursions of certain functionals on the probability simplex. The results of this paper extend our earlier work where similar proximal recursions were derived for the Kalman-Bucy filter. 
    more » « less
  4. Cyber-physical systems are conducting increasingly complex tasks, which are often modeled using formal languages such as temporal logic. The system’s ability to perform the required tasks can be curtailed by malicious adversaries that mount intelligent attacks. At present, however, synthesis in the presence of such attacks has received limited research attention. In particular, the problem of synthesizing a controller when the required specifications cannot be satisfied completely due to adversarial attacks has not been studied. In this paper, we focus on the minimum violation control synthesis problem under linear temporal logic constraints of a stochastic finite state discrete-time system with the presence of an adversary. A minimum violation control strategy is one that satisfies the most important tasks defined by the user while violating the less important ones. We model the interaction between the controller and adversary using a concurrent Stackelberg game and present a nonlinear programming problem to formulate and solve for the optimal control policy. To reduce the computation effort, we develop a heuristic algorithm that solves the problem efficiently and demonstrate our proposed approach using a numerical case study. 
    more » « less
  5. Facing stochastic variations of the loads due to an increasing penetration of renewable energy generation, online decision making under uncertainty in modern power systems is capturing power researchers' attention in recent years. To address this issue while achieving a good balance between system security and economic objectives, we propose a surrogate-enhanced scheme under a joint chance-constrained (JCC) optimal power-flow (OPF) framework. Starting from a stochastic-sampling procedure, we first utilize the copula theory to simulate the dependence among multivariate uncertain inputs. Then, to reduce the prohibitive computational time required in the traditional Monte-Carlo (MC) method, we propose to use a polynomial-chaos-based surrogate that allows us to efficiently evaluate the power-system model at non-Gaussian distributed sampled values with a negligible computing cost. Learning from the MC simulated samples, we further proposed a hybrid adaptive approach to overcome the conservativeness of the JCC-OPF by utilizing correlation of the system states, which is ignored in the traditional Boole's inequality. The simulations conducted on the modified Illinois test system demonstrate the excellent performance of the proposed method. 
    more » « less