Sage Journals: Discover world-class research

Abstract

This article proposes an experience-based route map continuous learning method and applies it into robot planning and navigation. First of all, the framework for robot route map learning and navigation is designed, which incorporates the four cyclic processes of planning, motion, perception, and extraction, enabling robot to constantly learn the information of the road experience and to obtain and improve the route map of the environment. Besides, a growing-on-demand self-organizing neural network learning algorithm is also proposed. This algorithm is based on growing neural gas algorithm, but it does not require presetting of network scale, and under the condition of dynamically growing input data, it can regulate the increase scale of network online in a self-adaptive and self-organized manner to obtain stable learning results. Finally, with robot roaming in an environment, this algorithm is used to conduct continuous learning of dynamically increasing route information, extract the topological structure of the raw road data in feature space, and ultimately obtain the route map of the environment. Mobile robot utilizes the route map to plan a suitable route and guides robot to move to the destination along the route and complete navigation task. Through physical experiments in outdoor environment, its feasibility and validity are verified.

Keywords

Route-based navigation route map self-organizing neural network continuous learning growing neural gas

Introduction

Human beings and animals exhibit superior capabilities in spatial cognition and navigation even in a complex large-scale environment or without complete and accurate perception information. This motivates robot researchers to pay close attention to biological working mechanisms that can be implemented on an autonomous mobile robot, so as to improve the navigation and motion ability of robots.^1
–3 As an important kind of behavioral strategy in human navigation, route-based navigation strategy has been used in autonomous mobile robots, that is, a process of using real-time perceived environment information and self-motion ability to reach the destination along the preset route.^4
–6 Route serves as the basis of route-based navigation strategy, represented as a sequence of decision points, and considered as a part of the spatial knowledge.⁷ The integration of different routes forms a network-like structure, called route map, which can represent complex and large-scale navigation environment. The building of route map serves as an important stage in human environment perception process, in which human beings, through individual experience, use routes to connect scattered landmarks to form a route network. Route map can show navigation-related environment structure features and reflect the overall human understanding of environment, so it is suitable for route planning, autonomous navigation, spatial knowledge reasoning, and so on.

At present, the researches on route map are focused on route map representation and route map–based planning and navigation.^8

–12 Hybrid map, integrating metric information and topological information, is the major representation model of route map.^13
–15 This model expresses route map as a graph-like structure, in which metric information is often used to show the position of route nodes in the global space, and topological information is used to show the connectivity among route nodes. Such a route map model concentrates on the data mapping of spatial structure and is suitable for robot route planning and navigation. Route map can abstract the connectivity of the traversable areas as an undirected graph structure, so it has significantly reduced the search space size and computation complexity of planning algorithm when compared with the grid-based maps.¹⁶ To improve robots’ understanding of environment and human–robot interaction ability, semantic and multilayered route map has attracted more and more attention from researchers. To enable robot to possess navigation ability, semantic map is normally combined with traditional map models to form a kind of multilayered hybrid map model.^17,18

Although representation and application of route map have been studied widely, there still exist some limits in terms of its independent building, especially under an unknown environment. As for route map building in known environment, many methods have been proposed. Wang et al.¹⁹ proposed an algorithm to automatically construct a hierarchical route map, called “route tree.” Voronoi diagrams method was usually used to build route map for known structured environment.²⁰ At present, the research on the autonomous building of route map under an unknown environment has also achieved some results.²¹ Park et al.¹⁶ proposed a hierarchical roadmap building method in indoor environment, which first built a grid-based map for the environment, and then, extracted route maps from the grid-based map. However, it is difficult to apply this method to large-scale outdoor environment. By far, there are still problems in the independent building and application of route map in large-scale outdoor environment. Therefore, how to solve them has always been a research hot spot in robotics field.

After arrival at a strange environment, human beings will build route perceptions of the environment while exploring it, forming an overall understanding; meanwhile, the route-based knowledge will make it easy to carry out planning a route toward the destination and complete autonomous navigation task ultimately under the guidance of the route. To the mobile robot in an unknown environment, the route knowledge extracted from environment data serves as the basic condition for realizing environment perception and, ultimately, autonomous navigation. With the expansion of detected environment and the increase of input information, how to express the enormous descriptive data online as the overall knowledge turns out to be the major issue in route knowledge extraction. This article proposes one kind of online route map learning method suitable for large-scale outdoor unknown environment which is also applied into robot navigation planning. This method utilizes the growing-on-demand self-organizing neural network to build the route map of an environment through constantly adding new route nodes with the deepening exploration of robot into the environment, so as to form an experience-driven route knowledge learning model and apply it into robot planning and navigation.

