We present a scalable combined localization infrastructure deployment and task planning algorithm for underwater assembly. Infrastructure is autonomously modified to suit the needs of manipulation tasks based on an uncertainty model on the infrastructure’s positional accuracy. Our uncertainty model can be combined with the noise characteristics from multiple sensors. For the task planning problem, we propose a layer-based clustering approach that completes the manipulation tasks one cluster at a time. We employ movable visual fiducial markers as infrastructure and an autonomous underwater vehicle (AUV) for manipulation tasks. The proposed task planning algorithm is computationally simple, and we implement it on AUV without any offline computation requirements. Combined hardware experiments and simulations over large datasets show that the proposed technique is scalable to large areas.

The optical effects that are observed in underwater imagery are more complex than those in-air. This is partially because we enclose most underwater cameras in a watertight enclosure, such as a hemispheric dome window. We then observe optical issues including the distortion effects of the lens, e.g., wide-angle field-of-view (FOV), the refractive effects at the enclosure (water-acrylic and acrylic-air) interfaces, and offset effects of a non-centered camera with respect to the dome. In this paper, we present an N-Sphere (NS) and Shifted N-Sphere (S-NS) camera models, tailored to these cameras and lenses mounted in water-tight dome enclosures. The proposed camera models treat each layer of effects as a ‘sphere’ that a 3D point will project on. Furthermore, the S-NS model includes additional parameters to address the camera offset variability. The versatility of the NS model makes it applicable to various lenses, as validated with fisheye (FOV >120°) and wide-FOV (FOV ≈ 120°). We validated our models with different in-water calibration sequences, lenses, and housing setups, as well as with comparisons with other state-of-the-art camera models. Additionally, we demonstrated the performance of our proposed models in an example stereo-based visual odometry application. The low computational load of the proposed models makes it ideal for integrating in real-time visual navigation and reconstruction frameworks. We provide full math derivations of the proposed models as well as example C++ header files1for easy incorporation in independent projects.

We present the first free-floating autonomous underwater construction system capable of using active bal-lasting to transport cement building blocks efficiently. It is the first free-floating autonomous construction robot to use a paired set of resources: compressed air for buoyancy and a battery for thrusters. In construction trials, our system built structures of up to 12 components and weighing up to 100 Kg (75 Kg in water). Our system achieves this performance by combining a novel one-degree-of-freedom manipulator, a novel two-component cement block construction system that corrects errors in placement, and a simple active ballasting system combined with compliant placement and grasp behaviors. The passive error correcting components of the system minimize the required complexity in sensing and control. We also explore the problem of buoyancy allocation for building structures at scale by defining a convex program which allocates buoyancy to minimize the predicted energy cost for transporting blocks.

Locating underwater robots is fundamental for enabling important underwater applications. The current mainstream method requires a physical infrastructure with relays on the water surface, which is largely ad-hoc, introduces a significant logistical overhead, and entails limited scalability. Our work, Sunflower, presents the first demonstration of wireless, 3D localization across the air-water interface - eliminating the need for additional infrastructure on the water surface. Specifically, we propose a laser-based sensing system to enable aerial drones to directly locate underwater robots. The Sunflower system consists of a queen and a worker component on a drone and each tracked underwater robot, respectively. To achieve robust sensing, key system elements include (1) a pinhole-based sensing mechanism to address the sensing skew at air-water boundary and determine the incident angle on the worker, (2) a novel optical-fiber sensing ring to sense weak retroreflected light, (3) a laser-optimized backscatter communication design that exploits laser polarization to maximize retroreflected energy, and (4) the necessary models and algorithms for underwater sensing. Real-world experiments demonstrate that our Sunflower system achieves average localization error of 9.7 cm with ranges up to 3.8 m and is robust against ambient light interference and wave conditions.

This paper presents a method of computing free motions of a planar assembly of rigid bodies connected by loose joints. Joints are modeled using local distance constraints, which are then linearized with respect to configuration space velocities, yielding a linear programming formulation that allows analysis of systems with thousands of rigid bodies. Potential applications include analysis of collections of modular robots, structural stability perturbation analysis, tolerance analysis for mechanical systems, and formation control of mobile robots.

