From archaeology to the inspection of subsea structures, underwater mapping has become critical to many applications. Because of the balanced trade-off between range and resolution, multibeam sonars are often used as the primary sensor in underwater mapping platforms. These sonars output an image representing the intensity of the received acoustic echos over space, which must be classified into free and occupied regions before range measurements are determined and spatially registered. Most classifiers found in the underwater mapping literature use local thresholding techniques, which are highly sensitive to noise, outliers, and sonar artifacts typically found in these images. In this paper we present an overview of some of the techniques developed in the scope of our work on sonar-based underwater mapping, with the aim of improving map accuracy through better segmentation performance. We also provide experimental results using data collected with a DIDSON imaging sonar that show that these techniques improve both segmentation accuracy and robustness to outliers.

We propose a submap-based technique for mapping of underwater structures with complex geometries. Our approach relies on the use of probabilistic volumetric techniques to create submaps from multibeam sonar scans, as these offer increased outlier robustness. Special attention is paid to the problem of denoising/enhancing sonar data. Pairwise submap alignment constraints are used in a factor graph framework to correct for navigation drift and improve map accuracy. We provide experimental results obtained from the inspection of the running gear and bulbous bow of a 600-foot, Wright-class supply ship.

Multi-vehicle operations in the ocean are increasingly attractive as more vehicles become commercially available, however acoustics still defines the main practical channel for long-range wireless communication underwater. Long transmission times, scheduling delays and packet losses remain obstacles to implementing real-time multi-vehicle cooperative control for marine vehicles. We present a control system for dynamic pursuit with multiple vehicles exchanging time-difference-of-arrival (TDOA) measurements via underwater acoustic communications. Using data from field experiments conducted with autonomous surface vehicles, we show that a decentralized controller can track fast-moving targets and formation changes, leveraging partial information updates and decreased effective cycle times. As a comparison, we show results for trials conducted with one similar but centralized control scheme.

Without access to GPS and high-quality visual landmarks, many autonomous underwater vehicles (AUV) face a fundamental navigation vs. cost tradeoff: advanced navigation systems that might include an INS, Doppler velocity, or long-baseline acoustics are expensive. Supporting low-cost operations, this work focuses on collaborative positioning for a team of AUV's, given a bathymetric terrain map, and only an altimeter and acoustic modem on each vehicle. The joint localization is performed via decentralized particle filtering, where we extend the usual measurement model to allow received information to modulate the importance function. We investigate the impact on performance of sensor noise, communication interval and number of vehicles. Results are shown for bathymetry maps near St. John's Island, Singapore, and for the Charles River Basin, Boston. In the second case, we ran our algorithm with physical measurements from actual vehicles executing trajectories.

We apply the stationary multi-armed bandit (MAB) formalism to the problem of maximizing underwater acoustic data transmission through adaptive positioning of a mobile relay. Shallow-water environments, in particular, show complex and variable performance across physical space. This is a classic exploration vs. exploitation scenario, since choosing to visit new sites to learn their properties may be disadvantageous for cumulative data transmission if a better-performing site is already known with high confidence. Normal Gittins indices define a rule by which an optimal relay position can be chosen at each decision epoch, without assuming prior information and while pursuing the overall goal of maximizing total data transmission. We present results from shallow-water field experiments conducted with autonomous surface vehicles and acoustic modems transmitting data through a one-way, two-hop network in the Charles River Basin, Boston.

Marine robots are an increasingly attractive means for observing and monitoring in the ocean, but underwater acoustic communication (“acomms”) remains a major challenge, especially for real-time control. Packet loss occurs widely, bit rates are low, and there are significant delays. We consider here strategies for feedback control with acomms links in either the sensor-controller channel, or the controller-actuator channel. On the controller-actuator side we implement sparse packetized predictive control (S-PPC), which simultaneously addresses packet-loss and the data rate limit. For the sensor-controller channel we study a modified information filter (MIF) in a Linear Quadratic Gaussian (LQG) control scheme. Field experiments were carried out with both approaches, regulating crosstrack error in a robotic kayak using acomms. Outcomes with both the S-PPC and MIF LQG confirm that good performance is achievable.

