A hierarchical map building for SLAM used in ruins environments

As to the morphological characteristics of the seismic damage of the interior ruins, this paper presents a map building mechanism by using the analytic hierarchy process and proposes a hierarchical simultaneous localization and mapping (SLAM) algorithm that is based on the hybrid metric-topological map. The architecture of the ruins-oriented SLAM system consists of three layers. In the intermediate layer, the global environment is partitioned on the basis of the spectral clustering that can reduce the computational cost and ensure the global consistency. A semantic map is built in the top layer where the node identification and logic location are included. According to the characteristics of the seismic destruction, an aggregation degree of features is proposed as an identification method for building topological nodes to improve the interactivity. In the bottom layer, details of the morphology of the destruction are described as grid maps that ensure the environmental adaptability. Through experiments, the ability of environmental description and the availability at an artificial ruins environment are verified.


I. INTRODUCTION
The frequent outbreak of natural disasters, such as earthquake, is a serious problem in recent years [1]. The development of autonomous robots for the search and rescue then gradually becomes a hot topic. For a rescue robot, the ability of the localization and mapping is a precondition. The internal environment of ruins which is formed by random seismic damage is complex and unknown. The process of localization and mapping lacks an absolute reference. That is both is highly relevant and constantly iteration, which is the problem of simultaneous localization and mapping (SLAM). SLAM [2] addresses a problem how to acquire the localization of a mobile robot while simultaneously building a spatial map of environment without information about the global position (e.g. GPS).
The research of SLAM gradually extends from the theoretical simulation to the practical application. In terms of the search and rescue after earthquakes, Behdad Soleimani [3] at Tehran University solved the SLAM problems at the external of ruins via the extraction of invariant features from aerial images. To realize the localization and mapping of the rough terrain in narrow canals, a three-dimensional map representation called S-DEM [4] was proposed by Keiji Nagatani. In [5], Alexander Kleiner presented the DSLAM algorithm based on the method of non-selfish sharing of information to execute the rapid rescue while the communication is intermittent.
The above methods, however, did not consider the environmental model based on morphological characteristics of the seismic damage of the interior ruins. As a model of the environment, the map building not only desires an appropriate description for the target environment, but also takes into account the computational complexity of filters.
In this paper, by using the analytic hierarchy process (AHP), a hierarchical SLAM based on the hybrid metrictopological map is proposed. To begin with the division of the environment based on the spectral clustering method in the intermediate layer, the computational efficiency and global consistency are balanced. Then on this basis, details of seismic damage are described as grid maps in the metric layer. In the semantic layer, the damaged structure is recognized by the aggregation degree of corner features to build a semantic map. Finally, the simultaneous localization and mapping of the internal ruins is achieved at different hierarchies.
The rest of this paper is organized as follows. Section II presents the modeling of the internal ruins environments. Section III describes the architecture of the hierarchical SLAM that is based on the hybrid metric-topological map. The implementation of the metric map on bottom layer and the semantic map on the top layer are presented in section IV. Section V presents system experiments and analysis. Finally, some conclusions are summarized.

II. DECISION MODEL OF THE MAP REPRESENTATION OF INTERNAL RUINS ENVIRONMENTS
As one of core issues of SLAM, the map representation determines the estimation method and the data association. A map model for the ruins environment needs to describe the seismic damage inside buildings and simultaneously meets needs of the rescue mission. Based on the analytic hierarchy process (AHP), a building mechanism of the map 978-1-4799-5825-2/14/$31.00 ©2014 IEEE Proceeding of the 11th World Congress on Intelligent Control and Automation Shenyang, China, June 29 -July 4 2014 representation for the interior ruins is analyzed. Then on this basis, an optimal decision of the environment model can be obtained.

A. Analysis of the Irregular Seismic Damage inside Semi-Collapsed Buildings
In this paper, the ruins environment means seismic disasters. The internal environment is composed of severely damaged or completely destroyed building components [6]. The seismic damages are related to the structural type and construction time of buildings, and the intensity of earthquakes. Degrees of seismic damages [7] are divided into five grades. The grades of basically intact, minor damage, moderate damage and seriously destroy are mainly considered in this paper. Among them, the damage degree of bearing members is an especially important criterion to the grade evaluation of the seismic damage of buildings. Therefore, the environmental modeling needs to focus on the seismic damage of the columns and the construction walls. The schematic diagrams of the four destructive grades of building components are shown in Table I. Damaged structures, such as cracks in walls and columns or collapsed deposits, partially appear inside the semi-collapse building, as shown in Fig. 1. The randomized and uneven distribution of damaged structures appears irregular boundary on a two-dimensional plane. Such a complex environmental characteristic requires an appropriate map representation for the SLAM problem.
Besides, because of the large-scale search and urgent time, a SLAM algorithm for the auxiliary rescue or the disaster evaluation should has strong computational capabilities to achieve the rapid localization and mapping.

