Search

Optimization algorithms are pivotal in advancing various scientific and industrial fields but often encounter obstacles such as trapping in local minima, saddle points, and plateaus (flat regions), which makes the convergence to reasonable or near-optimal solutions particularly challenging. This paper presents the Steepest Perturbed Gradient Descent (SPGD), a novel algorithm that innovatively combines the principles of the gradient descent method with periodic uniform perturbation sampling to effectively circumvent these impediments and lead to better solutions whenever possible. SPGD is distinctively designed to generate a set of candidate solutions and select the one exhibiting the steepest loss difference relative to the current solution. It enhances the traditional gradient descent approach by integrating a strategic exploration mechanism that significantly increases the likelihood of escaping sub-optimal local minima and navigating complex optimization landscapes effectively. Our approach not only retains the directed efficiency of gradient descent but also leverages the exploratory benefits of stochastic perturbations, thus enabling a more comprehensive search for global optima across diverse problem spaces. We demonstrate the efficacy of SPGD in solving the 3D component packing problem, an NP-hard challenge. Preliminary results show a substantial improvement over four established methods, particularly on response surfaces with complex topographies and in multidimensional non-convex continuous optimization problems. Comparative analyses with established 2D benchmark functions highlight SPGD's superior performance, showcasing its ability to navigate complex optimization landscapes. These results emphasize SPGD's potential as a versatile tool for a wide range of optimization problems., Comment: 28 pages, 26 figures, submitted to Journal of Mechanical Design

Many machine learning methods have been recently developed to circumvent the high computational cost of the gradient-based topology optimization. These methods typically require extensive and costly datasets for training, have a difficult time generalizing to unseen boundary and loading conditions and to new domains, and do not take into consideration topological constraints of the predictions, which produces predictions with inconsistent topologies. We present a deep learning method based on generative adversarial networks for generative design exploration. The proposed method combines the generative power of conditional GANs with the knowledge transfer capabilities of transfer learning methods to predict optimal topologies for unseen boundary conditions. We also show that the knowledge transfer capabilities embedded in the design of the proposed algorithm significantly reduces the size of the training dataset compared to the traditional deep learning neural or adversarial networks. Moreover, we formulate a topological loss function based on the bottleneck distance obtained from the persistent diagram of the structures and demonstrate a significant improvement in the topological connectivity of the predicted structures. We use numerous examples to explore the efficiency and accuracy of the proposed approach for both seen and unseen boundary conditions in 2D.

The published literature on topology optimization has exploded over the last two decades to include methods that use shape and topological derivatives or evolutionary algorithms formulated on various geometric representations and parametrizations. One of the key challenges of all these methods is the massive computational cost associated with 3D topology optimization problems. We introduce a transfer learning method based on a convolutional neural network that (1) can handle high-resolution 3D design domains of various shapes and topologies; (2) supports real-time design space explorations as the domain and boundary conditions change; (3) requires a much smaller set of high-resolution examples for the improvement of learning in a new task compared to traditional deep learning networks; (4) is multiple orders of magnitude more efficient than the established gradient-based methods, such as SIMP. We provide numerous 2D and 3D examples to showcase the effectiveness and accuracy of our proposed approach, including for design domains that are unseen to our source network, as well as the generalization capabilities of the transfer learning-based approach. Our experiments achieved an average binary accuracy of around 95% at real-time prediction rates. These properties, in turn, suggest that the proposed transfer-learning method may serve as the first practical underlying framework for real-time 3D design exploration based on topology optimization

