Coverage Path Planning (CPP) describes the process of generating robot trajectories that fully cover an area or volume. Applications are, amongst many others, mobile cleaning robots, lawn mowing robots or harvesting machines in agriculture. Many approaches and facets of this problem have been discussed in literature but despite the availability of several surveys on the topic there is little work on quantitative assessment and comparison of different coverage path planning algorithms. This paper analyzes six popular off-line coverage path planning methods, applicable to previously recorded maps, in the setting of indoor coverage path planning on room-sized units. The implemented algorithms are thoroughly compared on a large dataset of over 550 rooms with and without furniture.

The division of floor plans or navigation maps into single rooms or similarly meaningful semantic units is central to numerous tasks in robotics such as topological mapping, semantic mapping, place categorization, human-robot-interaction, or automatized professional cleaning. Although many map partitioning algorithms have been proposed for various applications there is a lack of comparative studies on these different algorithms. This paper surveys the literature on room segmentation and provides four publicly available implementations of popular methods, which target the semantic mapping domain and are tuned to yield segmentations into complete rooms. In an attempt to provide new users of such technologies guidance in the choice of map segmentation algorithm, those methods are compared qualitatively and quantitatively using several criteria. The evaluation is based on a novel compilation of 20 challenging floor plans.

Millions of office workplaces are cleaned by a surprisingly small group of cleaning workers every day, however, cleaning companies struggle to recruit enough personnel these days. One solution to this challenge is to schedule available professionals for demanding tasks while relieving them from simpler activities which are transferred to a robotic cleaning assistant. Two of such tasks are floor cleaning and waste disposal which account for 70% of the daily cleaning efforts. This paper presents the world's first autonomous cleaning robot prototype that masters both of these tasks and whose development was accompanied by the advice of a large cleaning company. Besides a detailed description of the overall system and its individual components an evaluation is provided based on real world experiments. The results indicate that both cleaning tasks can be solved at high quality but with potential for increased efficiency to meet the required performance. Hence, the paper concludes with a discussion on measures necessary for the development of a commercial prototype.

Accurate surface normal computation is one of the most basic and important tasks for 3d perception. While much progress has been made in speeding up normal estimation algorithms and improving their accuracy, a significant inaccuracy still remains even with modern implementations, which is the correct determination of surface normals close to non-differentiable surface edges. Current algorithms tend to amalgamate neighborhood points from independent surfaces yielding normals that neither fit well to the one nor the other surface. This paper introduces a fast and accurate 3d edge detection algorithm suitable to detect discontinuities both in depth and on surfaces with nearly 90% accuracy at rates beyond 30 Hz. Based on this method, we demonstrate how established normal estimation algorithms can be extended for edge-awareness. Additionally, a new edge-aware, fast, accurate, and robust normal estimation approach is described which exploits the data structures computed for 3d edge detection and estimates normals at 23 Hz. We assess the performance of all proposed methods and compare them with other state-of-the-art approaches.

We present a descriptor estimator for surface-based 3D input data for coarse localization of mobile robots. From the input pointclouds surfaces are reconstructed and simplified to detect stable keypoints which are used to evaluate rotation and translation invariant features. The invariance is achieved by transforming the triangulated input data into the frequency domain by Fourier transformation and spherical harmonics. The pipeline was evaluated against state of the art algorithms and tested to localize a mobile robot. The source code is publicly available.

Derivation of geometric structures from point clouds is an important step towards scene understanding for mobile robots. In this paper, we present a novel method for segmentation and surface classification of ordered point clouds. Data from RGB-D cameras are used as input. Normal based region growing segments the cloud and point feature descriptors classify each segment. Not only planar segments can be described but also curved surfaces. In an evaluation on indoor scenes we show the performance of our approach as well as give a comparison to state of the art methods.

In this paper, we present a novel method for surface reconstruction with a low execution time for segmenting and representing scattered scenes accurately. The surfaces are described in a memory-efficient fashion as polynomial functions and polygons. Segmentation and parameter determination is done in one pass by using a quadtree on ordered point clouds, which results in a complexity of O(log n). This paper includes an evaluation with respect to reconstruction accuracy, segmentation precision, execution time and compression ratio of everyday indoor scenes. Our surface reconstruction algorithm outperforms comparable approaches with respect to execution time and accuracy. More importantly, the new technique handles curved shapes accurately and enables complex tasks like 3D mapping for mobile robots in an unknown environment.