A novel fuzzy three-dimensional grid navigation method for mobile robots

Abstract

The objective of the autonomous navigation aims to achieve the self-motion control for a robot with the environmental feedbacks and becomes popular recently. Problems of complex modeling, large amount of calculation, and lacking of environmental information always exist in autonomous navigation methods. This article proposes a self-navigation method with a fuzzy three-dimensional grid depicted by dual two-dimensional grid maps. Meanwhile, a synthetic preprocess is presented to perform localization through switching among the weighted three-point localization method, the two-point localization method, and the weighted average localization method. For reducing the amount of calculation, an improved fuzzy three-dimensional grid mapping method where the three-dimensional map is described by dual two-dimensional grid maps, the identifier map, and the height map is designed. Especially, the static and dynamic information within the map are divided and updated fuzzily. The global path planning is performed with the static information, and the real-time obstacle avoidance is conducted with the dynamic information. The results of simulations and experiments demonstrate that the proposed method has better properties in efficiency of navigation and lower amount of calculation than the competing methods.

Introduction

Nowadays, intelligent robot application areas expand into every walk of life such as the biped robots, ^{1 –3} unmanned aerial vehicles, ^{4 –6} mobile robots, ⁷ and so on. Among them, the researches on mobile robots always play an important role complying with their better stability. ⁷ Along with the development of mobile robots, researches on self-navigation of the mobile robots have attracted many scholars’ interests. Generally speaking, the autonomous navigation process usually performs three main tasks, localization, mapping, and navigation, and every task plays an important role to the others. ⁸

In earlier times, some navigation methods, such as potential field methods, ^9,10 topological navigation, ^11,12 and so on, are applied frequently. Through these methods, a robot can achieve self-navigation easily, whereas these methods may have some shortcomings. For instance, in potential field method, the singular point may cause the robot to stop at a certain position, and the robot may show decision jitter problem under complex environment. For the more flexible navigation, the adaptive finite state machine (AFSM) integrating the artificial neural network (ANN) classifier with the traditional FSM is applied. ^8,13 Through the ANN, a robot can be trained/adapted to recognize a complex set of state changes. Then, the AFSM allows the mobile robot to autonomously follow a sequence of states/behaviors to reach the destination. However, training data may not be easily obtained and its covering domain may also be the limitation of the method. Facing the problem of large requirement for training data, reinforcement learning is used in some navigation methods. ^14,15 A mobile robot can choose the action with the largest value in a state through updating the values of the Q-table. By reinforcement learning, a mobile robot is able to perform self-learning and self-adapting continuously and to implement the dynamic autonomous navigation under an unknown environment perfectly. The outstanding navigation performance may need a great amount of learning under various scenes, which may be a huge cost on time and energy.

In addition to above-mentioned methods, vision-based navigation is also a hot research direction. Single vision-based navigation is introduced in some works. ^16,17 Feature extraction is executed for recognizing the identification markers. Then, the localization and the autonomous navigation are conducted according to the recognized information. Vision-based navigation combined with other sensors such as laser is also designed. ^18,19 The visual identity is used for scene recognition and marker searching. Meanwhile, sensors are used for capturing the depth information for real-time obstacle avoidance. Vision-based methods have high practicality and flexibility in the complex environments. However, the obtained environmental images change along with the motion of a robot, which may not only result in a complex navigation model but also may have high requirements for the camera’s calibration model and kinematics model.

Contrast to vision-based navigation, grid map-based navigation methods achieve the self-navigation while reducing the resources cost and promoting the running efficiency and speed. ^20,21 In general, grid maps can be divided into two-dimensional (2-D) and three-dimensional (3-D) gird maps. Whereas, traditional 2-D gird map may lack the 3-D environmental information and may make the information about the traversable area be over cut during navigation. In 3-D grid map, there may be more resource consumption compared with 2-D grid.

Complying with the more simple structure and lower resource cost the grid map-based methods have compared to other methods, this article proposed a fuzzy 3-D navigation method (FTGNM). For accurate localization, a synthetic localization approach (SLA) is proposed where a switcher is designed among three proposed localization methods: the weighted three-point localization method (WTPLM), the two-point localization method (Two-PLM), and the weighted average localization method (WALM). Inspired from grid maps, a fuzzy 3-D grid map, described by dual 2-D grid maps, the identifier map, and the height map, is proposed. Especially, the states of objects in the grid map are divided and updated by fuzzy logic. Finally, according to the distribution of static and dynamic objects, the holonomic navigation is constructed, where the global path planning can be executed by the static information, and real-time obstacle avoidance can be performed by the dynamic information. The overall navigation method architecture is improved, resulting in the proposition of this new navigation method architecture. The sections of this article are organized as follows. “Synthetic localization approach” section presents the SLA with switching among three localization methods. The fuzzy 3-D grid mapping method (FTGMM), where dual 2-D grid maps depict a 3-D grid map, is presented in “Fuzzy 3-D grid mapping method” section. The holonomic autonomous navigation logic is given in “Autonomous navigation method” section. “Simulations and experiments” section presents the experimental results obtained on the simulation platform and the real mobile robot to illustrate the performance of the proposed method. The last section presents the conclusions.

