Sage Journals: Discover world-class research

Abstract

Traversability analysis is one of the core issues in the autonomous navigation for mobile robots to identify the accessible area by the information of sensors on mobile robots. This paper proposed a model to analyze the traversability of complex terrains based on rough sets and training revising. The model described the traversability for mobile robots by traversability cost. Through the experiment, the paper gets the conclusion that traversability analysis model based on rough sets and training revising can be used where terrain features are rich and complex, can effectively handle the unstructured environment, and can provide reliable and effective decision rules in the autonomous navigation for mobile robots.

1. Introduction

A mobile robot is a synthesis of environmental awareness, dynamic decision-making and planning, behavior control and execution, and other functions into one integrated system. With the improvement of the performance of mobile robots, the applications of mobile robots greatly expand and mobile robots begin to play a vital role in many industries. In some dangerous circumstances, mobile robots are used to complete environmental detection, searching, and rescue tasks. Therefore, technology of intelligent mobile robots has raised the widespread concern around the world.

These robots are given priority to master-slave operation mode. But due to the complex environment on site, they easily cause the operator's observation errors and they have a great influence on communication. Thus, the robot must possess the abilities of certain environmental awareness and autonomous navigation. To realize the autonomous navigation of the robot, the main several problems that need to be solved are mapping, traversability analysis for classified terrains, and path planning. Among these problems, the traversability analysis for classified terrains plays a vital role in autonomous navigation for mobile robots. It is one of the core issues of the autonomous navigation for mobile robots to identify the accessible area by the information of sensors on mobile robots.

Under the unstructured environment, such as underground coal mine, open field, and planet surface, mobile robots often work on uneven and complex terrains. Seraji and Howard [1, 2] proposed using roughness, gradient, discontinuous degree, surface hardness, and traversability index to quantify the degree of complexity for mobile robots going through uneven road surface. Brooks and Iagnemma [3] established the measure method of traversability by analyzing the interaction between the wheels and the ground. Al-Milli et al. [4] calculated the force between the robot and the terrain to reflect the degree of difficulty for the mobile robot to go through this terrain. Opportunity and Spirit Mars Probe of NASA exactly used online traversability assessment to ensure its safe operation on the surface of Mars as investigated by Baumgartner [5]. Jin et al. [6] achieved fuzzy logic based traversability analysis on the basis of surface fitting based slope data and fractal theory based roughness data. Collier et al. [7] realized traversability analysis based on calculation of the statistical geometry data of the traversability terrain map and applied it to the navigation of unmanned vehicles. Gu et al. [8] and Liu et al. [9] presented a method of using fuzzy logic to analyze traversability and using altitude, gradient, and fluctuation to determine the traversability index. Guo et al. [10] attempted to build the relationship between the optimal path and the terrain traversability. Suzuki et al. [11] proposed to analyze the terrain traversability by predictive probability. Tse et al. [12] proposed a unified mixture-model based terrain estimation with Markov random fields (MRF). Bogoslavskyi et al. [13] addressed the problem of online traversability analysis for robots that were only equipped with a Kinect-style sensor. Belter et al. [14] presented a probabilistic regression technique to solve the traversability assessment problem for a walking robot.

The above methods are mainly used in environment such as the wilderness and flat road where terrain features are not rich and all of them have a good effect. But in complex environment where terrain features are rich, the above methods hardly meet the requirements of traversability analysis for mobile robots. It is easier to bring great uncertainty to data collection and transmission. In the past research, the authors only used rough sets to analyze traversability and gave the traversability index only by experience. But the knowledge base acquired by rough sets is not precise enough. Based on the above consideration, this paper presents a traversability analysis algorithm based on rough sets and training revising. This method which can solve the problem of complex terrain features and high uncertainty can get more precise knowledge base than the previous research. Through validating the performance of algorithm by experiments, the results show that this method can effectively value the traversability of different terrains and provide reliable information in the autonomous navigation for mobile robots.

2. Primary Features Sensing and Description for Typical Terrains

It is easy to get that the bumps of mobile robots on an uneven road can cause the observed inconsistencies on the absolute elevation through the research and analysis. But the relative elevation within a certain range remains unchanged and the relative uncertainty remains smaller. The relative invariance is very important to determine the impassable area.

2.1. Terrain Fluctuation Calculation

Terrain fluctuation is a reflection of the degree of elevation for a designated point neighborhood area that departs from the average elevation of this neighborhood area. The calculation of the fluctuation can be described by the neighborhood variance.

Firstly, the average elevation of a designated point neighborhood area can be determined by