The rest of this article is organized as follows. “Continuous learning and navigation framework” section introduces the concept of continuous learning and presents the navigation framework. “Route map learning system” section presents a growing-on-demand self-organizing neural network to learn the route map. The simulation and physical experiments are presented in “Experiment and analysis” section. Finally, the conclusions are made in “Conclusion” section.

Continuous learning and navigation framework

During the process of navigation, human beings use sensory system to constantly obtain information of the surrounding environment and improve perception and understanding of it through continuous learning, thus obtaining route knowledge and other knowledge of environment. This shows the characteristics of the self-organization, self-increase, and self-learning in the process of human spatial cognition. Continuous learning of environment incorporates four repeated cyclic processes of planning, movement, perception, and extraction of environment knowledge, as shown in Figure 1. This is a process of conscious and active participation of each function parts instead of a discrete and linear one. For example, the extraction of environment knowledge is a independent process of continuous learning. So, the robot, even though not movement, can still constantly extract environment knowledge from perceived environment information to make the route knowledge more accurate. Through continuous learning, the robot is enabled to constantly expand route knowledge and obtain a better understanding of environment, which is conducive to improving robots environment adaptability ability and independent navigation ability.

Figure 1.

Cyclic process of continuous learning.

As a major representation form of route knowledge, route map is normally represented as a graph $G = (V, E)$ , where G represents environment route map, V represents the set of route nodes, and E represents the set of connection relations between route nodes. This article focuses on how to build the route map by robot through online continuous learning of the environment. To this end, the robot route map continuous learning and navigation framework is designed as shown in Figure 2. The robot in outdoor environment is equipped with global positioning system (GPS), laser range finder, sonar, and odometer sensor. When the robot is patrolling in an outdoor environment, its real-time position information will be collected and stored in a route information data pool in the form of discrete point sets as a input space of route map learning algorithm. Route knowledge learning and extraction modules use the route learning algorithm to constantly learn and extract in data pool to generate route map for global route planning. Global route planning plans one route consisted of a sequence of position nodes, while route tracking module guides the robot to move from one position to another along the route until reaching the destination. When the robot is actually moving along the planned route, it will conduct local movement planning according to local environment information, enabling it to avoid obstacles and ensuring safe, reliable movement. Such a series of route map building and navigation show the process of robot continuous learning of environment. From the angle of robot, with the deepening activities in environment and enriched experience, the built route map will become more and more complete and reliable. This article focuses on continuous learning of route map.

Figure 2.

Robot route map continuous learning and navigation framework.

Route map learning system

Learning principle of route map based on the growing neural gas network

Fritzke proposed one kind of growing neural gas (GNG) network,²² which in essence was a self-organizing map (SOM). Figure 3 presents a non-hidden layer GNG network model consisted of input and output layers, where input space $N = {x_{1}, x_{2}, \dots, x_{n}}$ indicates that there are n signal points, ξ_i indicates input signals randomly produced in N, and w_ij indicates the weight between input signal ξ_i and GNG network node j. Input layer is used to receive randomly generated input signal ξ_i in input space; output layer maps input signal in a self-organized manner onto topologically network model. GNG network is an unsupervised and competitive learning clustering algorithm characterized by density matching and topological sorting, with its network scale having adjustable and self-learning features.

Figure 3.

Topological features of input space N extracted by GNG network. GNG: growing neural gas.

The adjustability of GNG network is shown in its scale and structure. GNG network does not have to know the distribution of input space in advance. With the constant self-learning and adjustment of network nodes and its increase in number, the distribution features of data in input space can be discovered in a self-organized manner, and then mapped onto output space. Places with high data density in input space occupy more network nodes in mapping space, which can accurately realize input space model clustering and model classification. This is similar to the features of human perception of space, shown as intelligent learning and generalizing ability. When reflected in one kind of artificial model, this model shall possess abilities of self-adapting to new samples and learning new knowledge.

