skip to main content

Title: Mapping and coverage with a particle swarm controlled by uniform inputs
We propose an approach to mapping tissue and vascular systems without the use of contrast agents, based on moving and measuring magnetic particles. To this end, we consider a swarm of particles in a 1D or 2D grid that can be tracked and controlled by an external agent. Control inputs are applied uniformly so that each particle experiences the same applied forces. We present algorithms for three tasks: (1) Mapping, i.e., building a representation of the free and obstacle regions of the workspace; (2) Subset Coverage, i.e., ensuring that at least one particle reaches each of a set of desired locations; and (3) Coverage, i.e., ensuring that every free region on the map is visited by at least one particle. These tasks relate to a large body of previous work from robot navigation, both from theory and practice, which is based on individual control. We provide theoretical insights that have potential relevance for fast MRI scans with magnetically controlled contrast media. In particular, we develop a fundamentally new approach for searching for an object at an unknown distance D, where the search is subject to two different and independent cost parameters for moving and for measuring. We show that regardless more » of the relative cost of these two operations, there is a simple O(log D/log log D)-competitive strategy, which is the best possible. Also, we provide practically useful and computationally efficient strategies for higher-dimensional settings. These algorithms extend to any number of particles and show that additional particles tend to reduce the mean and the standard deviation of the time required for each task. « less
; ; ;
Award ID(s):
1553063 1619278
Publication Date:
Journal Name:
Intelligent Robots and Systems (IROS), 2017 IEEE/RSJ International Conference on
Page Range or eLocation-ID:
1097 to 1104
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract
    Site description. This data package consists of data obtained from sampling surface soil (the 0-7.6 cm depth profile) in black mangrove (Avicennia germinans) dominated forest and black needlerush (Juncus roemerianus) saltmarsh along the Gulf of Mexico coastline in peninsular west-central Florida, USA. This location has a subtropical climate with mean daily temperatures ranging from 15.4 °C in January to 27.8 °C in August, and annual precipitation of 1336 mm. Precipitation falls as rain primarily between June and September. Tides are semi-diurnal, with 0.57 m median amplitudes during the year preceding sampling (U.S. NOAA National Ocean Service, Clearwater Beach, Florida, station 8726724). Sea-level rise is 4.0 ± 0.6 mm per year (1973-2020 trend, mean ± 95 % confidence interval, NOAA NOS Clearwater Beach station). The A. germinans mangrove zone is either adjacent to water or fringed on the seaward side by a narrow band of red mangrove (Rhizophora mangle). A near-monoculture of J. roemerianus is often adjacent to and immediately landward of the A. germinans zone. The transition from the mangrove to the J. roemerianus zone is variable in our study area. An abrupt edge between closed-canopy mangrove and J. roemerianus monoculture may extend for up to several hundred metersMore>>
  2. This paper addresses the complete area coverage problem of a known environment by multiple-robots. Complete area coverage is the problem of moving an end-effector over all available space while avoiding existing obstacles. In such tasks, using multiple robots can increase the efficiency of the area coverage in terms of minimizing the operational time and increase the robustness in the face of robot attrition. Unfortunately, the problem of finding an optimal solution for such an area coverage problem with multiple robots is known to be NP-complete. In this paper we present two approximation heuristics for solving the multi-robot coverage problem. The first solution presented is a direct extension of an efficient single robot area coverage algorithm, based on an exact cellular decomposition. The second algorithm is a greedy approach that divides the area into equal regions and applies an efficient single-robot coverage algorithm to each region. We present experimental results for two algorithms. Results indicate that our approaches provide good coverage distribution between robots and minimize the workload per robot, meanwhile ensuring complete coverage of the area.
  3. Abstract

    Advances in visual perceptual tasks have been mainly driven by the amount, and types, of annotations of large-scale datasets. Researchers have focused on fully-supervised settings to train models using offline epoch-based schemes. Despite the evident advancements, limitations and cost of manually annotated datasets have hindered further development for event perceptual tasks, such as detection and localization of objects and events in videos. The problem is more apparent in zoological applications due to the scarcity of annotations and length of videos-most videos are at most ten minutes long. Inspired by cognitive theories, we present a self-supervised perceptual prediction framework to tackle the problem of temporal event segmentation by building a stable representation of event-related objects. The approach is simple but effective. We rely on LSTM predictions of high-level features computed by a standard deep learning backbone. For spatial segmentation, the stable representation of the object is used by an attention mechanism to filter the input features before the prediction step. The self-learned attention maps effectively localize the object as a side effect of perceptual prediction. We demonstrate our approach on long videos from continuous wildlife video monitoring, spanning multiple days at 25 FPS. We aim to facilitate automated ethogramming bymore »detecting and localizing events without the need for labels. Our approach is trained in an online manner on streaming input and requires only a single pass through the video, with no separate training set. Given the lack of long and realistic (includes real-world challenges) datasets, we introduce a new wildlife video dataset–nest monitoring of the Kagu (a flightless bird from New Caledonia)–to benchmark our approach. Our dataset features a video from 10 days (over 23 million frames) of continuous monitoring of the Kagu in its natural habitat. We annotate every frame with bounding boxes and event labels. Additionally, each frame is annotated with time-of-day and illumination conditions. We will make the dataset, which is the first of its kind, and the code available to the research community. We find that the approach significantly outperforms other self-supervised, traditional (e.g., Optical Flow, Background Subtraction) and NN-based (e.g., PA-DPC, DINO, iBOT), baselines and performs on par with supervised boundary detection approaches (i.e., PC). At a recall rate of 80%, our best performing model detects one false positive activity every 50 min of training. On average, we at least double the performance of self-supervised approaches for spatial segmentation. Additionally, we show that our approach is robust to various environmental conditions (e.g., moving shadows). We also benchmark the framework on other datasets (i.e., Kinetics-GEBD, TAPOS) from different domains to demonstrate its generalizability. The data and code are available on our project page:

    « less
  4. Counting and uniformly sampling motifs in a graph are fundamental algorithmic tasks with numerous applications across multiple fields. Since these problems are computationally expensive, recent efforts have focused on devising sublinear-time algorithms for these problems. We consider the model where the algorithm gets a constant size motif H and query access to a graph G, where the allowed queries are degree, neighbor, and pair queries, as well as uniform edge sample queries. In the sampling task, the algorithm is required to output a uniformly distributed copy of H in G (if one exists), and in the counting task it is required to output a good estimate to the number of copies of H in G. Previous algorithms for the uniform sampling task were based on a decomposition of H into a collection of odd cycles and stars, denoted D∗(H) = {Ok1 , ...,Okq , Sp1 , ..., Spℓ19 }. These algorithms were shown to be optimal for the case where H is a clique or an odd-length cycle, but no other lower bounds were known. We present a new algorithm for sampling arbitrary motifs which, up to poly(log n) factors, for any motif H whose decomposition contains at least twomore »components or at least one star, is always preferable. The main ingredient leading to this improvement is an improved uniform algorithm for sampling stars, which might be of independent interest, as it allows to sample vertices according to the p-th moment of the degree distribution. We further show how to use our sampling algorithm to get an approximate counting algorithm, with essentially the same complexity. Finally, we prove that this algorithm is decomposition-optimal for decompositions that contain at least one odd cycle. That is, we prove that for any decomposition D that contains at least one odd cycle, there exists a motif HD 30 with decomposition D, and a family of graphs G, so that in order to output a uniform copy of H in a uniformly chosen graph in G, the number of required queries matches our upper bound. These are the first lower bounds for motifs H with a nontrivial decomposition, i.e., motifs that have more than a single component in their decomposition.« less
  5. We investigate the effect of inertial particles on the stability and decay of a prototypical vortex tube, represented by a two-dimensional Lamb–Oseen vortex. In the absence of particles, the strong stability of this flow makes it resilient to perturbations, whereby vorticity and enstrophy decay at a slow rate controlled by viscosity. Using Eulerian–Lagrangian simulations, we show that the dispersion of semidilute inertial particles accelerates the decay of the vortex tube by orders of magnitude. In this work, mass loading is unity, ensuring that the fluid and particle phases are tightly coupled. Particle inertia and vortex strength are varied to yield Stokes numbers 0.1–0.4 and circulation Reynolds numbers 800–5000. Preferential concentration causes these inertial particles to be ejected from the vortex core forming a ring-shaped cluster and a void fraction bubble that expand outwards. The outward migration of the particles causes a flattening of the vorticity distribution, which enhances the decay of the vortex. The latter is further accelerated by small-scale clustering that causes enstrophy to grow, in contrast with the monotonic decay of enstrophy in single-phase two-dimensional vortices. These dynamics unfold on a time scale that is set by preferential concentration and is two orders of magnitude lower than themore »viscous time scale. Increasing particle inertia causes a faster decay of the vortex. This work shows that the injection of inertial particles could provide an effective strategy for the control and suppression of resilient vortex tubes.« less