Keywords

1 Introduction

The environment map construction robot is one of the basic links for navigation, there are many scholars research on robot map building problems, common environmental map representation of geometric feature map and grid map, the topological graph, the grid map can be more vivid characterization of environmental space and uncertainty, but limited to the environment size; geometry map can express simple environment for complex environment is difficult to say; topological map does not need to know the scale of specific information, which can be characterized as a connection between the specific points in the environment and specific location, suitable for robot path planning and navigation, but the process of constructing the topological map is relatively complex. There are many shortcomings are trying to map building method to characterize the mixed environment to make up a single environment map representation methods, such as Thrun S and grid map topology combined with the grid construction of indoor topological graph [1], completes the construction of Hybrid Map [2] solemn and Xu Xiaodong according to the geometry and topology of the environment model, but to accurately describe the environment the structure requires a large amount of data in the robot navigation process will produce a lot of search and data storage of [3].

Self-organizing feature map (Self-Organizing Map, SOM [4] can imitate the human brain map) feature mapping function, has the high dimensional input space to a low dimensional space compression mapping neural computing function and keep the input space topological invariant features. Vlassis [5] using the robot position as samples, topological map building indoor environment using SOM and its application in robot path planning, but the topological map errors that exist neuronal connections between neurons through the connecting wire obstacles may mislead the robot into the obstacle in the navigation process. Derived from SOM GCS (Growing Cell Structure) [6], GSOM (Growing Self-Organizing Map), [7] (Growing Neural Gas, GNG [8]) without prior design of the number of nodes, and will expand as the input of the network scale grows. The network structure and node generation control conditions adopted by them are different, but they are trained by the best matching and neighborhood weight correction method. The author in previous work can increase the self-organizing map GSOM algorithm is applied to the algorithm in [9] modeling environment, constantly adding new neuron self drawn topological map, and on the desktop robot maze physical experiment system is verified on the [3]. Yan et al. [10] use GNG neural networks (Growing Neural Gas) to build indoor environmental cognitive maps, and obtain topological maps which can describe environment accurately. Both GSOM and GNG can determine the optimal number of SOM neurons describing the environmental features under the condition that the number of samples is unknown, and a more accurate environment map can be established. But the growth of their neurons is very slow, and it is not suitable for occasions with high time requirements.

In view of the problem of the connection between neurons and neurons in the map created by the fixed SOM neural network, a SOM graph algorithm with PSOM structure is proposed. The algorithm first uses SOM neural network to create a topological map of the environment preliminary, then the wrong neurons and neurons connect line topology map to find, finally removing errors of neurons and segment may be an accurate description of the topological map of the environment. Compared with the GSOM diagram, the SOM graph and the GSOM algorithm can accurately represent the environment topology, but the convergence time is greatly reduced.

2 Relating Work

2.1 SOM Algorithm

In 1982, Kohonen proposed an organization feature map called simply SOM, SOM, or SOM neural networks. Figure SOM neurons with structure of feedforward and feedback the dimension of the input vector is arbitrary, the dimension of the output layer usually has only one or two dimensional form, operation mechanism of SOM graph contains 3 important aspects: competition, collaborative links and synaptic adaptive link.

figure a

In If the sample collection Sample = {S1, S2, …, S n } has been previously obtained, where S i (i = 1, 2 , …, N) is the i sample point, then the algorithm using SOM chart algorithm, see Algorithm 1.

From the implementation of the algorithm, we can see that the self-organizing process of SOM diagram can be divided into a “competition, coordination and adaptation” process.

2.2 Environment Representation with SOM

Figure 1 is the indoor environment at Beijing University of Technology’s 1101 laboratory. The black area in the diagram is the barrier area.

Fig. 1.
figure 1

Indoor environment

Full size image

The indoor mobile robot has a ranging sensor, and the robot body is equipped with an indoor positioning system to obtain the position information of the mobile robot.

First let the robot traverse the interior, and the robot will return its position coordinates at intervals of sampling time as Si(i = 1, 2, …, N) and finally get the set of sample points S = {S1, S2, …, Sn}. Figure 2 is the sketch map of sample set.

Fig. 2.
figure 2

Sketch map of sample set

Full size image

The computer used in the experiment simulation is HP dc5850, and the processor is AMD Athlon (TM) Dual core processor 5200B 2.70 GHz, and the simulation software is MATLAB2013b.

