Keywords

1 Introduction

Although home cleaning robots (HCRs) are the most popular service robots used in domestic, the coverage rate, overlap rate and efficiency often hamper their user acceptance [1]. To solve this problem, the HCR should be able to build the map autonomously [2] and locate itself within the map simultaneously [3]. These two tasks are called the Simultaneous Localization and Mapping (SLAM). In this paper, we focus on proposing an efficient SLAM algorithm.

The researchers have developed out a lot of creative solutions about localization after years of researches [4,5,6,7,8]. Biswas [4] proposed a WiFi localization algorithm that used Monte Carlo localization with Bayesian filtering. The localization error at a mean of 1.2 m was too large for HCRs. Gutmann [5] discovered that all of the wireless signals exist multipath and attenuation, due to the domestic environment contains multiple walls and barriers consisting of different materials. Segura [6] proposed an ultra-wideband (UWB) based localization system that solved the multipath identification problem owing to its high bandwidth. Cho [7] presented a dead reckoning localization algorithm with the rotary encoders and the inertial navigation system to reduce the accumulation errors. However, the existing localization methods all have limitations in practical domestic environments [8], such as low localization accuracy, high cost and so on.

Meanwhile, there are many possible ways have been proposed to represent the environment map [9]. The map representations can be categorized into two classifications. One is grid map [10,11,12] and the other is feature map [13,14,15]. The constructed map was modeled with a coarse-grain occupancy grid [10, 11]. Each square cell was of the size of sweeping tool and the partially covered cells were marked as real barriers. So this method was not accurate enough to describe the real environment. A few years later, Lee [12] adopted a high-resolution grid map representation with small cells, leading to a higher degree of freedom. There were also some grid maps that used the grids to store the environment image information [16] or the geomagnetic filed information [17, 18]. In spite of the information can be used to improve the localization accuracy, it doesn’t get rid of the problem of demanding large storage size. The feature map was put forward as an alternative method of grid map at first, becoming research hotspot recently. Pfister [13] first provided a weighted line fitting algorithm to fit a line segment, which was adapted to most domestic environments. An [14, 15] proposed a line segment based map which was a compact map representation even in a cluttered environment. But the raw data, which was obtained from laser range finder, required a series of steps to get line segment [19]. The vector map is an advanced form of feature map, due to vector is a directed line segment [2] and the vector map has the same representation capability as grid map and topological map [20]. Compared to the feature map, its main advantage is that it simplifies the discrimination of barrier kinds [21].

The combined map [2, 9, 22] has been put forward nearly twenty years. Thrun [22] proposed the metric-topological map which was implemented by partitioning the grid map into coherent regions and building topological maps on the top of the regions. Due to the irregular shape of regions, it isn’t possible to realize intelligent cleaning. Sohn [2] used a topological map as the robot trajectory to import the loop closing method to the mapping algorithm. In this paper, although some figures were a combination of topological map and vector map, there was no reference and application of combined map from start to the end. In the survey of Jelinek [9], the topological-metric map was considered to be a good representation in the nearest future.

It must be stressed that only in few papers that the SLAM problem was addressed with limited sensors. Abrate [23] proposed an EKF-based SLAM to enhance the autonomy of the educational robots with eight infrared range sensors only. Choi [19] presented a line feature based SLAM applied to a HCR to realize real-time control with low computing load. Although the sensor data of the two approaches was sparse and noisy, the amount of data was reduced significantly making it possible to use complicated algorithm. But the map accuracy was not enough for intelligent cleaning due to low data precision. Thus, partitioning algorithm [1, 2, 24] was used in the SLAM to improve the localization accuracy for low cost HCRs. Lee [1] proposed the incremental sector creation method which was proofed that the smaller sector could improve localization accuracy. Beak [25] used the sweep-invariant decomposition (SID). But the adjective cells should be merged together considering the efficiency. Dugarjav [24] modified the SID with oriented rectilinear decomposition which decomposed the map according to the exploring procedure and the longer boundary of the cell. Myung [26] decomposed the domestic environment into sub-regions based on the feature of map. And it used the photographs of rooms taken by CMOS camera. Although the above algorithms are based on the grid maps, we can refer the theory and then apply it to the new map representation.

The rest of this paper is organized as follows. Section 2 introduces the combined localization system and Sect. 3 explains the proposed direction control system and data acquisition algorithm. After that, Sect. 4 presents the topological-vector map building approach. Then, Sect. 5 presents the setup and results of simulations for verifying the proposed algorithm. Finally, we state the conclusion and future work in Sect. 6.