Current point cloud processing algorithms do not have the capability to automatically extract semantic information from the observed scenes, except in very specialized cases. Furthermore, existing mesh analysis paradigms cannot be directly employed to automatically perform typical shape analysis tasks directly on point cloud models. We present a potent framework for shape analysis, similarity, and segmentation of noisy point cloud models for real objects of engineering interest, models that may be incomplete. The proposed framework relies on spectral methods and the heat diffusion kernel to construct compact shape signatures, and we show that the framework supports a variety of clustering techniques that have traditionally been applied only on mesh models. We developed and implemented one practical and convergent estimate of the Laplace-Beltrami operator for point clouds as well as a number of clustering techniques adapted to work directly on point clouds to produce geometric features of engineering interest. The key advantage of this framework is that it supports practical shape analysis capabilities that operate directly on point cloud models of objects without requiring surface reconstruction or global meshing. We show that the proposed technique is robust against typical noise present in possibly incomplete point clouds, and segment point clouds scanned by depth cameras (e.g. Kinect) into semantically-meaningful sub-shapes., Comment: 21 pages, 20 figures. To appear in The Journal of Computer Aided Geometric Design's Special Issue on Heat Diffusion Equation and Optimal Transport in Geometry Processing and Computer Graphics

An important application of haptic technology to digital product development is in virtual prototyping (VP), part of which deals with interactive planning, simulation, and verification of assembly-related activities, collectively called virtual assembly (VA). In spite of numerous research and development efforts over the last two decades, the industrial adoption of haptic-assisted VP/VA has been slower than expected. Putting hardware limitations aside, the main roadblocks faced in software development can be traced to the lack of effective and efficient computational models of haptic feedback. Such models must 1) accommodate the inherent geometric complexities faced when assembling objects of arbitrary shape; and 2) conform to the computation time limitation imposed by the notorious frame rate requirements---namely, 1 kHz for haptic feedback compared to the more manageable 30-60 Hz for graphic rendering. The simultaneous fulfillment of these competing objectives is far from trivial. This survey presents some of the conceptual and computational challenges and opportunities as well as promising future directions in haptic-assisted VP/VA, with a focus on haptic assembly from a geometric modeling and spatial reasoning perspective. The main focus is on revisiting definitions and classifications of different methods used to handle the constrained multibody simulation in real-time, ranging from physics-based and geometry-based to hybrid and unified approaches using a variety of auxiliary computational devices to specify, impose, and solve assembly constraints. Particular attention is given to the newly developed 'analytic methods' inherited from motion planning and protein docking that have shown great promise as an alternative paradigm to the more popular combinatorial methods., Comment: Technical Report, University of Connecticut, 2016

The basic problem of shape complementarity analysis appears fundamental to applications as diverse as mechanical design, assembly automation, robot motion planning, micro- and nano-fabrication, protein-ligand binding, and rational drug design. However, the current challenge lies in the lack of a general mathematical formulation that applies to objects of arbitrary shape. We propose that a measure of shape complementarity can be obtained from the extent of approximate overlap between shape skeletons. A space-continuous implicit generalization of the skeleton, called the skeletal density function (SDF) is defined over the Euclidean space that contains the individual assembly partners. The SDF shape descriptors capture the essential features that are relevant to proper contact alignment, and are considerably more robust than the conventional explicit skeletal representations. We express the shape complementarity score as a convolution of the individual SDFs. The problem then breaks down to a global optimization of the score over the configuration space of spatial relations, which can be efficiently implemented using fast Fourier transforms (FFTs) on nonequispaced samples. We demonstrate the effectiveness of the scoring approach for several examples from 2D peg-in-hole alignment to more complex 3D examples in mechanical assembly and protein docking. We show that the proposed method is reliable, inherently robust against small perturbations, and effective in steering gradient-based optimization., Comment: Technical Report, University of Connecticut, 2014