Synthetic localization approach

Mobile robots can receive the infrared signals from the sources through the infrared sensors. Then, the distances between the robot and the signal sources can be obtained with the infrared phase ranging method, ²² and the robot’s global position can be calculated through these distances. Considering the number of sensed signal sources is different, an SLA is proposed by switching among three designed localization methods which correspond to different situations. The WTPLM is executed when the robot receives three and more than three source signals. The Two-PLM is utilized within two source signals. And the WALM is conducted when there is only one received source signal.

Especially, while the real-time coordinate of a mobile robot is calculated by the three methods continuously, the last five historic coordinates are recorded continuously as {(x_i , y_i )|i = 1,2,...,5}, where (x ₁, y ₁) is the newest coordinate and (x ₅, y ₅) is the oldest coordinate. In initialization phase, the five coordinates are set to the start coordinate of a robot.

Weighted three-point localization method

When the number of sensed signal sources is three or more than three, the WTPLM is proposed according to the horizontal distances between a mobile robot and sensed signal sources. The specific steps of WTPLM are as follows:

Step 1: Assuming sensed signal sources is SS = {SS1,...,SSN}, corresponding horizontal distances are L = {l ₁,...,l_N }. Then, three signal sources SSi, SSj, SSk(1 ≤ i < j < k ≤ N) are selected from the sources set SS , and the corresponding position (x_ijk , y_ijk ) of the robot can be obtained. Therefore, all the position set is ( X , Y ) = {(x_ijk , y_ijk )|i = 1,...,N − 2;i < j < k ≤ N}.

Step 2: Considering the signal decay, larger distance between a signal source and a robot is, less reliable the localization result is. The average distance ${\tilde{l}}_{ijk}$ between a robot and a signal source combination SSi, SSj, SSk(1 ≤ i < j < k ≤ N) is defined as

${\tilde{l}}_{ijk}=\frac{\left(l_i+l_j+l_k\right)}{3}$

1

Step 3: Repeat step 2, and the average distances $\tilde{\mathit{L}}=\left\{{\tilde{l}}_{ijk}\right|i=1,\mathrm{...},N;i<j\le N;j<k\le N\}$ of all the three signal sources combinations can be obtained. The weights W = {w_ijk |i = 1,...,N − 2;i < j < k ≤ N} of all combinations are defined as

$w_{ijk}=\frac{1}{{\tilde{l}}_{ijk}}/{\displaystyle \sum _{1\le i<j<k\le N}\frac{1}{{\tilde{l}}_{ijk}}}$

2

Step 4: The mobile robot’s final weighted coordinate (x_m , y_m ) can be calculated by

$\left[\begin{array}{c}{x}_m\\ y_m\end{array}\right]=\left[\begin{array}{c}\mathit{X}\\ \mathit{Y}\end{array}\right]\mathit{W}$

3

In particular, calculation process of the robot’s coordinate under the combination of one three signal sources is as follows.

As shown in Figure 1, ∑ w denotes the world projection frame, SSi(i = 1, 2, 3) represents the corresponding infrared signal emitters whose coordinates are (x ₁, y ₁),(x ₂, y ₂),(x ₃, y ₃), the horizontal distances between the mobile robot and the signal sources are l ₁, l ₂, l ₃, and the intersection of the three circles whose center is the signal sources, respectively, is the coordinate of the robot (x_m , y_m ). Consequently