B. The Decision Model of Map Representation Based on Analytic Hierarchy Process
On the basis of AHP algorithm [8], a building mechanism for the decision model of map representation needs to determine relative weights of the decision criteria and relative rankings of alternatives. The building process is shown in  The model criterion layer is created in accordance with created targets and evaluation criteria of SLAM problem. This layer includes applicability C 1 , accuracy C 2 , computational cost C 3 , and interactivity C 4 . Map representations at the scheme layer are topological map S 1 , metric map S 2 and hierarchical map S 3 . Please refer to [9] for a detailed description of the comparison of alternative map representations.
2) Calculation of Judgment Matrixes and the Single Hierarchical Ranking: The influence from each item of criterion layer to the target is calculated and pairwise compared. And then, the proportion of each criterion is determined to sort the importance.
According the aforementioned analysis of the seismic damages, the pairwise comparisons are calculated to construct a judgment matrix A=(a ij ) n×n . The maximum eigenvalue and eigenvector of A are calculated. And then, the consistency ratio (C.R.) is checked based on C.R.=C.I./R.I.=0.0564<0.1. Among them, C.I. is the consistency index and R.I. is the random index.
Thus, the resulting eigenvector can be the weight vector which means the single hierarchical ranking, as shown in Table II. ω C ={ω C1 , ω C2 , ω C3 , ω C4 }={0.4369, 0.0467, 0.4066, 0.1099}. The single hierarchical ranking of the scheme layer and the criterion layer is calculated in the same way. The weight C S ω is shown in Table III.

3) Decision of the environment model in ruins:
According to the resulting ranking of criterion layer and scheme layer, the weight ω S between each scheme to the target can be calculated based on (1).
The weight of scheme S 3 is the highest. Thus, a hierarchical map representation is the optimal decision of the environmental model. According to the above analysis, a theoretical basis is provided for the hierarchical map representation of SLAM in ruins environments.

III. THE OVERVIEW STRUCTURE OF THE HIERARCHICAL SLAM IN RUINS ENVIRONMENTS
A. The Hierarchy of the SLAM System According to the above decision model of the map representation, the architecture of the ruins-oriented SLAM system based on a hierarchical map is shown in Fig. 4. The architecture is composed of three parts: semantic layer, intermediate layer and metric layer. The intermediate layer includes several sub maps which are obtained by dividing a large scale environment. On each sub map, the damaged structure is identified as a topological node which represents the distribution of damage of walls or columns in the semantic layer. Environmental details inside each sub map are described by occupancy grids.  The building flow of the three layers is shown in Fig. 5. The process is started with the preprocessing of original data which is relative distances from a laser range finder and control instructions of a mobile robot in this paper. After the extraction and estimation, positions of corner features and the robot are achieved. Then, the current environment can be divided into several sub maps based on the spectral clustering. The detail of the sub map is represented as grids by updating the occupy probability in the underlying metric layer. And in the upper semantic layer, on the basis of calculation of the aggregation degree, the damaged structure is identified at each sub map.

B. Environmental partitioning based on spectral clustering
Based on the map segmentation, a large-scale environment is divided into several local regions with an appropriate scale. Through the segmentation, each local region is independent, and therefore the computational cost is reduced. Unfortunately, the inherent connection between local maps is also cut off. Discarding the interregional correlation would affect the accuracy and consistency of SLAM. A pivotal issue is how to balance the computational complexity and the global consistency during the map segmentation.
An environmental partition based on spectral clustering [10][11] is utilized in this paper. According to the similarity of environmental structure, a recursive normalized cut is proposed to obtain local sub maps.
This approach considers each robot's pose as a node of an incrementally built graph whose edge represents the sensedspace overlap (SSO) between two observations which have sensed at each node. The SSO is a pairwise similarity measure which reflects the common space between observations, is defined as: Where M(z t ) stands for the set of map elements sensed in a given observation z t . The map segmentation is then abstracted as an observation graph cut issue.
Finding the exact min-Ncut bisection is a NP-complete problem, thus we use an approximate approach which analysis the spectrum of the Laplacian matrix of the graph based on spectral bisection of graphs. Please refer to [12] for a detail description of spectral bisection of a graph. The whole process of environmental partitioning is summarized as shown in Fig. 6.