Therefore, this article builds route map with environment structure features through utilizing the characteristic of GNG network output space able to constantly approximate space structure features. The building of robot route map is divided into route information extraction and route map learning as shown in Figure 2. These two parts are independent from each other, for either of them focuses on their own task, displaying as an online asynchronous learning mechanism. With robot patrolling in an environment, the robot position information will be collected and stored as discrete point sets. Then, the route map learning algorithm can extract the topological structure from the discrete point sets through constantly increasing and regulating network nodes and ultimately obtaining environment route map.

GPS-based route data acquisition

When patrolling in an outdoor environment, robot constantly samples position information and stores it in a route information data pool. Route information is a set of discrete robot position points, represented as $N = {x_{1}, x_{2}, \dots, x_{n}}$ . The set N will be regarded as input space for route learning algorithm. The set N is dynamic and its elements x_n+1 should satisfy the following conditions for joining the set

∥ x_{n + 1} - x_{n} ∥ > d

When the spacing distance d_s between new position x_{n + 1} and the last position point x_n joining the set N is equal to or greater than the distance parameter d, x_{n + 1} will be added into the set N. The spacing distance $d_{s} = ∥ x_{n + 1} - x_{n} ∥$ is related to GPS sampling frequency f and movement velocity v, namely d_s = v/f, and when d_s = d, $v_{d} = f * d$ . Therefore, when v < = v_d, route data collection speed increases with movement velocity v; when v > v_d, route data collection frequency is the same as GPS sampling frequency, because the distance between two collected GPS locations is larger than d. So, when the sampling frequency is high enough, it can be seen that the faster the robot moves, the faster the new position points are generated. And the element number of set N increases with robot movement in environment, showing the process of robot deepening its perception of the environment.

Route map learning with growing-on-demand self-organizing neural network

GNG network has the ability to constantly learn and generate topological network nodes in the dynamically incremental input space. However, in the GNG algorithm proposed by Fritzke, the largest neuron number was preset, which limited the application of GNG algorithm in the scenarios with increasing scale of input space, hence making the algorithm to lack self adaptability to the dynamic increment of environment scale. This makes the networks inappropriate for continuously learning the nonstationary data. When the neuron number is preset, an excessively small input space produces a lot of redundant neurons, making the whole network huge, while if the input space is excessively large, loss of descriptive input space features will also be caused due to lack of neuron number influencing accuracy of feature extraction. To solve the problem, this article modifies GNG network by introducing the distance factor d _max between network nodes to regulate the scale of network growth on the basis of previously adding new neurons, and this network is called as a growing-on-demand self-organizing neural network which enhances the self adaptability of GNG algorithm against growing input space N.

Like GNG network, the growing-on-demand self-organizing neural network in this article also assumes that each neuron c has the following parameters:

w_c ∈ R_n, position vector of neuron c in input space;

error_c, local cumulative error of neuron c;

N_c, neighbor set of neuron c.

Hence, the generation algorithm of route map G = (V,E) based on the growing-on-demand self-organizing neural network is given in Algorithm 1.

Algorithm 1.

Growing-on-demand self-organizing neural network.

Inputs

The input space, N;

Outputs

The route map, G = (V,E);

Initialize route map

1: Randomly generate two nodes V = (v₁, v₂) in input space N in a probability of p(ξ) = 1/N;

2: Set neighboring matrix E ⊂ V × V as empty set E = 0;

Steps

1: Update input space N, randomly generate one input signal ξ in a probability of p(ξ) = 1/N; calculate the winning nodes s₁ and s₂ nearest and next nearest to ξ as shown in Figure 4(a).

s_{1} = {argmin}_{v \in V} ∥ ξ - w_{v} ∥

s_{2} = {argmin}_{v \in V \ {s_{1}}} ∥ ξ - w_{v} ∥

2: Adjust s₁ and s₂.

• If there is no connection between s₁ and s₂, create connecting edges:

E = E \cup {(s_{1}, s_{2})}

• Set this edge age_(s₁,s₂) = 0.

• Adjust the error of winning node s₁:

{error}_{s_{1}} = {error}_{s_{1}} + ∥ ξ - w_{s_{1}} ∥

• Use learning rate ∊_b and ∊_n to adjust winning node s₁ as well as position vector connecting nodes with it as shown in Figure 4(b):

w_{s_{1}} = w_{s_{1}} + ε_{b} (ξ - w_{s_{1}})

