Gaussian processes autonomous mapping and exploration for range-sensing mobile robots

Most of the existing robotic exploration schemes use occupancy grid representations and geometric targets known as frontiers. The occupancy grid representation relies on the assumption of independence between grid cells and ignores structural correlations present in the environment. We develop a Gaussian processes (GPs) occupancy mapping technique that is computationally tractable for online map building due to its incremental formulation and provides a continuous model of uncertainty over the map spatial coordinates. The standard way to represent geometric frontiers extracted from occupancy maps is to assign binary values to each grid cell. We extend this notion to novel probabilistic frontier maps computed efficiently using the gradient of the GP occupancy map. We also propose a mutual information-based greedy exploration technique built on that representation that takes into account all possible future observations. A major advantage of high-dimensional map inference is the fact that such techniques require fewer observations, leading to a faster map entropy reduction during exploration for map building scenarios. Evaluations using the publicly available datasets show the effectiveness of the proposed framework for robotic mapping and exploration tasks.     

Real-time building of a thinning-based topological map

An accurate and compact map is essential to an autonomous mobile robot system. A topological map, one of the most popular map types, can be used to represent the environment in terms of discrete nodes with edges connecting them. It is usually constructed by Voronoi-like graphs, but in this paper the topological map is incrementally built based on the local grid map by using a thinning algorithm. This algorithm, when combined with the application of the C-obstacle, can easily extract only the meaningful topological information in real-time and is robust to environment change, because this map is extracted from a local grid map generated based on the Bayesian update formula. In this paper, position probability is defined to evaluate the quantitative reliability of the end node extracted by the thinning process. Since the thinning process builds only local topological maps, a global topological map should be constructed by merging local topological maps according to nodes with high position probability. For real and complex environments, experiments showed that the proposed map building method based on the thinning process can accurately build a local topological map in real-time, with which an accurate global topological map can be incrementally constructed.     

Terrain trafficability analysis for autonomous navigation: A GIS-based approach

This article presents a method of generating grid maps for autonomous navigation using a geographic information system (GIS). Besides developing ordinary map systems, a GIS can be applicable to the terrain trafficability analysis for an unmanned ground vehicle (UGV) by generating maps in which information about its spatial environment is encoded for path planning as part of autonomous navigation. For such maps, the most commonly used is a grid map over which a UGV’s paths can be optimized. As the UGV moves and its situation changes, grid maps need to be generated quickly in an automatic manner for new paths. First of all, a GIS is analyzed to identify meaningful data, layers and attributes, which are then related to the UGV’s navigation. For each grid in the grid map, every meaningful layer included is processed so that the set of values of attributes of the layer can be converted into the traverse cost. If multiple layers are included in a single grid, those traverse costs are fused and the result data is then replaced in the grid. Grid map generation is finished after all grids are filled with such costs. From test results using an experimental program, it is validated that the proposed method can be a viable tool for the timely generation of grid maps using a geographic information system for the UGV’s autonomous navigation.     

基于图像配准的栅格地图拼接方法

栅格地图拼接是多移动机器人协同创建环境地图中的一项关键技术. 本文提出一种图像配准意义下的栅格地图拼接方法. 该方法将栅格地图拼接问题视为图像配准问题, 建立相应的目标函数, 并给出局部收敛的迭代最近点算法求解该目标函数. 为获得最优的拼接结果, 该方法从待拼接的地图中提取局部不变特征, 并借助随机抽样一致性算法分析初始拼接参数, 以作为迭代最近点算法的初值. 最后, 提出了拼接参数已知时的栅格地图融合规则. 实验结果表明, 该方法能可靠地实现栅格地图拼接, 且具有精度高和速度快的优点.     

矢量地图的无损数据隐藏算法研究

在矢量地图中隐含水印信息,地图数据的质量往往由于水印的嵌入而受到影响。可逆水印技术(又称无损数据隐藏)具有完整恢复载体数据的能力,因而更加适用于矢量地图。基于差值扩大的思想,提出了一种应用于矢量地图的无损数据隐藏算法。算法根据矢量地图对数据精度的特殊要求提出了相应的水印嵌入条件,并通过修改地图中相邻顶点坐标间的差值来嵌入水印信息。水印的提取过程不仅能够得到隐藏信息,而且能够准确无误地恢复原始地图数据。采用两类地图进行实验,实验结果表明,算法在具有较强坐标相关性的地图中具有较高的嵌入容量,并且引入较低的扰动。算法的应用前景包括矢量地图数据的篡改鉴别、元数据格式兼容以及基于矢量地图的隐藏通信。     

Metro Maps on Octilinear Grid Graphs