Underwater acoustic communication channels display highly variable and stochastic performance, especially in multipath-limited shallow-water and harbor environments. A mobile acoustic node can, however, learn the channel's properties as it moves about. Maximizing the cumulative data transmission through adaptive node positioning is a clean exploitation vs. exploration scenario because learning about poorly characterized locations must be balanced against exploiting known ones. While this problem is well described with the stochastic multi-armed bandit formalism, the classical assumption of costless switching is untenable in the field, where slow-moving vehicles often cover large distances. We present a heuristic adaptation to the MAB Gittins index rule with limited policy enumeration to account for switching costs, and describe field experiments conducted in the Charles River (Boston MA). The field data establish that the MAB and its switching cost extension are tractable in this application, and that performance is consistently superior to that of ϵ-greedy policies.

We make two contributions toward integrated monitoring over large spatial scales, with multiple collaborating vehicles. Our focus is dynamic ocean features such as fronts and plumes. To support strong networked-control designs, we first develop a clean linear time-invariant framework for tracking features, that directly couples the global structure of the process to vehicle positioning. To address the packet loss inherent in underwater acoustic communications, we then extend the synthesis technique of Imer et al. [1] to the case where measurements and control commands suffer loss with differing statistics among the multiple channels. Simulations show that the integrated feedback system achieves good performance in front tracking.

We discuss the problem of inspecting an underwater structure, such as a submerged ship hull, with an autonomous underwater vehicle (AUV). In such scenarios, the goal is to construct an accurate 3D model of the structure and to detect any anomalies (e.g., foreign objects or deformations). We propose a method for constructing 3D meshes from sonar-derived point clouds that provides watertight surfaces, and we introduce uncertainty modeling through non-parametric Bayesian regression. Uncertainty modeling provides novel cost functions for planning the path of the AUV to minimize a metric of inspection performance. We draw connections between the resulting cost functions and submodular optimization, which provides insight into the formal properties of active perception problems. In addition, we present experimental trials that utilize profiling sonar data from ship hull inspection.

We present a hybrid algorithm that plans feasible paths for 100% sensor coverage of complex 3D structures. The structures to be inspected are segmented to isolate planar areas, and back-and-forth sweep paths are generated to view as much of these planar areas as possible while avoiding collision. A randomized planning procedure fills in the remaining gaps in coverage. The problem of selecting an order to traverse the elements of the inspection is solved by reduction to the traveling salesman problem. We present results of the planning algorithm for an autonomous underwater vehicle inspecting the in-water portion of a ship hull. The randomized configurations succeed in observing confined and occluded areas, while the 2D sweep paths succeed in covering the open areas.

We examine the problem of utilizing an autonomous underwater vehicle (AUV) to collect data from an underwater sensor network. The sensors in the network are equipped with acoustic modems that provide noisy, range-limited communication. The AUV must plan a path that maximizes the information collected while minimizing travel time or fuel expenditure. We propose AUV path planning methods that extend algorithms for variants of the Traveling Salesperson Problem (TSP). While executing a path, the AUV can improve performance by communicating with multiple nodes in the network at once. Such multi-node communication requires a scheduling protocol that is robust to channel variations and interference. To this end, we examine two multiple access protocols for the underwater data collection scenario, one based on deterministic access and another based on random access. We compare the proposed algorithms to baseline strategies through simulated experiments that utilize models derived from experimental test data. Our results demonstrate that properly designed communication models and scheduling protocols are essential for choosing the appropriate path planning algorithms for data collection.

Conventional methods for rotation angle estimation are not very robust to variations in object shape or intensity. However in real object recognition scenarios like in underwater sonar images, the object seldom retains the same appearance in different test cases. Object representation using Zernike moments allows to capture these variabilities in a way that makes it robust in the context of rotation angle estimation. This paper presents a novel way to exploit the phase information of Zernike moments to infer the object orientation. This is achieved via a compact directional representation that describes the variation in object shape along different directions. Results yielded on the DIDSON sonar imageset collected by CSAIL at MIT show that the method can robustly infer the relative orientation between objects.