{\bar{f}}_{Φ_{i, j}} = \frac{\sum_{(x_{m}, y_{n}) \in Φ_{i, j}} f (x_{m}, y_{n})}{N_{Φ_{i, j}}},

(1)

where the center (x_m,y_n) refers to the neighborhood area Φ_i,j and N_i,j represents the number of elements in this neighborhood area.

Secondly, the elevation variance can be further described as

{\bar{σ}}_{Φ_{i, j}} = \frac{\sum_{(x_{m}, y_{n}) \in Φ_{i, j}} {f (x_{m}, y_{n}) - {\bar{f}}_{Φ_{i, j}}}^{2}}{N_{Φ_{i, j}} - 1},

(2)

where $f (x_{m}, y_{n}) - {\bar{f}}_{Φ_{i, j}}$ represents the relative elevation of a certain neighborhood area.

2.2. Terrain Gradient Calculation

Terrain gradient of a point on surface represents the degree of the inclination of this point. It is a vector. It is easy to prove that the gradient of any slope is equal to the slope of the bevel on the two mutually perpendicular components of the vector and the direction. In the elevation map, the gradient reflects the rate of change of terrain elevation values in a certain direction. In a geographic information system, the surface fitting method is a better way to calculate gradient. Table 1 shows a 3 × 3 gradient template.

Table 1:

A 3 × 3 gradient template.

f(i–1, j–1)	f(i–1, j)	f(i–1, j + 1)
f(i, j–1)	f(i, j)	f(i, j + 1)
f(i + 1, j–1)	f(i + 1, j)	f(i + 1, j + 1)

The characteristic value of gradient can be expressed as follows:

\begin{matrix} {slope}_{x} = \frac{1}{8 \times Δ d} {(f (i - 1, j - 1) + 2 f (i - 1, j) + f (i - 1, j + 1)) - (f (i + 1, j - 1) + 2 f (i + 1, j) + f (i + 1, j + 1))}, \\ {slope}_{y} = \frac{1}{8 \times Δ d} {(f (i - 1, j - 1) + 2 f (i, j - 1) + f (i + 1, j - 1)) - (f (i - 1, j + 1) + 2 f (i, j + 1) + f (i + 1, j + 1))}, \\ slope = arc tan {{({slope}_{x}^{2} + {slope}_{y}^{2})}^{1 / 2}}, \end{matrix}

(3)

where slope_x and slope_y represent the gradient on the vertical direction and the forward direction for the mobile robot, respectively, and Δd represents the grid spacing.

The direction of gradient can be described as

aspect = \frac{{slope}_{x}}{{slope}_{y}} .

(4)

2.3. Terrain Texture Calculation

The texture of terrain surface which can reflect the depth and surface information is also an important feature. The paper calculates the texture of different terrains by the Gabor filter.

The steps for calculation of texture based on the Gabor filter are detailed as follows.

Select the direction parameter and the scale parameter of the Gabor filter. The Gabor function can be expressed as

\begin{matrix} φ (x, y) = \frac{1}{2 π σ_{x} σ_{y}} \exp [- \frac{1}{2} (\frac{x^{2}}{{σ_{x}}^{2}} + \frac{y^{2}}{{σ_{y}}^{2}})] \\ \times \exp [i 2 π (μ x + υ y)] . \end{matrix}

(5)

The Gabor wavelet transform filter can be obtained by a series of directions and scale transformations for this function.

Calculate the specific parameters of the Gabor filter, such as the scale factor on the horizontal axis of each filter, the abscissa of the center of each filter, and the standard deviation of differential filters.

The standard deviations of different axis for different filters are determined by

\begin{matrix} σ_{x_{m}} = σ_{x_{M}} a^{m - M} = \frac{a - 1}{a + 1} \frac{U_{h}}{\sqrt{2 \ln 2}} a^{m - M}, \\ σ_{y_{m}} = σ_{y_{M}} a^{m - M} = t g \frac{π}{L} \sqrt{\frac{U_{h}^{2}}{2 \ln 2} - σ_{x_{M}}} \cdot a^{m - M}, \\ σ_{y_{M}} = t g \frac{π}{L} \sqrt{\frac{U_{h}^{2}}{2 \ln 2} - σ_{x_{M}}}, m = 1,2, \dots, M . \end{matrix}

(6)

Get the texture characteristics of the image by the above Gabor filter. The output via the Gabor filter can be described as follows:

\begin{matrix} F_{m l p q} = | I_{m l p q} |, \\ I_{m l p q} = \iint f (x, y) φ_{m l} (x - p Δ x, y - Δ y) d x d y, \end{matrix}

(7)