$\{\begin{array}{c}{\left(x_m-x_1\right)}^2+{\left(y_m-y_1\right)}^2=l_1^2\\ {\left(x_m-x_2\right)}^2+{\left(y_m-y_2\right)}^2=l_2^2\\ {\left(x_m-x_3\right)}^2+{\left(y_m-y_3\right)}^2=l_3^2\end{array}$

4

Figure 1.

Three points localization method diagram.

Equation (4) can be transformed into

$\left[\begin{array}{c}{x}_m\\ y_m\end{array}\right]={\mathit{A}}^{-1}\mathit{B}=\left[\begin{array}{c}\frac{K_1}{K}\left(y_2-y_3\right)+\frac{K_2}{K}\left(y_3-y_1\right)\\ \frac{K_1}{K}\left(x_3-x_2\right)+\frac{K_2}{K}\left(x_1-x_3\right)\end{array}\right]$

5

where $\mathit{A}=[2(x_1-x_3),2(y_1-y_3);2(x_2-x_3),2(y_2-y_3)]$ , $\mathit{B}=[x_1^2-x_3^2+y_1^2-y_3^2-l_1^2+l_3^2;x_2^2-x_3^2+y_2^2-y_3^2-l_1^2+l_3^2]$ , $K_1=x_1^2-x_3^2+y_1^2-y_3^2-l_1^2+l_3^2$ , $K_2=x_2^2-x_3^2+y_2^2-y_3^2-l_2^2+l_3^2$ , and $K=2(x_1-x_3)($ $y_2-y_3)-2(x_2-x_3)(y_1-y_3)$ .

Two points localization method

When the number of sensed signal sources is two, the Two-PLM is conducted. The coordinates of the two signal sources A and B are (x_A , y_A ) and (x_B , y_B ), respectively, and the feedback horizontal distances are l_A and l_B . Similar to Figure 1, the mobile robot is located at the intersection of two circles whose center is A or B and radius is l_A and l_B , respectively. Hence

$\{\begin{array}{c}{\left(x-x_A\right)}^2+{\left(y-y_A\right)}^2=l_A{ }^2\\ {\left(x-x_B\right)}^2+{\left(y-y_B\right)}^2=l_B{ }^2\end{array}$

6

In general, two solutions (x _m1, y _m1) and (x _m2, y _m2) can be obtained by solving equation (6), and one of the solutions must be the real coordinate of the robot.

According to the weighted least square method, T ₁ and T ₂ can be calculated by

$\{\begin{array}{l}{T}_1={\displaystyle {\sum }_{i=1}^5{\left(x_i-x_{m1}\right)}^2{\left(y_i-y_{m1}\right)}^2\left(6-i\right)/15}\\ T_2={\displaystyle {\sum }_{i=1}^5{\left(x_i-x_{m2}\right)}^2{\left(y_i-y_{m2}\right)}^2\left(6-i\right)/15}\end{array}$

7

Therefore, the real coordinate of the robot (x_m , y_m ) is (x_mi , y_mi ) with the smallest value between T ₁ and T ₂ with

$\left[\begin{array}{l}{x}_m\\ y_m\end{array}\right]=\{\begin{array}{l}{\left(x_{m1},y_{m1}\right)}^T,T_1\le T_2\\ {\left(x_{m2},y_{m2}\right)}^T,T_1>T_2\end{array}$

8

Weighted average localization method

If the arrangement of the signal sources is unreasonable, the situation may be appear that the number of received signal is only one or zero. If the number is zero, the mobile robot will stop and send out a warning. If the number is one, this situation should be last for a very short time and the general guidance should be rendered. Therefore, a WALM is presented in this article.

According to the historic coordinates {(x_i , y_i )|i = 1, 2,..., 5}, the approximate moving trajectory of the robot could be obtained by line or curve-fitting methods. Five points limit the power of the fitting polynomial to less than 5. Consequently, there will be four fitting polynomial models

$y={\beta }_K^K{x}^K+{\beta }_{K-1}^K{x}^{K-1}+\cdots +{\beta }_1^{K}x+{\beta }_0^K,K=1,2,3,4$

9

The five historic coordinates are substituted into the four fitting functions, and the matrix representations are

$\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_5\end{array}\right]=\left[\begin{array}{cccc}{x}_1^K& x_1^{K-1}& \cdots & 1\\ x_2^K& x_2^{K-1}& \cdots & 1\\ ⋮& ⋮& \ddots & ⋮\\ x_5^K& x_5^{K-1}& \cdots & 1\end{array}\right]\left[\begin{array}{c}{\beta }_K^K\\ {\beta }_{K-1}^K\\ ⋮\\ {\beta }_0^K\end{array}\right],K=1,2,3,4$

10

Then, equation (10) can be transformed into

$Y=X_K{\mathit{\beta }}_K,K=1,2,3,4$

11

Assuming X _ki (i = 1,..., λ, ki ∈ {1, 2, 3, 4}, λ ≤ 4) are full-rank, the corresponding β_Ki has the unique solution, which means λ models can fit the moving trajectory. Assuming the robot moves uniformly, along with the moving direction, $\lambda$ points $\{({\tilde{x}}_i,{\tilde{y}}_i),i=1,\mathrm{...},\lambda \}$ can be calculated. Complying with the fact that the amount of data is too small resulting in that the trajectory is not easy to determine, with the multimodel error correction theory, the average $(\overline{\tilde{x}},\overline{\tilde{y}})$ of $\{({\tilde{x}}_i,{\tilde{y}}_i),i=1,\mathrm{...},\lambda \}$ is calculated as the desired value. Meanwhile, assuming the coordinate of the single signal source A is (x_A , y_A ) and the horizontal distance between A and the robot is l, the intersection of $(\overline{\tilde{x}},\overline{\tilde{y}})$ and circle A is regarded as the robot’s current coordinate (x_m , y_m ) that

${\left(x_m-x_A\right)}^2+{\left(y_m-y_A\right)}^2=l^2$

12

$\frac{\left(y_m-y_A\right)}{\overline{\tilde{y}}-y_A}=\frac{\left(x_m-x_A\right)}{\left(\overline{\tilde{x}}-x_A\right)}$

13

Through this way, the robot could conduct a general motion guidance in signal source situation. This situation may appear in a very short time and a certain range of error could be tolerated. The efficiency of the navigation is mainly related to the WTPLM and Two-PLM. What’s more, this situation should be avoided by increasing the number of signal sources as possible.

Fuzzy 3-D grid mapping method

For researches on mapping, the map projection method and 3-D map method become recently popular. Whereas, the map projection ²⁰ may forsake the height information of the objects, which may be not suitable in some scenes. For instance, chairs and tables are regarded as unpassable with the map projection method, while they may be passable for mobile robot. The 3-D mapping methods such as the 3-D grid construction method ²¹ and the vision-based 3-D reconstruction method ²³ may have a little large amount of calculation which may not satisfy the requirement of the hard real-time property of the embed robot system. Meanwhile, the 3-D-based mapping algorithms may be a little complex. Consequently, in order to obtain enough 3-D information while ensuring the low amount of calculation, this article proposes an FTGMM for mapping. In the map information storage part of FTGMM, an improved 3-D grid map is put forward which has dual 2-D grid maps: one is for identification makers and the other is for height information. In the map information updating part of FTGMM, the states of objects are divided into static or dynamic state through the fuzzy division method.

Improved 3-D grid map

First of all, the size of each mesh of the grid map should be determined, which can affect the calculation amount of searching in the grid map. Generally speaking, the size of each mesh could be set as the same size of the robot. The signal sources and target point should be set in the grid map in the initialization phase. Some particular obstacles could also be preset in the grid map such as the wall and so on.

Then, the grid map can be reconstructed and updated during the motion of a robot. For instance, as shown in Figure 2, Figure 2(a) is the identifier map and Figure 2(b) is the corresponding height map. The sensed obstacles and signal sources are set as different ID numbers in identifier map. In Figure 2(a), the red meshes are the signal sources and the ID numbers such as −1, 5, and 8 are the sensed obstacles. By the sensors of a robot, such as the laser and sonars, the height and size of an obstacle can be obtained. Especially, the height state of obstacles can be suspending, for example, chairs, and complete covering, for example, boxes, and when the obstacle is suspending high enough, the robot is able to pass through. The article uses negative value to represent the suspension height and positive value to stand for the height above ground, and zero or null means there is no obstacle, as shown in Figure 2(b). If the robot cannot perceive the height of complete covering objects, which means the height of objects is large, such as the wall, the height can be given a relative large value.

Figure 2.

Improved 3-D gird map diagram. (a) Identifier grid map. (b) Height information grid map.

Map updating with fuzzy logic

Along with the motion of a robot, the 3-D grid map should be updated real timely. In traditional mapping methods, the state of objects is the same, such as in Lin et al., ²⁰ Lau et al.,²¹ and Endres et al., ²³ and they are all regarded as obstacles. Considering conducting the path planning according to all the objects information is a little complex, in this article, the states of objects are divided into two parts: the static objects and the dynamic objects. The static objects are a position set of objects which do not move within a certain time, and the dynamic objects are a position set of moving objects. Then, the navigation method can be performed according to the static and dynamic information. Especially, objects’ state may change between the dynamic and the static, and there is no clear boundary between the two states, which is to say that it is a fuzzy concept. Therefore, this article makes use of the fuzzy logic ^7,24,25 to divide the objects’ states and update the map of the scene real timely.

Fuzzy judgment for two objects’ relationship

As shown in Figure 3, the x - y represents the world projection frame ∑w; the x_r - y_r denotes the self-frame of a mobile robot. The distance l and angle α between a robot and a sensed obstacle can be obtained by sensors. Meanwhile, through the electronic compass, the real-time pose and the angle β between the x -axis of the self-frame and the x -axis of ∑w can also be obtained. Meanwhile, set the anticlockwise value of the angle is positive. The relative position (Δx, Δy) of the sensed obstacle to the mobile robot can be calculated by

$\left[\begin{array}{l}\Delta x\\ \Delta y\end{array}\right]=\left[\begin{array}{l}l\text{cos}(\alpha +\beta )\\ l\text{sin}(\alpha +\beta )\end{array}\right]$

14

Figure 3.

Relative position diagram of a mobile robot and an obstacle.

Assuming the global coordinate of the robot is (x_m , y_m ), the global coordinate of the sensed obstacle can be calculated by

$\{\begin{array}{c}{x}_o=x_m+\Delta x\\ y_o=y_m+\Delta y\end{array}$

15

When judging the relationship of two sensed objects by fuzzy logic, assuming the distance between them is d, the ratio d/ε is used as the input and the slave state possibility grade of the two objects is selected as the output, where ε is the minimum detection difference between two obstacles and its value should be set according to the actual environment such as the measurement error of the sensors and the scale of each grid in the map. The fuzzy process can be described as follows.

Fuzzifier

• Step 1: According to the membership function as shown in Figure 4(a), the ratio of distance can be fuzzed as “the distance between the obstacles is small (Close)” and “the distance between the obstacles is large (Far).”

• Step 2: The slave state possibility grade of the two obstacles is described as “the two obstacle are the same object (Yes)” and “the two obstacle are not the same object (No)” through the membership function shown in Figure 4(b).

• Step 3: The membership functions corresponding to the two fuzzy input description {Close, Far} are $\{{\mu }_i^d(d/\epsilon )|i=1,2\}$ in turn and the membership functions relative to the two fuzzy output description {Yes, No} are $\{{\mu }_i^g(\text{grade}),i=1,2\}$ in turn. The expression of every membership degree function can be obtained by Figure 4.

• Step 4: n discrete points $\mathit{P}={(p_j)}_{n\times 1}$ are selected uniformly from the input domain. Therefore, every point will have two degrees of trust relative to the two fuzzy input description, and the corresponding input degree of trust discrete matrix $\mathit{\psi }={({\psi }_{ij})}_{2\times n}$ can be constructed. In the same way, m discrete points $\mathit{S}={(s_k)}_{m\times 1}$ are selected uniformly from the output domain and the corresponding output degree of trust discrete matrix is constructed as $\eta ={({\eta }_{ij})}_{2\times m}$ . The calculation formulas of ψ and η are

  $\{\begin{array}{c}{\psi }_{ij}=u_i^d\left(p_j\right)\\ {\eta }_{ik}=u_i^g\left(s_k\right)\end{array},i=1,2;j=1,\mathrm{...},n;k=1,\mathrm{...},m$

  16

• Step 5: The fuzzy rules are appointed as “IF the distance IS Far THEN No; IF the distance IS Close THEN Yes.” According to the “max-min compose operation,” the fuzzy translator $\mathit{R}={(r_{ij})}_{n\times m}$ can be inferred by

  $r_{ij}=\underset{k=1}{\overset{2}{\vee }}({\psi }_{ki}\wedge {\eta }_{kj}),i=1,2,\mathrm{...},n;j=1,2,\mathrm{...},m$

  17

  where “∧” presents choosing the minimum value and “∨” presents choosing the maximum value.

• Step 6: When a distance d ₀ is measured, fuzzification should be conducted to transform d ₀ into a fuzzy input vector $\alpha ={({\alpha }_i)}_{1\times n}$ and the calculation formula is

  ${\alpha }_j=\{\begin{array}{c}0,\left|l_0/\epsilon -p_j\right|\ge 1\\ 1-\left|l_0/\epsilon -p_j\right|,\left|l_0/\epsilon -p_j\right|<1\end{array},j=1,2,\mathrm{...},n$

  18

Inference

• Step 7: According to the “max-min compose operation,” the fuzzy output vector $\beta ={({\beta }_j)}_{1\times m}$ corresponding to the fuzzy input vector α and fuzzy translator R can be calculated by

  ${\beta }_j=\underset{k=1}{\overset{n}{\vee }}({\alpha }_k\wedge r_{kj}),j=1,2,\mathrm{...},m$

  19

Defuzzifier

• Step 8: The final possibility grade result grade₀ can be calculated according to the fuzzy output vector $\beta ={({\beta }_j)}_{1\times m}$ . A weighted average method is used to obtain the average possibility grade with

  ${\text{grade}}_0={\displaystyle {\sum }_{j=1}^m\left(s_j\times {\beta }_j/{\displaystyle {\sum }_{i=1}^m{\beta }_i}\right)}$

  20

• Step 9: Binarization is conducted for the grade₀, and when it is less than 4.5, they are not the same object, otherwise they are the same object.

Figure 4.

Input and output membership function diagram. (a) Distance ratio (input) membership function. (b) Possibility grade (output) membership function.

Map information updating

According to the definition of the improved 3-D grid map, there are two storage areas in the mobile robot system. One is the static object storage area, which records coordinates information of N static objects $\{({x\prime }_i,{y\prime }_i)|i=1,2,\mathrm{...},N\}$ , while the other is the dynamic object storage area, which contains coordinates information of M dynamic objects {(x_j , y_j )|j = 1, 2,..., M}. Meanwhile, N multiplicities are set as $K_i{ }^{\prime },i=1,2,\mathrm{...},N$ for N static objects and the multiplicities are important indexes for the state division.

• a) Initiation

In the beginning, the two storage areas are empty; if one object (x₀ , y ₀) is detected, (x ₀, y ₀) is added into the static object storage area directly until the area is full. Meanwhile, the elements number of dynamic storage matters little and the largest number is M.

• b) Search in static storage

If the elements number in static storage area is N, since M >> N, so the detected objects (x ₀, y ₀) and the static objects $({x\prime }_i,{y\prime }_i)$ should be tested first to determine whether they are the same one. Through fuzzy judgment, each static object is compared and if (x ₀, y ₀) and $({x\prime }_i,{y\prime }_i)$ are the same one, the corresponding multiplicity of static object is ${K\prime }_j={K\prime }_j+1$ . If (x ₀, y ₀) is not the same with any static objects after fuzzy judgment, then we move into the dynamic object fuzzy judgment stage.

• c) Search in dynamic storage

In the dynamic object fuzzy judgment phase, (x ₀, y ₀) initializes a corresponding multiplicity K ₀, and the same method is used for fuzzy judgment and to determine whether the object (x ₀, y ₀) is the same as (x_j , y_j ), and if they are the same, the multiplicity should be K ₀ = K ₀ + 1, and the final value of K ₀ is

$K_0={\displaystyle {\sum }_{j=1}^{M^{\prime }}{k}_j}$

21

where M^′ is the current element number in dynamic object storage area and the calculation formula of k_j is

$k_j=\{\begin{array}{c}1,{\text{grade}}_j\ge 4.5\\ 0,{\text{grade}}_j<4.5\end{array}$

22

where grade _j is the slave state possibility grade of the (x ₀, y ₀) and (x_j , y_j ).

• d) Update static and dynamic storages

If K ₀ is bigger than the minimum of $\{{K\prime }_1,{K\prime }_2,\mathrm{...},{K\prime }_N\}$ , the corresponding coordinate $({x\prime }_i,{y\prime }_i)$ of the minimal ${K\prime }_i$ is deleted from the static object queue, and (x ₀, y ₀) is added. If K ₀ is less than the minimum of $\{{K\prime }_1,{K\prime }_2,\mathrm{...},{K\prime }_N\}$ and the current element number in dynamic storage area is less than M, (x ₀, y ₀) is added into dynamic storage area. Otherwise, the information of the object which has been saved for the longest time in the dynamic storage area is deleted and (x ₀, y ₀) is added instead.

In this way, the information of the static objects and the dynamic objects can be updated, and the coordinate information of the two sets can be shown on the map.

Autonomous navigation method

According to the reconstructed map by FTGMM, the mobile robot can choose a collision-free path in the map. Especially, the static information consisting of static objects is used for global path planning, and the dynamic information is used for real-time obstacle avoidance. Based on the above, the whole navigation logic can be designed. The corresponding flow chart of the proposed navigation method is shown in Figure 5.

Figure 5.

Navigation algorithm flowchart based on FTGNM. FTGNM: fuzzy 3-D navigation method.

As shown in Figure 5, the coordinates of signal sources and target point should be preset in the static storage in advance. The other unique obstacles such as wall can also be initialized in the static storage. Then, according to the static information, the real-time global path planning is conducted. During the mobile robot moves along with the planned path, the obstacles are detected by its sensors, and if the robot finds a dynamic obstacle in the front, it goes back with a distance and conducts obstacle avoidance keeping the global path broadly unchanged. Finally, the static and dynamic information are updated according to the fuzzy logic. The iteration is executed among above steps until the robot arrives at the target point.

Simulations and experiments

In this section, comparisons are conducted to demonstrate the efficiency of proposed method. First, tests are made for the WTPLM and the Two-PLM, through compared with the binocular ranging localization method (BRLM) ^26,27 to illustrate the high accuracy of the WTPLM. In order to illustrate the practicability of the proposed fuzzy state division method in “Fuzzy judgment for two objects’ relationship” section, comparison is made between the linear binary divided method and the fuzzy division method. For showing the low amount of calculation the proposed FTGMM has, the practical mapping results of the proposed FTGMM, the traditional 2-D grid mapping method (Two-DGMM) ²⁰ and the 3-D grid mapping method (Three-DGMM) ²¹ are compared. In the proposed FTGNM, the objects are divided into the static objects and dynamic objects, and the corresponding dynamic path planning method is designed. Hence, the final navigation results of the FTGNM and the vision-based navigation method ^8,23 with all the objects being regarded as the static objects to demonstrate the efficiency of the proposed method.

As shown in Figure 6, the comparisons are tested in a structural lab whose width is about 10 m, length is 10 m, and height is 3 m. U-bot is used as the mobile robot platform, and the obtained information is then sent to a computer for running the navigation methods. All the conditions, such as the light, star point, target point, distributions of obstacles, and so on are the same in every methods.

Figure 6.

Experimental environment.

Localization test

Multi-point localization

In SLA, if the signal sources are arranged reasonably, the number of the sensed signal sources should be always three or more than three; namely, the WTPLM is used most frequently so that it is most important in SLA. Hence, in order to demonstrate the efficiency of the proposed WTPLM, the WTPLM is compared with the single three-point localization method (STPLM) firstly. Considering the signal decay, different distances of the signal sources are tested. As shown in Figure 7, four signal sources marked A, B, C, and D are arranged and the localization results of WTPLM are compared with the results of the combination A, B, and C and results of the combination B, C, and D. During the test, the positions of the mobile robot are changed and the localization error is defined as

$e=\sqrt{{\left(x^{*}-x_m\right)}^2+{\left(y^{*}-y_m\right)}^2}$

23

Figure 7.

Multipoint localization comparison scene diagram.

where (x ^*, y ^*) is the real coordinate in the world projection frame and (x_m , y_m ) is the calculated coordinate by localization method.

Fifty positions are selected for testing, and the errors of WTPLM, STPLM with signal sources A, B, C (STPLM-ABC), and STPLM with signal sources B, C, D (STPLM-BCD) are compared and shown in Figure 8.

Figure 8.

Multipoint localization comparison results.

From Figure 8, the localization errors of STPLM-ABC with the smallest distances waving from 0.0 m to 0.07 m, and the errors of STPLM-BCD with the largest distances waving from 0.0 m to 0.29 m. The reason is that the distribution of the signal sources can affect the localization accuracy of the STPLM. Meanwhile, the errors of WTPLM is 0.0–0.11 m which shows that the WTPLM could reduce the influence of the far signal sources so that the accuracy can be increased. In addition, for a generic application, WTPLM could weaken the influence of the abnormal points which could cause the STPLM failure.

Localization comparisons among different methods

Similarly, the WTPLM, the Two-PLM, and the BRLM ^26,27 are compared. Especially, 100 positions are selected for testing, and the localization errors are shown in Figure 9, and the fluctuation results are shown in Table 1.

Figure 9.

Localization comparison with different methods.

Table 1.

Fluctuation results comparison of different localization methods.

Method name	Error range	Error mean	Error variance
Two-PLM	0.0–0.3 m	0.182 m	0.0087 m2
WTPLM	0.0–0.13 m	0.06 m	0.0015 m2
BRLM	0.0–0.11 m	0.055 m	0.00127 m2

Two-PLM: two points localization method; WTPLM: weighted three points localization method; BRLM: binocular ranging localization method.

From Figure 9 and Table 1, it can be obtained that the accuracy of Two-PLM is lower than WTPLM and BRLM; meanwhile, the accuracy of WTPLM and BRLM is similar and is high enough for navigation. In this article, an SLA is proposed which designs different methods for different signal sources number. Among the proposed localization methods, the WTPLM, the Two-PLM, and the WALM, the accuracy of WTPLM is highest and the other methods could give a general guidance for the mobile robot. Consequently, the SLA gives a kind of synthetic localization architecture which could be a reference for other researches.

Fuzzy logic comparison

Setting the parameters of fuzzy logic with n = 5, m = 4, and ε = 0.8m, the corresponding fuzzy membership function matrix tables ψ and η are shown in Tables 2 and 3. Thirty-one test values are selected from 0 m to 2.4 m for every 0.08 m, and the values are fuzzed by equation (18). Then, the fuzzy output results through equations (19) and (20) can be calculated and the results are shown in Figures 10 and 11.

Table 2.

Input degree of trust discrete matrix table.

Ratio Description	0	0.5	1	1.5	2
Close	1	1	0.5	0	0
Far	0	0	0.5	1	1

Table 3.

Output degree of trust discrete matrix table.

Grade Description	0	3	6	9
Yes	0	0	0.5	1
No	1	0.5	0	0

Figure 10.

Fuzzy input diagram. (a) Linear distribution of input. (b) Fuzzy result of input relative to 0. (c) Fuzzy result of input relative to 0.5. (d) Fuzzy result of input relative to 1. (e) Fuzzy result of input relative to 1.5. (f) Fuzzy result of input relative to 2.

Figure 11.

Fuzzy output diagram. (a) Fuzzy average result of output. (b) Fuzzy result distribution of grade 0. (c) Fuzzy result distribution of grade 3. (d) Fuzzy result distribution of grade 6. (e) Fuzzy result distribution of grade 9.

From Figures 10 and 11, linear input is converted into a smooth curve result, which is very suitable for real control system. Thus, this fuzzy division method is more applicable to the object state division than the absolute division with the linear binarization.

Mapping comparison

In order to prove that the method proposed in this article is of high efficiency and low amount of calculation, the FTGMM, Two-DGMM ²⁰ , and Three-DGMM ²¹ are compared. During the comparison, the conditions such as the size of mesh are the same.

Saving information test

As shown in Figure 12, tables and boxes are ranged in the environment with sensed height value −50 and 80 cm; the “O” is the target point and the green curve is the robot’s moving trajectory.

Figure 12.

Mapping comparison between FTGMM and Two-DGMM. (a) Photo sequence of passing the table by FTGMM. (b) Photo sequence of going around the table by Two-DGMM. (c) Moving trajectory in FTGNA (fuzzy three-dimensional grid navigation algorithm). (d) Moving trajectory in Two-DGMM. FTGMM: fuzzy 3-D grid mapping method; Two-DGMM: 2-D grid mapping method.

It can be observed from Figure 12(a) and (b) that the mobile robot can pass through the table by FTGNM, while it goes around the table by Two-DGMM. The reason is that in 2-D grid, the table is not passable, which means 2-D grid lacks of the 3-D environmental information. Therefore, FTGNM could save more 3-D environmental information than 2-D grid while ensure the low calculation amount.

Amount of calculation test

Similar to 2-D grid map, in Three-DGMM, the environment is divided into many cubes, and the distribution information of the objects are stored in the cubes. The reconstruction for the experimental scene shown in Figure 6 is conducted by proposed FTGMM and Three-DGMM, respectively, and the reconstructed results are shown in Figure 13.

Figure 13.

Reconstructed map comparison between FTGMM and Three-DGMM. (a) Identifier map of FTGMM. (b) Height map of FTGMM. (c) Reconstructed map of Three-DGMM. FTGMM: fuzzy 3-D grid mapping method; Three-DGMM: 3-D grid mapping method.

It can be seen in Figure 13 that the proposed FTGMM uses dual 2-D grid map to describe the scene, as shown in Figure 13(a) and (b). The Three-DGMM uses a 3-D grid to describe the scene, as shown in Figure 13(c), while there are many 3-D meshes having no elements and that will be waste of the resources. In addition, it is obvious that when conducting the path planning, the amount of calculation of searching best collision-free path in Three-DGMM is larger than the proposed FTGMM. Therefore, it is proved that FTGMM can reduce the amount of calculation while ensuring enough 3-D environmental information which could satisfy the hard real-time property of the embed robot system better.

Navigation test

This article proposes an FTGNM where the state of objects is divided into static and dynamic objects, and the global path planning is performed with the static information, and the real-time obstacle avoidance is executed with the dynamic information. In order to illustrate the efficiency of the proposed FTGNM, it is compared with the vision-based navigation method, ^8,23 where the objects are regarded as the same and the path is planned with all the sensed objects.

As shown in Figure 6, a person is walking in the scene as the moving obstacles. The FTGNM conducts navigation with its sensors. The vision-based navigation method performs navigation with a Kinect. Kinect is a line of motion sensing input devices by Microsoft for Xbox 360 and Xbox One video game consoles and Microsoft Windows PCs. Through the Kinect and RGB recognition method, an object can be recognized and the distance between the object and the robot can be obtained. With the distance information, the vision-based navigation method can calculate its coordinate and obtain the environmental map. At last, the navigation could be executed. The conditions of two methods are the same for a fair comparison. The map reconstructions of two methods are all conducted during robot’s moving and the map is updated continuously. Every methods are test for 10 times and the average motion trajectories are shown in Figures 14 and 15. The real-time trajectories in every T=30 s time are recorded. In Figures 14 and 15, the red dashed is the global planed path of the FTGNM based on the static map information, and the green curve is the actual path.

Figure 14.

Navigation result of FTGNM. (a) 1T. (b) 2T. (c) 3T. (d) 4T. (e) 5T. (f) 6T. FTGNM: fuzzy 3-D navigation method.

Figure 15.

Navigation result of vision-based navigation method. (a) 1T. (b) 2T. (c) 3T. (d) 4T. (e) 5T. (f) 6T. (g) 7T. (h) 8T.

From Figure 14, it is obvious that the global planed path is a guidance for the mobile robot and the real-time obstacle avoidance is conducted, which leads to that the general directions of the global path and the actual path are the same in FTGNM. Meanwhile, compared to the FTGNM, the path of the vision-based navigation is smoother. However, the objects in this method are all regarded as the obstacle, and there is no global path for guidance. For instance, in Figure 15(d), the robot regards the person as a static object, and the global path is replanned, while in FTGNM, the person is regarded as dynamic object and for real-time obstacle avoidance. So, the time cost of vision-based navigation method is longer than FTGNM, 6 T, with 8 T. It can be proved that the faster and higher efficient navigation can be achieved through dividing the state of objects into static and dynamic objects fuzzily with the static information for global path planning and the dynamic information for real-time obstacle avoidance.

In addition, FTGNM needs signal sources to be set in advance, while the vision-based navigation methods don’t need that. However, along with the development of technology, many public equipment, such as the Wi-Fi base stations, mobile phone signal base stations, and so on, can be used as the signal sources. Hence, if the environment has the condition of signal sources, the proposed FTGNM may conduct the more efficient navigation than the vision-based navigation, no matter indoor or outdoor.

Conclusions

Since problems such as complex modeling, large amount of calculation, lacking of environmental information, and so on always exist in autonomous navigation methods, this article proposes an FTGNM to achieve fast and practical self-navigation. To be specific, an SLA is designed for accuracy localization with different signal sources number. Then, an FTGMM is presented with dual 2-D grid maps describing a 3-D map to reduce the amount of calculation of mapping and path planning. Especially, according to the fuzzy logic, the state of objects is divided into static and dynamic objects, and the two objects are used for global path planning and real-time obstacle avoidance, respectively, to promote the navigation efficiency. The results of simulations and experiments demonstrate that the proposed FTGNM can achieve fast and efficient navigation while ensure the low amount of calculation that has a certain promoting for the mobile robot autonomous navigation technology field.