In developing autonomous solutions for mapping and localization, one problem that often needs to be dealt with is determining when an area is revisited despite having poor or no prior information on the relative alignment error. There are well-formulated approaches for recognizing such matches using the rich information in camera data; however, it is a much more challenging problem using lidar sensors alone. Most existing approaches employ a pairwise place comparison of place descriptors and thus finding matches requires linear time per place. We instead propose the use of a keypoint voting approach to achieve sub-linear matching times. A constant number of nearest neighbor votes per keypoint are queried from a database of local descriptors and aggregated to determine likely place matches. It becomes critical to analyze the distributions of vote scores such that a suitable threshold for matching scores can be determined a priori, so that the system is not overwhelmed by false positives nor starved for true matches. We have empirically determined that the vote scores follow a log-normal distribution, and we are able to fit a parametric model of its hyper-parameters based on the number of neighbors, the number of keypoints in a place, and the total number of keypoints in the database. We demonstrate the performance of our system in a variety of large scale 3D lidar datasets using data collected from a continually scanning handheld lidar sensor, and also on two publicly available lidar datasets.

Creating rich representations of environments requires integration of multiple sensing modalities with complementary characteristics such as range and imaging sensors. To precisely combine multisensory information, the rigid transformation between different sensor coordinate systems (i.e., extrinsic parameters) must be estimated. The majority of existing extrinsic calibration techniques require one or multiple planar calibration patterns (such as checkerboards) to be observed simultaneously from the range and imaging sensors. The main limitation of these approaches is that they require modifying the scene with artificial targets. In this paper, we present a novel algorithm for extrinsically calibrating a range sensor with respect to an image sensor with no requirement of external artificial targets. The proposed method exploits natural linear features in the scene to precisely determine the rigid transformation between the coordinate frames. First, a set of 3D lines (plane intersection and boundary line segments) are extracted from the point cloud, and a set of 2D line segments are extracted from the image. Correspondences between the 3D and 2D line segments are used as inputs to an optimization problem which requires jointly estimating the relative translation and rotation between the coordinate frames. The proposed method is not limited to any particular types or configurations of sensors. To demonstrate robustness, efficiency and generality of the presented algorithm, we include results using various sensor configurations.

Situational awareness for industrial vehicles is crucial to ensure safety of personnel and equipment. While human drivers and onboard sensors are able to detect obstacles and pedestrians within line-of-sight, in complex environments, initially occluded or obscured dynamic objects can unpredictably enter the path of a vehicle. We propose a system that integrates a vision-based offboard pedestrian tracking subsystem with an onboard localization and navigation subsystem. This combination enables warnings to be communicated and effectively extends the vehicle controller's field of view to include areas that would otherwise be blind spots. A simple flashing light interface in the vehicle cabin provides a clear and intuitive interface to alert drivers of potential collisions. Alternatively, the system can be also applied to vehicles that have autonomous navigation capabilities, in which case, instead of alert lights, the vehicle is halted or redirected. We implemented and tested the proposed solution on an automated industrial vehicle under autonomous operation and on a human-driven vehicle in a full-scale production facility, over a period of four months.

Three-dimensional perception is a key technology for many robotics applications, including obstacle detection, mapping, and localization. There exist a number of sensors and techniques for acquiring 3-D data, many of which have particular utility for various robotic tasks. We introduce a new design for a 3-D sensor system, constructed from a 2-D range scanner coupled with a passive linkage mechanism, such as a spring. By mounting the other end of the passive linkage mechanism to a moving body, disturbances resulting from accelerations and vibrations of the body propel the 2-D scanner in an irregular fashion, thereby extending the device's field of view outside of its standard scanning plane. The proposed 3-D sensor system is advantageous due to its mechanical simplicity, mobility, low weight, and relatively low cost. We analyze a particular implementation of the proposed device, which we call Zebedee, consisting of a 2-D time-of-flight laser range scanner rigidly coupled to an inertial measurement unit and mounted on a spring. The unique configuration of the sensor system motivates unconventional and specialized algorithms to be developed for data processing. As an example application, we describe a novel 3-D simultaneous localization and mapping solution in which Zebedee is mounted on a moving platform. Using a motion capture system, we have verified the positional accuracy of the sensor trajectory. The results demonstrate that the six-degree-of-freedom trajectory of a passive spring-mounted range sensor can be accurately estimated from laser range data and industrial-grade inertial measurements in real time and that a quality 3-D point cloud map can be generated concurrently using the same data.

