We propose the first method that determines the exact worst-case execution time (WCET) for implicit linear model predictive control (MPC). Such WCET bounds are imperative when MPC is used in real time to control safety-critical systems. The proposed method applies when the quadratic programming solver in the MPC controller belongs to a family of well-established active-set solvers. For such solvers, we leverage a previously proposed complexity certification framework to generate a finite set of archetypal optimization problems; we prove that these archetypal problems form an execution-time equivalent cover of all possible problems; that is, that they capture the execution time for solving any possible optimization problem that can be encountered online. Hence, by solving just these archetypal problems on the hardware on which the MPC is to be deployed, and by recording the execution times, we obtain the exact WCET. In addition to providing formal proofs of the methods efficacy, we validate the method on an MPC example where an inverted pendulum on a cart is stabilized. The experiments highlight the following advantages compared with classical WCET methods: (i) in contrast to classical static methods, our method gives the exact WCET; (ii) in contrast to classical measurement-based methods, our method guarantees a correct WCET estimate and requires fewer measurements on the hardware.
相關內容
The class of Galled-Tree Explainable (GaTEx) graphs has just recently been discovered as a natural generalization of cographs. Cographs are precisely those graphs that can be uniquely represented by a rooted tree where the leaves of the tree correspond to the vertices of the graph. As a generalization, GaTEx graphs are precisely those graphs that can be uniquely represented by a particular rooted directed acyclic graph (called galled-tree). We consider here four prominent problems that are, in general, NP-hard: computing the size $\omega(G)$ of a maximum clique, the size $\chi(G)$ of an optimal vertex-coloring and the size $\alpha(G)$ of a maximum independent set of a given graph $G$ as well as determining whether a graph is perfectly orderable. We show here that $\omega(G)$, $\chi(G)$, $\alpha(G)$ can be computed in linear-time for GaTEx graphs $G$. The crucial idea for the linear-time algorithms is to avoid working on the GaTEx graphs $G$ directly, but to use the the galled-trees that explain $G$ as a guide for the algorithms to compute these invariants. In particular, we show first how to employ the galled-tree structure to compute a perfect ordering of GaTEx graphs in linear-time which is then used to determine $\omega(G)$, $\chi(G)$, $\alpha(G)$.
The ongoing deep learning revolution has allowed computers to outclass humans in various games and perceive features imperceptible to humans during classification tasks. Current machine learning techniques have clearly distinguished themselves in specialized tasks. However, we have yet to see robots capable of performing multiple tasks at an expert level. Most work in this field is focused on the development of more sophisticated learning algorithms for a robot's controller given a largely static and presupposed robotic design. By focusing on the development of robotic bodies, rather than neural controllers, I have discovered that robots can be designed such that they overcome many of the current pitfalls encountered by neural controllers in multitask settings. Through this discovery, I also present novel metrics to explicitly measure the learning ability of a robotic design and its resistance to common problems such as catastrophic interference. Traditionally, the physical robot design requires human engineers to plan every aspect of the system, which is expensive and often relies on human intuition. In contrast, within the field of evolutionary robotics, evolutionary algorithms are used to automatically create optimized designs, however, such designs are often still limited in their ability to perform in a multitask setting. The metrics created and presented here give a novel path to automated design that allow evolved robots to synergize with their controller to improve the computational efficiency of their learning while overcoming catastrophic interference. Overall, this dissertation intimates the ability to automatically design robots that are more general purpose than current robots and that can perform various tasks while requiring less computation.
The Fokker-Planck equation describes the evolution of the probability density associated with a stochastic differential equation. As the dimension of the system grows, solving this partial differential equation (PDE) using conventional numerical methods becomes computationally prohibitive. Here, we introduce a fast, scalable, and interpretable method for solving the Fokker-Planck equation which is applicable in higher dimensions. This method approximates the solution as a linear combination of shape-morphing Gaussians with time-dependent means and covariances. These parameters evolve according to the method of reduced-order nonlinear solutions (RONS) which ensures that the approximate solution stays close to the true solution of the PDE for all times. As such, the proposed method approximates the transient dynamics as well as the equilibrium density, when the latter exists. Our approximate solutions can be viewed as an evolution on a finite-dimensional statistical manifold embedded in the space of probability densities. We show that the metric tensor in RONS coincides with the Fisher information matrix on this manifold. We also discuss the interpretation of our method as a shallow neural network with Gaussian activation functions and time-varying parameters. In contrast to existing deep learning methods, our method is interpretable, requires no training, and automatically ensures that the approximate solution satisfies all properties of a probability density.
A well-established approach for inferring full displacement and stress fields from possibly sparse data is to calibrate the parameter of a given constitutive model using a Bayesian update. After calibration, a (stochastic) forward simulation is conducted with the identified model parameters to resolve physical fields in regions that were not accessible to the measurement device. A shortcoming of model calibration is that the model is deemed to best represent reality, which is only sometimes the case, especially in the context of the aging of structures and materials. While this issue is often addressed with repeated model calibration, a different approach is followed in the recently proposed statistical Finite Element Method (statFEM). Instead of using Bayes' theorem to update model parameters, the displacement is chosen as the stochastic prior and updated to fit the measurement data more closely. For this purpose, the statFEM framework introduces a so-called model-reality mismatch, parametrized by only three hyperparameters. This makes the inference of full-field data computationally efficient in an online stage: If the stochastic prior can be computed offline, solving the underlying partial differential equation (PDE) online is unnecessary. Compared to solving a PDE, identifying only three hyperparameters and conditioning the state on the sensor data requires much fewer computational resources. This paper presents two contributions to the existing statFEM approach: First, we use a non-intrusive polynomial chaos method to compute the prior, enabling the use of complex mechanical models in deterministic formulations. Second, we examine the influence of prior material models (linear elastic and St.Venant Kirchhoff material with uncertain Young's modulus) on the updated solution. We present statFEM results for 1D and 2D examples, while an extension to 3D is straightforward.
This paper introduces a numerical approach to solve singularly perturbed convection diffusion boundary value problems for second-order ordinary differential equations that feature a small positive parameter {\epsilon} multiplying the highest derivative. We specifically examine Dirichlet boundary conditions. To solve this differential equation, we propose an upwind finite difference method and incorporate the Shishkin mesh scheme to capture the solution near boundary layers. Our solver is both direct and of high accuracy, with computation time that scales linearly with the number of grid points. MATLAB code of the numerical recipe is made publicly available. We present numerical results to validate the theoretical results and assess the accuracy of our method. The tables and graphs included in this paper demonstrate the numerical outcomes, which indicate that our proposed method offers a highly accurate approximation of the exact solution.
The Plackett--Luce model is a popular approach for rank data analysis, where a utility vector is employed to determine the probability of each outcome based on Luce's choice axiom. In this paper, we investigate the asymptotic theory of utility vector estimation by maximizing different types of likelihood, such as the full-, marginal-, and quasi-likelihood. We provide a rank-matching interpretation for the estimating equations of these estimators and analyze their asymptotic behavior as the number of items being compared tends to infinity. In particular, we establish the uniform consistency of these estimators under conditions characterized by the topology of the underlying comparison graph sequence and demonstrate that the proposed conditions are sharp for common sampling scenarios such as the nonuniform random hypergraph model and the hypergraph stochastic block model; we also obtain the asymptotic normality of these estimators and discuss the trade-off between statistical efficiency and computational complexity for practical uncertainty quantification. Both results allow for nonuniform and inhomogeneous comparison graphs with varying edge sizes and different asymptotic orders of edge probabilities. We verify our theoretical findings by conducting detailed numerical experiments.
We present Holistic Cube Analysis (HoCA), a framework that augments the capabilities of relational queries for data insights. We first define AbstractCube, a data type defined as a function from RegionFeatures space to relational tables. AbstractCube provides a logical form of data for HoCA operators and their compositions to operate on to analyze the data. This function-as-data modeling allows us to simultaneously capture a space of non-uniform tables on the co-domain of the function, and region space structure on the domain of the function. We describe two HoCA operators, cube crawling and cube join, which are cube-to-cube transformations (i.e., higher-order functions). Cube crawling explores a region subspace, and outputs a cube mapping regions to signal vectors. Cube join, in turn, allows users to meld information in different cubes, which is critical for composition. The cube crawling interface introduces two novel features: (1) Region Analysis Models (RAMs), which allows one to program and organize analysis on a set of data features into a module. (2) Multi-Model Crawling, which allows one to apply multiple models, potentially on different feature sets, during crawling. These two features, together with cube join and a rich RAM library, allows us to construct succinct HoCA programs to capture a wide variety of data-insight problems in system monitoring, experimentation analysis, and business intelligence. HoCA poses a rich algorithmic design space, such as optimizing crawling performance leveraging region space structure, optimizing cube join performance, and physical designs of cubes. We describe several cube crawling implementations leveraging different foundations (an in-house relational query engine, and Apache Beam), and evaluate their performance characteristics. Finally, we discuss avenues in extending the framework, such as devising more useful HoCA operators.
We consider high-throughput experiments that take measurements regarding many parameters. Due to resource limitations, ``breadth-first'' high-throughput experiments take only a few independent samples of each parameter, and so it is challenging to assess estimator error. We propose a new model-free method for bounding type S errors in this context, based on a quantity we call the Cross-replicate Sign Error Rate (CSER). The CSER is the expected sign agreement between a fixed set of estimates and estimates based on an independent experimental replicate. To show the CSER can be estimated with enough accuracy to be useful in practice, we develop new improvements to Hoeffding's bounds for sums of bounded random variables, obtaining the tightest bounds that can be obtained from the Chernoff inequality. We apply this method to analyzing measurements from cell-perturbation experiments. Our method reveals that existing error control practices fail to control error at their nominal level in some cases and are needlessly conservative in others. The CSER is easy to estimate, enabling practitioners to detect problems in their experimental designs and identify subsets of parameters with a low proportion of type S errors.
Recently, the use of deep equilibrium methods has emerged as a new approach for solving imaging and other ill-posed inverse problems. While learned components may be a key factor in the good performance of these methods in practice, a theoretical justification from a regularization point of view is still lacking. In this paper, we address this issue by providing stability and convergence results for the class of equilibrium methods. In addition, we derive convergence rates and stability estimates in the symmetric Bregman distance. We strengthen our results for regularization operators with contractive residuals. Furthermore, we use the presented analysis to gain insight into the practical behavior of these methods, including a lower bound on the performance of the regularized solutions. In addition, we show that the convergence analysis leads to the design of a new type of loss function which has several advantages over previous ones. Numerical simulations are used to support our findings.
In this monograph, I introduce the basic concepts of Online Learning through a modern view of Online Convex Optimization. Here, online learning refers to the framework of regret minimization under worst-case assumptions. I present first-order and second-order algorithms for online learning with convex losses, in Euclidean and non-Euclidean settings. All the algorithms are clearly presented as instantiation of Online Mirror Descent or Follow-The-Regularized-Leader and their variants. Particular attention is given to the issue of tuning the parameters of the algorithms and learning in unbounded domains, through adaptive and parameter-free online learning algorithms. Non-convex losses are dealt through convex surrogate losses and through randomization. The bandit setting is also briefly discussed, touching on the problem of adversarial and stochastic multi-armed bandits. These notes do not require prior knowledge of convex analysis and all the required mathematical tools are rigorously explained. Moreover, all the proofs have been carefully chosen to be as simple and as short as possible.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191