Interacting with the environment, such as object detection and tracking, is a crucial ability of mobile robots. Besides high accuracy, efficiency in terms of processing effort and energy consumption are also desirable. To satisfy both requirements, we propose a detection framework based on simultaneous classification and tracking in the point stream. In this framework, a tracker performs data association in sequences of the point cloud, guiding the detector to avoid redundant processing (i.e. classifying already-known objects). For objects whose classification is not sufficiently certain, a fusion model is designed to fuse selected key observations that provide different perspectives across the tracking span. Therefore, performance (accuracy and efficiency of detection) can be enhanced. This method is particularly suitable for detecting and tracking moving objects, a process which would require expensive computations if solved using conventional procedures. Experiments were conducted on the benchmark dataset, and the results showed that the proposed method outperforms original tracking-by-detection approaches in both efficiency and accuracy.

In general, proposed solutions for LiDAR-based localization used in autonomous cars require expensive sensors and computationally expensive mapping processes. Moreover, the global localization for autonomous driving is converging to the use of maps. Straightforward strategies to reduce the costs are to produce simpler sensors and use maps already available on the Internet. Here, an analysis is presented to show how simple can a LiDAR sensor be without degrading the localization accuracy that uses road and satellite maps together to globally pose the car. Three characteristics of the sensor are evaluated: the number of range readings, the amount of noise in the LiDAR readings, and the frame rate, with the aim of finding the minimum number of LiDAR lines, the maximum acceptable noise and the sensor frame rate needed to obtain an accurate position estimation. The analysis is performed using an autonomous car in complex field scenarios equipped with a 3D LiDAR Velodyne HDL-32E. Several experiments were conducted reducing the number of frames, the number of scans per 3D point-cloud and artificially adding up to 15% of error in the ray length. Among other results, we found that using only 4 vertical lines per scan and with an artificial error added up to 15% of the ray length, the car was capable to localize itself within 2.11 meters error average. All experimental results and the followed methodology are explained in detail herein.

The optimal estimation of dynamic random fields is a relevant problem in diverse areas of robotics application. The associated estimation process in these problems implicitly requires dealing with high dimensional multi-variate Probability Density Functions (PDFs) with unaffordable processing cost. The Generalised Compressed Kalman Filter (GCKF) with subsystem switching and proper information exchange architecture is capable of solving such problems with comparable performance to the optimal full Gaussian estimators but at a remarkably lower cost. In this paper, an explicit algorithm is proposed for replacing the Kalman Filter core with a suitable Gaussian Filter core to solve non-linear estimation problems. The computational advantages of GCKF are highlighted, where the computational complexities of different Gaussian Filters are compared against their compressed counterpart. The performance of the algorithm has been verified through its application in solving linear Stochastic Partial Differential Equations (SPDEs) with unknown parameters.

Vehicle localization in large-scale urban environments has been commonly addressed as a map-matching problem in the literature. Generally, the maps are 2D images of the world where each pixel covers a part of it. However, building maps for large-scale urban environments requires driving the vehicle along the desired path at least once. In order to simplify this task, in this work, we propose a new localization system that uses satellite aerial map-images available on the Internet to localize a vehicle in a complex urban environment. Satellite aerial map-images are compared against re-emission maps built from the infrared reflectance information of the vehicle's LiDAR. Normalized Mutual Information (NMI) is used to compare re-emission and aerial map images. A Particle Filter Localization strategy is applied for vehicle's localization. As a result, the system has an accuracy of 0.89m in a test course with 6.5km. Our system can be used continuously without losing track, and it works even in dark and partially occluded areas.

Indoor and outdoor accurate 3D mapping is a relevant resource for a diversity of applications. This paper describes an autonomous platform capable of generating 3D imagery of the environment in unknown indoor and outdoor contexts. The system is composed by a number of Data Fusion processes that are performed in real-time by on-board and/or off-board processing nodes. The platform's sensing capabilities are composed of multiple laser scanners for 2D and 3D perception, IMU units, 3D cameras (indoor Kinect), standard cameras, GPS (for outdoor operation) and dead reckoning sensors. The acquired data is shared with multiple client processes that are in charge of different levels of perception and control. The resulting data, produced by the perception processes is also shared for being used by higher-level processes such as the 3D mapping, generation of maps of diverse dense properties, detection and classifications of obstacles and other context features that are application specific.