w_{i} = w_{i} + ε_{n} (ξ - w_{i}), \forall i \in N_{s_{1}}

• Adjust all age of edges connected with node s₁:

{age}_{(s_{1}, i)} = {age}_{(s_{1}, i)} + 1, \forall i \in N_{s_{1}}

3: Remove all edges with age larger than a _max and delete all nodes without connecting edges as shown in Figure 4(c)

4: Insert new nodes and divide into two parts as shown in Figure 4(d):

5: a. Decide whether to insert new nodes,

• If the time of input signal production is integral multiple over λ, then locate the node u with the largest error:

u = {argmax}_{u \in V} error (u)

• Locate the topological neighborhood N_u(d) with u as center and a radius of d:

N_{u} (d) = {j | d_{u j} \leq d, j \in V}

• Locate induced subgraph

G [V^{'}] = (V^{'}, E^{'})

with the nodes in N_u(d) as vortex set, where

V^{'} = N_{u} (d)

• Calculate the average

{\bar{d}}_{E^{'}}

of all edges

(v_{i}^{'}, v_{j}^{'})

spatial distance in edge set E′,

{\bar{d}}_{E^{'}} = \frac{1}{| E^{'} |} \sum_{({v'}_{i}, {v'}_{j}) \in E^{'}} ∥ w_{v_{i}^{'}} - w_{v_{j}^{'}} ∥

Where |E′| represents the number of elements in edge set.

• If

{\bar{d}}_{E^{'}} > d_{max}

, insert new nodes.

6: b. Insert new nodes in the following steps,

• Locate the neighboring node v of u with the largest error, and insert new node r between them,

V = V \cup {r}

w_{r} = (w_{u} + w_{v}) / 2

• Create the edges of r with u and v, and delete edge between u and v,

E = E \cup {(r, u), (r, v)}

E = E \ {(u, v)}

• Locate induced subgraph

G [V^{'}] = (V^{'}, E^{'})

with the nodes in N_u(d) as vortex set, where V′ = N_u(d).

• Lower down error of u and v, and set the error of node r.

{error}_{u} = (1 - α) \times {error}_{u}

{error}_{v} = (1 - α) \times {error}_{v}

{error}_{r} = ({error}_{u} + {error}_{v}) / 2

• Regulate error of all nodes,

{error}_{c} = (1 - β) \times {error}_{c}, (\forall c \in V)

7: If stop conditions are not satisfied, then go back to Step1.

In traditional GNG algorithms, new nodes tend to be inserted into GNG network in fixed cycles. When each iteration time is integral multiple over λ, insert new node between the node with the largest error and its neighboring node with the largest error. It is not always reasonable to insert new nodes in fixed cycles, because it causes unnecessary and unsuitable node growth. Especially when input space has dynamic growth, this method may cause two problems: one is that the unmatching between node inserting speed and growth speed causes imbalanced node distribution, making GNG network to consume more regulating learning time; the other one is that it is difficult to give suitable node total number due to the difficulty in knowing the space size. Hence, this article modifies traditional GNG algorithms by introducing distance factor d _max between neurons to regulate network growth scale in a self-adaptive manner in combination with online learning route mate application requirement. Line 4 represents the modifications to traditional GNG algorithms, and explanations to the part are made in reference to Figure 4(d):

First, find out the node u with the largest error, as shown in Figure 4(d).

Find out the topological neighborhood $N_{u} (2) = {1, 2, 3, 4, 5}$ with u as center and a radius of d = 2.

Find out the induced subgraph $G [V^{'}] = (V^{'}, E^{'})$ with N_u(2) node as the vortex set V′, where $E^{'} = {(1, 2), (1, 3), (1, 4), (2, 4), (2, 5), (4, 5)}$ , as shown in Figure 4(d).

Calculate average ${\bar{d}}_{E^{'}}$ of all edges distance of induced subgraph G[V′] according to equation (11) in Algorithm 1.

If ${\bar{d}}_{E^{'}} > d_{max}$ , then insert the new node r between the node with the largest error and its neighbor v with the largest error as shown in Figure 4(d).

Figure 4.

Modified GNG algorithm feature learning diagram. (a) Input signal ξ. (b) Adapt the reference vectors of the winner and its direct topological neighbors. (c) Remove edges with an age larger than a _max. (d) Insert a new unit r to the network. GNG: growing neural gas.

Through these steps, growing-on-demand self-organizing neural network is provided with the ability of inserting new nodes according to the need and inserting suitable number of nodes in a self-adaptive manner according to the environment scale growth, without presetting the network scale. Unlike traditional competitive SOMs with predefined structure, it has no fixed topological structure and it can regulate partial neuron weight, the connection between neurons, and the number of neurons in a self-adaptive manner according to input data and several simple rules, hence making it able to extract input data structure and distribution features with suitable number of nodes.

Experiment and analysis

Online generation of campus environment route map

This section explains the validity of the growing-on-demand self-organizing neural network through online continuous learning and generating route map in campus environment.

Experiment platform

On PowerBot robot platform, the global navigation satellite system (GNSS)/inertial measurement unit (IMU) integrated navigation system (KY-INS100 Kit, Beijing BDStar Positioning Co., Ltd) is installed to provide high precision outdoor positioning and navigation data as shown in Figure 5. The PowerBot robot is also equipped with sonar sensor and laser ranger finder, with the major calculation platform being one set of laptop with i5-2540 M CPU.

Figure 5.

PowerBot mobile robot for physical experiment.

The Xiasha Campus of Hangzhou Dianzi University was used as the outdoor experimental environment as illustrated in Figure 6. In order to get the campus road information more conveniently, the KY-INS100 Kit was installed on a car. After driven the car along the campus road, we collected the road data of our campus. So the car is also a route collector.

Figure 6.

The experiment environment.

Experiment process and analysis

The red lines in Figure 6 were the movement traces of the route collector in campus environment, with yellow arrows indicating the direction. The route collector started from point a and followed the yellow arrows through a − b − c − b − c − a back to point a, hence completing the experiment processes of major road information online collection and route map building. The parameter settings were as follows: λ = 600, ∊_b = 0.1, ∊_n = 0.001, α = 0.5, β = 0.0005, a_max = 88, d = 2, and d_max = 5m. Under the condition of not presetting the network scale, growing-on-demand self-organizing neural network continuously learned the environment while exploring it. With suitable number of nodes inserted as the environment scale increased, suitable scale route map was built. Figure 7 shows the route map building process by the route collector through online continuous learning. Figure 7(a) and (b) shows the initial stage of the route collector setting off, during which the element number in input space N was 50, and initialization generated two nodes. Figure 7(c) to (f) shows the intermediary stage of building route map, from which it could be seen that route map scale increased with the collection of route information and realized online environment learning and map updating through constantly growing network nodes. Figure 7(g) and (h) shows the route collector returning to starting point a and completing campus route information collection. At this time, a total of 3692 route discrete dots were collected, as shown in Figure 7(i), and route map with 575 nodes was generated with the growing-on-demand self-organizing neural network, and each node contains latitude and longitude data.

Figure 7.

Route map building process by online continuous learning.

Figure 8(a) shows the relationship between the route collector movement speed and inserted new nodes. When the route collector is accelerated (indicated as red lines in the figure), more new nodes were inserted, with a high density of blue insertion lines. Comparatively, when the route collector slowed down, less new nodes were inserted due to the limitation of inserting new nodes conditions, with a sparse density of blue insertion lines. This shows that the growing-on-demand self-organizing neural network had the ability of adapting to environment scale growth independently and regulating network growth speed according to the increased speed of input space. Especially when the route collector moved from point b to point c again, although the movement speed was fast, no new nodes were inserted, showing that the growing-on-demand self-organizing neural network had terminated the insertion of new nodes due to distance factor limitation between neurons. Although no new nodes were inserted, the growing-on-demand self-organizing neural network still continuously learned the input space and adjusted the network to better approximate input space distribution feature and structure feature. The blue points in Figure 8(b) represent the average ${\bar{d}}_{E^{'}}$ of all edges of induced subgraph with topological neighborhood N_u(d) as vortex set. The distribution of blue points better explains the role of distance factor. When ${\bar{d}}_{E^{'}}$ was larger than d _max (indicated as black dotted lines), the condition of inserting new nodes was satisfied. It can be seen that when robot moved from point b to point c again, generation of new nodes was hindered, because suitable neuron number average ${\bar{d}}_{E^{'}}$ generated by learning algorithm was smaller than d _max. Red curves in Figure 8(b) represent partial cumulative error, which was reduced at the initial stage of environment learning and kept stable in the whole process of building route map. This shows that the growing-on-demand self-organizing neural network can quickly respond to input space growth, characterized by rapid convergence rate and strong feature learning ability.

Figure 8.

Data analysis of route map building process. (a) The relationship between movement velocity and inserted new modes. (b) Local cumulative error and the average ${\bar{d}}_{E^{'}}$ .

From the obtained route map, it could be seen that a small number of route network nodes can obtain a large amount of map information. The longer the robot explores in the obstacle environment, the more information about passable areas and the deeper perception of the environment. This also testifies that route map can soundly represent the connectivity of passable space, whose growth feature displays robot learning of the environment. Route map possesses the overall structure of topological network, so it maintains consistency in overall environment representation that can effectively help mobile robots in realizing navigation planning.

In the following, robot can utilize A* algorithm to plan out routes with learned route map as shown in Figure 9. The 961.2 m long route is consisted of the sequences of 245 nodes to guide robot to move from one place to another until reaching the destination and completing the navigation task. This is completed by our previous work, so we wont belabor here.

Figure 9.

The motion trail of PowerBot robot from the start point to the end point; the blue line is the motion trajectory and the total length of the motion trail is 961.2 m.

Comparison with the traditional GNG algorithm

This section compares the learning process of traditional GNG algorithm in a dynamically growing input space with the learning process of the proposed algorithm for analysis, so as to further demonstrate the features and effectiveness of the proposed algorithm.

Similarly, the campus of Hangzhou Dianzi University was selected as the experiment environment, and the maximum number of GNG nodes was preset to 100. The parameters set for the GNG network algorithm in this experiment were λ = 600, ∊_b = 0.1, ∊_n = 0.001, α = 0.5, β = 0.0005, and a_max = 88. The red lines in Figure 10 are the route collectors motion curve in the campus environment, and yellow arrows are the motion directions. The route collector started from point a and moved along yellow arrows to the end point d. Figure 11 presents the learning results of the route collector moving to the end point d. At that moment, it collected the information of 1576 path locations in total, and the GNG algorithm was utilized to generate the route map with 100 nodes.

Figure 10.

The experiment environment of the traditional GNG algorithm. GNG: growing neural gas.

Figure 11.

Route map consists of 100 nodes.

Figure 12(a) reflects the relationship between the velocity and new inserted nodes. It could be seen that the traditional GNG algorithm generates new nodes in regular cycle, having nothing to do with the growth speed of input space. This causes inconsistency between the generation speed of new nodes and the growth speed of input space, hence leading to imbalanced node density. Similar issues can also be observed from the distribution of node density in Figure 11. From Figure 11, the density of location information points from point a to point b is consistent, but the nodes are distributed from dense to sparse, because of unmatched speed. The algorithm proposed in this article adopted the strategy of growth upon demand, hence eliminating similar issues, which can be seen from Figure 7(h). In the same way, when the robot goes back from point c to point b, the traditional GNG algorithm is still generating new nodes continuously because of not adopting the above strategy. When the number of nodes in GNG network reaches the preset maximum of 100, the traditional GNG algorithm will not generate new nodes any more (as shown in Figure 11), but the input space is still growing, hence resulting into the loss of input space features and ultimately affecting feature extraction accuracy. However, the algorithm proposed in this article can regulate the scale of network growth self-adaptingly, so as to extract input data structure and distribution features with suitable number of nodes.

Figure 12.

Data analysis of route map building process by using traditional GNG algorithm. (a) The relationship between movement velocity and inserted new modes. (b) Local cumulative error. GNG: growing neural gas.

The red curve in Figure 12(b) is local cumulative error. At the primary stage of environment learning, it reduces rapidly, but due to the fact that traditional GNG algorithm is not appropriate for the input space with dynamic growth, local cumulative error is very unstable in constructing the whole route map. Especially after reaching the maximum of network nodes, the error increases rapidly with obvious oscillation. Theoretically, under a fixed input space, GNG algorithm will finally reach convergence, which, however, requires longer regulated learning time. Through comparison, it can be known that the modified GNG algorithm, characterized by a rapid convergence speed and a strong feature learning ability, can more quickly respond to the growth of input space.

Experiment analysis of continuous input space

Through experiment and analysis of learning continuous input space, this section aims at explaining the validity of the growing-on-demand self-organizing neural network. The 100-m long and wide square area was regarded as the input space of algorithm. Figure 13 shows the network learning situations of input space when parameters d _max were, respectively, 5 and 10 m, with 523 and 136 network nodes generated in total. Figure 14 shows the relational schema of local error, distance average ${\bar{d}}_{E^{'}}$ , and new nodes generation with learning time. It can be seen from the figures that with the proceeding of learning, local error rapidly converged and kept stable; distance average ${\bar{d}}_{E^{'}}$ quickly dropped to expected value, hence hindering the continued generation of new nodes; green vertical lines represented the generation of new nodes, which were more dense at the initial stage of learning algorithm operation, showing that the algorithm was rapidly generating new nodes to extract input space features while with ${\bar{d}}_{E^{'}}$ dropping to expected value, ${\bar{d}}_{E^{'}}$ started to hinder the generation of new nodes, hence causing sparse distribution of green vertical lines.

Figure 13.

Generated GNG network when d _max is (a) 5 and (b) 10, respectively. GNG: growing neural gas.

Figure 14.

Relational schema of local error, distance average ${\bar{d}}_{E^{'}}$ and new nodes generation with learning time. The value of d _max is (a) 5 and (b) 10.

From the experiment of continuous input space, it can be seen that after introducing distance factor d _max between neurons, the growing-on-demand self-organizing neural network did not require the presetting of network scale but instead it could regulate network growth scale in a self-adaptive manner and ultimately obtain suitable network scale.

Conclusion

This article proposes one kind of growing-on-demand self-organizing neural network which can conduct online incremental unsupervised learning of data and carry out clustering and topological representation of dynamic input data without priori knowledge. Introducing distance factor d _max between network nodes to regulate network growth scale in a self-adaptive manner without presetting the largest network generation scale enables this network to dynamically generate suitable number of new neurons to represent input space, obtain stable learning results, and reflect topological structure of initial data on feature space.

This article applies the growing-on-demand self-organizing neural network into the building of large-scale route map in unknown environment as well as robot planning and navigation. With the deepening exploration of robot into environment, this method will constantly add new route nodes to build environment route map, hence forming an experience-driven route knowledge learning mode to be applied into robot planning and navigation. The environment map built with this method can not only satisfy the requirement of environment information data compression, but also conduct real-time map updating and environment learning while robot patrolling the environment, showing the features of self learning and self adaption.

Growing-on-demand self-organizing neural network is one kind of neural network model based on competitive learning, which does require too much artificial intervention or preset network scale, so this algorithm can be applied into scenario without priori knowledge or with dynamically growing input space. In future studies, we hope to promote two-dimensional learning algorithm into three-dimensional space so that it can be applied to robot moving in three-dimensional space and its application scope can be widened, such as exploration and building of underwater robot into its movable space. Meanwhile, the growing-on-demand strategy of the algorithm will be further studied, and the convergence of the competitive type neural network with time will remain a research focus.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed financial support for the research, authorship, and/or publication of this article: This work was supported in part by the Natural Science Foundation of Zhejiang Province (grant no. LY17F030022) and in part by the National Natural Science Foundation of China (grant nos 61503108 and 61375104).

References

Milford

Wyeth

. Persistent navigation and mapping using a biologically inspired SLAM system. Int J Robot Res 2010; 29(9): 1131–1153.

Fan

. Bioinspired intelligent algorithm and its applications for mobile robot control: a survey. Comput Int Neurosci 2016; 2016: 1–16.

Bonnet

Cazenille

Séguret

. Design of a modular robotic system that mimics small fish locomotion and body movements for ethological studies. Int J Adv Robot Syst 2017; 14(3): 1–12.

Werner

Krieg-Brckner

Mallot

. Spatial cognition: the role of landmark, route, and survey knowledge in human and robot navigation. In: Jarke

Pasedach

Pohl

(eds) Informatik97 Informatik als Innovationsmotor. Berlin: Springer, 1997, pp. 41–50.

Shah

Campbell

. A qualitative path planner for robot navigation using human-provided maps. Int J Robot Res 2013; 32(13): 1517–1535.

Pepperell

Corke

Milford

. Routed roads: probabilistic vision-based place recognition for changing conditions, split streets and varied viewpoints. Int J Robot Res 2016; 35(9): 1057–1179.

Zhang

Zherdeva

Ekstrom

. Different “routes” to a cognitive map: dissociable forms of spatial knowledge derived from route and cartographic map learning. Mem Cognit 2014; 42(7): 1106–1117.

Werner

Krieg-Brückner

Herrmann

. Modelling navigational knowledge by route graphs. In: Freksa

Habel

Brauer

Wender

(eds) Spatial cognition II. Berlin, Heidelberg: Springer, 2000, pp. 295–316.

Foo

Warren

Duchon

. Do humans integrate routes into a cognitive map? Map-versus landmark-based navigation of novel shortcuts. J Exp Psychol Learn Mem Cogn 2005; 31(2): 195–215.

10.

Krieg-Brckner

Frese

Lttich

. Specification of an ontology for route graphs. In: Anon (ed) International conference on spatial cognition IV (eds Freksa

Knauff

Krieg-Brckner

Nebel

Barkowsky

), Frauenchiemsee, Germany, 11–13 October 2004, pp. 390–412. Berlin: Springer.

11.

Kielar

Biedermann

Kneidl

. A unified pedestrian routing model combining multiple graph-based navigation methods. In: Knoop

Daamen

(eds) Traffic and granular flow’15. Cham: Springer International Publishing, 2016, pp. 241–248.

12.

Herrero-

Alcaraz-Jiménez

Martínez-Barberá

. An accurate and robust flexible guidance system for indoor industrial environments. Int J Adv Robot Syst 2013; 10(7): 1–10.

13.

Thrun

Gutmann

Fox

. Integrating topological and metric maps for mobile robot navigation: a statistical approach. In: Anon (ed) Conference on innovative applications of artificial intelligence AAAI/IAAI (eds Bruce

Ramasamy

), Madison, Wisconsin, USA, 27–29 July 1998, pp. 989–995. Palo Alto: AAAI.

14.

Hossain

Yeap

. How Albot₁ computes its topological-metric map. Procedia – Soc Behav Sci 2013; 97: 553–560.

15.

Tomatis

Nourbakhsh

Siegwart

. Hybrid simultaneous localization and map building: a natural integration of topological and metric. Robot Auton Syst 2003; 44(1): 3–14.

16.

Park

Choi

Chung

. An efficient mobile robot path planning using hierarchical roadmap representation in indoor environment. In: Max

Meng

(ed) IEEE international conference on robotics and automation (ICRA), Saint Paul, MN, USA, 14–18 May 2012, pp. 180–186. Piscataway: IEEE.

17.

Kostavelis

Gasteratos

. Semantic mapping for mobile robotics tasks: a survey. Robot Auton Syst 2015; 66: 86–103.

18.

Kostavelis

Charalampous

Gasteratos

. Robot navigation via spatial and temporal coherent semantic maps. Eng Appl Artifi Int 2016; 48: 173–187.

19.

Wang

Sakamoto

. Hierarchical route maps for efficient navigation. In: Joyce

Chai

Antonio

Krüger

(eds) International conference on intelligent user interfaces, Haifa, Israel, 24–27 February 2014, pp. 169–178. New York, USA: ACM.

20.

Beeson

Jong

NK,

Kuipers

. Towards autonomous topological place detection using the extended voronoi graph. In: Max

Meng

(ed) IEEE international conference on robotics and automation, Barcelona, Spain, 18–22 April 2005, pp. 4373–4379. Piscataway: IEEE.

21.

Yang

Worboys

. Generation of navigation graphs for indoor space. Int J Geogra Inform Sci 2015; 29(10): 1737–1756.

22.

Fritzke

. A growing neural gas network learns topologies. Adv Neural Inform Proc Syst 1995; 7: 625–632.

Continuous learning route map for robot navigation using a growing-on-demand self-organizing neural network

Abstract

Keywords

Introduction

Continuous learning and navigation framework

Route map learning system

Learning principle of route map based on the growing neural gas network

GPS-based route data acquisition

Route map learning with growing-on-demand self-organizing neural network

Experiment and analysis

Online generation of campus environment route map

Experiment platform

Experiment process and analysis

Comparison with the traditional GNG algorithm

Experiment analysis of continuous input space

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References