Search for: programming

Authored robotics applications have a diverse set of requirements for their authoring interfaces, being dependent on the underlying architecture of the program, the capability of the programmers and engineers using them, and the capabilities of the robot. Visual programming approaches have long been favored for both novice-level accessibility, and clear graphical representations, but current tools are limited in their customizability and ability to be integrated holistically into larger design interfaces. OpenVP attempts to address this by providing a highly congurable and customizable component library that can be integrated easily into other modern web-based applications. 

Knitting turns yarn, a 1D material, into a 2D fabric that is flexible, durable, and can be patterned to adopt a wide range of 3D geometries. Like other mechanical metamaterials, the elasticity of knitted fabrics is an emergent property of the local stitch topology and pattern that cannot solely be attributed to the yarn itself. Thus, knitting can be viewed as an additive manufacturing technique that allows for stitch-by-stitch programming of elastic properties and has applications in many fields ranging from soft robotics and wearable electronics to engineered tissue and architected materials. However, predicting these mechanical properties based on the stitch type remains elusive. Here we untangle the relationship between changes in stitch topology and emergent elasticity in several types of knitted fabrics. We combine experiment and simulation to construct a constitutive model for the nonlinear bulk response of these fabrics. This model serves as a basis for composite fabrics with bespoke mechanical properties, which crucially do not depend on the constituent yarn.

 

Water distribution systems (WDSs) are critical infrastructure used to convey water from sources to consumers. The mathematical framework governing the distribution of flows and heads in extended period simulations of WDSs lends itself to application in a wide range of optimization problems. Applying the classical mixed integer linear programming (MILP) approach to model WDSs hydraulics within an optimization framework can contribute to higher solution accuracy with lower computational effort. However, adapting WDSs models to conform to a MILP formulation has proven challenging because of the intrinsic non‐linearity of system hydraulics and the complexity associated with modeling hydraulic devices that influence the state of the WDS. This paper introduces MILPNet, an adjustable framework for WDSs that can be used to build and solve an extensive array of MILP optimization problems. MILPNet includes constraints that represent the mass balance and energy conservation equations, hydraulic devices, control rules, and status checks. To conform to MILP structure, MILPNet employs piece‐wise linear approximation and integer programming. MILPNet was implemented and tested using Gurobi Python API. Modeling accuracy was shown to be comparable to EPANET, a public domain software for hydraulic modeling, and sensitivity analyses were conducted to examine the impacts of the modeling assumptions on the performance of MILPNet. Additionally, application of the framework was demonstrated using pump scheduling optimization examples in single and rolling horizon scenarios. Our results show that MILPNet can facilitate the construction and solution of optimization problems for a range of applications in WDSs operations.

 

We have developed a differentiable programming framework for truncated hierarchical B-splines (THB-splines), which can be used for several applications in geometry modeling, such as surface fitting and deformable image registration, and can be easily integrated with geometric deep learning frameworks. Differentiable programming is a novel paradigm that enables an algorithm to be differentiated via automatic differentiation, i.e., using automatic differentiation to compute the derivatives of its outputs with respect to its inputs or parameters. Differentiable programming has been used extensively in machine learning for obtaining gradients required in optimization algorithms such as stochastic gradient descent (SGD). While incorporating differentiable programming with traditional functions is straightforward, it is challenging when the functions are complex, such as splines. In this work, we extend the differentiable programming paradigm to THB-splines. THB-splines offer an efficient approach for complex surface fitting by utilizing a hierarchical tensor structure of B-splines, enabling local adaptive refinement. However, this approach brings challenges, such as a larger computational overhead and the non-trivial implementation of automatic differentiation and parallel evaluation algorithms. We use custom kernel functions for GPU acceleration in forward and backward evaluation that are necessary for differentiable programming of THB-splines. Our approach not only improves computational efficiency but also significantly enhances the speed of surface evaluation compared to previous methods. Our differentiable THB-splines framework facilitates faster and more accurate surface modeling with local refinement, with several applications in CAD and isogeometric analysis.

 

Generalizing work of Künnemann, Paturi, and Schneider [ICALP 2017], we study a wide class of high-dimensional dynamic programming (DP) problems in which one must find the shortest path between two points in a high-dimensional grid given a tensor of transition costs between nodes in the grid. This captures many classical problems which are solved using DP such as the knapsack problem, the airplane refueling problem, and the minimal-weight polygon triangulation problem. We observe that for many of these problems, the tensor naturally has low tensor rank or low slice rank. We then give new algorithms and a web of fine-grained reductions to tightly determine the complexity of these problems. For instance, we show that a polynomial speedup over the DP algorithm is possible when the tensor rank is a constant or the slice rank is 1, but that such a speedup is impossible if the tensor rank is slightly super-constant (assuming SETH) or the slice rank is at least 3 (assuming the APSP conjecture). We find that this characterizes the known complexities for many of these problems, and in some cases leads to new faster algorithms. 