Schematic transit maps (often called “metro maps” in the literature) are important to produce comprehensible visualizations of complex public transit networks. In this work, we investigate the problem of automatically drawing such maps on an octilinear grid with an arbitrary (but optimal) number of edge bends. Our approach can naturally deal with obstacles that should be respected in the final drawing (points of interest, rivers, coastlines) and can prefer grid edges near the real-world course of a line. This allows our drawings to be combined with existing maps, for example as overlays in map services. We formulate an integer linear program which can be used to solve the problem exactly. We also provide a fast approximation algorithm which greedily calculates shortest paths between node candidates on the underlying octilinear grid graph. Previous work used local search techniques to update node positions until a local optimum was found, but without guaranteeing octilinearity. We can thus calculate nearly optimal metro maps in a fraction of a second even for complex networks, enabling the interactive use of our method in map editors.     

β-SLAM: Simultaneous localization and grid mapping with beta distributions

Simultaneous localization and mapping (SLAM) is one of the most frequently studied problems in mobile robotics. Different map representations have been proposed in the past and a popular one are occupancy grid maps, which are particularly well suited for navigation tasks. The uncertainty in these maps is usually modeled as a single Bernoulli distribution per grid cell. This has the disadvantage that one cannot distinguish between uncertainty caused by different phenomena like missing or conflicting information. In this paper, we overcome this limitation by modeling the occupancy probabilities as random variables. Those are assumed to be beta-distributed and account for the different causes of uncertainty. Based on this map representation, we derive a SLAM algorithm, including all necessary sensor models, for building maps composed of beta-distributed random variables and using these maps for localization. Furthermore, we propose measures for quantifying uncertainty in the resulting maps and for solving navigation tasks. We evaluate our approach using real-world as well as simulation-based datasets and we compare it to a state-of-the-art SLAM algorithm for building classical grid maps.     

Sonar Map Construction for Autonomous Mobile Robots Using a Data Association Filter

This paper presents a method for building a probability grid map for autonomous mobile robots with ultrasonic sensors using a data association filter (DAF). The method is based on evaluating the possibility that the acquired sonar data are all reflected by the same object. The DAF is able to associate data points with each other. Data affected by specular reflection are not likely to be associated with the same object, so they are excluded from the data cluster by the DAF, thereby improving the reliability of the data used for the probability grid map. Since the corrupted data are not used to update the probability map, it is possible to build a good quality grid map even in a specular environment. The DAF was applied to the Bayesian and the Orientation probability models, which are typical models used to build grid maps, to verify its effectiveness. Experimental results were also obtained using a mobile robot in a real-world environment.     

Simplified map representation and map learning system for autonomous navigation of mobile robots

Autonomous mobile robots need environmental maps to navigate to specific destinations, but there are difficulties in generating and acquiring efficient maps for them. Map learning systems and map representation for autonomous robot navigation are highly interrelated and need a total system design that combines these two factors. This study considers a combined simple map representation and map learning system. The proposed map representation includes geometrical relationships between important places and grid maps for these places, but not a total grid map of the environment. In particular, the study focuses on the ability to recognize places based on image features. Successful experiments on autonomous navigation with the proposed map representation using an actual mobile robot are described.     

Building maps of indoor environments by merging line segments extracted from registered laser range scans

The recent trend of deploying mobile robots in large indoor environments calls for development of efficient map representation techniques. Compared to the more common occupancy grid representation, maps built with line segments are more compact and scale well with the environment size. In this paper, we propose an offline method for building maps of indoor environments using line segments extracted from registered laser range scans. At the core of this method lies a new formulation for identifying and then merging into one, all line segments that represent the same planar surface in the environment. Two successive steps of density-based clustering, applied on the extracted segments, enable us to delineate the segments that are in close proximity to each other and hence represent the same surface. The proposed method has accurately built maps of a wide variety of indoor environments, both real and simulated. Compared to two other similar methods, it has generally produced better maps. We also propose ways by which the goodness of the produced maps, in terms of how closely they resemble the ground truth, can be assessed.     

Enhanced-spectrum-based map merging for multi-robot systems

This paper addresses the problem of grid map merging for multi-robot systems, which can be resolved by acquiring the map transformation matrix (MTM) among robot maps. Without the initial correspondence or any rendezvous among robots, the only way to acquire the MTM is to find and match the common regions of individual robot maps. This paper proposes a novel map merging technique which is capable of merging individual robot maps by matching the spectral information of robot maps. The proposed technique extracts the spectra of robot maps and enhances the extracted spectra using visual landmarks. Then, the MTM is accurately acquired by finding the maximum cross-correlation among the enhanced spectra. Experimental results in outdoor environments show that the proposed technique was performed successfully. Also, the comparison result shows that the map merging errors were significantly reduced by the proposed technique.     