where (p,q) represents a pixel in the image and I_mlpq represents the wavelet transform of f(x,y) and Δx and Δy represent the sampling intervals.

F_mlpq retains the energy information of the image and ignores the location information. Thus, it preferably reflects the texture features of the image. The texture features of the image can be described as

E_{m l} = \frac{\sum_{p, q} F_{m l p q}^{2}}{\sum_{m, l, p, q} F_{m l p q}^{2}} .

(8)

3. Traversability Analysis Model and Algorithm Based on Rough Sets and Training Revising

The mobile robot is trained repeatedly to move through the typical terrains to get prior knowledge of traversability index. In terms of the information sampled by the mobile robot, an initial decision table about terrain traversability according to the prior knowledge will be set up. Then, the table will be processed by rough sets.

The basic idea of data processing using rough sets theory is to select a reasonable method of discretization to discretize the continuous attributes, to carry out the relative reduction of the condition attributes by removing redundant condition attributes through a reasonable method, to get the smallest condition attributes set and core of the decision table, to select the rules credibility threshold according to the actual condition, and to obtain the briefest decision rules.

At last, the mobile robot is put into the unknown terrains to validate the decision rules. The decision rules will be revised by the comparison with the actual situation to form the last rule base.

Traversability analysis frame based on rough sets and training revising is shown in Figure 1.

Figure 1:

The traversability analysis frame based on rough sets and training revising.

3.1. Training Sample Data Collection of Typical Terrains

The training sample of typical terrains contains cement road, soil road, muddy road, stone road, ladder, slope, and so forth. Figure 2 shows part of typical terrains to train the mobile robot.

Figure 2:

The part of typical terrains for training.

The mobile robot is trained repeatedly to move through the typical terrains to get prior knowledge. Terrain information is collected by the stereo vision sensor, which contains condition attributes such as the grayscale, texture, elevation, gradient, and fluctuation. Traversability as the decision attribute is acquired by operator's guidance in the moving process of the mobile robot.

3.2. The Discretization of Sample Data

The terrain characteristic data collected by the stereo vision sensor is continuous, but the process of the rough sets analysis which requires the condition attributes and decision attributes of the decision table must be discrete. In this paper, the Boolean reasoning algorithm is used to convert the continuous attribute values into several intervals.

After discretization, a two-dimensional decision table of a typical terrain information system is established, in which each row describes terrain information and each column corresponds to an attribute of this terrain.

3.3. Attributes Reduction

The attributes reduction is one of the core issues of rough sets theory. It is proved that attributes reduction is an NP-hard problem in [15]. In most cases, extracting the rules only needs part of the condition attributes, without the need to know all of the attributes. This means that the role of each attribute is different from one to another. Some indispensable attributes play a major role and even some condition attributes are redundant for obtaining the decision rules. This means that the value of certain features of the terrain is not useful to the terrain identification. It will not only result in a waste of storage resources in information processing but also interfere with people to make the right decisions. Thus, the unnecessary or unimportant attributes under the same conditions should be deleted.

This paper adopts a genetic reduction algorithm, which can effectively reduce the search space and improve the efficiency of the reduction.

3.4. Rules Extraction

According to the relative reduction decision table, the relationship between the terrain features attributes and traversability can be easily obtained. It is called decision-making rules of traversability. The support and confidence rules can be selected according to the actual situation to simplify the rules.

3.5. Training Revising

After the processing of rough sets, the mobile robot should be put into unknown terrains to validate the decision rules. To revise the traversability index, some data should be collected. The attitude of the mobile robot is collected by the inertial measurement unit (IMU) in this paper.

Traversability index can reflect the degree of complexity of mobile robots going through an uneven road surface. The relative vibration intensity is used to quantify traversability index in this paper.

The acceleration of pitch angle and roll angle collected by IMU can reflect the vibration intensity of mobile robots to go through an uneven road. So, the absolute vibration intensity [16] can be expressed as

V_{a} = [\frac{1}{n} \sqrt{\sum_{i = 1}^{n} {(\overset{\cdot \cdot}{α} - E (\overset{\cdot \cdot}{α}))}^{2}} \times \frac{1}{n} \sqrt{\sum_{i = 1}^{n} {(\overset{\cdot \cdot}{γ} - E (\overset{\cdot \cdot}{γ}))}^{2}}],

(9)

where α and γ represent the pitch angle and roll angle of mobile robots, respectively, and n represents the number of samples.

In order to use a unified standard to compare the vibration intensity, the relative vibration intensity is introduced. The relative vibration intensity [16] can be described as