A new algorithm for solving multi-goal planning problems in the presence of obstacles is introduced. We extend ant colony optimization (ACO) from its well-known application, the traveling salesman problem (TSP), to that of multi-goal feasible path planning for inspection and surveillance applications. Specifically, the ant colony framework is combined with a sampling-based point-to-point planning algorithm; this is compared with two successful sampling-based multi-goal planning algorithms in an obstacle-filled two-dimensional environment. Total mission time, a function of computational cost and the duration of the planned mission, is used as a basis for comparison. In our application of interest, autonomous underwater inspections, the ACO algorithm is found to be the best-equipped for planning in minimum mission time, offering an interior point in the tradeoff between computational complexity and optimality.

This paper considers mission design strategies for mobile robots whose task is to perform spatial sampling of a static environmental field, in the framework of compressive sensing. According to this theory, we can reconstruct compressible fields using O(log n) nonadaptive measurements (where n is the number of sites of the spatial domain), in a basis that is "in coherent" to the representation basis [1]; random uncorrelated measurements satisfy this incoherence requirement. Because an autonomous vehicle is kinematically constrained and has finite energy and communication resources, it is an open question how to best design missions for CS reconstruction. We compare a two-dimensional random walk, a TSP approximation to pass through random points, and a randomized boustrophedon (lawnmower) strategy. Not unexpectedly, all three approaches can yield comparable reconstruction performance if the planning horizons are long enough; if planning occurs only over short time scales, the random walk will have an advantage.

We have developed an underwater vehicle that offers significant performance improvements over existing sub sea elevators. Our Vertical Glider Robot falls under its own weight to a precise location on the seafloor, employing streamlining, active steering, and basic navigation instrumentation. We examine typical at-sea mission requirements, mention several key governing parameters, and outline our design approach. We then describe a prototype device, and present results from model-scale experiments.

We define a class of Laplacians for multicommodity, undirected flow networks, and bound their smallest nonzero eigenvalues with a generalization of the sparsest cut.

This paper presents a simultaneous localisation and mapping (SLAM) algorithm implemented on an autonomous sea kayak with a commercial off-the-shelf X-band marine radar mounted. The Autonomous Surface Craft (ASC) was driven in an off-shore test site in Singapore's southern Selat Puah marine environment. Data from the radar, GPS and an inexpensive single-axis gyro data were logged by an on-board processing unit as the ASC traversed the environment, which comprised geographical and surface vessel landmarks. An automated feature extraction routine is presented, based on a probabilistic landmark detector, followed by a clustering and centroid approximation approach. With restrictive feature modeling, and a lack of vehicle control input information, it is demonstrated that via the novel RB-PHD-SLAM Filter, useful results can be obtained, despite an actively rolling and pitching ASC on the sea surface. In addition, the merits of investigating ASC SLAM are demonstrated, particularly with respect to the map estimation, obstacle avoidance and target tracking problems. Despite the presence of GPS and gyro data, heading information on such small ASC's is greatly compromised which induces large sensing error, further accentuate by the large range of the radar sensor. This work is a step towards realising an ASC capable of performing environmental or security surveillance and reporting a real-time active awareness of the above-water scene.

We introduce an algorithm to achieve complete sensor coverage of complex, three-dimensional structures surveyed by an autonomous agent with multiple degrees of freedom. Motivated by the application of an ocean vehicle performing an autonomous ship hull inspection, we consider a planning problem for a fully-actuated, six degree-of-freedom hovering AUV using a bathymetry sonar to inspect the complex structures underneath a ship hull. We consider a discrete model of the structure to be inspected, requiring only that the model be provided in the form of a closed triangular mesh. A dense graph of feasible paths is constructed in the robot's configuration space until the set of edges in the graph allows complete coverage of the structure. Then, we approximate the minimum-cost closed walk along the graph which observes 100% of the structure. We emphasize the embedding of observations within the edges of the graph as a means of utilizing all available sensor data in planning the inspection.

