Teams of cooperating autonomous underwater vehicles (AUVs) rely on acoustic communication for coordination, yet this communication medium is constrained by limited range, multi-path effects, and low bandwidth. One way to address the uncertainty associated with acoustic communication is to learn the communication environment in real-time. We address the challenge of a team of robots building a map of the probability of communication success from one location to another in real-time. This is a decentralized classification problem – communication events are either successful or unsuccessful – where AUVs share a subset of their communication measurements to build the map. The main contribution of this work is a rigorously derived data sharing policy that selects measurements to be shared among AUVs. We experimentally validate our proposed sharing policy using real acoustic communication data collected from teams of Virginia Tech 690 AUVs, demonstrating its effectiveness in underwater environments.

We present the results of experiments performed using a team of small autonomous underwater vehicles (AUVs) to determine the location of an isobath. The primary contributions of this work are (1) the development of a novel objective function for level set estimation that utilizes a rigorous assessment of uncertainty, and (2) a description of the practical challenges and corresponding solutions needed to implement our approach in the field using a team of AUVs. We combine path planning techniques and an approach to decentralization from prior work that yields theoretical performance guarantees. Experimentation with a team of AUVs provides empirical evidence that the desirable performance guarantees can be preserved in practice even in the presence of limitations that commonly arise in underwater robotics, including slow and intermittent acoustic communications and limited computational resources.

Cooperating autonomous underwater vehicles (AUVs) often rely on acoustic communication to coordinate their actions effectively. However, the reliability of underwater acoustic communication decreases as the communication range between vehicles increases. Consequently, teams of cooperating AUVs typically make conservative assumptions about the maximum range at which they can communicate reliably. To address this limitation, we propose a novel approach that involves learning a map representing the probability of successful communication based on the locations of the transmitting and receiving vehicles. This probabilistic communication map accounts for factors such as the range between vehicles, environmental noise, and multi-path effects at a given location. In pursuit of this goal, we investigate the application of Gaussian process binary classification to generate the desired communication map. We specialize existing results to this specific binary classification problem and explore methods to incorporate uncertainty in vehicle location into the mapping process. Furthermore, we compare the prediction performance of the probability communication map generated using binary classification with that of a signal-to-noise ratio (SNR) communication map generated using Gaussian process regression. Our approach is experimentally validated using communication and navigation data collected during trials with a pair of Virginia Tech 690 AUVs.

We present the results of experiments performed using a small autonomous underwater vehicle to determine the location of an isobath within a bounded area. The primary contribution of this work is to implement and integrate several recent developments real-time planning for environmental map-ping, and to demonstrate their utility in a challenging practical example. We model the bathymetry within the operational area using a Gaussian process and propose a reward function that represents the task of mapping a desired isobath. As is common in applications where plans must be continually updated based on real-time sensor measurements, we adopt a receding horizon framework where the vehicle continually computes near-optimal paths. The sequence of paths does not, in general, inherit the optimality properties of each individual path. Our real-time planning implementation incorporates recent results that lead to performance guarantees for receding-horizon planning.

We consider the problem of decentralized multiagent environmental learning through maximizing the joint information gain among a team of agents. Inspired by subsea applications where bandwidth is severely limited, we explicitly consider the challenge of restricted communication between agents. The environment is modeled as a Gaussian process (GP), and the global information gain maximization problem in a GP is a set-valued optimization problem involving all agents' locally acquired data. We develop a decentralized method to solve it based on decomposition of information gain and exchange of limited subsets of data between agents. A key technical novelty of our approach is that we formulate the incentives for information exchange among agents as a submodular set optimization problem in terms of the log-determinant of their local covariance matrices. Numerical experiments on real-world data demonstrate the ability of our algorithm to explore trade-off between objectives. In particular, we demonstrate favorable performance on mapping problems where both decentralized information gathering and limited information exchange are essential.

We provide theoretical bounds on the worst case performance of the greedy algorithm in seeking to maximize a normalized, monotone, but not necessarily submodular ob-jective function under a simple partition matroid constraint. We also provide worst case bounds on the performance of the greedy algorithm in the case that limited information is available at each planning step. We specifically consider limited information as a result of unreliable communications during distributed execution of the greedy algorithm. We utilize notions of curvature for normalized, monotone set functions to develop the bounds provided in this work. To demonstrate the value of the bounds provided in this work, we analyze a variant of the benefit of search objective function and show, using real-world data collected by an autonomous underwater vehicle, that theoretical approximation guarantees are achieved despite non-submodularity of the objective function.

