More Like this

1. A Model and Analysis of House-Hunting in Ant Colonies

   Zhang, E.; Zhao, J.; Lynch, N. (January 2021, 8th Workshop on Biological Distributed Algorithms (BDA))

   We study the problem of house-hunting in ant colonies, where ants reach consensus on a new nest and relocate their colony to that nest, from a distributed computing perspective. We propose a house-hunting algorithm that is biologically inspired by Temnothorax ants. Each ant is modelled as a probabilistic agent with limited power, and there is no central control governing the ants. We show a (log n) lower bound on the running time of our proposed house-hunting algorithm, where n is the number of ants. Further, we show a matching upper bound of expected O(log n) rounds for environments with only one candidate nest for the ants to move to. Our work provides insights into the house-hunting process, giving a perspective on how environmental factors such as nest qualities or a quorum rule can affect the emigration process. In particular, we find that a quorum threshold that is high enough causes transports to the inferior nest to cease to happen after O(log n) rounds when there are two nests in the environment. 

   more » « less
2. A Model and Analysis of House-Hunting in Ant Colonies

   Zhang, E.; Zhao, J.; Lynch, N. (January 2021, 8th Workshop on Biological Distributed Algorithms (BDA))

   We study the problem of house-hunting in ant colonies, where ants reach consensus on a new nest and relocate their colony to that nest, from a distributed computing perspective. We propose a house-hunting algorithm that is biologically inspired by Temnothorax ants. Each ant is modelled as a probabilistic agent with limited power, and there is no central control governing the ants. We show a Ω(log n) lower bound on the running time of our proposed house-hunting algorithm, where n is the number of ants. Further, we show a matching upper bound of expected O(log n) rounds for environments with only one candidate nest for the ants to move to. Our work provides insights into the house-hunting process, giving a perspective on how environmental factors such as nest qualities or a quorum rule can affect the emigration process. In particular, we find that a quorum threshold that is high enough causes transports to the inferior nest to cease to happen after O(log n) rounds when there are two nests in the environment. 

   more » « less
3. Fréchet Distance for Uncertain Curves

   https://doi.org/10.1145/3597640  

   Buchin, Kevin; Fan, Chenglin; Löffler, Maarten; Popov, Aleksandr; Raichel, Benjamin; Roeloffzen, Marcel (July 2023, ACM Transactions on Algorithms)

   In this article, we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. An uncertain curve is a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fréchet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves. We prove that both problems are NP-hard for the Fréchet distance in several uncertainty models, and that the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound (discrete [ 5 ] and continuous) Fréchet distance can be computed in polynomial time in some models. Furthermore, we show that computing the expected (discrete and continuous) Fréchet distance is #P-hard in some models. On the positive side, we present an FPTAS in constant dimension for the lower bound problem when Δ/δ is polynomially bounded, where δ is the Fréchet distance and Δ bounds the diameter of the regions. We also show a near-linear-time 3-approximation for the decision problem on roughly δ-separated convex regions. Finally, we study the setting with Sakoe–Chiba time bands, where we restrict the alignment between the curves, and give polynomial-time algorithms for the upper bound and expected discrete and continuous Fréchet distance for uncertainty modelled as point sets. 

   more » « less
4. Learning ecosystem-scale dynamics from microbiome data with MDSINE2

   https://doi.org/10.1038/s41564-025-02112-6  

   Gibson, Travis_E; Kim, Younhun; Acharya, Sawal; Kaplan, David_E; DiBenedetto, Nicholas; Lavin, Richard; Berger, Bonnie; Allegretti, Jessica_R; Bry, Lynn; Gerber, Georg_K (September 2025, Nature Microbiology)

   Abstract Although dynamical systems models are a powerful tool for analysing microbial ecosystems, challenges in learning these models from complex microbiome datasets and interpreting their outputs limit use. We introduce the Microbial Dynamical Systems Inference Engine 2 (MDSINE2), a Bayesian method that learns compact and interpretable ecosystems-scale dynamical systems models from microbiome timeseries data. Microbial dynamics are modelled as stochastic processes driven by interaction modules, or groups of microbes with similar interaction structure and responses to perturbations, and additionally, noise characteristics of data are modelled. Our open-source software package provides multiple tools for interpreting learned models, including phylogeny/taxonomy of modules, and stability, interaction topology and keystoneness. To benchmark MDSINE2, we generated microbiome timeseries data from two murine cohorts that received faecal transplants from human donors and were then subjected to dietary and antibiotic perturbations. MDSINE2 outperforms state-of-the-art methods and identifies interaction modules that provide insights into ecosystems-scale interactions in the gut microbiome. 

   more » « less
5. An Open Source Video Analytics Tool for Analyzing Learner Navigation in Immersive Simulated Environments

   Soriano, N.; Negahban, A.; Ozden, S.; Ashour, O. (January 2023, 2023 Annual Modeling and Simulation Conference)

   In educational research, user-simulation interaction is gaining importance as it provides key insights into the effectiveness of simulation-based learning and immersive technologies. A common approach to study user-simulation interaction involves manually analyzing participant interaction in real-time or via video recordings, which is a tedious process. Surveys/questionnaires are also commonly used but are open to subjectivity and only provide qualitative data. The tool proposed in this paper, which we call Environmental Detection for User-Simulation Interaction Measurement (EDUSIM), is a publicly available video analytics tool that receives screen-recorded video input from participants interacting with a simulated environment and outputs statistical data related to time spent in pre-defined areas of interest within the simulation model. The proposed tool utilizes machine learning, namely multi-classification Convolutional Neural Networks, to provide an efficient, automated process for extracting such navigation data. EDUSIM also implements a binary classification model to flag imperfect input video data such as video frames that are outside the specified simulation environment. To assess the efficacy of the tool, we implement a set of immersive simulation-based learning (ISBL) modules in an undergraduate database course, where learners record their screens as they interact with a simulation to complete their ISBL assignments. We then use the EDUSIM tool to analyze the videos collected and compare the tool’s outputs with the expected results obtained by manually analyzing the videos. 

   more » « less