This paper proposes a new inspection planning algorithm, called Random Inspection Tree Algorithm (RITA). Given a perfect model of a structure, sensor specifications, robot's dynamics, and an initial configuration of a robot, RITA computes the optimal inspection trajectory that observes all points on the structure. Many inspection planning algorithms have been proposed, most of them consist of two sequential steps. In the first step, they compute a small set of observation points such that each point on the structure is visible. In the second step, they compute the shortest trajectory to visit all observation points at least once. The robot's kinematic and dynamic constraints are taken into account only in the second step. Thus, when the robot has differential constraints and operates in cluttered environments, the observation points may be difficult or even infeasible to reach. To alleviate this difficulty, RITA computes both observation points and the trajectory to visit the observation points simultaneously. RITA uses sampling-based techniques to find admissible trajectories with decreasing cost. Simulation results for 2-D environments are promising. Furthermore, we present analysis on the probabilistic completeness and asymptotic optimality of our algorithm.

Over the last eight years, significant scientific effort has been dedicated on the problem of 3-D surface reconstruction for structural systems. However, the critical area of marine structures remains insufficiently studied. The research presented here focuses on the problem of 3-D surface reconstruction in the marine environment. This work is an extension of our previous approach, in which a surface vehicle that was equipped with a powerful laser scanner was designed and used to scan the above-water part of the marine structure of interest. Here we propose the design of a novel surface vehicle that is capable of using laser scanners and a side-looking sonar to scan marine structures both above and below the waterline. We also study the issue of downsampling the dataset in order to perform efficient surface reconstruction of the considered 3-D geometry, and we present a methodology for combining and integrating data from the above- and below-water parts of the structure. To illustrate the proposed robotic platform and validate our algorithms, we present results from a set of experiments in the Singapore Sea. Specifically, we present 2 different maps: the above-water map and the combined above-and below-water map. In both cases, we have two different maps: a lower quality map, that can be generated on-line, and a higher quality map that is generated off-line. To the best of our knowledge, our work is the only one that provides a 3-D model for both above- and below-water parts of marine structures. In this work we assumed a GPS-denied environment, without using any other navigation sensor such as DVL or INS.

Among today's robotics applications, exploration missions in dynamic, high clutter and uncertain environmental conditions is quite common. Autonomous multi-vehicle systems come in handy for such exploration missions since a team of autonomous vehicles can explore an environment more efficiently and reliably than a single autonomous vehicle (AV). In order to improve the navigation accuracy, especially in the absence of a priori feature maps, various simultaneous localization and mapping (SLAM) algorithms are widely used in such applications. As for multi-vehicle scenarios, collaborative multi-vehicle simultaneous localization and mapping algorithm (CSLAM) is an effective strategy. However use of multiple AVs poses additional scaling problems such as inter-vehicle map fusion, and data association which needs to be addressed. Although existing CSLAM algorithms are shown to perform quite adequately in simulations, their performance is much less to be desired in high clutter scenarios that is inevitable in actual environments. In this paper, we present an approach to improve the performance of a CSLAM algorithm in the presence of high clutter, by combining an effective clutter filter framework based on Random Finite Sets (RFS). The performance of the improved CSLAM algorithm is evaluated using simulations under varying clutter conditions.

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.

This paper investigates the problem of cooperative navigation of autonomous marine vehicles using range-only acoustic measurements. We consider the use of a single maneuvering autonomous surface vehicle (ASV) to aid the navigation of one or more submerged autonomous underwater vehicles (AUVs), using acoustic range measurements combined with position measurements for the ASV when data packets are transmitted. The AUV combines the data from the surface vehicle with its proprioceptive sensor measurements to compute its trajectory. In previous work, we presented an experimental demonstration of this approach, using an extended Kalman filter (EKF) for state estimation. In the present paper, we analyze the observability properties of the cooperative ASV/AUV localization problem and present experimental results comparing several different state estimators. Using the weak observability theorem for nonlinear systems, we demonstrate that this cooperative localization problem is best attacked using nonlinear least squares (NLS) optimization. We present experimental results for this new approach and compare it to alternative state estimators, demonstrating superior performance.

In this paper we describe a fully integrated system for detecting and tracking pedestrians in a dynamic urban environment. The system can reliably detect and track pedestrians to a range of 100 m in highly cluttered environments. The system uses a highly accurate 3D LIDAR from Velodyne to segment the scene into regions of interest or blobs, from which the pedestrians are determined. The pedestrians are then tracked using probability hypothesis density (PHD) filter which is based on random finite set theoretic framework. In contrast to classical approaches, this random finite set framework does not require any explicit data associations. The PHD filter is implemented using a Gaussian Mixture technique. Experimental results obtained in dynamic urban settings demonstrate the efficacy and tracking performance of the proposed approach.

We present a system for the automatic global registration of voxelized data using the wavelet transform. The huge size of current data sets makes such multi-resolution techniques appealing; however, the traditional discrete wavelet transform has the drawback of variance with translation and rotation. We employ the dual-tree complex wavelet transform (Kingsbury, 2003), which carefully adds near invariance to translation and reduced sensitivity to rotation in computationally efficient ways, thus enabling the object matching application. We employ the wavelet transform to accomplish registration by extracting features in a multi-resolutional format, thus rapidly detecting and matching feature points. The method is robust to occlusion, clutter and noise. The efficacy of the algorithm is demonstrated through examples from solid modeling and biomedical applications.