This paper presents the application of the PPQ Dijkstra approach for solving 2D path planning problems. The approach is a Dijkstra process whose priority queue (PQ) is implemented through a Pseudo Priority Queue (PPQ) also known as Untidy PQ. The performance of the optimization process is dramatically improved by the application of the PPQ. This modification can be used for a family of problems. The path planning problem belongs to the family of feasible problems that can be solved by considering PPQ-Dijkstra approach. The solution provided by the PPQ-Dijkstra algorithm is optimal, i.e. it is identical to the solution obtained through the standard Dijkstra algorithm. The PPQ-Dijkstra algorithm can be also applied for higher dimensionality problems such as non-holonomic planning processes, e.g. involving configuration spaces of higher dimension.

This paper presents an efficient approach to global path planning for multiple agents during large-scale map deformation. The problem of planning using dense data during large-scale map deformation is addressed by using a hybrid metric-topological planner that maintains locally consistent policies. These policies are cached, providing efficiency gains relative to alternate planning approaches that are characterized using complexity analysis. Simulation results show the effectiveness of this approach in handling notable map deformation while achieving good efficiency.

This paper describes a novel approach to surface fitting for the creation of a 3D surface map for use by a small articulated wall-climbing robot. Both a laser range finder and a low-resolution camera are used to acquire data in a sparse manner. By scanning at large intervals, such as every 5–10°, and then fusing the data, it is shown that it is possible to fit planar surfaces at an accuracy comparable to dense range scanning. Infinite planes are fit to lines extracted from the range scans and then the image corners and lines are used to provide polygon boundaries on these planes. This method is faster and more flexible, both in acquiring data and in computing the planar features and less memory is required. This method also works well in feature poor environments where stereo vision can struggle and does not need to process the feature correspondences in the typical fashion which also saves time. This surface fitting approach is demonstrated using a real data set and results show promise in providing quick yet accurate 3D planar surfaces which could be integrated into SLAM and motion planning frameworks.

This paper presents a framework for efficient path planning in a deformable map. A roadmap and local cost maps are combined and integrated into a generic SLAM process to provide fast path querying for multiple sources and multiple destinations. Analysis of a simple deformation metric shows the ability of the framework to efficiently maintain a consistent plan during major map adjustment by updating the roadmap and selected local cost maps. Results from simulation verify the effectiveness of the framework in handling deformable maps in an efficient manner.

This paper presents a method to perform localization in urban environments using segment-based maps together with particle filters. In the proposed approach, the likelihood function is generated as a grid, derived from segment-based maps. The scheme can efficiently assign weights to the particles in real time, with minimum memory requirements and without any additional pre-filtering procedure. Multi-hypotheses cases are handled transparently by the filter. A local history-based observation model is formulated as an extension to deal with 'out-of-map' navigation cases. This feature is highly desirable since the map can be incomplete, or the vehicle can be actually located outside the boundaries of the provided map. The system behaves like a 'virtual GPS', providing global localization in urban environments, without using an actual GPS. Experimental results show the performance of the proposed architecture in large scale urban environments using route network description (RNDF) segment-based maps.

This paper presents an analysis of the extended Kalman filter formulation of simultaneous localisation and mapping (EKF-SLAM). We show that the algorithm produces very optimistic estimates once the "true" uncertainty in vehicle heading exceeds a limit. This failure is subtle and cannot, in general, be detected without ground-truth, although a very inconsistent filter may exhibit observable symptoms, such as disproportionately large jumps in the vehicle pose update. Conventional solutions - adding stabilising noise, using an iterated EKF or unscented filter, etc., - do not improve the situation. However, if "small" heading uncertainty is maintained, EKF-SLAM exhibits consistent behaviour over an extended time-period. Although the uncertainty estimate slowly becomes optimistic, inconsistency can be mitigated indefinitely by applying tactics such as batch updates or stabilising noise. The manageable degradation of small heading variance SLAM indicates the efficacy of submap methods for large-scale maps