IV. IMPLEMENTATION METHODS OF THE HIERARCHICAL MAP BUILDING
A. Topological map building and localization in the top layer 1) Definition of topological nodes: Random earthquakes cause serious damage to the building. The existing methods of node identification are mainly used to identify specific locations of the structured indoor environment, such as walls and doors. Thus, those methods cannot be applied in ruins directly. For missions of rescue and assessment, the damage of bearing members is a main target area. Therefore, we define walls and columns with cracks or breakages and collapsed deposits as topological nodes to construct the semantic space.
Among them, the topological node N is refers to the seismic damage region R i which includes walls and columns with cracks W j and collapsed deposits D k .
2) Identification of topological nodes: In a twodimensional mapping plane, general destructive patterns appear complex boundaries which can be abstracted as a plurality of intersecting line segments. We identify the topological node by the aggregation degree of corner features (intersection point of lines).
Firstly, the iterative end point fit (IEPF) [13] is used to extract the line segment in polar coordinates. The process of feature extraction is expressed as: Wherein, Z 0 is the original observation. l i is the line segments feature and g j is the corner feature. S g is the set of extraction results of corners. Secondly, the aggregation degree of corner feature is used to identify the damaged structure. Density [14] of corner features in the detected area is calculated based on (6).
Wherein, (g) i r refers to the weight which is proportional to the distance from the corner. σis the integration degree of each point.
Special irregular contour of the damaged structure forms a region of dense corner features. Density f(p) of each corner feature is calculated. The function value is proportional to the aggregation degree of corners. The feature which has a greater value than the preset threshold can be joined into the set of damaged structures.

B. Metric map building and localization in the bottom layer
Grid maps which have no specific limitations of the environmental type are used to describe details of seismic damage morphology and ensure the accuracy.
Bayesian estimation is used to iteratively update the probability of occupancy grids. The initial state of grids is determined according to the expression range and detection accuracy of the laser range finder [15]. The state of grid is updated by "odds" on the updated phase. And the formula of iteratively update is expressed as: Among them, ( ) , | ,

V. EXPERIMENTS AND ANALYSIS
The effectiveness of the proposed hierarchical SLAM is verified in two environments. As shown in Fig. 7, a shape shifting search and rescue robot AMOEBA-I which carries a laser scanning distance sensor URG-04LX is used in these experiments. The sensor is carried on the middle module of the robot. The height of sensor from ground is about 35 cm. The distance range of the measure is 4 m and the angular range is 240 degree. The ability of the hierarchical map model to describe irregular obstacles is verified in an office environment. This is a cluttered indoor environment. Legs of chairs and tables, books and cardboard boxes on the ground are randomly distributed which appear complex contours on the observation plane. The result of SLAM algorithm on the bottom metric layer is shown in Fig. 8. According to partial enlarged views, grid maps can accurately depict the complicated shape that means it can completely describe irregular obstacles within a clutter environment. Therefore, the map representation is appropriate for the expression of the interior of ruins environment.

B. Experiment II
In order to simulate the afflicted scene after earthquakes, an artificial ruins experimental environment is constructed according to the seismic damage morphology. The correspondence between damage structures is shown in Fig. 9. Crevices in the wall are simulated by gaps between cartons. And the broken building components are randomly stacked on both sides of the corridor to simulate the local collapsed deposits. The experimental result illustrates that the algorithm can accurately describe the environmental structure. In this paper, a hierarchical map is used for the robot environmental modeling. The semantic map provides the distribution of damaged structures for the less complexity. A grid map is used in each partition to represent details of the irregular obstacles. On the premise of ensuring the computing power, a composite map is built to identify and describe the damaged structure.

VI. CONCLUSION AND FUTURE WORKS
Facing the search and rescue after earthquakes, a decision model of the map representation based on analytic hierarchy process has been proposed, according to the random seismic characteristics of the bearing members inside a semi-collapsed building. A collection of environmental expression was built by using the proposed hierarchical representation based on the hybrid metric-topological map. The environment was divided into sub maps on the basis of spectral clustering algorithm. Then, damaged structures were identified as semantic nodes and seismic damaged shapes were described as occupancy grids in each partition. Experimental results in a cluttered indoor environment and an artificial ruins environment were presented to verify the efficiency and applicability of the algorithm. To further improve the reliability and robustness of SLAM for actual search and rescue, we will pay more attention to the extensive application of multi perception information such as visual information and 3 dimensional point cloud data in the future.