The most widely used methods for toolpath planning in 3D printing slice the input model into successive 2D layers to construct the toolpath. Unfortunately the methods can incur a substantial amount of wasted motion (i.e., the extruder is moving while not printing). In recent years we have introduced a new paradigm that characterizes the space of feasible toolpaths using a dependency graph on the input model, along with several algorithms that optimize objective functions (wasted motion or print time). A natural question that arises is, under what circumstances can we efficiently compute an optimal toolpath? In this paper, we give an algorithm for computing fused deposition modeling (FDM) toolpaths that utilizes Monte Carlo Tree Search (MCTS), a powerful generalpurpose method for navigating large search spaces that is guaranteed to converge to the optimal solution. Under reasonable assumptions on printer geometry that allow us to compress the dependency graph, our MCTS-based algorithm converges to find the optimal toolpath. We validate our algorithm on a dataset of 75 models and examine the performance on MCTS against our previous best local search-based algorithm in terms of toolpath quality. We show that a relatively short time budget for MCTS yields results on par with local search, while a larger time budget yields a 15% improvement in quality over local search. Additionally, we examine the properties of the models and MCTS executions that lead to better or worse results.

The most widely used methods for toolpath planning in fused deposition 3D printing slice the input model into successive 2D layers in order to construct the toolpath. Unfortunately slicing-based methods can incur a substantial amount of wasted motion (i.e., the extruder is moving while not printing), particularly when features of the model are spatially separated. In recent work we have introduced a new paradigm that constructs the toolpath in 3D and prints local features to minimize wasted motion. Our algorithm is based on a local search and we have demonstrated substantial improvements in the efficiency of the resulting toolpaths. Our approach is amenable to incorporating physical constraints of the 3D printing process, and, in this paper we extend our approach to incorporate kinematic properties into toolpath optimization. With an accurate kinematic model of the extruder, our algorithm is able to model the real-world fabrication time of the model with a high degree of accuracy. To our knowledge, this toolpath optimization algorithm is the first to encode real-world fabrication time as the objective function. We demonstrate the real-world improvement in fabrication time that is possible with our algorithm on a benchmark of almost 600 models. We find improvement in nearly every toolpath generated for our benchmark set (with a mean of 3.2%), but substantially larger improvements for some models. To rationalize these results, we introduce a metric for model characterization that we call “oriented compactness” and show that it correlates positively with our observations. We believe this metric can be an important tool in the setup of fabrication (e.g., by guiding an orientation search of the model).

Widely-used methods for toolpath planning in fused filament fabrication slice the input 3D model into 2D layers and construct a toolpath. In prior work (ICRA 2016) we gave a simple greedy algorithm that changed this paradigm and constructed the toolpath in 3D by printing local features in their entirety. This algorithm significantly improved upon layer-based methods, achieving a 34% mean reduction of wasted motion. In this paper we give a new algorithm that is more robust and achieves significantly better performance than the greedy approach. Our algorithm utilizes local search and nearly doubles our prior improvement, achieving a mean/median reduction of 62% over layer-based methods on the same benchmark of over 400 models. We also study toolpath optimality using a novel integer linear programming formulation. This formulation allows us to solve a linear programming relaxation that, while computationally intensive, can give us a lower bound on the optimal solution quality, giving us the ability to rigorously characterize solution quality for a given input model.

Fused filament fabrication (FFF) is gaining traction for rapid prototyping and custom fabrication. Existing toolpath generation methods for FFF printers take as input a three-dimensional model of the target object and construct a layered toolpath that will fabricate the object in 2D slices of a chosen thickness. While this approach is computationally straightforward, it can produce toolpaths that can contain significant, yet unnecessary, extrusionless travel. In this paper we propose a novel 3D toolpath generation paradigm that leverages local feature independence in the target object. In contrast to existing FFF slicing methods which print an object layer by layer, our algorithm provides a means to print local features of an object without being constrained to a single layer. The key benefit of our approach is a tremendous reduction in “extrusionless travel,” in which the printer must move between features without performing any extrusion. We show on a benchmark of 409 objects that our method can yield substantial savings in extrusionless travel, 34% on average, that can directly translate to a reduction in total manufacturing time.