V_{r} = \frac{| V_{a} - V_{f} |}{V_{f}},

(10)

where V_f represents the absolute vibration intensity of mobile robots to go through the flat road.

Thus, the traversability index can be calculated by the relative vibration intensity. The greater the relative vibration intensity is, the bigger the traversability index is.

As expressed by (9) and (10), the traversability index on unknown terrains can be obtained. Then, the decision rules will be revised by the comparison with the actual situation and finally put the rules into the knowledge base for mobile robots as the domain knowledge.

4. Experiment Analysis

In this experiment, the mobile robot developed by the Center for Robotics of Shandong University (SUCRO) is applied to collect the data of different terrains. The mobile robot is a tracked structure and carries the front zoom camera, the stereo vision camera, assistant lights, the thermal imager, the wide-angle cameras, gas sensors, and so on. Figure 3 shows the structure of this mobile robot.

Figure 3:

The mobile robot used in the experiment.

4.1. Experiment Design

In this decision table, the terrain information is collected by the stereo vision sensor, which contains condition attributes such as the grayscale, texture, elevation, gradient, and fluctuation. The traversability index which is labeled in a training way is regarded as the decision attribute.

1000 pieces of data are collected by the stereo vision camera installed on mobile robot. After the processing of rough sets, decision-making rules of traversability can be easily obtained. Table 2 shows part of the sample data after discretization.

Table 2:

Part of the sample data after discretization.

Number	Grayscale	Texture	Gradient	Elevation	Fluctuation	Traversability

161	40	43	13	6	15	9
162	20	8	8	2	2	2
163	32	8	1	2	3	0
164	36	26	8	6	3	3
165	21	22	4	2	3	1
166	60	32	2	2	2	3
167	4	3	2	2	3	2
168	5	12	6	6	3	5
169	10	18	6	6	5	6
170	36	50	10	18	13	10
171	40	28	2	8	4	4
172	42	20	2	−1	2	2
173	43	76	16	54	18	10
174	25	32	10	6	5	3
175	18	19	4	5	3	1
176	20	28	1	6	4	0
177	58	65	18	8	18	9
178	35	18	8	10	6	6
179	32	25	3	4	4	1
180	52	39	5	4	7	4

Note: the data in this table is processed by the Boolean reasoning algorithm. Grayscale ranges from 0 to 100, and 0 represents absolute white; texture ranges from 0 to 100, and 0 means no ripple; gradient ranges from 0 to 90; the initial position of the ground elevation for the mobile robot is regarded as the reference zero point; fluctuation ranges from 0 to 100, and 0 represents very smooth; traversability index ranges from 0 to 10, and 0 means the easiest to pass for mobile robots.

4.2. Verification and Analysis

After the processing of rough sets, the mobile robot will be put into the unknown terrains to validate the decision rules. Then, the decision-making rules will be revised by the comparison with the actual training data.

The attitude of the mobile robot is collected by inertial measurement unit (IMU). At the same time, the terrain information is collected by the stereo vision sensor. Figure 4 shows the variation of roll angle and pitch angle under part of the different terrains.

Figure 4:

The variation of roll angle and pitch angle under part of the different terrains.

The traversability knowledge base for the mobile robot will be obtained ultimately based on the actual situation after training revising. Table 3 shows part of the decision-making table of traversability after training revising.

Table 3:

Part of the decision-making table of traversability after training revising.

Number	Grayscale	Texture	Gradient	Elevation	Fluctuation	Traversability

38	25	8	5	6	*	10
43	10	3	1	8	*	10
66	30	40	13	8	*	4
69	36	20	8	9	*	5
80	4	3	2	2	*	2
87	35	18	8	10	*	6
104	31	*	2	6	5	0
112	25	*	1	5	5	0
175	*	7	3	1	3	7
182	*	6	5	2	3	6
200	3	3	1	*	1	2
215	6	2	2	*	2	3

means no influence to the value of traversability.

Some rules of traversability for the mobile robot can be gotten from the above table. According to Table 3, some rules are as follows.

Rule 38: if grayscale = 25, texture = 8, gradient = 5, and elevation = 6, then the traversability is 10.

Rule 104: if grayscale = 31, gradient = 2, elevation = 6, and fluctuation = 5, then the traversability is 0.

Rule 175: if texture = 7, gradient = 3, elevation = 1, and fluctuation = 3, then the traversability is 7.

Rule 200: if grayscale = 3, texture = 3, gradient = 1, and fluctuation = 1, then the traversability is 2.