We seek to rigorously evaluate the benefit of using a few beams rather than a single beam for a low-cost obstacle avoidance sonar for small AUVs. For a small low-cost AUV, the complexity, cost, and volume required for a multi-beam forward looking sonar are prohibitive. In contrast, a single-beam system is relatively easy to integrate into a small AUV, but does not provide the performance of a multi-beam solution. To better understand this trade-off, we seek to rigorously quantify the improvement with respect to obstacle avoidance performance of adding just a few beams to a single-beam forward looking sonar relative to the performance of the single-beam system. Our work fundamentally supports the goal of using small low-cost AUV systems in cluttered and unstructured environments. Specifically, we investigate the benefit of incorporating a port and starboard beam to a single-beam sonar system for collision avoidance. A methodology for collision avoidance is developed to obtain a fair comparison between a single-beam and multi-beam system, explicitly incorporating the geometry of the beam patterns from forward-looking sonars with large beam angles, and simulated using a high-fidelity representation of acoustic signal propagation.

We present a multi-agent approach to receding horizon path planning that utilizes terminal costs. We show that the value of the receding horizon paths produced using the proposed methods have a guaranteed lower bound that can be determined using any readily-available, naive solution. We present a modified sequentially allocated optimal path planner with terminal costs that is guaranteed to satisfy the assumptions required to provide a guaranteed lower bound. We utilize a slightly modified version of the Decentralized Monte Carlo Tree Search algorithm to solve for near-optimal paths within a short planning horizon with an appended terminal cost to demonstrate the flexibility of the proposed method. We compare these receding horizon methods that incorporate a terminal cost to related receding horizon methods that do not incorporate a terminal cost. Our approach is developed specifically for multiple agents engaged in search, but can be easily adapted for other information gathering applications.

In this paper, we propose two decentralized approximate algorithms for nested Gaussian processes in multi-robot systems. The distributed implementation is achieved with iterative and consensus methods that facilitate local computations at the expense of inter-robot communications. Moreover, we propose a covariance-based nearest neighbor robot selection strategy that enables a subset of agents to perform predictions. In addition, both algorithms are proved to be consistent. Empirical evaluations with real data illustrate the efficiency of the proposed algorithms.

Gaussian processes (GPs) are a well-known nonparametric Bayesian inference technique, but they suffer from scalability problems for large sample sizes, and their performance can degrade for non-stationary or spatially heterogeneous data. In this work, we seek to overcome these issues through (i) employing variational free energy approximations of GPs operating in tandem with online expectation propagation steps; and (ii) introducing a local splitting step which instantiates a new GP whenever the posterior distribution changes significantly as quantified by the Wasserstein metric over posterior distributions. Over time, then, this yields an ensemble of sparse GPs which may be updated incrementally, and adapts to locality, heterogeneity, and non-stationarity in training data. We provide a 1-dimensional example to illustrate the motivation behind our approach, and compare the performance of our approach to other Gaussian process methods across various data sets, which often achieves competitive, if not superior predictive performance, relative to other locality-based GP regression methods in which hyperparameters are learned in an online manner.

This paper presents a novel multi-level generative chaotic Recurrent Neural Network (RNN) for image inpainting. This technique utilizes a general framework with multiple chaotic RNN that makes learning the image prior from a single corrupted image more robust and efficient. The proposed network utilizes a randomly-initialized process for parameterization, along with a unique quad-directional encoder structure, chaotic state transition, and adaptive importance for multi-level RNN updating. The efficacy of the approach has been validated through multiple experiments. In spite of a much lower computational load, quantitative comparisons reveal that the proposed approach exceeds the performance of several image-restoration benchmarks.

The computational difficulty of planning search paths that seek to maximize a general deterministic value function increases dramatically as desired path lengths increase. Mobile search agents with limited computational resources often utilize receding horizon methods to address the path planning problem. Unfortunately, receding horizon planners may perform poorly due to myopic planning horizons. We provide methods of incorporating terminal costs in the construction of receding horizon paths that provide a theoretical lower bound on the performance of the search paths produced. The results presented in this paper are of particular value in subsea search applications. We present results from simulated subsea search missions that use real-world data acquired by an autonomous underwater vehicle during a subsea survey of Boston Harbor.

