pwc-archive/papers-with-abstracts huggingface dataset:
Metaheuristics for the Minimum Set Cover Problem: A Comparison
Authors: Lukas Rosenbauer, Helena Stegherr, Anthony Stein, Jörg Hähner
Date: 2020-11-12 00:00:00
Proceeding: ECTA 2020 11
Tasks: Evolutionary Algorithms

The minimum set cover problem (MSCP) is one of the first NP-hard optimization problems discovered. Theoretically it has a bad worst case approximation ratio. As the MSCP turns out to appear in several real world
problems, various approaches exist where evolutionary algorithms and metaheuristics are utilized in order to
achieve good average case results. This work is intended to revisit and compare current results regarding the
application of metaheuristics for the MSCP. Therefore, a recapitulation of the MSCP and its classification into
the class of NP-hard optimization problems are provided first. After an overview of notable approximation
methods, the focus is shifted towards a brief review of existing metaheuristics which were adapted for the
MSCP. In order to allow for a targeted comparison of the existing algorithms, the theoretical worst case complexities in terms of the big O-notation are derived first. This is followed by an empirical study where the
identified metaheuristics are examined. Here we use Steiner triple systems, Beasley’s OR library, and introduce a new class of instances. Several of the considered approaches achieve close to optimal results. However,
our analysis reveals significant differences in terms of runtime and shows that some approaches may even have
exponential runtime.
A Germinal Centre Artificial Immune System for Software Test Suite Reduction
Authors: Lukas Rosenbauer, Anthony Stein, Jörg Hähner
Date: 2020-07-18 00:00:00
Proceeding: ALIFE 2020 7

Testing is a crucial part in the development of a new product.
If too little testing is done, customers might discover previously undetected failures. A common approach to avoid this
is to define a test suite that contains at least one test for every
requirement. As the execution of manual tests and the implementation of automated ones is timeintensive, it is a profitable
goal to reduce the amount of tests during the specification of
the test suite whilst still covering all requirements. In this
work we provide an artificial immune system to detect redundant tests. Our new approach achieves optimal results for our
industrial data sets and further we are able to reduce its runtime and memory usage drastically compared to the existing
germinal centre artificial immune system (GCAIS).
An Artificial Immune System for Adaptive Test Selection
Authors: Lukas Rosenbauer, Anthony Stein, Jörg Hähner
Date: 2020-12-04 00:00:00
Proceeding: IEEE Symposium Series on Computational Intelligence 2020 12

The verification of a new product is a major challenge for companies. With the rise of test automation, companies can rely on vast numbers of test cases. There are situations where it is not feasible to run all available tests due to time constraints. Hence a test suite of critical tests must be compiled. The corresponding test suite is usually chosen according to a quality metric. We combine the newest insights about germinal centre artificial immune systems (GCAIS) to produce test suites with high requirement coverage and low execution time. Tests and requirements might change over the lifetime of a project and hence the test suite must be adapated. We exploit results about the usage of memory to reduce the runtime of the test suite's recomputation.
An artificial immune system for black box test case selection
Authors: Lukas Rosenbauer, Anthony Stein, Jörg Hähner
Date: 2021-03-15 00:00:00
Proceeding: Springer EvoStar 2021 3

Testing is a crucial part of the development of a new product. For software validation a transformation from manual to automated tests can be observed which enables companies to implement large numbers of test cases. However, during testing situations may occur where it is not feasible to run all tests due to time constraints. Hence a set of critical test cases must be compiled which usually fulfills several criteria. Within this work we focus on criteria that are feasible for black box testing such as system tests. We adapt an existing artificial immune system for our use case and evaluate our method in a series of experiments using industrial datasets. We compare our approach with several other test selection methods where our algorithm shows superior performance.
BagPipe: Accelerating Deep Recommendation Model Training
Authors: Saurabh Agarwal, Chengpo Yan, Ziyi Zhang, Shivaram Venkataraman
Date: 2022-02-24 00:00:00
Tasks: model

