Moment-Sum-Of-Squares Approach For Motion Planning.
Find the shortest path (i.e., a continuously-differentiable function) $x: [0, T] \rightarrow [-1, 1]^d$ that starts on $x_0 \in R^d$, ends on $x_T \in R^d$, and avoids $m$ (time-varying) obstacles given by polynomial equations of the form $g_i(t, x) \ge 0$ for $i=1,\ldots,m$.
On sum of squares representation of convex forms and generalized Cauchy-Schwarz inequalities.
Published in SIAM J. Appl. Algebra Geometry, 4(2), 377–400..
A convex form of degree larger than one is always nonnegative since it vanishes together with its gradient at the origin. In 2007, Parrilo asked if convex forms are always sums of squares. A few years later, Blekherman answered the question in the negative by showing through volume arguments that for high enough number of variables, there must be convex forms of degree 4 that are not sums of squares. Remarkably, no examples are known to date. In this talk, we show that all convex forms in 4 variables and of degree 4 are sums of squares. We also show that if a conjecture of Blekherman related to the so-called Cayley-Bacharach relations is true, then the same statement holds for convex forms in 3 variables and of degree 6. These are the two minimal cases where one would have any hope of seeing convex forms that are not sums of squares (due to known obstructions). A main ingredient of the proof is the derivation of certain "generalized Cauchy-Schwarz inequalities" which could be of independent interest.
Learning to effectively imitate human teleoperators, with generalization to unseen and dynamic environments, is a promising path to greater autonomy enabling robots to steadily acquire complex skills from supervision. We propose a new motion learning technique rooted in contraction theory and sum-of-squares programming for estimating a control law in the form of a polynomial vector field from a given set of demonstrations. Notably, this vector field is provably optimal for the problem of minimizing imitation loss while providing continuous-time guarantees on the induced imitation behavior. Our method generalizes to new initial and goal poses of the robot and can adapt in real-time to dynamic obstacles during execution, with convergence to teleoperator behavior within a well-defined safety tube. We present an application of our framework for pick-and-place tasks in the presence of moving obstacles on a 7-DOF KUKA IIWA arm. The method compares favorably to other learning-from-demonstration approaches on benchmark handwriting imitation tasks.
We study the problem of learning dynamical systems from very limited data but in presence of “side information”, such as physical laws or contextual knowledge. This is motivated by safety-critical applications where an unknown dynamical system needs to be controlled after a very short learning phase where a few of its trajectories are observed. (Imagine, e.g., the task of autonomously landing a passenger airplane that has gone through sudden wing damage.) We show that sum of squares optimization is particularly suited for exploiting side information in order to assist the task of learning when data is limited.
We study time-varying semidefinite programs (TV-SDPs), which are semidefinite programs whose data (and solutions) are functions of time. Our focus is on the setting where the data varies polynomially with time. We show that under a strict feasibility assumption, restricting the solutions to also be polynomial functions of time does not change the optimal value of the TV-SDP. Moreover, by using a Positivstellensatz on univariate polynomial matrices, we show that the best polynomial solution of a given degree to a TV-SDP can be found by solving a semidefinite program of tractable size. We also provide a sequence of dual problems which can be cast as SDPs and that give upper bounds on the optimal value of a TV-SDP (in maximization form). We prove that under a boundedness assumption, this sequence of upper bounds converges to the optimal value of the TV-SDP. Under the same assumption, we also show that the optimal value of the TV-SDP is attained. We demonstrate the efficacy of our algorithms on a maximum-flow problem with time-varying edge capacities, a wireless coverage problem with time-varying coverage requirements, and on bi-objective semidefinite optimization where the goal is to approximate the Pareto curve in one shot.
A Globally Asymptotically Stable Polynomial Vector Field with Rational Coefficients and no Local Polynomial Lyapunov Function.
Published in Systems & Control Letters.
We give an explicit example of a two-dimensional polynomial vector field of degree seven that has rational coefficients, is globally asymptotically stable, but does not admit an analytic Lyapunov function even locally.
We prove that if a homogeneous, continuously differentiable vector field is asymptotically stable, then it admits a Lyapunov function which is the ratio of two polynomials (i.e., a rational function). We further show that when the vector field is polynomial, the Lyapunov inequalities on both the rational function and its derivative have sums of squares certificates and hence such a Lyapunov function can always be found by semidefinite programming. This generalizes the classical result that an asymptotically stable linear system admits a quadratic Lyapunov function which satisfies a certain linear matrix inequality. In addition to homogeneous vector fields, the result can be useful for showing local asymptotic stability of non-homogeneous systems, by proving asymptotic stability of their lowest order homogeneous component. We show that in absence of homogeneity, globally asymptotically stable polynomial vector fields may fail to admit a rational Lyapunov function, and that in presence of homogeneity, the degree of the numerator of a rational Lyapunov function may need to be arbitrarily high (even for vector fields of fixed degree and dimension). On the other hand, we also give a family of homogeneous polynomial vector fields that admit a low-degree rational Lyapunov function but necessitate polynomial Lyapunov functions of arbitrarily high degree. This shows the potential benefits of working with rational Lyapunov functions, particularly as the ones whose existence we guarantee have structured denominators and are not more expensive to search for than polynomial ones.