This content will become publicly available on October 18, 2024
 Award ID(s):
 1932529
 NSFPAR ID:
 10482834
 Publisher / Repository:
 IEEE
 Date Published:
 Journal Name:
 Journal of Guidance, Control, and Dynamics
 ISSN:
 07315090
 Page Range / eLocation ID:
 1 to 14
 Subject(s) / Keyword(s):
 ["Path Integral Methods, Stochastic Control, Barrier Functions"]
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

In this work, we propose a trajectory generation method for robotic systems with contact force constraint based on optimal control and reachability analysis. Normally, the dynamics and constraints of the contactconstrained robot are nonlinear and coupled to each other. Instead of linearizing the model and constraints, we directly solve the optimal control problem to obtain the feasible state trajectory and the control input of the system. A tractable optimal control problem is formulated which is addressed by dual approaches, which are samplingbased dynamic programming and rigorous reachability analysis. The samplingbased method and Partially Observable Markov Decision Process (POMDP) are used to break down the endtoend trajectory generation problem via samplewise optimization in terms of given conditions. The result generates sequential pairs of subregions to be passed to reach the final goal. The reachability analysis ensures that we will find at least one trajectory starting from a given initial state and going through a sequence of subregions. The distinctive contributions of our method are to enable handling the intricate contact constraint coupled with system’s dynamics due to the reduction of computational complexity of the algorithm. We validate our method using extensive numerical simulations with a legged robot.more » « less

Abstract In this paper, we study multistage stochastic mixedinteger nonlinear programs (MSMINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with
nonLipschitzian value functions and multistage stochastic mixedinteger linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MSMINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a stage stochastic MINLP satisfying$$(T+1)$$ $(T+1)$L exact Lipschitz regularization withd dimensional state spaces, to obtain an optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by$$\varepsilon $$ $\epsilon $ , and is lower bounded by$${\mathcal {O}}((\frac{2LT}{\varepsilon })^d)$$ $O\left({\left(\frac{2LT}{\epsilon}\right)}^{d}\right)$ for the general case or by$${\mathcal {O}}((\frac{LT}{4\varepsilon })^d)$$ $O\left({\left(\frac{\mathrm{LT}}{4\epsilon}\right)}^{d}\right)$ for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity depends$${\mathcal {O}}((\frac{LT}{8\varepsilon })^{d/21})$$ $O\left({\left(\frac{\mathrm{LT}}{8\epsilon}\right)}^{d/21}\right)$polynomially on the number of stages. We further show that the iteration complexity dependslinearly onT , if all the state spaces are finite sets, or if we seek a optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale with$$(T\varepsilon )$$ $\left(T\epsilon \right)$T . To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed in the general setting of multistage stochastic mixedinteger optimization. 
null (Ed.)We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions. Such problems arise widely in the theory of random graphs, theoretical computer science, and statistical physics. Two concrete problems we consider are (a) optimizing the Hamiltonian of a spherical or Ising pspin glass model, and (b) finding a large independent set in a sparse ErdosRenyi graph. Two families of algorithms are considered: (a) lowdegree polynomials of the inputa general framework that captures methods such as approximate message passing and local algorithms on sparse graphs, among others; and (b) the Langevin dynamics algorithm, a canonical Monte Carlo analogue of the gradient descent algorithm (applicable only for the spherical pspin glass Hamiltonian). We show that neither family of algorithms can produce nearly optimal solutions with high probability. Our proof uses the fact that both models are known to exhibit a variant of the overlap gap property (OGP) of nearoptimal solutions. Specifically, for both models, every two solutions whose objective values are above a certain threshold are either close or far from each other. The crux of our proof is the stability of both algorithms: a small perturbation of the input induces a small perturbation of the output. By an interpolation argument, such a stable algorithm cannot overcome the OGP barrier. The stability of the Langevin dynamics is an immediate consequence of the wellposedness of stochastic differential equations. The stability of lowdegree polynomials is established using concepts from Gaussian and Boolean Fourier analysis, including noise sensitivity, hypercontractivity, and total influence.more » « less

We develop a new computational framework to solve the partial differential equations (PDEs) governing the flow of the joint probability density functions (PDFs) in continuoustime 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 “curseofdimensionality”. 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 timestep 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 conepreserving fixed point recursion that is proved to be contractive in Thompson metric. A block coordinate iteration scheme is proposed to solve the resulting nonlinear recursions with guaranteed convergence. This approach enables remarkably fast computation for nonparametric transient joint PDF propagation. Numerical examples and various extensions are provided to illustrate the scope and efficacy of the proposed approach.more » « less

Abstarct This work presents a theoretical framework for the safety‐critical control of time delay systems. The theory of control barrier functions, that provides formal safety guarantees for delay‐free systems, is extended to systems with state delay. The notion of control barrier functionals is introduced, to attain formal safety guarantees by enforcing the forward invariance of safe sets defined in the infinite dimensional state space. The proposed framework is able to handle multiple delays and distributed delays both in the dynamics and in the safety condition, and provides an affine constraint on the control input that yields provable safety. This constraint can be incorporated into optimization problems to synthesize pointwise optimal and provable safe controllers. The applicability of the proposed method is demonstrated by numerical simulation examples.