An official website of the United States government
Kinematic synthesis to meet an approximate motion specification naturally forms a constrained optimization problem. Instead of using local methods, we conduct global design searches by direct computation of all critical points. The idea is not new, but performed at scale is only possible through modern polynomial homotopy continuation solvers. Such a complete computation finds all minima, including the global, which allows for a full exploration of the design space, whereas local solvers can only find the minimum nearest to an initial guess. We form equality-constrained objective functions that pertain to the synthesis of spherical four-bar linkages for approximate function generation. We consider the general case where all mechanism dimensions may vary and a more specific case that enables the placement of ground pivots. The former optimization problem is shown to permit 268 sets of critical points, and the latter permits 61 sets. Critical points are classified as saddles or minima through a post-process eigenanalysis of the projected Hessian. The discretization points are contained within the coefficients of the stationarity polynomials, so the algebraic structure of the synthesis equations remains invariant to the number of points. The results of our computational work were used to design a mechanism that coordinates the folding wings. We also use this method to parameterize mechanism dimensions for a family of hyperbolic curves.
more »
« less
Complete Solutions for the Approximate Synthesis of Spherical Four-Bar Function Generators
Abstract Kinematic synthesis to meet an approximate motion specification naturally forms a constrained optimization problem. In this work, we conduct global design searches by direct computation of all critical points through stationarity conditions. The idea is not new, but performed at scale is only possible through modern polynomial homotopy continuation solvers. Such a complete computation finds all minima, including the global, serving as a powerful design exploration technique. We form equality constrained objective functions that pertain to the synthesis of spherical four-bar linkages for approximate function generation. For each problem considered, Lagrangian stationarity conditions set up a square system of polynomials. We consider the most general case where all mechanism dimensions may vary, and a more specific case that enables the placement of ground pivots. The former optimization problem is shown to permit an estimated maximum of 268 sets of critical points, and the latter permits 61 sets. Critical points are classified as saddles or minima through a post-process eigenanalysis of the projected Hessian. Approximate motion is specified as discretized points from a desired input-output angle function. The coefficients of the stationarity polynomials can be expressed as summations of symmetric matrices indexed by the discretization points. We take the sums themselves to parameterize these polynomials rather than constituent terms (the discrete data). In this way, the algebraic structure of the synthesis equations remains invariant to the number of discretization points chosen. The results of our computational work were used to design a mechanism that coordinates the unfolding of wings for a deployable aircraft.
more »
« less
- Award ID(s):
- 2144732
- PAR ID:
- 10483981
- Publisher / Repository:
- American Society of Mechanical Engineers
- Date Published:
- ISBN:
- 978-0-7918-8736-3
- Format(s):
- Medium: X
- Location:
- Boston, Massachusetts, USA
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this paper, we form a constrained optimization problem for spherical four-bar motion generation. Instead of using local optimization methods, all critical points are found using homotopy continuation solvers. The complete solution set provides a full view of the optimization landscape and gives the designer more freedom in selecting a mechanism. The motion generation problem admits 61 critical points, of which two must be selected for each four-bar mechanism. We sort solutions by objective value and perform a second order analysis to determine if the solution is a minimum, maximum, or saddle point. We apply our approximate synthesis technique to two applications: a hummingbird wing mechanism and a sea turtle flipper gait. Suitable mechanisms were selected from the respective solution sets and used to build physical prototypes.more » « less
-
Semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of low-rank solutions and low complexity algorithms, we consider the Burer–Monteiro factorization approach for solving SDPs. For a large class of SDPs, upon random perturbation of the cost matrix, with high probability, we show that all approximate second-order stationary points are approximate global optima for the penalty formulation of appropriately rank-constrained SDPs, as long as the number of constraints scales sub-quadratically with the desired rank. Our result is based on a simple penalty function formulation of the rank-constrained SDP along with a smoothed analysis to avoid worst-case cost matrices. We particularize our results to two applications, namely, Max-Cut and matrix completion.more » « less
-
Beattie, C.A.; Benner, P.; Embree, M.; Gugercin, S.; Lefteriu, S. (Ed.)This paper introduces reduced order model (ROM) based Hessian approximations for use in inexact Newton methods for the solution of optimization problems implicitly constrained by a large-scale system, typically a discretization of a partial differential equation (PDE). The direct application of an inexact Newton method to this problem requires the solution of many PDEs per optimization iteration. To reduce the computational complexity, a ROM Hessian approximation is proposed. Since only the Hessian is approximated, but the original objective function and its gradient is used, the resulting inexact Newton method maintains the first-order global convergence property, under suitable assumptions. Thus even computationally inexpensive lower fidelity ROMs can be used, which is different from ROM approaches that replace the original optimization problem by a sequence of ROM optimization problem and typically need to accurately approximate function and gradient information of the original problem. In the proposed approach, the quality of the ROM Hessian approximation determines the rate of convergence, but not whether the method converges. The projection based ROM is constructed from state and adjoint snapshots, and is relatively inexpensive to compute. Numerical examples on semilinear parabolic optimal control problems demonstrate that the proposed approach can lead to substantial savings in terms of overall PDE solves required.more » « less
-
This paper reports a novel result: with proper robot models based on geometric mechanics, one can formulate the kinodynamic motion planning problems for rigid body systems as exact polynomial optimization problems. Due to the nonlinear rigid body dynamics, the motion planning problem for rigid body systems is nonconvex. Existing global optimization-based methods do not parameterize 3D rigid body motion efficiently; thus, they do not scale well to long-horizon planning problems. We use Lie groups as the configuration space and apply the variational integrator to formulate the forced rigid body dynamics as quadratic polynomials. Then, we leverage Lasserre’s hierarchy of moment relaxation to obtain the globally optimal solution via semidefinite programming. By leveraging the sparsity of the motion planning problem, the proposed algorithm has linear complexity with respect to the planning horizon. This paper demonstrates that the proposed method can provide globally optimal solutions or certificates of infeasibility at the second-order relaxation for 3D drone landing using full dynamics and inverse kinematics for serial manipulators. Moreover, we extend the algorithms to multi-body systems via the constrained variational integrators. The testing cases on cart-pole and drone with cable-suspended load suggest that the proposed algorithms can provide rank-one optimal solutions or nontrivial initial guesses. Finally, we propose strategies to speed up the computation, including an alternative formulation using quaternion, which provides empirically tight relaxations for the drone landing problem at the first-order relaxation.more » « less