In the context of a multi-agent system that uses a Gaussian process to estimate a spatial field of interest, we propose an approach that enables an agent to reduce the amount of data it shares with other agents. The main idea of the strategy is to rigorously assign a novelty metric to each measurement as it is collected, and only measurements that are sufficiently novel are communicated. We consider the ideal scenario where an agent can instantly share novel measurements, and we also consider the more practical scenario in which communication suffers from low bandwidth and is range-limited. For this scenario, an agent can only broadcast an informative subset of the novel measurements when the agent encounters other agents. We explore three different informative criteria for subset selection, namely entropy, mutual information, and a new criterion that reflects the value of a measurement. We apply our approach to three real-world datasets relevant to robotic mapping. The empirical findings show that an agent can reduce the amount of communicated measurements by two orders of magnitude and that the new criterion for subset selection yields superior predictive performance relative to entropy and mutual information.

We present a novel method of using terminal costs in the construction of a receding horizon search path. We prove that the proposed method of constructing search paths provides a theoretical lower bound on the performance of the search path. Our result can be interpreted as ensuring that the receding horizon path performs no worse in expectation than a given sub-optimal search path. This result is especially practical for subsea applications where, due to use of side-scan sonar in search applications, search paths typically consist of parallel straight lines. Thus for subsea search applications, our approach ensures that expected performance is no worse than the usual subsea search path, and it might be much better. We demonstrate the efficacy of the proposed method by planning search paths in simulation using real-world data that was acquired by an autonomous underwater vehicle during a subsea survey of Boston Harbor.

We present an anytime Monte Carlo tree search (MCTS) algorithm to generate real-time, near-optimal search paths in large subsea environments. The MCTS planner continuously builds a tree of the search space until either the allowed time per move is reached or the budget constraint for the search mission is met. In order to improve the performance of the MCTS planner, we propose a novel heuristic action selection policy to determine the value of a leaf node. The proposed heuristic is tailored to problems where making a turn incurs a higher cost than moving straight, such as the case on autonomous underwater vehicles. Through extensive simulations, we show that our heuristic yields a significant performance improvement over a lawnmover path planner - a commonly employed approach in subsea search applications - and over a simple MCTS planner where actions are selected uniformly at random. In our numerical illustrations, we use a real data set abstracted from sonar measurements acquired from the Boston Harbor.

We address the challenge of computing search paths in real-time for subsea applications where the goal is to locate an unknown number of targets on the seafloor. Our approach maximizes a formal definition of search effectiveness given finite search effort. We account for false positive measurements and variation in the performance of the search sensor due to geographic variation of the seafloor. We compare near-optimal search paths that can be computed in real-time with optimal search paths for which real-time computation is infeasible. We show how sonar data acquired for locating targets at a specific location can also be used to characterize the performance of the search sonar at that location. Our approach is illustrated with numerical experiments where search paths are planned using sonar data previously acquired from Boston Harbor.

We introduce a novel approach to controlling the motion of a team of agents so that they jointly minimize a cost function utilizing Bayes risk. We use a particle-based approach and approximations that allow us to express the optimization problem as a mixed-integer linear program. We illustrate this approach with an area protection problem in which a team of mobile agents must intercept mobile targets before the targets enter a specified area. Bayes risk is a useful measure of performance for applications where agents must perform a classification task. By minimizing Bayes risk, agents are able to explicitly account for the cost of incorrect classification. In our application, a team of mobile agents must classify potential mobile targets as threat or safe based on the likelihood the targets will enter the specified area. The agents must also maneuver to intercept targets that are classified as threat.

We introduce a novel task that arises in underwater search and inspection. In this task, an underwater vehicle must re-acquire and identify clusters of discrete objects. The challenge is to generate an efficient path for the vehicle given a probabilistic description of potential target locations. We propose an algorithm that generates an efficient path and show that the algorithm is superior to standard approaches.

In this paper we propose a framework for optimal coordinated sensor motion using the Bayes risk. For the purpose of illustration, we address an intrusion detection problem, which is cast as a binary hypothesis testing problem. We consider two distinct hypotheses or classes for moving targets. They are classified as threat or safe, depending on the future target trajectory entering or not entering a specified area of interest. The principal contribution of our work is a formal analysis, under various simplifying assumptions, of how Bayes risk can used to generate sensor motion control laws. We propose the use of the extended Kalman filter (EKF) state estimate and covariance as the summary statistic for the sensor observations. Thus the novelty of our approach lies in combining the classification and estimation problems formally, leading to an optimal coordinated sensor motion control algorithm.

