In this paper, we present extensive advances in live-fly field experimentation capabilities of large numbers of fixed-wing aerial robots, and highlight both the enabling technologies as well as the challenges addressed in such largescale flight operations. We showcase results from recent field tests, including the autonomous launch, flight, and landing of 50 UAVs, which illuminate numerous operational lessons learned and generate rich multi-UAV datasets. We detail the design and open architecture of the testbed, which intentionally leverages low-cost and open-source components, aimed at promoting continued advances and alignment of multi-robot systems research and practice.

Increasing unmanned aerial vehicle (UAV) capabilities and decreasing costs have facilitated growing interest in the development of large, multi-UAV systems, or swarms. The constrained communications environments in which these swarms operate, however, have limited the development of behaviors that require a high degree of deliberative coordination. This work presents two algorithms that use a consensus-algorithm approach to reliably exchange information throughout large swarms as a means of facilitating swarm behavior coordination. Results from experiments conducted in simulation and live-fly exercises are presented and discussed.

Despite the recent flight control regulations, Unmanned Aerial Vehicles (UAVs) are still gaining popularity in civilian and military applications, as much as for personal use. Such emerging interest is pushing the development of effective collision avoidance systems. Such systems play a critical role UAVs operations especially in a crowded airspace setting. Because of cost and weight limitations associated with UAVs payload, camera based technologies are the de-facto choice for collision avoidance navigation systems. This requires multi-target detection and tracking algorithms from a video, which can be run on board efficiently. While there has been a great deal of research on object detection and tracking from a stationary camera, few have attempted to detect and track small UAVs from a moving camera. In this paper, we present a new approach to detect and track UAVs from a single camera mounted on a different UAV. Initially, we estimate background motions via a perspective transformation model and then identify distinctive points in the background subtracted image. We find spatio-temporal traits of each moving object through optical flow matching and then classify those candidate targets based on their motion patterns compared with the background. The performance is boosted through Kalman filter tracking. This results in temporal consistency among the candidate detections. The algorithm was validated on video datasets taken from a UAV. Results show that our algorithm can effectively detect and track small UAVs with limited computing resources.

In this paper we study the multi-robot deployment problem under hard temporal constraints. After proposing a model for this task, we consider the simplest deployment algorithm and we analyze the relationship between three fundamental parameters, the temporal deadline, the probability of success, and the number of robots. Because an exact analysis of even the simplest algorithm is computationally intractable, we derive an approximate bound leading to performance curves useful to answer design questions (how many robots are needed to get a certain performance guarantee?) or analysis questions (what is the probability of success given a certain deadline and number of robots?) Simulations show that the bounds are sharp and provide a useful tool to predict team deployment performance and tradeoffs.

This research explores the efficient and safe landing and recovery of a swarm of unmanned aerial vehicles (UAVs). The presented work involves the use of an overarching (centralized) airspace optimization model, formulated analytically as a network-based model with side constraints describing a time-expanded network model of the terminal airspace in which the UAVs navigate to one or more (possibly moving) landing zones. This model generates optimal paths in a centralized manner such that the UAVs are properly sequenced into the landing areas. The network-based model is “grown” using agent-based simulation with simple flocking rules. Relevant measures of performance include, e.g., the total time necessary to land the swarm. Extensive simulation studies and sensitivity analyses are conducted to demonstrate the relative effectiveness of the proposed approaches.

In this study, we explore the use of nondeterministic search trajectories to accomplish a two-fold mission of mobile robot search for a stationary target while avoiding counter-targeting by the adversary throughout the operation. We analyze the characteristics associated with a Levy distribution of search leg lengths to generate appropriate randomized search trajectories. We discuss the alteration of the probability distribution of the Levy search as a result of the method utilized to best address the presence of the bounded search area and confine the searcher within its boundaries. Through regression analysis of simulation results, we determine expressions for the coverage ratio evolution of the modified Levy search strategy and the distribution on time to target detection TD, from which we are able to calculate the expected time, E[TD], to detect the target uniformly distributed within the search area. We assert assumptions regarding the adversary's detection and tracking abilities to estimate the expected time, E[TC], required for it to counter target the searcher. From these two expected times, we construct a novel probabilistic mission performance metric that measures the likelihood that the searcher will detect the target before it is counter targeted itself.