In this paper we address the problem of drift-free navigation for underwater vehicles performing harbor surveillance and ship hull inspection. Maintaining accurate localization for the duration of a mission is important for a variety of tasks, such as planning the vehicle trajectory and ensuring coverage of the area to be inspected. Our approach only uses onboard sensors in a simultaneous localization and mapping setting and removes the need for any external infrastructure like acoustic beacons. We extract dense features from a forward-looking imaging sonar and apply pair-wise registration between sonar frames. The registrations are combined with onboard velocity, attitude and acceleration sensors to obtain an improved estimate of the vehicle trajectory. We show results from several experiments that demonstrate drift-free navigation in various underwater environments.

Path planning algorithms that incorporate risk and uncertainty need to be able to predict the evolution of path-following error statistics for each candidate plan. We present an analytic method to predict the evolving error statistics of a holonomic vehicle following a reference trajectory in a planar environment. This method is faster than integrating the plant through time or performing a Monte Carlo simulation. It can be applied to systems with external Gaussian disturbances, and it can be extended to handle plant uncertainty through numerical quadrature techniques.

Our aim is to explore the fundamental stability issues of a robotic vehicle carrying out localization, mapping, and feedback control in a perturbation-filled environment. Motivated by the application of an ocean vehicle performing an autonomous ship hull inspection, our planar vehicle model performs localization using point features from a given map. Cases in which the agent must update the map are also considered. The stability of the controller and estimator duo is investigated using a pair of theorems requiring boundedness and convergence of the transition matrix Euclidean norm. These theorems yield a stability test for the feedback controller. Perturbations are then considered using a theorem on the convergence on the perturbed system transition matrix, yielding a robustness test for the estimator. Together, these tests form a set of tools which can be used in planning and evaluating the robustness of marine vehicle survey trajectories, which is demonstrated through experiment.

By combining a low-order model of forecast errors, the extended Kalman filter, and classical continuous optimization, we develop an integrated methodology for planning mobile sensor paths to sample continuous fields. Agent trajectories are developed that specifically take into account the fact that data collected will be used for near real-time assimilation with large predictive models. This aspect of the problem has significant implications because the trajectories generated are very different from those which do not take the assimilation step into account, and their performance in controlling error is notably better.

The position control of agents having double-integrator dynamic response, with explicit dependence on an estimator that simultaneously reconstructs agent states and refines a feature map, is considered. We show that under broad conditions the phase and gain margins of an equivalent control system based on absolute navigation sensors can be significantly eroded when the dynamic map is used. The closed-loop bandwidth achieved depends strongly on the bandwidth of the filter, which is in turn dictated by the ratio of process to sensor noise, on the control gains, and on the arrangement of features being tracked. The findings are relevant to the integration of SLAM algorithms in high-performance positioning of mobile agents. A specific example is the case undersea robots working near large structures, where traditional navigation systems may not be practical.

Many important missions for autonomous underwater vehicles (AUVs), such as undersea inspection of ship hulls, require integrated navigation, control, and motion planning in complex, 3D environments. This paper describes a SLAM implementation using forward-looking sonar (FLS) data from a highly maneuverable, hovering AUV performing a ship hull inspection mission. The exactly sparse extended information filter (ESEIF) algorithm is applied to perform SLAM based upon features manually selected within FLS images. The results demonstrate the ability to effectively map a ship hull in a challenging marine environment. This provides a foundation for future work in which real-time SLAM will be integrated with motion planning and control to achieve autonomous coverage of a complete ship hull.

Point stabilization of an underactuated vehicle is most often accomplished using a periodic time-varying control law, resulting in oscillatory trajectories. We present a two-stage algorithm that achieves point stabilization without oscillatory behavior. A low-level controller regulates as many outputs as available control inputs. The unregulated states are generally nonzero when the regulated states have converged, but for certain initial conditions the vehicle arrives at the origin of the state space using only the low-level controller. This set of initial conditions forms a manifold in the state space. A separate Lyapunov-based manifold convergence controller drives the vehicle states to this manifold so that the low-level controller can bring the vehicle to the origin. We provide experimental results of this two-stage algorithm applied to a 1.25-meter ship model.