In this paper we present an approach to solving a stochastic multi-target interception problem. In the multi-target interception problem, a team of mobile sensors is tasked with intercepting a set of potential targets to reduce appropriately assigned damage cost. Our principal contribution is to express a stochastic version of the problem with a generalized cost as a mixed-integer linear program so that optimal sensor motion can be computed efficiently. Indeed, our optimization program for the stochastic problem has similar computational costs as the optimization program for the corresponding deterministic problem. Our solution presumes that the system can be approximated by linear dynamics and Gaussian noise, with Gaussian localization uncertainty.

We present an approach to planning dynamically feasible vehicle trajectories for applications where the vehicle operates in very large environments and for which a kinematic model is poor approximation of the vehicle's dynamics. Using a standard receding horizon control framework, we compute a sequence of short-horizon optimal trajectories that can be computed in real-time. We also compute a global path that is updated only occasionally. Because the environment is very large, we presume that the global path cannot be updated in real-time. By selecting a terminal state cost in the finite-time optimal control problem that approximates the cost-to-go, we are able to propose a formal condition under which the sequence of dynamically feasible trajectories is guaranteed to converge to a desired goal location. Moreover, we show that the global path need be updated only when the formal condition is not satisfied, which allows us to delay update of the global path.

We address the minimal risk motion planning problem in a two dimensional environment in the presence of both moving and static obstacles. Our approach is inspired by recent results due to Vladimirsky in which path planning on time-varying maps is addressed using a new level-set approach, and for which computational costs are remarkably low. Toward practical implementation of these results for path planning in unstructured environments, we develop a receding-horizon formulation in which path planning for moving and static obstacles is addressed locally, while path planning for static obstacles is addressed globally. This formulation reduces the overall computational burden of path planning and makes it suitable for very large domains. The result is a suboptimal receding horizon planner and a matching condition that connects local planning with global planning. We present a rigorous analysis from which convergence to a desired endpoint is guaranteed.

For an autonomous vehicle navigating in a static environment for which an a priori map is inaccurate, we propose a hybrid receding horizon control method to determine optimal routes when new obstacles are detected. The hybrid method uses the level sets of the solution to either a global or local Eikonal equation in the formulation of the receding horizon control problem. Whenever an obstacle is detected along the path of the autonomous vehicle, a solution to a local Eikonal equation is used to determine whether a new, global Eikonal equation must be solved for use in the receding horizon optimization problem. The decision to select a new level set solution is made based on certain matching conditions that guarantee the optimality of the path. The selection of a global or local solution to the Eikonal equation induces a hybrid system structure in the control formulation. We rigorously prove sufficient conditions that guarantees that the vehicle will converge to the goal as long as the goal is accessible. In the end, simulation results are discussed.

We propose an efficient method for updating a path that was computed using level-set methods. Our approach is suitable for autonomous vehicles navigating in a static environment for which an a priori map of the environment is inaccurate. When the autonomous vehicle detects a new obstacle, our algorithm replans an optimal route without recomputing the entire path. Computational costs when planning paths with level set methods are due to creation of the level set. Once the level set has been computed, the optimal path is simply gradient descent down the level set. Our approach is based on formal analysis of how the level set changes when a new obstacle is detected. We show that in many practical cases, only a small portion of the level set needs to be re-computed when a new obstacle is detected. Simulation examples are presented to validate the effectiveness of the proposed method.

Towards the goal of achieving truly autonomous navigation for a surface vehicle in maritime environments, a critical task is to detect surrounding obstacles such as the shore, docks, and other boats. In this paper, we demonstrate a real-time vision-based mapping system which detects and localizes stationary obstacles using a single omnidirectional camera and navigational sensors (GPS and gyro). The main challenge of this work is to make mapping robust to a large number of outliers, which stem from waves and specular reflections on the surface of the water. To address this problem, a two-step robust outlier rejection method is proposed. Experimental results obtained in unstructured large-scale environments are presented and validated using topographic maps.