The set neuron number is N = 23 * 23 = 529, and the feed forward weight of the neuron takes the random value between 0~1, the maximum number of iterations is T = 400. When t = 0, the effective radius σ0 = 4, κσ = 0.01, the learning rate α0 = 1, κα = 0.01. Using SOM algorithm, after 400 iterations, the running time of the program for the 65.02 s. As shown in Fig. 3, the red line is the edges of obstacles, the small blue circle point out the wrong neurons within the obstacles, the blue line within a ellipse point out a wrong neural connections that cross the obstacles. Indeed, there are 13 such points and 15 such lines, these points and lines are not reachable for the robot. Those errors neuronal connections and neurons led to the representation of topological environment map is not accurate.

Fig. 3.
figure 3

Topological environment map with SOM (Color figure online)

Full size image

Fritzke based on SOM neural network, the growing cell structures (Growing Cell Structures, GCS) of the concept, the structure of records of all cells in the competitive learning in winning times, by comparing the number to change the number of nerve cells, can realize network structure growth.

figure b

The author in the previous work of GSOM (Growing Self-Organizing Map) to construct the topological map for the algorithm, and the results were compared with the SOM algorithm, compared with SOM algorithm; GSOM algorithm can better express the environment. GSOM algorithm has the input samples in each input, to judge the input samples and win SOM neurons weights of the Euclidean distance is greater than a given value of max_d, if it is, is that the SOM map of the size of the current is not sufficient to describe the characteristics of the sampling points, an increase of SOM neurons, and in the near range search can be established the connections between neurons, neurons called adjacent neurons. The adjacent neurons finding Algorithm is shown in Algorithm 2.

The algorithm requires f(n) = num(N1) * (num(N2)−1)2 cycles, and the time complexity of the algorithm is T(n) = O(f(n)). As GSOM runs, the number of neurons increases, and the number of neurons N1 and neuron N2, num(N1) and num(N2) will become larger and larger, which will inevitably cause new neurons to look for their neighboring neurons for longer periods of time.

When the GSOM growth process is over, two training sessions are required to achieve the optimal sample distribution structure description.

The same GSOM algorithm is used to express the environment shown in Fig. 1, set the parameters of growth process: the initial number of neurons was 1, max_d = 0.03, when t = 0, the effective radius σ0 = 0; set the second training process parameters: t = 0, the effective radius σ0 = 0.01, κσ = 0.01, learning rate α0 = 0.01, κα = -0.001. When the program runs for 13.1 h at the end, the environment topology map is shown, as shown in Fig. 4, when the number of neurons is 519. As can be seen from the results, GSOM is more accurate in expressing the environment. Only when the diameter of the obstacle is less than n1*max_d is it possible to pass through the connection between the neurons, which greatly reduces the error. However, as the number of neurons increases, the search for new neurons becomes longer and closer to the neuron, resulting in a long running time for the entire GSOM algorithm.

Fig. 4.
figure 4

Topological environment map with GSOM

Full size image

3 Prunable Self-Organizing Map (PSOM)

GSOM algorithm can describe the environment very well, but its program running time is too long, and the environment represented by SOM diagram is not accurate, but the program running time is much faster than GSOM. You can see from Fig. 3, there are obstacles where the SOM graph is relatively sparse, expressed in neurons and neurons around the Euclidean distance and large, another obstacle in sample neurons distance is far, line length longer neurons connection through the obstacles. According to these features, SOM can be found between the error figure error structure, neurons and neuron connections, the SOM structure is wrong, you can delete the error structure, get the topological map is more precise. Specific algorithms see Algorithm 3.

Based on 1.2 experiments, using the above graph cut SOM error structure algorithm, the threshold parameters DistSumThre = 0.118, DistNeuronSampleThre = 0.004, DistLineThre = 0.1, get the result shown in Fig. 5, with the deletion of SOM map error structure algorithm to find the wrong neuron topology (figure in the “×” mark) and neuron connections (error the blue line), finally cut the final topology error environment map structure is obtained as shown in Fig. 6, we can see that the use of the algorithm to find the number of neurons in error is 13, the error is 12 root connections between neurons, this topology can better express the environment. The running time of the whole algorithm is 68.14 s, which shows that the algorithm runs faster than the GSOM algorithm.

Fig. 5.
figure 5

Wrong neurons and wrong connections result (Color figure online)

Full size image
Fig. 6.
figure 6

Topological environment map with PSOM

Full size image
figure c

4 Conclusion

  1. (1)

    The traditional SOM algorithm and GSOM algorithm have advantages and disadvantages in the topological map building environment, SOM map containing the error structure, can not accurately describe the environment, GSOM algorithm can be a good description of the environment, but its time complexity is too large, causing the program running time is too long, not high efficiency and quick access to the topology map the environment.

  2. (2)

    In the SOM graph, this paper proposes a pruning algorithm of SOM graph structure (PSOM), this algorithm can obtain the environment topology accurately, but compared to the GSOM greatly reduces the running time of the program, is a method for constructing an efficient and accurate environment map.