Deep learning based recommendation models (DLRM) are widely used in several business critical applications. Training such recommendation models efficiently is challenging because they contain billions of embedding-based parameters, leading to significant overheads from embedding access. By profiling existing systems for DLRM training, we observe that around 75\% of the iteration time is spent on embedding access and model synchronization. Our key insight in this paper is that embedding access has a specific structure which can be used to accelerate training. We observe that embedding accesses are heavily skewed, with around 1\% of embeddings representing more than 92\% of total accesses. Further, we observe that during offline training we can lookahead at future batches to determine exactly which embeddings will be needed at what iteration in the future. Based on these insights, we develop Bagpipe, a system for training deep recommendation models that uses caching and prefetching to overlap remote embedding accesses with the computation. We design an Oracle Cacher, a new component that uses a lookahead algorithm to generate optimal cache update decisions while providing strong consistency guarantees against staleness. We also design a logically replicated, physically partitioned cache and show that our design can reduce synchronization overheads in a distributed setting. Finally, we propose a disaggregated system architecture and show that our design can enable low-overhead fault tolerance. Our experiments using three datasets and four models show that Bagpipe provides a speed up of up to 5.6x compared to state of the art baselines, while providing the same convergence and reproducibility guarantees as synchronous training.
Can autonomy make bicycle-sharing systems more sustainable? Environmental impact analysis of an emerging mobility technology
Authors: Naroa Coretti Sanchez, Luis Alonso Pastor, Kent Larson
Date: 2022-02-24 00:00:00

Autonomous bicycles have recently been proposed as a new and more efficient approach to bicycle-sharing systems (BSS), but the corresponding environmental implications remain unresearched. Conducting environmental impact assessments at an early technological stage is critical to influencing the design and, ultimately, environmental impacts of a system. Consequently, this paper aims to assess the environmental impact of autonomous shared bikes compared with current station-based and dockless systems under different sets of modeling hypotheses and mode-shift scenarios. The results indicate that autonomy could reduce the environmental impact per passenger kilometer traveled of current station-based and dockless BSS by 33.1 % and 58.0 %. The sensitivity analysis shows that the environmental impact of autonomous shared bicycles will mainly depend on vehicle usage rates and the need for infrastructure. Finally, this study highlights the importance of targeting the mode replacement from more polluting modes, especially as traditional mobility modes decarbonize and become more efficient.
Can the clocks tick together despite the noise? Stochastic simulations and analysis
Authors: Stéphanie M. C. Abo, José A. Carrillo, Anita T. Layton
Date: 2022-02-24 00:00:00
Tasks: Rhythm

The suprachiasmatic nucleus (SCN), also known as the circadian master clock, consists of a large population of oscillator neurons. Together, these neurons produce a coherent signal that drives the body's circadian rhythms. What properties of the cell-to-cell communication allow the synchronization of these neurons, despite a wide range of environmental challenges such as fluctuations in photoperiods? To answer that question, we present a mean-field description of globally coupled neurons modeled as Goodwin oscillators with standard Gaussian noise. Provided that the initial conditions of all neurons are independent and identically distributed, any finite number of neurons becomes independent and has the same probability distribution in the mean-field limit, a phenomenon called propagation of chaos. This probability distribution is a solution to a Vlasov-Fokker-Planck type equation, which can be obtained from the stochastic particle model. We study, using the macroscopic description, how the interaction between external noise and intercellular coupling affects the dynamics of the collective rhythm, and we provide a numerical description of the bifurcations resulting from the noise-induced transitions. Our numerical simulations show a noise-induced rhythm generation at low noise intensities, while the SCN clock is arrhythmic in the high noise setting. Notably, coupling induces resonance-like behavior at low noise intensities, and varying coupling strength can cause period locking and variance dissipation even in the presence of noise.
Model predictive control for retinal laser treatment at 1 kHz
Authors: Manuel Schaller, Viktoria Kleyman, Mario Mordmüller, Christian Schmidt, Mitsuru Wilson, Ralf Brinkmann, Matthias A. Müller, Karl Worthmann
Date: 2022-02-25 00:00:00
Tasks: Model Predictive Control, State Estimation