Although full 3D navigation and mapping is recognized as one of the most important challenges for autonomous navigation, the lack of robust sensors, providing 3D information in real time, has burdened the progress in this direction. This paper presents our ongoing work towards the deployment of an integrated sensing system for 3D mapping in outdoor environments. We first describe a 3D data acquisition architecture based on a standard 2D laser. Techniques for registering scans using a scan matching procedure and for estimating the errors are then introduced. We finally present results showing the performance of the proposed architecture in real outdoor environments by means of the integration of the 3D scans with dead reckoning and inertial measurement unit (IMU) information

This paper describes the derivation and experimental validation of a novel sensor model for radio frequency sensors to be used for localisation purposes. A comprehensive description of the modelling aspects is presented. Outdoor range only tracking results using the newly derived model are fully described with a comparison to the free space model commonly used for radio frequency applications. Although this approach is applicable for generic localisation purposes in indoor and outdoor environments, it is of fundamental importance when applied to proximity detection involving large machines. In particular in environments such as mining, stevedoring and construction there is a need to detect the presence of personnel in close proximity to machines. A close proximity system that makes use of the newly derived model is presented working with a 100 tons mining haul truck

In the navigation context it is typical the presence of sensors that introduce uncertainties that cannot be modeled as white Gaussian noise. Such measures cannot be directly used in gaussian estimators. This paper presents a technique that allows the consistent processing of this type of measurements in combination with a standard EKF estimator. The method can be applied in an efficient implementation of SLAM based on a Gaussian estimator.

Perception by autonomous systems, in unstructured dynamic worlds, is one of the significant research challenges in the development of effective intelligent systems. Nonlinear dimensionality reduction techniques have been extensively utilized within the artificial intelligence community to devise compact representations of high dimensional data. These techniques display great promise in yielding low dimensional, meaningful representations of an unstructured environment in real time from raw sensory information. Two such techniques, the kernel principal component analysis method and locally linear embedding (LLE) are evaluated herein, with respect to their ability to generate compact and physically reasonable embeddings of an unstructured environment. The LLE technique shows great potential in the computation of low dimensional and perceptually meaningful embeddings of natural environments.

This work presents a new hybrid metric map representation (HYMM) that combines feature maps with other dense metric sensory information. The global feature map is partitioned into a set of connected local triangular regions (LTRs), which provide a reference for a detailed multi-dimensional description of the environment. The HYMM framework permits the combination of efficient feature-based SLAM algorithms for localisation with, for example, occupancy grid (OG) maps. This fusion of feature and grid maps has several complementary properties; for example, grid maps can assist data association and can facilitate the extraction and incorporation of new landmarks as they become identified from multiple vantage points. The representation presented here will allow the robot to perform DenseSLAM. DenseSLAM is the process of performing SLAM whilst obtaining a dense environment representation.

This paper proposes a new algorithm named "SIGMA" to address the problem of simultaneous information and global motion analysis for a car working in unstructured outdoor environments. The map of the environment is made by a Simultaneous Localization and Mapping (SLAM) algorithm that uses an Hybrid Metric Map (HYMM) structure for mapping. The path planning approach presents a global solution maximizing overall information gain of the map. The cost function used considers the present and future uncertainty in the map and vehicle and is based on the variation of the covariance matrix trace. Eigenvalue concepts are utilized to determine overall information change from the information matrix properties. An information graph is constructed followed by a search to find the optimal information-based rough path. Results are presented to demonstrate performance of the algorithm.