This work presents a novel method to detect an important flow feature, vortices, in the ocean. Our method can detect closed streamlines around vortex cores. Coupled with existing vortex core detection, the entire vortex area, which is the combination of the vortex core and surrounding streamlines, can be detected. A variety of feature extraction methods are presented, and those more pertinent to this study are implemented. Detection results are evaluated in terms of accuracy, clarity and usability.

We present methods for the computation of roots of univariate and bivariate nonlinear polynomial systems as well as the identification of their multiplicity. We first present an algorithm, called the TDB algorithm, which computes the values and the multiplicities of roots of a univariate polynomial. The procedure is based on the concept of the degree of a certain Gauss map, which is deduced from the polynomial itself. In the bivariate case, we use a combination of resultants and our procedure for the univariate case, as the basis for developing an algorithm for locating the roots and computing their multiplicities. Our methods are robust and global in nature. Complexity analysis of the proposed methods is included together with comparison with standard subdivision methods. Examples illustrate our techniques.

The ocean, is fundamentally important to many areas of modern society and thus improved knowledge of the ocean is essential. Ocean scientists have made remarkable progress in observation technology, modeling and assimilation in physical oceanography, acoustics, and biology. To some extent, such advances have been confined to each discipline. Therefore a great demand has arisen for a modern distributed computing and networking infrastructure within which we bring together advanced modeling, observation tools and field estimation methods. The paper describes a knowledge network of distributed heterogeneous data and software resources for multidisciplinary ocean research.

We present an unstructured triangular mesh generation algorithm that approximates a set of mutually non-intersecting simple trimmed rational B-spline surface patches within a user specified geometric tolerance. The proposed method uses numerically robust interval geometric representations/computations and also addresses the problem of topological consistency (homeomorphism) between the exact geometry and its approximation. Those are among the most important outstanding issues in geometry approximation problems. Our surface tessellation algorithm is based on the unstructured Delaunay mesh approach which leads to an efficient adaptive triangulation. A robust decision criterion is utilized to prevent possible failures in the conventional Delaunay triangulation. To satisfy the prescribed geometric tolerance, an adaptive node insertion algorithm is employed. Unstructured triangular meshes for free-form surfaces frequently involve triangles with high aspect ratio and accordingly, result in ill-conditioned meshing. Our proposed algorithm constructs 2D triangulation domains which sufficiently preserve the shape of triangles when mapped into 2D space and furthermore, the algorithm provides an efficient method that explicitly controls the aspect ratio of the triangular elements.

We present an efficient and reliable method for computing the unit-in-the-last-place (ulp) of a double-precision floating-point number, taking advantage of the standard binary representation for floatingpoint numbers defined by IEEE Std 754-1985. The ulp is necessary to perform software rounding for robust rounded-interval arithmetic (RIA) operations. Hardware rounding, using two of the standard rounding modes defined by IEEE-754, may be more efficient. RIA has been used to produce robust software systems for the solution of systems of nonlinear equations, interrogation of geometric and differential properties of curves and surfaces, curve and surface intersections, and solid modeling.

This paper proposes a method for the representation of functions describing a measured geophysical property (via sparsely scattered ordensely defined point data) by tensor and triple product interval B-splines (IBS). The spline representation facilitates archiving, data storage reduction, visualization and more general high-level interrogation. Interval methods allow for the representation of the function values together with their uncertainty. The uncertainty is introduced, for example, because the measurement (or dependent variable) or the location of the sensor (the independent variable(s)) is known only to a finite precision. In this paper, we present algorithms for the creation of IBS geometries based on minimization with linear constraints and we illustrate the method using geophysical ocean data and their interrogation.

The medial axis transform (MAT) is a representation of an object which has been shown to be useful in design, interrogation, animation, finite element mesh generation, performance analysis, manufacturing simulation, path planning and tolerance specification. In this paper, an algorithm for determining the MAT is developed for general 3D polyhedral solids of arbitrary genus without cavities, with nonconvex vertices and edges. The algorithm is based on a classification scheme which relates different pieces of the medial axis (MA) to one another, even in the presence of degenerate MA points. Vertices of the MA are connected to one another by tracing along adjacent edges, and finally the faces of the axis are found by traversing closed loops of vertices and edges. Representation of the MA and its associated radius function is addressed, and pseudocode for the algorithm is given along with recommended optimizations. A connectivity theorem is proven to show the completeness of the algorithm. Complexity estimates and stability analysis for the algorithms are presented. Finally, examples illustrate the computational properties of the algorithm for convex and nonconvex 3D polyhedral solids with polyhedral holes.

This paper presents an algorithm for computing the intersection of the offset (or parallel) surface of a polynomial surface patch ( rogenitor) of arbitrary degree, with a straight line. The rogenitor patch is expressed in the tensor product Bernstein form. The intersection problem is reformulated in terms of computing the intersection of two algebraic curves within the parameter s ace of the patch. The tensor product Bernstein form is emplo ed for the representation of these algebraic curves. The solution method is based on subdivision relying on the convex hull roperty of the Bernstein representation of algebraic curves and minimization techniques. The resulting algorithm can form the basis for accurate visualization of offset surfaces through ray tracing methods.

A method for blendin non uniform rational B-spline surface patches, either open or periodic, is developed. he blending surface is expressed in terms of an integral, bicubic B-spline patch. The blend ensures position and normal vector continuity along linkage curves to within a specified accuracy. The linkage curves are either user-defined or are obtained by offsetting the intersection of the two patches using geodesics on each patch. An example illustrates the applicability of our method.