This paper investigates the combined use of ocean models, such as idealized surface current flows, and search models, including expanding area and discrete myopic search methods, to improve the probability of detecting a near-surface, drifting object over time. Enhanced search effectiveness is facilitated by the use of robotic search agents, such as a tactical unmanned aerial vehicle (UAV), leveraging simulation methods to inform the search process. The presented work investigates the impact of using naïve vs. optimized search patterns on localizing a drifting object, including a surrogate ocean model using idealized flow with Weibull-distributed perturbations. Numerical studies and extensive analysis using different permutations of model parameters (including the relative speed of the drifting object, time late in the searcher's arrival to the search area, sensor sweep width, and duration of the search mission) identify the significant factors affecting the overall probability of detection. Such insights enable further explorations using empirical datasets for specific oceanographic regions of interest.

In this paper, we propose a formulation of the spatial search problem, where a mobile searching agent seeks to locate a stationary target in a given search region or declare that the target is absent. The objective is to minimize the expected time until this search decision of target's presence (and location) or absence is made. Bayesian update expressions for the integration of observations, including false-positive and false-negative detections, are derived to facilitate both theoretical and numerical analyses of various computationally efficient (semi-)adaptive search strategies. Closed-form expressions for the search decision evolution and analytic bounds on the expected time to decision are provided under assumptions on search environment and/or sensor characteristics. Simulation studies validate the probabilistic search formulation and comparatively demonstrate the effectiveness of the proposed search strategies.

We propose a novel framework to search for a static target using a multiscale representation. The algorithm we present is appropriate when the target detection sensor trades off accuracy versus covered area, e.g., when a UAV can fly and sense at different elevations. A structure based on quadtrees is used to propagate a posterior about the target location using a variable resolution representation that is dynamically refined in regions associated with higher probability of target presence. Probabilities are updated using a Bayesian approach accounting for erroneous sensor readings in the form of false positives and missed detections. The model we propose is coupled with a search and decision algorithm that determines where to sense next and with which accuracy. The search algorithm is based on an objective function accounting for both probability of detection and motion costs, thus aiming to minimize traveled distances while trying to localize the target. The paper is concluded with simulation results showing our approach outperforms commonly used methods based on uniform resolution grids.

We consider the problem of searching for an unknown number of static targets inside an assigned area. The search problem is tackled using Probabilisitic Quadtrees (PQ), a data structure we recently introduced. Probabilistic quadtrees allow for a variable resolution representation and naturally induce a search problem where the searcher needs to choose not only where to sense, but also the sensing resolution. Through a Bayesian approach accommodating faulty sensors returning both false positives and missed detections, a posterior distribution about the location of the targets is propagated during the search effort. In this paper we extend our previous findings by considering the problem of searching for an unknown number of targets. Moreover, we substitute our formerly used heuristic with an approach based on information gain and expected costs. Finally, we provide some convergence results showing that in the worst case our model provides the same results as uniform grids, thus guaranteeing that the representation we propose gracefully degrades towards a known model. Extensive simulation results substantiate the properties of the method we propose, and we also show that our variable resolution method outperforms traditional methods based on uniform resolution grids.

This paper presents an algorithmic framework for conducting search and identification missions using multiple heterogeneous agents. Dynamic objects of type ldquoneutralrdquo or ldquotargetrdquo move through a discretized environment. Probabilistic representation of the current level of situational awareness - knowledge or belief of object locations and identities - is updated with imperfect observations. Optimization of search is formulated as a mixed-integer program to maximize the expected number of targets found and solved efficiently in a receding horizon approach. The search effort is conducted in tandem with object identification and target interception tasks, and a method for assignment of these missions among agents is developed. The proposed framework is demonstrated in simulation studies, and an implementation of its decision support capabilities in a recent field experiment is reported.

Consider the task of searching a region for the presence or absence of a target using a team of multiple searchers. This paper formulates this search problem as a sequential probabilistic decision, which enables analysis and design of efficient and robust search control strategies. Imperfect detections of the target's possible locations are made by each search agent and shared with teammates. This information is used to update the evolving decision variable which represents the belief that the target is present in the region. The sequential decision-theoretic formulation presented in this paper provides an analytic framework to evaluate team search systems, as it includes a performance metric (time until decision), a measure of uncertainty (decision confidence thresholds) and imperfect information gathering (detection error). Strategies for cooperative search are evaluated in this context, and comparisons between homogeneous and hybrid search strategies are investigated in numerical studies.

This paper presents the search problem formulated as a decision problem, where the searcher decides whether the target is present in the search region, and if so, where it is located. Such decision-based search tasks are relevant to many research areas, including mobile robot missions, visual search and attention, and event detection in sensor networks. The effect of control strategies in search problems on decision-making quantities, namely time-to-decision, is investigated in this work. We present a Bayesian framework in which the objective is to improve the decision, rather than the sensing, using different control policies. Furthermore, derivations of closed-form expressions governing the evolution of the belief function are also presented. As this framework enables the study and comparison of the role of control for decision-making applications, the derived theoretical results provide greater insight into the sequential processing of decisions. Numerical studies are presented to verify and demonstrate these results

This paper presents a decentralized motion planning algorithm for the distributed sensing of a noisy dynamical process by multiple cooperating mobile sensor agents. This problem is motivated by localization and tracking tasks of dynamic targets. Our gradient-descent method is based on a cost function that measures the overall quality of sensing. We also investigate the role of imperfect communication between sensor agents in this framework, and examine the trade-offs in performance between sensing and communication. Simulations illustrate the basic characteristics of the algorithms

In this paper we characterize the impact of imperfect communication on the performance of a decentralized mobile sensor network. We first examine and demonstrate the trade-offs between communication and sensing objectives, by determining the optimal sensor configurations when introducing imperfect communication. We further illustrate the performance degradation caused by non-ideal communication links in a decentralized mobile sensor network. To address this, we propose a decentralized motion-planning algorithm that considers communication effects. The algorithm is a cross-layer design based on the proper interface of physical and application layers. Simulation results will show the performance improvement attained by utilizing this algorithm.

In this paper, we consider the scenario where many sensors co-operate to estimate a process. Only one sensor can take a measurement at any time step. We wish to come up with optimal sensor scheduling algorithms. The problem is motivated by the use of sonar range-finders used by the vehicles on the Caltech multi-vehicle wireless testbed. We see that this problem involves searching a tree in general and propose and analyze two strategies for pruning the tree to keep the computation limited. The first is a sliding window strategy motivated by the Viterbi algorithm, and the second one uses thresholding. We also study a technique that employs choosing the sensors randomly from a probability distribution which can then be optimized. The performance of the algorithms are illustrated with the help of numerical examples.

We examine the problem of distributed estimation when only one sensor can take a measurement per time step. We solve for the optimal recursive estimation algorithm when the sensor switching schedule is given. We then consider the effect of noise in communication channels. We also investigate the problem of determining an optimal sensor switching strategy. We see that this problem involves searching a tree in general and propose two strategies for pruning the tree to minimize the computation. The first is a sliding window strategy motivated by the Viterbi algorithm, and the second one uses thresholding. The performance of the algorithms is illustrated using numerical examples.