In this paper we present a vector-based 3D localization formula for a paracatadioptric omnistereo system. Based on vector representation, the performance of this stereo system is analyzed numerically, including the maximum detectable range and the uncertainty of 3D localization, with respect to the flexible stereo configuration of the system, positions of scene points, as well as errors in correspondence matching and errors in stereo configuration. The results of performance analysis are used to guide the trajectory of an autonomous surface vehicle (ASV), which is equipped with a paracatadioptric omnidirectional camera, in a map building application.

Autonomous operation by a surface vehicle in a maritime setting requires that the surface vehicle detects non-water objects, including shoreline, hazards to navigation, and other moving vessels. In order to assess the utility of an omnidirectional camera for detecting and localizing non- water objects, we rigorously investigate observability of both stationary and moving features. For stationary features, we find that all but a small subset of the features are observable. For moving features, we show that an important class of feature and ASV trajectories are not observable.

Environmental tracking and formation control for a platoon of autonomous vehicles is studied. Vehicles travel through an environment that possesses a measurable scalar field, with the goal of moving in a desired spatial pattern about a desired constant value contour in the field. Each vehicle measures the local value of the field along its trajectory and shares information about its measurements and trajectory with other vehicles in the platoon. Platoon control involves estimation of a virtual leader trajectory coinciding with the target contour and about which vehicles form. Two approaches to leader estimation are considered. The first involves the synthesis of a common leader trajectory, whereas the second involves decentralized estimation of the leader trajectory by individual vehicles. Under the second approach, platoon control is posed as a two-level consensus problem, where vehicles reach agreement on the leader trajectory at one level and reach formation about the leader at the other level. The decentralized approach is effective even when communication among vehicles is limited. A target application involving an underwater vehicle platoon is considered

An underwater navigation algorithm is considered that enables an underwater vehicle to compute its trajectory and unknown currents by utilizing range measurements from a single known location. By assessing local observability about potential vehicle trajectories, we characterize those trajectories that cannot be asymptotically estimated. Analysis is also presented to clarify the relationship between finite time observability, a theme of this work, and existence of an observer with exponentially decaying observation dynamics. The navigation algorithm is illustrated using a hardware experiment.

An approach to real-time trajectory generation for platoons of autonomous vehicles is developed from well-known control techniques for redundant robotic manipulators. The partially decentralized structure of this approach permits each vehicle to independently compute its trajectory in real-time using only locally generated information and low-bandwidth feedback generated by a system exogenous to the platoon. Our work is motivated by applications for which communications bandwidth is severely limited, such for platoons of autonomous underwater vehicles. The communication requirements for our trajectory generation approach are independent of the number of vehicles in the platoon, enabling platoons composed of a large number of vehicles to be coordinated despite limited communication bandwidth.

Navigation technology is considered that enables an underwater vehicle to compute its trajectory in real-time by utilizing range measurements from a single known location. This concept is especially attractive for small underwater vehicles where more traditional navigation technology is prohibitive due to volume constraints. By assessing local observability of the underwater vehicle and available measurements about potential vehicle trajectories, we explicitly characterize those trajectories that can be asymptotically estimated. It is shown that all but a small class of trajectories can be estimated.

Platoons of cooperating autonomous underwater vehicles have the potential to contribute significantly to scientific investigations in the marine environment. Platoons of vehicles can survey large areas, adaptively track and measure time-varying processes such as tidal fronts and algal blooms, and they are robust to single-point failures. We have developed a prototype miniature low-cost autonomous underwater vehicle to address the platform requirements of these missions. The vehicle is designed as a test-bed for the development of distributed control and estimation algorithms, and for experiments in advanced navigation and control.

An efficient method for synthesis of decentralized controllers for a platoon of autonomous vehicles is presented. Though our results are applicable to land, sea, or air vehicles, our motivation arises from the requirements of underwater vehicles. Difficulties arising from communications bandwidth limitations imposed underwater are addressed by assuming a specific network topology that requires very little communication. While decentralized control synthesis problems are considered to be NP-hard in general, we show that decentralized controllers can be synthesized for the network topology considered using standard control design techniques along with a two-loop design methodology.

Decentralized control of multiple mobile robots for cooperative tasks often requires not only environmental sensing but communication among the robot subsystems. In this work, we develop observer-based methods for characterizing the implicit and explicit communications required for a swarm of robots to successfully achieve classes of control objectives.

Coordinated motion of a group of mobile robots bearing a common load is investigated. By extending the results of research with similar multi-robot material handling systems, a supervisory control is derived that provides an optimal distribution of work among the robots while accounting for the robots nonholonomic constraints.>