2 Combined Localization System

To generate a compact data structure and improve the localization accuracy, a multi-layer system is proposed. It’s composed of three layers form low to high, the data collection layer, the map building layer and the data association layer. It’s shown as Fig. 1.

Fig. 1.
figure 1

The architecture of multi-layer system.

Full size image

The true SLAM is difficult to realize without the aid of precise localization. So a combined localization system which is composed of dead reckoning localization and the UWB localization is proposed. The model of local localization is defined as follow:

$$ P_{i + 1} = P_{i} +\Delta P = \left[ {\begin{array}{*{20}c} {x_{i} } \\ {y_{i} } \\ {\theta_{i} } \\ \end{array} } \right] + \left[ {\begin{array}{*{20}c} {\Delta x} \\ {\Delta y} \\ {\Delta \theta } \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} {x_{i} } \\ {y_{i} } \\ {\theta_{i} } \\ \end{array} } \right] + \left[ {\begin{array}{*{20}c} {\int_{{t_{i} }}^{{t_{i + 1} }} {\frac{{v_{r} + v_{l} }}{2}dt\,\cos (\theta_{i - 1} + \int_{{t_{i} }}^{{t_{i + 1} }} {\frac{{2(v_{r} - v_{l} )}}{W}} dt)} } \\ {\int_{{t_{i} }}^{{t_{i + 1} }} {\frac{{v_{r} + v_{l} }}{2}dt\,\sin (\theta_{i - 1} + \int_{{t_{i} }}^{{t_{i + 1} }} {\frac{{2(v_{r} - v_{l} )}}{W}} dt)} } \\ {\int_{{t_{i} }}^{{t_{i + 1} }} {\frac{{2(v_{r} - v_{l} )}}{W}} dt} \\ \end{array} } \right] $$
(1)

where t i is the time arrive at the previous point, t i+1 is the time arrive at the present point, v r and v l are the speeds of the right wheel and left wheel respectively, and W is the width between two wheels. The speed is calculated according to the sensor data of rotary encoder as follow:

$$ \left\{ {\begin{array}{*{20}l} {v_{r} = 2\pi \cdot R \cdot \frac{{M_{r} }}{N}} \hfill \\ {v_{l} = 2\pi \cdot R \cdot \frac{{M_{l} }}{N}} \hfill \\ \end{array} } \right. $$
(2)

where R is the radius of the active wheel, N is the pulse generated while the wheel rotates 360 degrees, M r and M l are the measured pulse number of left encoder and right encoder per second respectively.

The standard of IEEE P8021.5 presented a path loss model for indoor UWB signals of nominal center frequency of 5 GHz. The signal can penetrate one wall to maximum of 4 walls and the maximum effective distance is 20 m, enough for most families. But the localization accuracy will be decreased as the number of penetrating walls increasing. The accuracy after penetrating two walls still reaches the requirement. Thus, the transmitters are fixed at the center of ceiling of each room, the farthest 4 corners of the home and one receiver is installed on the HCR. So the required number of transmitters to ensure accuracy can be as few as possible. Furthermore, the absolute positions of transmitters should be measured before stimulation. The signals that meet the required strength are chosen to calculate the position in the global coordinate:

$$ d = \frac{\alpha }{n}\sum\limits_{i = 1}^{n} {\frac{1}{{^{{10^{{\frac{{P_{i} - PL_{1} + S}}{10\gamma }}} }} }}} $$
(3)

where P i is the signal strength which the receiver receives from the i th transmitter. PL 1 is a constant that represents the loss of received signal strength at 1 m to the transmitter. The parameter γ has different values of different regions and obeys a normal distribution \( N[\mu_{\gamma } ,\sigma_{{_{\gamma } }} ] \).

The global position G = (x g ,y g ,θ g ) is got by solving the above equation every time when the robot arrives at a new turning point. Then, it is compared with the local position P i  = (x i ,y i ,θ i ) that is obtained by relative localization algorithm. If the position deviation Δd is bigger than the threshold σ or the orientation deviation Δα is larger than the threshold δ, the global position will be used to replace the local position.

3 Direction Control System and Data Acquisition Algorithm

3.1 Direction Control System

HCR uses the sensor data to control the behavior of the robot. According to the data generated by the sensor system composed of eight infrared range sensors and one ultrasonic sensor, the basic control system is produced. There are a total of 256 kinds of states, shown as Table 1.

Table 1. The different states of eight infrared range sensors.
Full size table

The state is calculated as follow:

$$ S_{i} = \sum\limits_{j = 1}^{8} {2^{{I_{ij} }} } $$
(4)

where I ij is the j th infrared range sensor signal at state i. When the signal level is high, it indicates that there is a barrier in this direction. According to the state S i , the HCR decides which direction should go. The direction control system will be performed from the start to the end of the map building process. In addition, according to combined localization system which can help the robot to confirm its position, the specific control flow is shown as Fig. 2.

Fig. 2.
figure 2

The control flow of the direction control system.

Full size image

3.2 Data Acquisition Algorithm

The outline data acquisition method only records points that the direction of cleaning robot changes. It is based on the right hand rule and wall following method. According to whether there is a barrier in front, the data points are sorted into two types, convex points and concave points. The storage form of point is defined as follow:

$$ p_{i} = \left[ {(x_{i} ,y_{i} ),\theta_{i} ,o_{i} ,c_{i} } \right]\quad i = 1,2, \ldots . \ldots ,n. $$
(5)

(x i ,y i ) is the current position of robot, θ i is the current direction of robot, o i is the sequence number of points and c i represents the type of points.

The inside data acquisition method collects the data of inside barriers when the outline data acquisition is completed. The ideal domestic environment is that the barriers inside are composed of simple geometric shapes. If a new barrier is found, it will be appended to the end of inside barrier list. When multiple barriers encountered at the same time, the barriers are recorded from right to the left. According to the Euclidean distance, the robot computes the distance to each not searched barrier in the list to find the nearest barrier to search. When a data collection of a barrier is over, the barrier will be marked as searched. Then the end of the inside data acquisition is all of the barriers have been found. The search of different barriers is shown as Fig. 3:

Fig. 3.
figure 3

The search of the inside barriers: (a) Triangle barrier, (b) Rectangle barrier, (c) Other polygons between (b) and (d), (d) Circle barrier.

Full size image

4 Topological-Vector Map Building Approach

4.1 Vector Generating Method

According to the proposed specialized data acquisition algorithm, the vector is generated by connecting the collected data according to the time stamp t i . The vector, \( v_{i}^{t} \in M^{t} \), at time t, is defined as follow:

$$ v_{i}^{t} = \left[ {\left( {x_{i} ,y_{i} } \right),l_{i} ,\alpha_{i} ,\sigma_{i} } \right] $$
(6)

where (x i ,y i ) are the start points, l i is the length, α i is the direction of the vector and σ i is the standard deviation.

4.2 Curve Fitting Method

Most of the objects of domestic environments, like furniture and walls, can be compassed with lines in two-dimensional map. And the curves can also be spliced with short line segments. So the vector is used as the minimal element to build the environment map. When the simple line segment fitting method is used according to the fitting coefficient, a more satisfactory result is obtained. Thus, a curve fitting method that based on short lines is selected.

4.3 Partitioning Algorithm

The proposed partitioning algorithm is mainly based on the geometric relation. Here are three basic steps:

  1. 1.

    Extract all the concave points from the outline points set P1. When it is an isolated point, the neighboring convex points are added to the list guaranteeing that there are at least two points.

  2. 2.

    Generate the linear equation with neighboring points belong to the same cluster.

  3. 3.

    Divide into sub-regions according to the geometric relation of the extracted vectors. The geometric relation just includes parallel and vertical.

4.4 Topological Relation Building Algorithm

Although the data amount of map is greatly reduced after the data acquisition algorithm, it still takes a great deal of time to perform the cleaning task. The proposed topological relation algorithm is based on the connectivity among the generated region nodes and the extracted turning nodes. The region node stores the entrance position and the information of including vector of the corresponding region. The turning node merely stores the turning points and the topological relations of connected nodes.

4.5 Map Updating Algorithm

In order to have a real-time map for exact path planning, the map is rebuilt every time before cleaning. But the majority regions remain the same, the rebuilding of total map is a waste of time. Therefore, a quick map updating method that only redraws the regions which have a relatively significant change is proposed. Whether the local map needs to rebuild, the referred formula of changing rate is as follow:

$$ Rl_{j} = k\frac{m}{n} + (1 - k)\sum\limits_{i = 1}^{m} {\frac{{o_{i} }}{O}} \quad j = 1,2, \ldots . \ldots h $$
(7)

where n/O is the total number/area of barriers and m/o i is the number/area of barriers that position has changed. k and (1-k) are the weights of the number and area of barrier respectively. If Rl j is bigger than the threshold, the local map of region j will be rebuilt. According to the Formula (7), the global updating formula is as follow:

$$ R_{g} = \sum\limits_{j = 1}^{h} {\frac{{Rl_{j} }}{h}} $$
(8)

where h is the number of sub-regions.

4.6 Autonomous Learning Algorithm

The real map is difficult to build by exploring the environment only one time. So we propose an autonomous leaning system based on the two regular behaviors. First, the HCR usually does the cleaning task at least once a day. Second, the complexity of different regions is different. So the regions are treated respectively to improve the efficiency of map building. The formula is as follow:

$$ t_{i} = k_{1} \frac{{l_{i} }}{{S_{i} }} + k_{2} \frac{{sl_{i} }}{{S_{i} }} + K\quad i = 1,2, \ldots . \ldots h $$
(9)

t i is the times of the region i that the HCR should explore. l i and sl i are the numbers of long and short line segment respectively. S i is the area of the region i. k1, k2 and K are constants obtained by experiment.

5 Simulations

5.1 Simulation Setup

Although the simulation is different from real experiment fundamentally, we do our best to make it as close to the real environment as possible. A differential-drive cleaning robot is used as the basement of the simulation. The arrangement of sensors is shown as Fig. 4.

Fig. 4.
figure 4

The sensor configuration of home cleaning robot experiment platform.

Full size image

5.2 Simulation Results

The evaluation of combined localization.

Reliability: In this test, the HCR stops at 20 randomly chosen positions on the map. Figure 5(a) shows a plot of the localization error e at different points. There are two relatively higher points. But all the errors are within 0.08 m. Then the test is performed 10 times to compute the standard deviation σ. The result is shown in Fig. 5(b), with a slight fluctuation around 0.05 m. Both of the results prove the reliability of the proposed localization method.

Fig. 5.
figure 5

The evaluation of combined localization.

Full size image

Accuracy: In this test, the robot again stops at 20 randomly chosen positions on the map. The mean estimated position is used to compare with the real position to eliminate the slight oscillation. The combined localization method shows the best accuracy with a mean error of 5 cm, shown as Fig. 6.

Fig. 6.
figure 6

Mean position error over all nine runs with average in parentheses.

Full size image

The evaluation of topological-vector map.

The vector map that changes from the grid map of SDR site B of University of Southern California was used for simulation, shown as Fig. 7(a) (http://radish.sourceforge.net/). Figure 7(b) is the converted original vector map composed of 458 vectors. It mainly consists of 6 sections according to the continuity of barrier.

Fig. 7.
figure 7

The map used for simulation.

Full size image

Because of the complexity of the environment, some regions of the constructed map are unexplored, shown as Fig. 8. However, the unexplored regions are almost found based on the proposed autonomous learning method with the increase of cleaning times. The ultimate constructed map agrees well with the real environment. In Fig. 9, a topological-vector map built with the proposed TVSLAM is shown. The topological map and vector map are linked through the turning nodes which belong to both of them.

Fig. 8.
figure 8

A comparison between the constructed map and the real environment.

Full size image
Fig. 9.
figure 9

The constructed topological-vector map.

Full size image

The proposed map representation has a lot of excellent performances compared with grid map and vector map, shown as Table 2. The memory size reduces to 13.96% of the vector map and 6.75% of the grid map significantly. And the consumption time also reduces by 56.93% of the grid map and 13.53% of the vector map.

Table 2. A comparison of memory and consumption time among different map representations.
Full size table

As a result, the constructed topological-vector map is accurate enough for the HCRs to perform cleaning task. And the amount of data is fewer and computation burden is lighter compared to other map representations. Meanwhile, the data of the map has a high degree of data association used by the robot to realize accurate localization.

6 Conclusion and Future Work

In this paper, a TVSLAM algorithm which builds a topological-vector map for HCRs is presented. Compared to grid map or vector map, the new map representation based on the proposed data acquisition algorithm requires relatively smaller amount of memory and shorter map building time. Meanwhile, the map stores the environment data based on a multi-layer system which promotes the realization of real-time control. In addition, a new combined localization method which shows the best localization accuracy with an average error of 5 cm in simulation environments is presented. Furthermore, the proposed map updating algorithm avoids rebuilding the total map every time and increases the speed of map building. Finally, the application of autonomous learning algorithm makes the constructed map closer to the real environment gradually. Simulation results show that the TVSLAM algorithm is an efficient and robust online localization and mapping algorithm which is suitable for majority of the domestic environment. However, the environment of the simulation is relative simple compared to the real environment. As future work, we would like to improve the TVSLAM algorithm and then apply it on a HCR in the real world.