By the training in the unknown terrains, the mobile robot sometimes would perform the wrong decisions. The main reasons for the wrong decisions are the uncertainty which existed in the collection process of sensors’ information and lacking of data samples. But the mobile robot can perform very well in most cases. Thus, this algorithm for traversability analysis which can achieve high accuracy can meet the requirements in autonomous navigation for mobile robots.

5. Conclusion

In this paper, a rough set and training revising based method is proposed. Firstly, this paper introduces the calculation method for primary features sensing and description for typical terrains. Secondly, the paper describes traversability analysis model and algorithm based on rough sets and training revising in detail. Finally, an experiment is put forward to verify the effectiveness of this model. Through the experiment, the paper gets the conclusion that traversability analysis model based on rough sets and training revising can be used where terrain features are rich and complex and can effectively handle the unstructured environment and provide reliable and effective decision rules in the autonomous navigation for mobile robots.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Footnotes

Acknowledgments

This study is supported by the National Natural Science Foundation of China (61233014, 61305130), the Plan for Science and Technology Development of Shandong Province (2012GGB01188) and the Fundamental Research Funds of Shandong University (2014JC037).

References

Seraji

, “Traversability index: a new concept for planetary rovers,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA99 '99) vol. 3, pp. 2006–2013, May 1999.

Seraji

and Howard

, “Behavior-based robot navigation on challenging terrain: a fuzzy logic approach,” IEEE Transactions on Robotics and Automation, vol. 18, no. 3, pp. 308–321, 2002.

Brooks

C. A.

and Iagnemma

, “Vibration-based terrain classification for planetary exploration rovers,” IEEE Transactions on Robotics, vol. 21, no. 6, pp. 1185–1190, 2005.

Al-Milli

Althoefer

, and Seneviratne

L. D.

, “Dynamic analysis and traversability prediction of tracked vehicles on soft terrain,” in Proceedings of the 2007 International Conference on Networking Sensing and Control (ICNSC '07), pp. 279–284, April 2007.

Baumgartner

, “Motion planning technologies for planetary rovers and manipulators,” in Proceedings of the International Workshop on Motion Planning in Virtual Environments, Toulouse, France, 2005.

Jin

G. G.

Lee

Y. H.

Lee

H. S.

, and So

M. O.

, “Traversability analysis for navigation of unmanned robots,” in Proceedings of the International Annual Conference on Instrumentation, Control and Information Technology (SICE '08), pp. 1806–1811, August 2008.

Collier

Broten

, and Giesbrecht

, “Traversability analysis for unmanned ground vehicles,” Technical Memorandum 2006-175, Defence Research and Development, Ontario, Canada, 2006.

J. J.

Cao

Q. X.

, and Huang

, “Rapid traversability assessment in 2.5D grid-based map on rough terrain,” International Journal of Advanced Robotic Systems, vol. 5, no. 4, pp. 389–394, 2008.

Liu

Yang

, and Zhao

, “A generic approach to rugged terrain analysis based on fuzzy inference,” in Proceedings of the 8th International Conference on Control, Automation, Robotics and Vision (ICARCV '04), pp. 1108–1113, December 2004.

10.

Guo

Song

Bao

, and Zhang

, “Optimal path planning in field based on traversability prediction for mobile robot,” in Proceedings of the 2011 International Conference on Electric Information and Control Engineering (ICEICE '11), pp. 563–566, April 2011.

11.

Suzuki

Terada

Saitoh

, and Kuroda

, “Vision based far-range perception and traversability analysis using predictive probability of terrain classification,” in Proceedings of 2010 41st International Symposium on and 2010 6th German Conference on Robotics (ROBOTIK '10), pp. 1–6, 2010.

12.

Tse

Ahmed

, and Campbell

, “United mixture-model based terrain estimation with Markov random fields,” in Proceedings of the 2012 IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems (MFI '12), pp. 238–243, 2012.

13.

Bogoslavskyi

Vysotska

Serafin

Grisetti

, and Stachniss

, “Efficient Traversability Analysis for Mobile Robots using the Kinect Sensor,” in Proceedings of the 2013 European Conference on Mobile Robots (ECMR '13), pp. 158–163, 2013.

14.

Belter

Labecki

, and Skrzypczynski

, “An exploration-based approach to terrain traversability assessment for a walking robot,” in Proceedings of the 2013 IEEE International Symposium on Safety, Security, and Rescue Robotics, pp. 1–6, 2013.

15.

Nguyen

S. H.

, “A Skowron Quantization of real value attributes-rough set and Boolean reasoning approach,” in Proceedings of 2nd Joint Annual Conference on Information Science, pp. 34–37, Wrightsville Beach, NC, USA, 1995.

16.

Guo