Growing a hypercubical output space in a self-organizing featuremap

Neural maps project data from an input space onto a neuron position in a (often lower dimensional) output space grid in a neighborhood preserving way, with neighboring neurons in the output space responding to neighboring data points in the input space. A map-learning algorithm can achieve an optimal neighborhood preservation only, if the output space topology roughly matches the effective structure of the data in the input space. We here present a growth algorithm, called the GSOM or growing self-organizing map, which enhances a widespread map self-organization process, Kohonen's self-organizing feature map (SOFM), by an adaptation of the output space grid during learning. The GSOM restricts the output space structure to the shape of a general hypercubical shape, with the overall dimensionality of the grid and its extensions along the different directions being subject of the adaptation. This constraint meets the demands of many larger information processing systems, of which the neural map can be a part. We apply our GSOM-algorithm to three examples, two of which involve real world data. Using recently developed methods for measuring the degree of neighborhood preservation in neural maps, we find the GSOM-algorithm to produce maps which preserve neighborhoods in a nearly optimal fashion.     

Generating Tile Maps

Tile maps are an important tool in thematic cartography with distinct qualities (and limitations) that distinguish them from better‐known techniques such as choropleths, cartograms and symbol maps. Specifically, tile maps display geographic regions as a grid of identical tiles so large regions do not dominate the viewer's attention and small regions are easily seen. Furthermore, complex data such as time series can be shown on each tile in a consistent format, and the grid layout facilitates comparisons across tiles. Whilst a small number of handcrafted tile maps have become popular, the time‐consuming process of creating new tile maps limits their wider use. To address this issue, we present an algorithm that generates a tile map of the specified type (e.g. square, hexagon, triangle) from raw shape data. Since the ‘best’ tile map depends on the specific geography visualized and the task to be performed, the algorithm generates and ranks multiple tile maps and allows the user to choose the most appropriate. The approach is demonstrated on a range of examples using a prototype browser‐based application.     

基于ORB-SLAM2的实时网格地图构建

针对目前视觉SLAM（同时定位与地图构建）系统只能输出相机的运动轨迹图而不能生成用于路径规划和导航地图的缺点,提出了一种基于ORB-SLAM2的网格地图实时构建算法。首先,建立了一个适用于视觉SLAM的逆传感器模型（inverse sensor model,ISM）;针对ISM模型重新编排了网格地图算法的构建机制,并对其进行详细推导;最后,介绍了ORB-SLAM2网格地图构建的具体实施方案。通过实验,对ISM模型和网格地图模型进行分析,确保了算法的可行性;用单目相机和RGB-D深度相机进行实时实验,实现了网格地图的实时构建,且能够清晰地显现出障碍物位置,验证了所提算法的有效性。     

实时更新的全局一致三维栅格建图

在未知的三维环境中,移动机器人自主导航通常需要实时构建与环境全局一致的栅格地图,而现有大部分系统缺少地图更新策略,构建的栅格地图与实际环境不一致.文中将同步定位与建图模块获得的环境信息以点云形式提供给栅格建图模块处理,同时提出基于关键帧的高效数据结构和地图实时更新策略,实时构建可用于移动机器人自主导航的全局一致的地图.室内动态的实验数据测试表明,文中方法可以有效实时更新地图,生成与环境一致的三维栅格地图,支持其后续的自主导航操作.     

基于激光雷达的动态障碍物实时检测

动态障碍的存在直接影响到环境地图的构建精度,可靠实时地检测出动态障碍物是未知环境下移动机器人构建环境地图的根本前提。基于2D激光雷达传感器,提出了一种移动机器人在未知环境下实时检测动态障碍物的方法。将激光雷达的观测数据经过滤波映射到世界坐标系,构建相邻采样时刻的三幅栅格地图;判断相邻时刻三幅栅格地图上对应栅格的占用状态,确定环境中的静态障碍物,以静态障碍物为参考,根据当前的栅格地图可以检测出环境中的动态障碍物。基于激光雷达时空关联性分析,采用八邻域滚动窗口的方法处理不确定性因素。在实际移动机器人MORCS-1上进行的实验结果表明,该方法可使移动机器人准确有效地检测出未知环境中的动态障碍物,实时性好,可靠性高。     

基于轮式机器人的实时3D栅格地图构建