The ability to simultaneously localise a robot and accurately map its surroundings is considered by many to be a key prerequisite of truly autonomous robots. This paper presents a real-world implementation of FastSLAM, an algorithm that recursively estimates the full posterior distribution of both robot pose and landmark locations. In particular, we present an extension to FastSLAM that addresses the data association problem using a nearest neighbor technique. Building on this, we also present a novel multiple hypotheses tracking implementation (MHT) to handle uncertainty in the data association. Finally an extension to the multi-robot case is introduced. Our algorithm has been run successfully using a number of data sets obtained in outdoor environments. Experimental results are presented that demonstrate the performance of the algorithms when compared with standard Kalman filter-based approaches.

This paper presents two approaches for the problem of multiple target tracking (MTT) and specifically people tracking. Both filters are based on sequential Monte Carlo methods (SMCM) and joint probability data association (JPDA). The filters have been implemented and tested on real data from a laser measurement system. Experiments show that both approaches are able to track multiple moving persons. A comparison of both filters is given and the advantages and disadvantages of the two approaches are presented.

This paper addresses the problem of on-line path following for a car working in unstructured outdoor environments. The partially known map of the environment is updated and expanded in real time by a Simultaneous Localization and Mapping (SLAM) algorithm. This information is used to implement global path planning. A cost graph is initially constructed followed by a search to find the near-optimal path considering uncertainty in both vehicle location and map. Selected points in the global path are connected by continuous-curvature paths. An improved feedback linearization technique is presented to guide the car along the defined path. Experimental results are presented to demonstrate the performance of the algorithms.

This paper presents new algorithms to implement simultaneous localization and mapping in environments with very large numbers of features. The algorithms present an efficient solution to the full update required by the compressed extended Kalman filter algorithm. It makes use of the relative landmark representation to develop very close to optimal decorrelation solutions. With this approach, the memory and computational requirements are reduced from /spl sim/O(N/sup 2/) to /spl sim/O(N/sup */N/sub a/), N and N/sub a/ proportional to the number of features in the map and features close to the vehicle, respectively. Experimental results are presented to verify the operation of the system when working in large outdoor environments.

Addresses the problem of implementing simultaneous localisation and map building (SLAM) in very large outdoor environments. A method is presented to reduce the computational requirement from /spl sim/O(N/sup 2/) to /spl sim/O(N), N being the states used to represent all the landmarks and vehicle pose. With this implementation the memory requirements are also reduced to /spl sim/O(N). This algorithm presents an efficient solution to the full update required by the compressed extended Kalman filter algorithm. Experimental results are also presented.

This paper address the problem of navigating in very large outdoor unstructured environments. It presents solutions to the problem of closing large loops in simultaneous localization and map building applications. A hybrid architecture is presented that make use of the extended Kalman filter to perform SLAM in an efficient form and a Monte Carlo type filter to resolve the data association problem present when closing large loops. The proposed algorithm incorporates integrity to the standard SLAM algorithms by allowing multimode distribution to be handled in real time. Experimental results in outdoor environments are also presented.

Addresses real-time implementation of the simultaneous localization and map-building (SLAM) algorithm. It presents optimal algorithms that consider the special form of the matrices and a new compressed filler that can significantly reduce the computation requirements when working in local areas or with high frequency external sensors. It is shown that by extending the standard Kalman filter models the information gained in a local area can be maintained with a cost /spl sim/O(N/sub a//sup 2/), where N/sub a/ is the number of landmarks in the local area, and then transferred to the overall map in only one iteration at full SLAM computational cost. Additional simplifications are also presented that are very close to optimal when an appropriate map representation is used. Finally the algorithms are validated with experimental results obtained with a standard vehicle running in a completely unstructured outdoor environment.

This paper presents the design of a high accuracy outdoor navigation system based on standard dead reckoning sensors and laser range and bearing information. The data validation problem is addressed using laser intensity information. Beacon design aspect and location of landmarks are also discussed in relation to desired accuracy and required area of operation. The results are important for simultaneous localization and map building applications since the feature extraction and validation are resolved at the sensor level using laser intensity. This facilitates the use of additional natural landmarks to improve the accuracy of the localization algorithm. Experimental results in outdoor environments are also presented.