An official website of the United States government
Abstract This paper presents a novel real-time kinematic simulation algorithm for planar N-bar linkage mechanisms, both single- and multi-degrees-of-freedom, comprising revolute and/or prismatic joints and actuators. A key feature of this algorithm is a reinterpretation technique that transforms prismatic elements into a combination of revolute joint and links. This gives rise to a unified system of geometric constraints and a general-purpose solver which adapts to the complexity of the mechanism. The solver requires only two types of methods—fast dyadic decomposition and relatively slower optimization-based—to simulate all types of planar mechanisms. From an implementation point of view, this algorithm simplifies programming without requiring handling of different types of mechanisms. This versatile algorithm can handle serial, parallel, and hybrid planar mechanisms with varying degrees-of-freedom and joint types. Additionally, this paper presents an estimation of simulation time and structural complexity, shedding light on computational demands. Demonstrative examples showcase the practicality of this method.
more »
« less
Parallel-in-Time Probabilistic Solutions for Time-Dependent Nonlinear Partial Differential Equations
We present an efficient probabilistic solver for time-dependent nonlinear partial differential equations.We formulate our method as the maximum a posteriori solver for a constrained risk problem on a reproducing kernel Hilbert space induced by a spatio-temporal Gaussian process prior. We show that for a suitable choice of temporal kernels, the risk objective can be minimized efficiently via a Gauss–Newton algorithm cor- responding to an iterated extended Kalman smoother (IEKS). Furthermore, by leveraging a parallel-in-time implementation of IEKS, our algorithm can take advantage of massively parallel graphical processing units to achieve logarithmic instead of linear scaling with time. We validate our method numerically on popular benchmark problems.
more »
« less
- Award ID(s):
- 2225507
- PAR ID:
- 10557914
- Publisher / Repository:
- IEEE
- Date Published:
- ISBN:
- 979-8-3503-7225-0
- Page Range / eLocation ID:
- 1 to 6
- Subject(s) / Keyword(s):
- partial differential equations kernel methods sparse optimization parallel computation.
- Format(s):
- Medium: X
- Location:
- London, United Kingdom
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Continuous and accurate decoding of intended motions is critical for human-machine interactions. Here, we developed a novel approach for real-time continuous prediction of forces in individual fingers using parallel convolutional neural networks (CNNs). We extracted populational motor unit discharge frequency using CNNs organized in a parallel structure. The CNNs parameters were trained based on two features from high-density electromyogram (HD-EMG), namely temporal energy heatmaps and frequency spectrum maps. The populational motor unit discharge frequency was then used to continuously predict finger forces based on a linear regression model. The force prediction performance was compared with a motor unit decomposition method and the conventional EMG amplitude-based method. Our results showed that the correlation coefficient between the predicted and the recorded forces of the parallel CNN approach was on average 0.91, compared with an offline decomposition method of 0.89, an online decomposition method of 0.82, and the EMG amplitude method of 0.81. Additionally, the CNN based approach showed generalizable performance, with CNN trained on one finger applying to a different finger. The outcomes suggest that our CNN based algorithm can offer an accurate and efficient force decoding method for human-machine interactions.more » « less
-
Chakraborty, Supratik; Jiang, Jie-Hong Roland (Ed.)Quantum Computing (QC) is a new computational paradigm that promises significant speedup over classical computing in various domains. However, near-term QC faces numerous challenges, including limited qubit connectivity and noisy quantum operations. To address the qubit connectivity constraint, circuit mapping is required for executing quantum circuits on quantum computers. This process involves performing initial qubit placement and using the quantum SWAP operations to relocate non-adjacent qubits for nearest-neighbor interaction. Reducing the SWAP count in circuit mapping is essential for improving the success rate of quantum circuit execution as SWAPs are costly and error-prone. In this work, we introduce a novel circuit mapping method by combining incremental and parallel solving for Boolean Satisfiability (SAT). We present an innovative SAT encoding for circuit mapping problems, which significantly improves solver-based mapping methods and provides a smooth trade-off between compilation quality and compilation time. Through comprehensive benchmarking of 78 instances covering 3 quantum algorithms on 2 distinct quantum computer topologies, we demonstrate that our method is 26× faster than state-of-the-art solver-based methods, reducing the compilation time from hours to minutes for important quantum applications. Our method also surpasses the existing heuristics algorithm by 26% in SWAP count.more » « less
-
Motivated by the computational difficulties incurred by popular deep learning algorithms for the generative modeling of temporal densities, we propose a cheap alternative that requires minimal hyperparameter tuning and scales favorably to high-dimensional problems. In particular, we use a projection-based optimal transport solver [Meng et al.,Advances in Neural Information Processing Systems (Curran Associates, 2019), Vol. 32] to join successive samples and, subsequently, use transport splines (Chewi et al., 2020) to interpolate the evolving density. When the sampling frequency is sufficiently high, the optimal maps are close to the identity and are, thus, computationally efficient to compute. Moreover, the training process is highly parallelizable as all optimal maps are independent and can, thus, be learned simultaneously. Finally, the approach is based solely on numerical linear algebra rather than minimizing a nonconvex objective function, allowing us to easily analyze and control the algorithm. We present several numerical experiments on both synthetic and real-world datasets to demonstrate the efficiency of our method. In particular, these experiments show that the proposed approach is highly competitive compared with state-of-the-art normalizing flows conditioned on time across a wide range of dimensionalities.more » « less
-
The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which trade-off solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a large-scale problem into a collection of smaller sub-problems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the sub-problem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and high-quality solutions. We utilize techniques that have been popularized recently in the context of online dial-a-ride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. Due to the lack of benchmark solvers similar to ours (i.e., temporal decomposition with an online solver), we compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances (with an average of 129 requests per instance), the baseline approach is as competitive as our framework. However, in larger problem instances (approximately 2,500 requests per instance), our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/MLSP58920.2024.10734739