Laser photocoagulation is a technique applied in the treatment of retinal diseases. While this is often done manually or using simple control schemes, we pursue an optimization-based approach, namely Model Predictive Control (MPC), to enforce bounds on the peak temperature and, thus, safety during the medical treatment procedure - despite the spot-dependent absorption of the tissue. To this end, a repetition rate of 1 kHz is desirable rendering the real-time requirements a major challenge. We present a tailored MPC scheme using parametric model reduction, an extended Kalman filter for the parameter and state estimation, and suitably constructed stage costs and verify its applicability both in simulation and experiments with porcine eyes. Moreover, we give some insight on the implementation specifically tailored for fast numerical computations.
Data-driven distributed MPC of dynamically coupled linear systems
Authors: Matthias Köhler, Julian Berberich, Matthias A. Müller, Frank Allgöwer
Date: 2022-02-25 00:00:00
Tasks: LEMMA, Model Predictive Control

In this paper, we present a data-driven distributed model predictive control (MPC) scheme to stabilise the origin of dynamically coupled discrete-time linear systems subject to decoupled input constraints. The local optimisation problems solved by the subsystems rely on a distributed adaptation of the Fundamental Lemma by Willems et al., allowing to parametrise system trajectories using only measured input-output data without explicit model knowledge. For the local predictions, the subsystems rely on communicated assumed trajectories of neighbours. Each subsystem guarantees a small deviation from these trajectories via a consistency constraint. We provide a theoretical analysis of the resulting non-iterative distributed MPC scheme, including proofs of recursive feasibility and (practical) stability. Finally, the approach is successfully applied to a numerical example.
A Lyapunov function for robust stability of moving horizon estimation
Authors: Julian D. Schiller, Simon Muntwiler, Johannes Köhler, Melanie N. Zeilinger, Matthias A. Müller
Date: 2022-02-25 00:00:00

We provide a novel robust stability analysis for moving horizon estimation (MHE) using a Lyapunov function. Additionally, we introduce linear matrix inequalities (LMIs) to verify the necessary incremental input/output-to-state stability ($\delta$-IOSS) detectability condition. We consider an MHE formulation with time-discounted quadratic objective for nonlinear systems admitting an exponential $\delta$-IOSS Lyapunov function. We show that with a suitable parameterization of the MHE objective, the $\delta$-IOSS Lyapunov function serves as an $M$-step Lyapunov function for MHE. Provided that the estimation horizon is chosen large enough, this directly implies exponential stability of MHE. The stability analysis is also applicable to full information estimation, where the restriction to exponential $\delta$-IOSS can be relaxed. Moreover, we provide simple LMI conditions to systematically derive $\delta$-IOSS Lyapunov functions, which allows us to easily verify $\delta$-IOSS for a large class of nonlinear detectable systems. This is useful in the context of MHE in general, since most of the existing nonlinear (robust) stability results for MHE depend on the system being $\delta$-IOSS (detectable). In combination, we thus provide a framework for designing MHE schemes with guaranteed robust exponential stability. The applicability of the proposed methods is demonstrated with a nonlinear chemical reactor process and a 12-state quadrotor model.
Learning-Based Fault-Tolerant Control for an Hexarotor with Model Uncertainty
Authors: Leonardo J. Colombo, Manuela Gamonal Fernandez, Juan I. Giribet
Date: 2022-02-25 00:00:00
Tasks: Gaussian Processes

In this paper we present a learning-based tracking controller based on Gaussian processes (GP) for a fault-tolerant hexarotor in a recovery maneuver. In particular, to estimate certain uncertainties that appear in a hexacopter vehicle with the ability to reconfigure its rotors to compensate for failures. The rotors reconfiguration introduces disturbances that make the dynamic model of the vehicle differ from the nominal model. The control algorithm is designed to learn and compensate the amount of modeling uncertainties after a failure in the control allocation reconfiguration by using GP as a learning-based model for the predictions. In particular the presented approach guarantees a probabilistic bounded tracking error with high probability. The performance of the learning-based fault-tolerant controller is evaluated through experimental tests with an hexarotor UAV.
Model Predictive Control with Preview: Recursive Feasibility and Stability
Authors: Xing Fang, Wen-Hua Chen
Date: 2022-02-25 00:00:00
Tasks: Model Predictive Control