Analytic methods are emerging in solid and configuration modeling, while providing new insights into a variety of shape and motion related problems by exploiting tools from group morphology, convolution algebras, and harmonic analysis. However, most convolution-based methods have used uniform grid-based sampling to take advantage of the fast Fourier transform (FFT) algorithm. We propose a new paradigm for more efficient computation of analytic correlations that relies on a grid-free discretization of arbitrary shapes as countable unions of balls, in turn described as sublevel sets of summations of smooth radial kernels at adaptively sampled 'knots'. Using a simple geometric lifting trick, we interpret this combination as a convolution of an impulsive skeletal density and primitive kernels with conical support, which faithfully embeds into the convolution formulation of interactions across different objects. Our approach enables fusion of search-efficient combinatorial data structures prevalent in time-critical collision and proximity queries with analytic methods popular in path planning and protein docking, and outperforms uniform grid-based FFT methods by leveraging nonequispaced FFTs. We provide example applications in formulating holonomic collision constraints, shape complementarity metrics, and morphological operations, unified within a single analytic framework., Comment: Special Issue on SIAM/ACM symposium on Solid and Physical Modeling (SPM'2015) (Best Paper Award, 2nd Place)

Haptic-assisted virtual assembly and prototyping has seen significant attention over the past two decades. However, in spite of the appealing prospects, its adoption has been slower than expected. We identify the main roadblocks as the inherent geometric complexities faced when assembling objects of arbitrary shape, and the computation time limitation imposed by the notorious 1 kHz haptic refresh rate. We addressed the first problem in a recent work by introducing a generic energy model for geometric guidance and constraints between features of arbitrary shape. In the present work, we address the second challenge by leveraging Fourier transforms to compute the constraint forces and torques. Our new concept of 'geometric energy' field is computed automatically from a cross-correlation of 'skeletal densities' in the frequency domain, and serves as a generalization of the manually specified virtual fixtures or heuristically identified mating constraints proposed in the literature. The formulation of the energy field as a convolution enables efficient computation using fast Fourier transforms (FFT) on the graphics processing unit (GPU). We show that our method is effective for low-clearance assembly of objects of arbitrary geometric and syntactic complexity., Comment: A shorter version was presented in ASME Computers and Information in Engineering Conference (CIE'2015) (Best Paper Award)

The development of a generic and effective force model for semi-automatic or manual virtual assembly with haptic support is not a trivial task, especially when the assembly constraints involve complex features of arbitrary shape. The primary challenge lies in a proper formulation of the guidance forces and torques that effectively assist the user in the exploration of the virtual environment (VE), from repulsing collisions to attracting proper contact. The secondary difficulty is that of efficient implementation that maintains the standard 1 kHz haptic refresh rate. We propose a purely geometric model for an artificial energy field that favors spatial relations leading to proper assembly, differentiated to obtain forces and torques for general motions. The energy function is expressed in terms of a cross-correlation of shape-dependent affinity fields, precomputed offline separately for each object. We test the effectiveness of the method using familiar peg-in-hole examples. We show that the proposed technique unifies the two phases of free motion and precise insertion into a single interaction mode and provides a generic model to replace the ad hoc mating constraints or virtual fixtures, with no restrictive assumption on the types of the involved assembly features., Comment: A shorter version was presented in ASME Computers and Information in Engineering Conference (CIE'2014) (Best Paper Award)

A reliable prediction of 3D protein structures from sequence data remains a big challenge due to both theoretical and computational difficulties. We have previously shown that our kinetostatic compliance method (KCM) implemented into the Protofold package can overcome some of the key difficulties faced by other de novo structure prediction methods, such as the very small time steps required by the molecular dynamics (MD) approaches or the very large number of samples needed by the Monte Carlo (MC) sampling techniques. In this article, we improve the free energy formulation used in Protofold by including the typically underrated entropic effects, imparted due to differences in hydrophobicity of the chemical groups, which dominate the folding of most water-soluble proteins. In addition to the model enhancement, we revisit the numerical implementation by redesigning the algorithms and introducing efficient data structures that reduce the expected complexity from quadratic to linear. Moreover, we develop and optimize parallel implementations of the algorithms on both central and graphics processing units (CPU/GPU) achieving speed-ups up to two orders of magnitude on the GPU. Our simulations are consistent with the general behavior observed in the folding process in aqueous solvent, confirming the effectiveness of model improvements. We report on the folding process at multiple levels; namely, the formation of secondary structural elements and tertiary interactions between secondary elements or across larger domains. We also observe significant enhancements in running times that make the folding simulation tractable for large molecules., Comment: Shorter versions were presented in two conference papers in ASME International Design Engineering Technical Conferences (IDETC'2013)