Optimization
Efficient collision avoidance for autonomous vehicles in polygonal domains
Fan, Jiayu, Murgovski, Nikolce, Liang, Jun
This research focuses on trajectory planning problems for autonomous vehicles utilizing numerical optimal control techniques. The study reformulates the constrained optimization problem into a nonlinear programming problem, incorporating explicit collision avoidance constraints. We present three novel, exact formulations to describe collision constraints. The first formulation is derived from a proposition concerning the separation of a point and a convex set. We prove the separating proposition through De Morgan's laws. Then, leveraging the hyperplane separation theorem we propose two efficient reformulations. Compared with the existing dual formulations and the first formulation, they significantly reduce the number of auxiliary variables to be optimized and inequality constraints within the nonlinear programming problem. Finally, the efficacy of the proposed formulations is demonstrated in the context of typical autonomous parking scenarios compared with state of the art. For generality, we design three initial guesses to assess the computational effort required for convergence to solutions when using the different collision formulations. The results illustrate that the scheme employing De Morgan's laws performs equally well with those utilizing dual formulations, while the other two schemes based on hyperplane separation theorem exhibit the added benefit of requiring lower computational resources.
Protein Design with Guided Discrete Diffusion
Gruver, Nate, Stanton, Samuel, Frey, Nathan C., Rudner, Tim G. J., Hotzel, Isidro, Lafrance-Vanasse, Julien, Rajpal, Arvind, Cho, Kyunghyun, Wilson, Andrew Gordon
A popular approach to protein design is to combine a generative model with a discriminative model for conditional sampling. The generative model samples plausible sequences while the discriminative model guides a search for sequences with high fitness. Given its broad success in conditional sampling, classifier-guided diffusion modeling is a promising foundation for protein design, leading many to develop guided diffusion models for structure with inverse folding to recover sequences. In this work, we propose diffusioN Optimized Sampling (NOS), a guidance method for discrete diffusion models that follows gradients in the hidden states of the denoising network. NOS makes it possible to perform design directly in sequence space, circumventing significant limitations of structure-based methods, including scarce data and challenging inverse design. Moreover, we use NOS to generalize LaMBO, a Bayesian optimization procedure for sequence design that facilitates multiple objectives and edit-based constraints. The resulting method, LaMBO-2, enables discrete diffusions and stronger performance with limited edits through a novel application of saliency maps. We apply LaMBO-2 to a real-world protein design task, optimizing antibodies for higher expression yield and binding affinity to several therapeutic targets under locality and developability constraints, attaining a 99% expression rate and 40% binding rate in exploratory in vitro experiments.
Rethinking Gauss-Newton for learning over-parameterized models
Arbel, Michael, Menegaux, Romain, Wolinski, Pierre
This work studies the global convergence and implicit bias of Gauss Newton's (GN) when optimizing over-parameterized one-hidden layer networks in the mean-field regime. We first establish a global convergence result for GN in the continuous-time limit exhibiting a faster convergence rate compared to GD due to improved conditioning. We then perform an empirical study on a synthetic regression task to investigate the implicit bias of GN's method. While GN is consistently faster than GD in finding a global optimum, the learned model generalizes well on test data when starting from random initial weights with a small variance and using a small step size to slow down convergence. Specifically, our study shows that such a setting results in a hidden learning phenomenon, where the dynamics are able to recover features with good generalization properties despite the model having sub-optimal training and test performances due to an under-optimized linear layer. This study exhibits a trade-off between the convergence speed of GN and the generalization ability of the learned solution.
Highlighting Named Entities in Input for Auto-Formulation of Optimization Problems
Gangwar, Neeraj, Kani, Nickvash
While solving mathematical systems is accomplished by analytical software, formulating a problem as a set of mathematical operations has been typically done manually by domain experts. Recent machine learning methods have shown promise in converting textual problem descriptions to corresponding mathematical formulations. This paper presents an approach that converts linear programming word problems into mathematical formulations. We leverage the named entities in the input and augment the input to highlight these entities. Our approach achieves the highest accuracy among all submissions to the NL4Opt Competition, securing first place in the generation track.
A Dynamic Programming Framework for Optimal Planning of Redundant Robots Along Prescribed Paths With Kineto-Dynamic Constraints
Ferrentino, Enrico, Savino, Heitor J., Franchi, Antonio, Chiacchio, Pasquale
Abstract--Offline optimal planning of trajectories for redundant we go through the whole process of planning and executing robots along prescribed task space paths is usually a time-optimal trajectory on a real robot, and discuss some broken down into two consecutive processes: first, the task practical details, such as trajectory smoothness and actuator space path is inverted to obtain a joint space path, then, the saturation, aiding the practitioners in deploying our algorithm latter is parametrized with a time law. If the two processes effectively. Currently, the algorithm's applicability is limited are separated, they cannot optimize the same objective function, to those cases where hours are available for planning, hence ultimately providing sub-optimal results. In this paper, it is not well-suited for those cases where the robot activity a unified approach is presented where dynamic programming has to change frequently. By replacing the underlying dynamic is the underlying optimization technique. Its flexibility allows programming engine with a different methodology, such as accommodating arbitrary constraints and objective functions, randomized algorithms, the planning time could be controlled thus providing a generic framework for optimal planning of real to be upper-bounded, thus returning the most efficient solution systems. To demonstrate its applicability to a real world scenario, that can be achieved in the time available for reconfiguring the the framework is instantiated for time-optimality on Franka production. Other applications of interest include optimal ground Emika's Panda robot.
Time-Optimal Trajectory Planning with Interaction with the Environment
Petrone, Vincenzo, Ferrentino, Enrico, Chiacchio, Pasquale
Optimal motion planning along prescribed paths can be solved with several techniques, but most of them do not take into account the wrenches exerted by the end-effector when in contact with the environment. When a dynamic model of the environment is not available, no consolidated methodology exists to consider the effect of the interaction. Regardless of the specific performance index to optimize, this article proposes a strategy to include external wrenches in the optimal planning algorithm, considering the task specifications. This procedure is instantiated for minimum-time trajectories and validated on a real robot performing an interaction task under admittance control. The results prove that the inclusion of end-effector wrenches affect the planned trajectory, in fact modifying the manipulator's dynamic capability.
GP+: A Python Library for Kernel-based learning via Gaussian Processes
Yousefpour, Amin, Foumani, Zahra Zanjani, Shishehbor, Mehdi, Mora, Carlos, Bostanabad, Ramin
In this paper we introduce GP+, an open-source library for kernel-based learning via Gaussian processes (GPs) which are powerful statistical models that are completely characterized by their parametric covariance and mean functions. GP+ is built on PyTorch and provides a user-friendly and object-oriented tool for probabilistic learning and inference. As we demonstrate with a host of examples, GP+ has a few unique advantages over other GP modeling libraries. We achieve these advantages primarily by integrating nonlinear manifold learning techniques with GPs' covariance and mean functions. As part of introducing GP+, in this paper we also make methodological contributions that (1) enable probabilistic data fusion and inverse parameter estimation, and (2) equip GPs with parsimonious parametric mean functions which span mixed feature spaces that have both categorical and quantitative variables. We demonstrate the impact of these contributions in the context of Bayesian optimization, multi-fidelity modeling, sensitivity analysis, and calibration of computer models.
Multi-granularity Causal Structure Learning
Liang, Jiaxuan, Wang, Jun, Yu, Guoxian, Xia, Shuyin, Wang, Guoyin
However, these algorithms simply deem causal relationships stand exclusively at the level of individual variables Data science is moving from the data-centric paradigm forward (micro-variable), ignoring the collective interactions from the science-centric paradigm, and causal revolution multiple variables (macro-variable). For instance, the brain is sweeping across various research fields. Causality learning can be characterized at a micro granularity of neurons and endeavors to unearth causal relationships among variables their synapses, but high-order synergistic subsystems are from observational data and generate causal graph, widespread, which typically sit between canonical functional that is, directed acyclic graph (DAG). Unlike correlationbased networks and may serve an integrative role (Varley study, causality analysis reveals the causal mechanism et al. 2023). Actually, observational data can be regarded of data generation. Identifying causality holds paramount as knowledge in the lowest granularity level, while knowledge significance for stable inference and rational decisions can be regarded as the abstraction of data at different in many applications, such as recommendation systems granularity levels (Wang 2017; Wang et al. 2022). Similar (Wang et al. 2020), medical diagnostics (Richens, Lee, and viewpoints appear in the research of complex systems, Johri 2020), epidemiology (Vandenbroucke, Broadbent, and which suggests that causal relationship is more pronounced Pearce 2016) and many others (Von Kรผgelgen et al. 2022).
Optimizing accuracy and diversity: a multi-task approach to forecast combinations
Felici, Giovanni, Sudoso, Antonio M.
Forecast combination involves using multiple forecasts to create a single, more accurate prediction. Recently, feature-based forecasting has been employed to either select the most appropriate forecasting models or to optimize the weights of their combination. In this paper, we present a multi-task optimization paradigm that focuses on solving both problems simultaneously and enriches current operational research approaches to forecasting. In essence, it incorporates an additional learning and optimization task into the standard feature-based forecasting approach, focusing on the identification of an optimal set of forecasting methods. During the training phase, an optimization model with linear constraints and quadratic objective function is employed to identify accurate and diverse methods for each time series. Moreover, within the training phase, a neural network is used to learn the behavior of that optimization model. Once training is completed the candidate set of methods is identified using the network. The proposed approach elicits the essential role of diversity in feature-based forecasting and highlights the interplay between model combination and model selection when optimizing forecasting ensembles. Experimental results on a large set of series from the M4 competition dataset show that our proposal enhances point forecast accuracy compared to state-of-the-art methods.
Bayesian Optimization with Conformal Prediction Sets
Stanton, Samuel, Maddox, Wesley, Wilson, Andrew Gordon
Bayesian optimization is a coherent, ubiquitous approach to decision-making under uncertainty, with applications including multi-arm bandits, active learning, and black-box optimization. Bayesian optimization selects decisions (i.e. objective function queries) with maximal expected utility with respect to the posterior distribution of a Bayesian model, which quantifies reducible, epistemic uncertainty about query outcomes. In practice, subjectively implausible outcomes can occur regularly for two reasons: 1) model misspecification and 2) covariate shift. Conformal prediction is an uncertainty quantification method with coverage guarantees even for misspecified models and a simple mechanism to correct for covariate shift. We propose conformal Bayesian optimization, which directs queries towards regions of search space where the model predictions have guaranteed validity, and investigate its behavior on a suite of black-box optimization tasks and tabular ranking tasks. In many cases we find that query coverage can be significantly improved without harming sample-efficiency.