This paper proposes a stabilising model predictive control (MPC) scheme with preview information of disturbance for nonlinear systems. The proposed MPC algorithm is able to not only reject disturbance by making use of disturbance preview information as necessary, but also take advantage of the disturbance if it is good for a control task. This is realised by taking into account both the task (e.g. reference trajectory) and disturbance preview in the prediction horizon when performing online optimisation. Conditions are established to ensure recursive feasibility and stability under the disturbance. First the disturbance within the horizon is augmented with the state to form a new composite system and then the stage cost function is modified accordingly. With the help of input-to-state stability theory, a terminal cost and a terminal constraint are constructed and added to the MPC algorithm with preview to guarantee its recursive feasibility and stability under a pre-bounded disturbance. Numerical simulation results demonstrate the effectiveness of the proposed MPC algorithm.
Koopman Spectral Analysis of Intermittent Dynamics in Complex Systems: A Case Study in Pathophysiological Processes of Obstructive Sleep Apnea
Authors: Phat K. Huynh, Arveity R. Setty, Trung Q. Le
Date: 2022-02-24 00:00:00
Tasks: Attribute, Heart Rate Variability

Complex systems, such as pathophysiological processes, commonly exhibit chaotic, nonlinear, and intermittent phenomena. Koopman operator theory and Hankel alternative view of Koopman (HAVOK) model have been widely used to decompose the chaos of the complex system dynamics into an intermittent forced linear system. Although the statistics of the intermittent forcing have been proposed to characterize intermittencies in the HAVOK model, they were not adequate to attribute for the mode switching of nonlinear dynamics and the fat-tailed non-Gaussian distribution originated from high-frequency bursts and rarely-observed intermittent forcing. The paper proposed a new intermittency dynamics analysis approach to characterize the intermittent phases, chaotic bursts, and local spectral-temporal properties of various intermittent dynamics modes using spectral decomposition and wavelet analysis. To validate our methods, the intermittency behavior of apneic events in obstructive sleep apnea disorder was selected as the case, in which heart rate variability (HRV) features were extracted. Next, we constructed the Hankel matrix from the HRV features and obtained the last eigen time-delay coordinate by singular value decomposition of the Hankel matrix, which was modeled as an intermittent forcing input. The statistics of the forcing in OSA demonstrated the fat-tailed distribution of the intermittent forcing, which correspond to the intermittency of the underlying OSA pathophysiological process. The pooled means and standard deviations of the burst duration and the inter-burst duration across OSA patients were also calculated to be minutes and minutes. Scalogram amplitude and spectral decomposition of the wavelet transform exhibited various predominant frequencies and dynamics modes associated with apneic events.
Applying Polynomial Decoupling Methods to the Polynomial NARX Model
Authors: Kiana Karami, David Westwick, Johan Schoukens
Date: 2022-02-24 00:00:00
Tasks: Friction

System identification uses measurements of a dynamic system's input and output to reconstruct a mathematical model for that system. These can be mechanical, electrical, physiological, among others. Since most of the systems around us exhibit some form of nonlinear behavior, nonlinear system identification techniques are the tools that will help us gain a better understanding of our surroundings and potentially let us improve their performance. One model that is often used to represent nonlinear systems is the polynomial NARX model, an equation error model where the output is a polynomial function of the past inputs and outputs. That said, a major disadvantage with the polynomial NARX model is that the number of parameters increases rapidly with increasing polynomial order. Furthermore, the polynomial NARX model is a black-box model, and is therefore difficult to interpret. This paper discusses a decoupling algorithm for the polynomial NARX model that substitutes the multivariate polynomial with a transformation matrix followed by a bank of univariate polynomials. This decreases the number of model parameters significantly and also imposes structure on the black-box NARX model. Since a non-convex optimization is required for this identification technique, initialization is an important factor to consider. In this paper the decoupling algorithm is developed in conjunction with several different initialization techniques. The resulting algorithms are applied to two nonlinear benchmark problems: measurement data from the Silver-Box and simulation data from the Bouc-Wen friction model, and the performance is evaluated for different validation signals in both simulation and prediction.
Symbol repetition in interstellar communications: methods and observations
Authors: William J. Crilly Jr
Date: 2022-02-25 00:00:00