University research labs focusing on education, psychology, and cognitive development have been collaborating with museums more and more over the past decade. Nevertheless, cognitive science labs that primarily engage in basic as opposed to applied research may find it difficult to entice museums to collaborate, and existing collaborations may fall short of their full potential to garner benefits to labs and museums alike. Here, we focus on a kind of lab and museum collaboration that has common content, philosophy, and programming and impacts both scientific theory development and museum practice. By illustrating one example of a collaboration between the Lab for the Developing Mind at New York University and the National Museum of Mathematics in New York City, we offer practical tips and suggestions for other cognitive science labs aiming to achieve strong lab‐museum synergy.

 

We develop a general framework for finding approximately-optimal preconditioners for solving linear systems. Leveraging this framework we obtain improved runtimes for fundamental preconditioning and linear system solving problems including the following. \begin{itemize} \item \textbf{Diagonal preconditioning.} We give an algorithm which, given positive definite $\mathbf{K} \in \mathbb{R}^{d \times d}$ with $\mathrm{nnz}(\mathbf{K})$ nonzero entries, computes an $\epsilon$-optimal diagonal preconditioner in time $\widetilde{O}(\mathrm{nnz}(\mathbf{K}) \cdot \mathrm{poly}(\kappa^\star,\epsilon^{-1}))$, where $\kappa^\star$ is the optimal condition number of the rescaled matrix. \item \textbf{Structured linear systems.} We give an algorithm which, given $\mathbf{M} \in \mathbb{R}^{d \times d}$ that is either the pseudoinverse of a graph Laplacian matrix or a constant spectral approximation of one, solves linear systems in $\mathbf{M}$ in $\widetilde{O}(d^2)$ time. \end{itemize} Our diagonal preconditioning results improve state-of-the-art runtimes of $\Omega(d^{3.5})$ attained by general-purpose semidefinite programming, and our solvers improve state-of-the-art runtimes of $\Omega(d^{\omega})$ where $\omega > 2.3$ is the current matrix multiplication constant. We attain our results via new algorithms for a class of semidefinite programs (SDPs) we call \emph{matrix-dictionary approximation SDPs}, which we leverage to solve an associated problem we call \emph{matrix-dictionary recovery}. 

Climate change undeniably impacts agriculture and natural resources, enterprises and markets. For informed decision making, there is a need for information on climate change adaptation possibilities and mitigation alternatives. Mathematical programming has been used to address the economic aspects of such questions and allows analysis as climate change moves the environment into previously unobserved conditions. It allows us to model spatial and dynamic features of the issue and analyze heretofore unobserved adaptation and mitigation possibilities. This review provides an overview of and references for modeling techniques, conceptual issues, and major assumptions involved with using mathematical programming as a climate change economic analyzing engine, along with a brief comparison with other methods. We also review a number of studies applying mathematical programming to examine climate change impacts, adaptation, and mitigation issues in the agricultural and natural resources arena. Finally, we present a very brief discussion on research needs. Expected final online publication date for the Annual Review of Resource Economics, Volume 15 is October 2023. Please see http://www.annualreviews.org/page/journal/pubdates for revised estimates. 

Analogical reasoning is considered to be a critical cognitive skill in programming. However, it has been rarely studied in a block-based programming context, especially involving both virtual and physical objects. In this multi-case study, we examined how novice programming learners majoring in early childhood education used analogical reasoning while debugging block code to make a robot perform properly. Screen recordings, scaffolding entries, reflections, and block code were analyzed. The cross-case analysis suggested multimodal objects enabled the novice programming learners to identify and use structural relations. The use of a robot eased the verification process by enabling them to test their analogies immediately after the analogy application. Noticing similar functional analogies led to noticing similarities in the relation between block code as well as between block code and the robot, guiding to locate bugs. Implications and directions for future educational computing research are discussed.

 

We study decision rule approximations for generic multistage robust linear optimization problems. We examine linear decision rules for the case when the objective coefficients, the recourse matrices, and the right-hand sides are uncertain, and we explore quadratic decision rules for the case when only the right-hand sides are uncertain. The resulting optimization problems are NP hard but amenable to copositive programming reformulations that give rise to tight, tractable semidefinite programming solution approaches. We further enhance these approximations through new piecewise decision rule schemes. Finally, we prove that our proposed approximations are tighter than the state-of-the-art schemes and demonstrate their superiority through numerical experiments.