The generation of accurate, watertight, three-dimensional models of environments are often crucial for the purposes of scientific study and infrastructure management. Most commonly, such models are acquired by using range sensors producing point clouds, and further processing steps are required for the construction of a surface model. We used a mobile lidar to map several kilometers of a natural cave system in order to obtain 3D volumetric models for use in scientific research studying the local palaeo-climatic record. For unstructured and GPS-denied environments, such as cave systems, the process of acquiring a complete map is difficult and further complicated by limited mobility within the cave. During the mapping process, many unwanted measurements occur due to occlusions from moving objects such as other people present in the cave. Most common point cloud surface reconstruction techniques are not designed to deal these occlusions; i.e., they require manual cleanup of the data set or are not capable of generating watertight surfaces. The large scale of the environments introduces the additional challenge of dealing with memory limitations. We propose a new volume-based approach to reconstruct a watertight surface from range measurements of enclosed environments without limitation on the scale of the collected data. Our approach carves all unoccupied voxels from the sensor to a triangulated and rasterized surface between successive scans, which is intended to fill in the missing data between the scan rays. The surface is then constructed from the isosurface between unoccupied and unknown cells. By decomposing the space, we are able to handle large-scale data without exceeding the memory limitation of a standard PC, at the cost of some additional computation time. The algorithm has been evaluated across several datasets within a variety of environments and observed to build more complete volumetric models than a simple space carving approach. We have mapped several kilometers of cave networks and, with the described method, produced watertight reconstructions suitable for further scientific analysis.

Reliable real-time localization is a key component of autonomous industrial vehicle systems. We consider the problem of using on-board vision to determine a vehicle's pose in a known, but non-static, environment. While feasible technologies exist for vehicle localization, many are not suited for industrial settings where the vehicle must operate dependably both indoors and outdoors and in a range of lighting conditions. We extend the capabilities of an existing vision-based localization system, in a continued effort to improve the robustness, reliability and utility of an automated industrial vehicle system. The vehicle pose is estimated by comparing an edge-filtered version of a video stream to an available 3D edge map of the site. We enhance the previous system by additionally filtering the camera input for straight lines using a Hough transform, observing that the 3D environment map contains only linear features. In addition, we present an automated approach for generating 3D edge maps from laser point clouds, removing the need for manual map surveying and also reducing the time for map generation down from days to minutes. We present extensive localization results in multiple lighting conditions comparing the system with and without the proposed enhancements.

Scan-matching is a technique that can be used for building accurate maps and estimating vehicle motion by comparing a sequence of point cloud measurements of the environment taken from a moving sensor. One challenge that arises in mapping applications where the sensor motion is fast relative to the measurement time is that scans become locally distorted and difficult to align. This problem is common when using 3D laser range sensors, which typically require more scanning time than their 2D counterparts. Existing 3D mapping solutions either eliminate sensor motion by taking a “stop-and-scan” approach, or attempt to correct the motion in an open-loop fashion using odometric or inertial sensors. We propose a solution to 3D scan-matching in which a continuous 6DOF sensor trajectory is recovered to correct the point cloud alignments, producing locally accurate maps and allowing for a reliable estimate of the vehicle motion. Our method is applied to data collected from a 3D spinning lidar sensor mounted on a skid-steer loader vehicle to produce quality maps of outdoor scenes and estimates of the vehicle trajectory during the mapping sequences.

Market-based multirobot coordination approaches have received significant attention and are growing in popularity within the robotics research community. They have been successfully implemented in a variety of domains ranging from mapping and exploration to robot soccer. The research literature on market-based approaches to coordination has now reached a critical mass that warrants a survey and analysis. This paper addresses this need for a survey of the relevant literature by providing an introduction to market-based multirobot coordination, a review and analysis of the state of the art in the field, and a discussion of remaining research challenges

Recent research trends and technology developments are bringing us closer to the realization of autonomous multirobot systems performing increasingly complex missions. However, existing multirobot task allocation mechanisms treat tasks as simple, indivisible entities and ignore any inherent structure and semantics that such complex tasks might have. These properties can be exploited to produce more efficient team plans by giving individual robots the ability to come up with new ways to perform a task, or by allowing multiple robots to cooperate by sharing the subcomponents of a task, or both. In this paper, we introduce the complex task allocation problem and describe a distributed solution for efficiently allocating a set of complex tasks to a robot team. The advantages of explicitly modeling complex tasks during the allocation process is demonstrated by a comparison of our approach with existing task allocation algorithms in an area reconnaissance scenario. An implementation on a team of outdoor robots further validates our approach.

Robustness is crucial for any robot team, especially when operating in dynamic environments. The physicality of robotic systems and their interactions with the environment make them highly prone to malfunctions of many kinds. Three principal categories in the possible space of robot malfunctions are communication failures, partial failure of robot resources necessary for task execution (or partial robot malfunction), and complete robot failure (or robot death). This paper addresses these three categories and explores means by which the TraderBots approach ensures robustness and promotes graceful degradation in team performance when faced with malfunctions.

Presents an approach to efficient multirobot mapping and exploration which exploits a market architecture in order to maximize information gain while minimizing incurred costs. This system is reliable and robust in that it can accommodate dynamic introduction and loss of team members in addition to being able to withstand communication interruptions and failures. Results showing the capabilities of our system on a team of exploring autonomous robots are given.