Discoverable interstellar communication signals are expected to exhibit al least one signal characteristic clearly distinct from random noise. A hypothesis is proposed that radio telescope received signals may contain transmitted delta-t delta-f opposite circular polarized pulse pairs, conveying a combination of information content and discovery methods, including symbol repetition. Hypothetical signals are experimentally measured using a 26 foot diameter radio telescope, a chosen matched filter receiver, and machine post processing system. Measurements are expected to present likelihoods explained by an Additive White Gaussian Noise model, augmented to reduce radio frequency interference. In addition, measurements are expected to present no significant differences across a population of Right Ascension ranges, during long duration experiments. The hypothesis and experimental methods described in this paper are based on multiple radio telescope delta-t delta-f polarized pulse pair experiments previously reported. (ref. arXiv:2105.03727, arXiv:2106.10168). In the current work, a Right Ascension filter spans twenty-one 0.3 hour Right Ascension bins over a 0 to 6.3 hr range, during a 143 day experiment. Apparent symbol repetition is measured and analyzed. The 5.25 plus or minus 0.15 hr Right Ascension, -7.6 degree plus or minus 1 degree Declination celestial direction has been associated with anomalous observations in previous work, and continues to present anomalies, having unknown cause.
Aggregation as an antipredator strategy in the rock-paper-scissors model
Authors: J. Menezes, E. Rangel, B. Moura
Date: 2022-02-24 00:00:00

We study a nonhierarchical tritrophic system, whose predator-prey interactions are described by the rock-paper-scissors game rules. In our stochastic simulations, individuals may move strategically towards the direction with more conspecifics to form clumps instead of moving aimlessly on the lattice. Considering that the conditioning to move gregariously depends on the organism's physical and cognitive abilities, we introduce a maximum distance an individual can perceive the environment and a minimum conditioning level to perform the gregarious movement. We investigate the pattern formation and compute the average size of the single-species spatial domains emerging from the grouping behaviour. The results reveal that the defence tactic reduces the predation risk significantly, being more profitable if individuals perceive further distances, thus creating bigger groups. Our outcomes show that the species with more conditioned organisms dominate the cyclic spatial game, controlling most of the territory. On the other hand, the species with fewer individuals ready to perform aggregation strategy gives its predator the chance to fill the more significant fraction of the grid. The spatial interactions assumed in our numerical experiments constitute a data set that may help biologists and data scientists understand how local interactions influence ecosystem dynamics.
Cardiac Reentry Modeled by Spatiotemporal Chaos in a Coupled Map Lattice
Authors: R. V. Stenzinger, M. H. R. Tragtenberg
Date: 2022-02-12 00:00:00
Tasks: Rhythm

Arrhythmias are potentially fatal disruptions to the normal heart rhythm, but their underlying dynamics is still poorly understood. Theoretical modeling is an important tool to fill this gap. Typical studies often employ detailed multidimensional conductance-based models. We describe the cardiac muscle with a three-dimensional map-based membrane potential model in lattices. Although maps retain the biophysical behavior of cells and generate computationally efficient tissue models, few studies have used them to understand cardiac dynamics. Our study captures healthy and pathological behaviors with fewer parameters and simpler equations than conductance models. We successfully generalize results obtained previously with reaction-diffusion systems, showing how chaotic properties result in reentry, a pathological propagation of stimuli that evolves to arrhythmias with complex spatiotemporal features. The bifurcation diagram of the single cell is very similar to that obtained in a detailed conductance-based model. We find torsade de pointes, a clinical manifestation of some types of tachycardia in the electrocardiogram, using a generic sampling of the whole network during spiral waves. We also find a novel type of dynamical pattern, with wavefronts composed of synchronized cardiac plateaus and bursts. Our study provides the first in-depth look at the use of map-based models to simulate complex cardiac dynamics.