More Like this

1. A finite-horizon approach to active level set estimation

   https://doi.org/10.3934/fods.2024050  

   Kearns, Phillip; Jedynak, Bruno; Lipor, John (January 2024, Foundations of Data Science)

   We consider the problem of active learning for level set estimation (LSE), where the goal is to localize all regions where a function of interest lies above/below a given threshold as quickly as possible. We present a finite-horizon search procedure to perform LSE in one dimension while optimally balancing both the final estimation error and the distance traveled during active learning for a fixed number of samples. A tuning parameter is used to trade off between the estimation accuracy and distance traveled. We show that the resulting optimization problem can be solved in closed form and that the resulting policy generalizes existing approaches to this problem. We then show how this approach can be used to perform level set estimation in two dimensions, under some additional assumptions, under the popular Gaussian process model. Empirical results on synthetic data indicate that as the cost of travel increases, our method's ability to treat distance nonmyopically allows it to significantly improve on the state of the art. On real air quality data, our approach achieves roughly one fifth the estimation error at less than half the cost of competing algorithms. 

   more » « less
2. Separable Representations for Duration and Distance in Virtual Movements

   https://doi.org/10.1162/jocn_a_02097  

   Gladhill, Keri Anne; Robinson, Eva Marie; Stanfield-Wiswell, Candice; Bader, Farah; Wiener, Martin (January 2024, Journal of Cognitive Neuroscience)

   Abstract To navigate through the environment, humans must be able to measure both the distance traveled in space, and the interval elapsed in time. Yet, how the brain holds both of these metrics simultaneously is less well known. One possibility is that participants measure how far and how long they have traveled relative to a known reference point. To measure this, we had human participants (n = 24) perform a distance estimation task in a virtual environment in which they were cued to attend to either the spatial or temporal interval traveled while responses were measured with multiband fMRI. We observed that both dimensions evoked similar frontoparietal networks, yet with a striking rostrocaudal dissociation between temporal and spatial estimation. Multivariate classifiers trained on each dimension were further able to predict the temporal or spatial interval traveled, with centers of activation within the SMA and retrosplenial cortex for time and space, respectively. Furthermore, a cross-classification approach revealed the right supramarginal gyrus and occipital place area as regions capable of decoding the general magnitude of the traveled distance. Altogether, our findings suggest the brain uses separate systems for tracking spatial and temporal distances, which are combined together along with dimension-nonspecific estimates. 

   more » « less
3. Boundary sketching with asymptotically optimal distance and rotation

   https://doi.org/10.1016/j.tcs.2024.114714  

   Dani, Varsha; Islam, Abir; Saia, Jared (September 2024, Theoretical Computer Science)

   We address the problem of designing a distributed algorithm for two robots that sketches the boundary of an unknown shape. Critically, we assume a certain amount of delay in how quickly our robots can react to external feedback. In particular, when a robot moves, it commits to move along path of length at least 𝜆, or turn an amount of radians at least 𝜆 for some positive 𝜆 ≤ 1∕26, that is normalized based on a unit diameter shape. Then, our algorithm outputs a polygon that is √ an 𝜖-sketch, for 𝜖 =8 𝜆, in the sense that every point on the shape boundary is within distance 𝜖 of the output polygon. Moreover, our costs are asymptotically optimal in two key criteria for the robots: total distance traveled and total amount of rotation. Additionally, we implement our algorithm, and illustrate its output on some specific shapes. 

   more » « less
4. Map-matching using shortest paths

   https://doi.org/10.1145/3191801.3191812  

   Chambers, Erin; Fasy, Brittany Terese; Wang, Yusu; Wenk, Carola (January 2018, IWISC)

   We consider several variants of the map-matching problem, which seeks to find a path Q in graph G that has the smallest distance to a given trajectory P (which is likely not to be exactly on the graph). In a typical application setting, P models a noisy GPS trajectory from a person traveling on a road network, and the desired path Q should ideally correspond to the actual path in G that the person has traveled. Existing map-matching algorithms in the literature consider all possible paths in G as potential candidates for Q. We find solutions to the map-matching problem under different settings. In particular, we restrict the set of paths to shortest paths, or concatenations of shortest paths, in G. As a distance measure, we use the Fréchet distance, which is a suitable distance measure for curves since it takes the continuity of the curves into account. 

   more » « less
5. Bounding the Distance to Unsafe Sets With Convex Optimization

   https://doi.org/10.1109/TAC.2023.3285862  

   Miller, Jared; Sznaier, Mario (August 2023, IEEE Transactions on Automatic Control)

   This work proposes an algorithm to bound the minimum distance between points on trajectories of a dynamical system and points on an unsafe set. Prior work on certifying safety of trajectories includes barrier and density methods, which do not provide a margin of proximity to the unsafe set in terms of distance. The distance estimation problem is relaxed to a Monge-Kantorovich-type optimal transport problem based on existing occupation-measure methods of peak estimation. Specialized programs may be developed for polyhedral norm distances (e.g. L1 and Linfinity) and for scenarios where a shape is traveling along trajectories (e.g. rigid body motion). The distance estimation problem will be correlatively sparse when the distance objective is separable. 

   more » « less