-
Empirical Individual State Observability
Authors:
Benjamin Cellini,
Burak Boyacıoğlu,
Floris van Breugel
Abstract:
A dynamical system is observable if there is a one-to-one mapping from the system's measured outputs and inputs to all of the system's states. Analytical and empirical tools exist for quantifying the (full state) observability of linear and nonlinear systems; however, empirical tools for evaluating the observability of individual state variables are lacking. Here, a new empirical approach termed E…
▽ More
A dynamical system is observable if there is a one-to-one mapping from the system's measured outputs and inputs to all of the system's states. Analytical and empirical tools exist for quantifying the (full state) observability of linear and nonlinear systems; however, empirical tools for evaluating the observability of individual state variables are lacking. Here, a new empirical approach termed Empirical Individual State Observability (E-ISO) is developed to quantify the level of observability of individual state variables. E-ISO first builds an empirical observability matrix via simulation, then applies convex optimization to efficiently determine the subset of its rows required to estimate each state variable individually. Finally, (un)observability measures for these subsets are calculated to provide independent estimates of the observability of each state variable. Multiple example applications of E-ISO on linear and nonlinear systems are shown to be consistent with analytical results. Broadly, E-ISO will be an invaluable tool both for designing active sensing control laws or optimizing sensor placement to increase the observability of individual state variables for engineered systems, and analyzing the trajectory decisions made by organisms.
△ Less
Submitted 14 September, 2023; v1 submitted 27 April, 2023;
originally announced April 2023.
-
A Method for Classifying Snow Using Ski-Mounted Strain Sensors
Authors:
Florian McLelland,
Floris van Breugel
Abstract:
Understanding the structure, quantity, and type of snow in mountain landscapes is crucial for assessing avalanche safety, interpreting satellite imagery, building accurate hydrology models, and choosing the right pair of skis for your weekend trip. Currently, such characteristics of snowpack are measured using a combination of remote satellite imagery, weather stations, and laborious point measure…
▽ More
Understanding the structure, quantity, and type of snow in mountain landscapes is crucial for assessing avalanche safety, interpreting satellite imagery, building accurate hydrology models, and choosing the right pair of skis for your weekend trip. Currently, such characteristics of snowpack are measured using a combination of remote satellite imagery, weather stations, and laborious point measurements and descriptions provided by local forecasters, guides, and backcountry users. Here, we explore how characteristics of the top layer of snowpack could be estimated while skiing using strain sensors mounted to the top surface of an alpine ski. We show that with two strain gauges and an inertial measurement unit it is feasible to correctly assign one of three qualitative labels (powder, slushy, or icy/groomed snow) to each 10 second segment of a trajectory with 97% accuracy, independent of skiing style. Our algorithm uses a combination of a data-driven linear model of the ski-snow interaction, dimensionality reduction, and a Naive Bayes classifier. Comparisons of classifier performance between strain gauges suggest that the optimal placement of strain gauges is halfway between the binding and the tip/tail of the ski, in the cambered section just before the point where the unweighted ski would touch the snow surface. The ability to classify snow, potentially in real-time, using skis opens the door to applications that range from citizen science efforts to map snow surface characteristics in the backcountry, and develop skis with automated stiffness tuning based on the snow type.
△ Less
Submitted 27 April, 2023;
originally announced April 2023.
-
Emergent behavior and neural dynamics in artificial agents tracking turbulent plumes
Authors:
Satpreet Harcharan Singh,
Floris van Breugel,
Rajesh P. N. Rao,
Bingni Wen Brunton
Abstract:
Tracking a turbulent plume to locate its source is a complex control problem because it requires multi-sensory integration and must be robust to intermittent odors, changing wind direction, and variable plume statistics. This task is routinely performed by flying insects, often over long distances, in pursuit of food or mates. Several aspects of this remarkable behavior have been studied in detail…
▽ More
Tracking a turbulent plume to locate its source is a complex control problem because it requires multi-sensory integration and must be robust to intermittent odors, changing wind direction, and variable plume statistics. This task is routinely performed by flying insects, often over long distances, in pursuit of food or mates. Several aspects of this remarkable behavior have been studied in detail in many experimental studies. Here, we take a complementary in silico approach, using artificial agents trained with reinforcement learning to develop an integrated understanding of the behaviors and neural computations that support plume tracking. Specifically, we use deep reinforcement learning (DRL) to train recurrent neural network (RNN) agents to locate the source of simulated turbulent plumes. Interestingly, the agents' emergent behaviors resemble those of flying insects, and the RNNs learn to represent task-relevant variables, such as head direction and time since last odor encounter. Our analyses suggest an intriguing experimentally testable hypothesis for tracking plumes in changing wind direction -- that agents follow local plume shape rather than the current wind direction. While reflexive short-memory behaviors are sufficient for tracking plumes in constant wind, longer timescales of memory are essential for tracking plumes that switch direction. At the level of neural dynamics, the RNNs' population activity is low-dimensional and organized into distinct dynamical structures, with some correspondence to behavioral modules. Our in silico approach provides key intuitions for turbulent plume tracking strategies and motivates future targeted experimental and theoretical developments.
△ Less
Submitted 17 December, 2021; v1 submitted 25 September, 2021;
originally announced September 2021.
-
A Nonlinear Observability Analysis of Ambient Wind Estimation with Uncalibrated Sensors, Inspired by Insect Neural Encoding
Authors:
Floris van Breugel
Abstract:
Estimating the direction of ambient fluid flow is key for many flying or swimming animals and robots, but can only be accomplished through indirect measurements and active control. Recent work with tethered flying insects indicates that their sensory representation of orientation, apparent flow, direction of movement, and control is represented by a 2-dimensional angular encoding in the central br…
▽ More
Estimating the direction of ambient fluid flow is key for many flying or swimming animals and robots, but can only be accomplished through indirect measurements and active control. Recent work with tethered flying insects indicates that their sensory representation of orientation, apparent flow, direction of movement, and control is represented by a 2-dimensional angular encoding in the central brain. This representation simplifies sensory integration by projecting the direction (but not scale) of measurements with different units onto a universal polar coordinate frame. To align these angular measurements with one another and the motor system does, however, require a calibration of angular gain and offset for each sensor. This calibration could change with time due to changes in the environment or physical structure. The circumstances under which small robots and animals with angular sensors and changing calibrations could self-calibrate and estimate the direction of ambient fluid flow while moving remains an open question. Here, a methodical nonlinear observability analysis is presented to address this. The analysis shows that it is mathematically feasible to continuously estimate flow direction and perform regular self-calibrations by adopting frequent changes in course (or active prevention thereof) and orientation, and requires fusion and temporal differentiation of three sensory measurements: apparent flow, orientation (or its derivative), and direction of motion (or its derivative). These conclusions are consistent with the zigzagging trajectories exhibited by many plume tracking organisms, suggesting that perhaps flow estimation is a secondary driver of their trajectory structure.
△ Less
Submitted 7 June, 2021;
originally announced June 2021.
-
Numerical differentiation of noisy data: A unifying multi-objective optimization framework
Authors:
Floris van Breugel,
J. Nathan Kutz,
Bingni W. Brunton
Abstract:
Computing derivatives of noisy measurement data is ubiquitous in the physical, engineering, and biological sciences, and it is often a critical step in developing dynamic models or designing control. Unfortunately, the mathematical formulation of numerical differentiation is typically ill-posed, and researchers often resort to an \textit{ad hoc} process for choosing one of many computational metho…
▽ More
Computing derivatives of noisy measurement data is ubiquitous in the physical, engineering, and biological sciences, and it is often a critical step in developing dynamic models or designing control. Unfortunately, the mathematical formulation of numerical differentiation is typically ill-posed, and researchers often resort to an \textit{ad hoc} process for choosing one of many computational methods and its parameters. In this work, we take a principled approach and propose a multi-objective optimization framework for choosing parameters that minimize a loss function to balance the faithfulness and smoothness of the derivative estimate. Our framework has three significant advantages. First, the task of selecting multiple parameters is reduced to choosing a single hyper-parameter. Second, where ground-truth data is unknown, we provide a heuristic for automatically selecting this hyper-parameter based on the power spectrum and temporal resolution of the data. Third, the optimal value of the hyper-parameter is consistent across different differentiation methods, thus our approach unifies vastly different numerical differentiation methods and facilitates unbiased comparison of their results. Finally, we provide an extensive open-source Python library \texttt{pynumdiff} to facilitate easy application to diverse datasets (https://github.com/florisvb/PyNumDiff).
△ Less
Submitted 7 September, 2020; v1 submitted 3 September, 2020;
originally announced September 2020.
-
FLIVVER: Fly Lobula Inspired Visual Velocity Estimation & Ranging
Authors:
Bryson Lingenfelter,
Arunava Nag,
Floris van Breugel
Abstract:
The mechanism by which a tiny insect or insect-sized robot could estimate its absolute velocity and distance to nearby objects remains unknown. However, this ability is critical for behaviors that require estimating wind direction during flight, such as odor-plume tracking. Neuroscience and behavior studies with insects have shown that they rely on the perception of image motion, or optic flow, to…
▽ More
The mechanism by which a tiny insect or insect-sized robot could estimate its absolute velocity and distance to nearby objects remains unknown. However, this ability is critical for behaviors that require estimating wind direction during flight, such as odor-plume tracking. Neuroscience and behavior studies with insects have shown that they rely on the perception of image motion, or optic flow, to estimate relative motion, equivalent to a ratio of their velocity and distance to objects in the world. The key open challenge is therefore to decouple these two states from a single measurement of their ratio. Although modern SLAM (Simultaneous Localization and Mapping) methods provide a solution to this problem for robotic systems, these methods typically rely on computations that insects likely cannot perform, such as simultaneously tracking multiple individual visual features, remembering a 3D map of the world, and solving nonlinear optimization problems using iterative algorithms. Here we present a novel algorithm, FLIVVER, which combines the geometry of dynamic forward motion with inspiration from insect visual processing to \textit{directly} estimate absolute ground velocity from a combination of optic flow and acceleration information. Our algorithm provides a clear hypothesis for how insects might estimate absolute velocity, and also provides a theoretical framework for designing fast analog circuitry for efficient state estimation, which could be applied to insect-sized robots.
△ Less
Submitted 10 April, 2020;
originally announced April 2020.
-
Computing Probabilistic Bisimilarity Distances for Probabilistic Automata
Authors:
Giorgio Bacci,
Giovanni Bacci,
Kim G. Larsen,
Radu Mardare,
Qiyi Tang,
Franck van Breugel
Abstract:
The probabilistic bisimilarity distance of Deng et al. has been proposed as a robust quantitative generalization of Segala and Lynch's probabilistic bisimilarity for probabilistic automata. In this paper, we present a characterization of the bisimilarity distance as the solution of a simple stochastic game. The characterization gives us an algorithm to compute the distances by applying Condon's si…
▽ More
The probabilistic bisimilarity distance of Deng et al. has been proposed as a robust quantitative generalization of Segala and Lynch's probabilistic bisimilarity for probabilistic automata. In this paper, we present a characterization of the bisimilarity distance as the solution of a simple stochastic game. The characterization gives us an algorithm to compute the distances by applying Condon's simple policy iteration on these games. The correctness of Condon's approach, however, relies on the assumption that the games are stopping. Our games may be non-stopping in general, yet we are able to prove termination for this extended class of games. Already other algorithms have been proposed in the literature to compute these distances, with complexity in $\textbf{UP} \cap \textbf{coUP}$ and \textbf{PPAD}. Despite the theoretical relevance, these algorithms are inefficient in practice. To the best of our knowledge, our algorithm is the first practical solution.
The characterization of the probabilistic bisimilarity distance mentioned above crucially uses a dual presentation of the Hausdorff distance due to Mémoli. As an additional contribution, in this paper we show that Mémoli's result can be used also to prove that the bisimilarity distance bounds the difference in the maximal (or minimal) probability of two states to satisfying arbitrary $ω$-regular properties, expressed, eg., as LTL formulas.
△ Less
Submitted 1 February, 2021; v1 submitted 3 July, 2019;
originally announced July 2019.
-
Measuring Progress of Probabilistic LTL Model Checking
Authors:
Elise Cormie-Bowins,
Franck van Breugel
Abstract:
Recently, Zhang and Van Breugel introduced the notion of a progress measure for a probabilistic model checker. Given a linear-time property P and a description of the part of the system that has already been checked, the progress measure returns a real number in the unit interval. The real number captures how much progress the model checker has made towards verifying P. If the progress is zero,…
▽ More
Recently, Zhang and Van Breugel introduced the notion of a progress measure for a probabilistic model checker. Given a linear-time property P and a description of the part of the system that has already been checked, the progress measure returns a real number in the unit interval. The real number captures how much progress the model checker has made towards verifying P. If the progress is zero, no progress has been made. If it is one, the model checker is done. They showed that the progress measure provides a lower bound for the measure of the set of execution paths that satisfy P. They also presented an algorithm to compute the progress measure when P is an invariant.
In this paper, we present an algorithm to compute the progress measure when P is a formula of a positive fragment of linear temporal logic. In this fragment, we can express invariants but also many other interesting properties. The algorithm is exponential in the size of P and polynomial in the size of that part of the system that has already been checked. We also present an algorithm to compute a lower bound for the progress measure in polynomial time.
△ Less
Submitted 3 July, 2012;
originally announced July 2012.
-
Approximating a Behavioural Pseudometric without Discount for<br> Probabilistic Systems
Authors:
Franck van Breugel,
Babita Sharma,
James Worrell
Abstract:
Desharnais, Gupta, Jagadeesan and Panangaden introduced a family of behavioural pseudometrics for probabilistic transition systems. These pseudometrics are a quantitative analogue of probabilistic bisimilarity. Distance zero captures probabilistic bisimilarity. Each pseudometric has a discount factor, a real number in the interval (0, 1]. The smaller the discount factor, the more the future is d…
▽ More
Desharnais, Gupta, Jagadeesan and Panangaden introduced a family of behavioural pseudometrics for probabilistic transition systems. These pseudometrics are a quantitative analogue of probabilistic bisimilarity. Distance zero captures probabilistic bisimilarity. Each pseudometric has a discount factor, a real number in the interval (0, 1]. The smaller the discount factor, the more the future is discounted. If the discount factor is one, then the future is not discounted at all. Desharnais et al. showed that the behavioural distances can be calculated up to any desired degree of accuracy if the discount factor is smaller than one. In this paper, we show that the distances can also be approximated if the future is not discounted. A key ingredient of our algorithm is Tarski's decision procedure for the first order theory over real closed fields. By exploiting the Kantorovich-Rubinstein duality theorem we can restrict to the existential fragment for which more efficient decision procedures exist.
△ Less
Submitted 9 April, 2008; v1 submitted 26 March, 2008;
originally announced March 2008.