移动机器人在各种任务中需要进行建图、定位和路径规划，但是目前的视觉SLAM只能输出相机的运动轨迹图，而不能生成用于路径规划和导航的地图。因此，在ORB_SLAM2的基础上，与RGB-D相机相结合，提出了一种实时3D栅格地图构建算法。建立了一个逆传感器模型（Inverse Sensor Model，ISM）；针对ISM模型，重新构建了3D栅格地图的算法；联合ORB_SLAM2进行数据集实验、仿真环境实验和实时构建实验。经实验验证，该算法能够利用ORB_SLAM2实时构建出具有尺度的3D栅格地图，且能够清晰地显示障碍物位置，验证了该算法的有效性。     

Use of an automatic content analysis tool: A technique for seeing both local and global scope

This paper examines what can be learned about bodies of literature using a concept mapping tool, Leximancer. Statistical content analysis and concept mapping were used to analyse bodies of literature from different domains in three case studies. In the first case study, concept maps were generated and analysed for two closely related document sets—a thesis on language games and the background literature for the thesis. The aim for the case study was to show how concept maps might be used to analyse related document collections for coverage. The two maps overlapped on the concept of “language”; however, there was a stronger focus in the thesis on “simulations” and “agents.” Other concepts were not as strong in the thesis map as expected. The study showed how concept maps can help to establish the coverage of the background literature in a thesis. In the second case study, three sets of documents from the domain of conceptual and spatial navigation were collected, each discussing a separate topic: navigational strategies, the brain's role in navigation, and concept mapping. The aim was to explore emergent patterns in a set of related concept maps that may not be apparent from reading the literature alone. Separate concept maps were generated for each topic and also for the combined set of literature. It was expected that each of the topics would be situated in different parts of the combined map, with the concept of “navigation” central to the map. Instead, the concept of “spatial” was centrally situated and the areas of the map for the brain and for navigational strategies overlaid the same region. The unexpected structure provided a new perspective on the coverage of the documents. In the third and final case study, a set of documents on sponges—a domain unfamiliar to the reader—was collected from the Internet and then analysed with a concept map. The aim of this case study was to present how a concept map could aid in quickly understanding a new, technically intensive domain. Using the concept map to identify significant concepts and the Internet to look for their definitions, a basic understanding of key terms in the domain was obtained relatively quickly. It was concluded that using concept maps is effective for identifying trends within documents and document collections, for performing differential analysis on documents, and as an aid for rapidly gaining an understanding in a new domain by exploring the local detail within the global scope of the textual corpus.     

Finding the right pixel size

This paper discusses empirical and analytical rules to select a suitable grid resolution for output maps and based on the inherent properties of the input data. The choice of grid resolution was related with the cartographic and statistical concepts: scale, computer processing power, positional accuracy, size of delineations, inspection density, spatial autocorrelation structure and complexity of terrain. These were further related with the concepts from the general statistics and information theory such as Nyquist frequency concept from signal processing and equations to estimate the probability density function. Selection of grid resolution was demonstrated using four datasets: (1) GPS positioning data—the grid resolution was related to the area of circle described by the error radius, (2) map of agricultural plots—the grid resolution was related to the size of smallest and narrowest plots, (3) point dataset from soil mapping—the grid resolution was related to the inspection density, nugget variation and range of spatial autocorrelation and (4) contour map used for production of digital elevation model—the grid resolution was related with the spacing between the contour lines i.e. complexity of terrain. It was concluded that no ideal grid resolution exists, but rather a range of suitable resolutions. One should at least try to avoid using resolutions that do not comply with the effective scale or inherent properties of the input dataset. Three standard grid resolutions for output maps were finally recommended: (a) the coarsest legible grid resolution—this is the largest resolution that we should use in order to respect the scale of work and properties of a dataset; (b) the finest legible grid resolution—this is the smallest grid resolution that represents 95% of spatial objects or topography; and (c) recommended grid resolution—a compromise between the two. Objective procedures to derive the true optimal grid resolution that maximizes the predictive capabilities or information content of a map are further discussed. This methodology can now be integrated within a GIS package to help inexperienced users select a suitable grid resolution without doing extensive data preprocessing.     

兵棋地图快速数字化算法的研究与实现

手工兵棋电子化过程中一个重要的方面就是兵棋地图的数字化,而兵棋地图数字化的基础工作就是地图网格化以及网格定位。在兵棋系统中,为了减小误差,一般采用六角网格覆盖原始地图的方法来实现地图的网格化。在实际推演过程中,作战地图覆盖范围一般很大,那么怎样提高网格化以及网格定位效率就成了地图数字化过程中必须考虑的问题。文章描述了一种效率很高的六边形网格绘制算法,并提出了基于元启发式方法的快速地图网格定位算法,它的时间以及空间复杂都仅有O（1）,能够很好的满足兵棋系统中超大地图数字化的要求。