A Novel Grey-RSS Navigation System Design for Mobile Robots

A Novel Grey-RSS Navigation System Design for Mobile Robots

Albert Wen-Long Yao*, 1, Hsin-Te Liao2, and Shiou-De Chen1

1Department of Mechanical and Automation Engineering, National Kaohsiung First University of Science and Technology, Taiwan
2Department of Mechanical Engineering of Ming-Hsin University of Science and Technology, Taiwan

(Received 12 January 2012; Accepted 13 February 2012; Published on line 1 June 2012)
*Corresponding author: yao@nkfust.edu.tw
DOI: 10.5875/ausmt.v2i2.137

Abstract: This study aims at developing a novel intelligent navigation system for mobile robots that eliminates cumulative errors by using a conventional optical encoder. The optical encoder for mobile robots was supplanted by an intelligent Grey-RSS navigation system (IGRNS) with a RFID system embedded with a RSS (Received Signal Strength) location estimation scheme and a Grey predictor for robot rotation angle prediction. The RFID system indicates the target with active RFID tag. The RSS location estimation scheme then calculates the possible route of robot. The Grey controller optimizes the traveling route quickly. The simulation result shows that the proposed IGRNS can reduce robot’s unnecessary rotation in order to locate the target. With IGRNS, mobile robot takes fewer steps to reach target quickly. The performance of IGRNS is better than the one of RSS navigation system.

Keywords: Intelligent Grey-RSS navigation system; RFID; Navigation system; Mobile robot

I. Introduction

Nowadays, robots have more and more functional applications, as well as come in a number of different forms, such as navigational robots, cleaning robots, security robots, nursing care robots, and so on. These intelligent robots usually need to move freely in their work areas. As such, it is very important to be able to recognize a robot’s position. Generally, GPS technology is able to provide outdoor navigation robots accurate navigation and positioning functions. However, the navigation and positioning jobs of an indoor mobile robot become more complicated due to the obstacle of being indoors. This situation has drawn a lot of attention from researchers to develop a suitable navigation and positioning system for indoor mobile robots.

Generally, the conventional robot navigation and positioning system is composed of optical encoders and gyroscopes (Figure 1). The robot has to know the distance between the starting point and the destination. Surveying the topography and environment has to be done beforehand, and is usually a very time-consuming task. Another difficulty encountered with indoor robots comes from wheel-sliding after the robots travel long distances. This can generate serious positioning error after long distance traveling of robot, and the cumulative error becomes troublesome to deal with.

There are a number of studies in the literature addressing indoor mobile robots and the issue of cumulative error. Yu [1] developed an obstacle avoidance robot by using a wheel drive and optical encoder navigation method. He explained that cumulative error comes from wheel sliding while a robot is turning. He claimed the error may be avoided by using larger wheels or high resistance rubber wheels. Jeng [2] claimed that positioning accuracy can be raised by using optical flow sensors instead of using optical encoders. Bahl and Padmanabhan [3] developed a RADAR (Radio Detection and Ranging) system with active RF badges. The active badges spread infrared signals which were picked up by a receiver. They adopted the actual measurement and signal propagation model to identify the position of the robot. Ni, Liu and Patil [4] presented a LANDMARC (Location Identification based on Dynamic Active RFID Calibration) system for indoor robot positioning. Their system uses four readers and 16 active tags for position calculation and tracking. This system employs reference tags to improve the accuracy of positioning.

The cumulative error of mobile robots occurs because of the inherent character of optical encoders and the robot wheels after moving a long distance. To construct map information is also very time-consuming and laborious. This has lead us to develop an intelligent navigation system for indoor mobile robots. This paper is organized as follows: Section II describes the applied methodologies; Section III illustrates the design of the system; Section IV presents and discusses the simulation results; and Section V presents the conclusion.

II. Methodology

In order to locate the position of the target, this proposed system adopted RFID technology, the RSS method and Grey prediction theory. The distance and orientation of the target destination is estimated by measuring the signal strength of the RFID tag on the target. The positioning method is done by RSS and Grey prediction theory. Because the measured signal strength is easily disturbed by the indoor environment, a lot of error may be generated. As a result, the robot can, hardly reach the target. Therefore, we adopted Grey prediction theory to improve and optimize the route estimation and the navigation path.

RSS Method

The RSS method is based on the power propagation model of a signal to calculate the distance between the transmitter and receiver [5]. In the free space of electromagnetic wave propagation, the power will decay with distance. The Equation of radio propagation is

\[{{P}_{r}}(r)=\frac{{{P}_{t}}\cdot {{G}_{t}}\cdot {{G}_{r}}\cdot {{\lambda }^{2}}}{{{(4\pi )}^{2}}\cdot {{r}^{2}}\cdot L},\tag{1}\]

where \({{P}_{r}}(r)\) is the received power; \({{P}_{t}}\) is the transmitted power; \({{G}_{t}}\) is the transmit antenna gain; \({{G}_{r}}\) is the receiving antenna gain; \(\lambda \) is wavelength; \(r\) is propagation distance; \(L\) is system loss factor. In Equation (1), only the distance (r) is unknown, and the others are measureable or system constants.

Figure 2 is the pictorial illustration of the RSS algorithm. For distance calculation, move the receiver to three places around the transmitter to measure their individual strength of receiving the RFID signal. Then, draw three circles using the location of the receivers as the center and the distance from the transmitter as radius. The Equation for distance calculation is:

\[{{r}_{i}}=\sqrt{{{({{x}_{i}}-x)}^{2}}+{{({{y}_{i}}-y)}^{2}}},\tag{2}\]

where \({{r}_{i}}\) is the distance between transmitter and receiver; \(({{x}_{i}},{{y}_{i}})\) is the location of the receiver; \((x,y)\) is the location of transmitter. From these measurements and Equation (2), the location of transmitter can be calculated by:

\[\left[ \begin{matrix} x \\ y \\\end{matrix} \right]={{({{A}^{T}}A)}^{-1}}({{A}^{T}}B),\tag{3}\]

where

\(A=\left[ \begin{matrix} 2({{x}_{2}}-{{x}_{1}}) & 2({{y}_{2}}-{{y}_{1}}) \\ 2({{x}_{3}}-{{x}_{1}}) & 2({{y}_{3}}-{{y}_{1}}) \\ \vdots & \vdots \\ 2({{x}_{n}}-{{x}_{1}}) & 2({{y}_{n}}-{{y}_{1}}) \\\end{matrix} \right]\) ,
\(B=\left[ \begin{matrix} r_{1}^{2}-r_{2}^{2}+x_{2}^{2}+y_{2}^{2}-x_{1}^{2}-y_{1}^{2} \\ r_{1}^{2}-r_{3}^{2}+x_{3}^{2}+y_{3}^{2}-x_{1}^{2}-y_{1}^{2} \\ \vdots \\ r_{1}^{2}-r_{n}^{2}+x_{n}^{2}+y_{n}^{2}-x_{1}^{2}-y_{1}^{2} \\\end{matrix} \right]\).

Trajectory Calculation Algorithm

Adopting the RSS algorithm to get the transmitter’s coordinates needs three receiver locations. The calculation algorithm is shown in Figure 3. The location coordinate can always be calculated from the trajectory \(({{x}_{1}},{{y}_{1}})\), \(({{x}_{2}},{{y}_{2}})\),…, \(({{x}_{n}},{{y}_{n}})\) of the robot by the reverse calculation method.

At the start, the coordinates of the robot are at the origin, \(({{x}_{0}},{{y}_{0}})=(0,0)\). The rotation angle is zero, \({{\phi }_{0}}=0\). The next coordinates \(({{x}_{1}},{{y}_{1}})\) can be obtained from as follows:

\[{{x}_{1}}={{x}_{0}}+[-s\cdot \cos (-{{\phi }_{0}})]=-S\]
\[{{y}_{1}}={{y}_{0}}+[-s\cdot \sin (-{{\phi }_{0}})]=0\]

In the same way, \(({{x}_{2}},{{y}_{2}})\) can also be obtained from \(({{x}_{1}},{{y}_{1}})\). Hence, the nth position \(({{x}_{n}},{{y}_{n}})\) can be ascertained from \(({{x}_{n-1}},{{y}_{n-1}})\):

\[{{x}_{n}}={{x}_{n-1}}+[-s\cdot \cos (-({{\phi }_{0}}+{{\phi }_{1}}+\cdots +{{\phi }_{n-1}}))]\]

\[{{y}_{n}}={{y}_{n-1}}+[-s\cdot \sin (-({{\phi }_{0}}+{{\phi }_{1}}+\cdots +{{\phi }_{n-1}}))]\]

Let \({{\phi }_{total}}=\sum\limits_{i=0}^{n-1}{{{\phi }_{i}}}\), the Equations can be simplified as:

\[{{x}_{n}}={{x}_{n-1}}-s\cdot \cos ({{\phi }_{total}})\tag{4}\]
\[{{y}_{n}}={{y}_{n-1}}+s\cdot \sin ({{\phi }_{total}})\tag{5}\]

Equations (4) and (5) are the formula for the trajectory calculation. In conjunction with the RSS algorithm, the coordinates of target \((x,y)\) can be calculated. Figure 4 shows the flowchart of coordinate calculation algorithm.

Grey Prediction Algorithm

Grey theory was first introduced by Prof. Deng in 1982 [6]. The main merit of Grey theory is that to build up a Grey model (GM), one only needs at least four historical data. The Grey prediction model is as follows:

Step 1. Form a row matrix:

\[\begin{align} & {{x}^{(0)}}=\{{{x}^{(0)}}(1),\text{ }{{x}^{(0)}}(2),\text{ }\ldots ,\text{ }{{x}^{(0)}}(n)\} \\ & =({{x}^{(0)}}(k),k=1,2,3,\cdots ,n) \\ \end{align}\tag{6}\]

Step 2. Accumulated Generating Operation (AGO):

\[\begin{align} & {{x}^{(1)}}=\{{{x}^{(1)}}(1),\text{ }{{x}^{(1)}}(2),\text{ }\ldots ,\text{ }{{x}^{(1)}}(n)\} \\ & =({{x}^{(1)}}(k),k=1,2,3,\cdots ,n) \\ \end{align}\tag{7}\]

where \({{x}^{(1)}}(k)=\sum\limits_{1}^{k}{{{x}^{(0)}}(m)}\).

Step 3. Form Grey differential Equation:

\[{{z}^{(1)}}=({{z}^{(1)}}(2),\text{ }{{z}^{(1)}}(3),\text{ }\ldots ,\text{ }{{z}^{(1)}}(n))\tag{8}\]

where \({{z}^{(1)}}(k)=0.5{{x}^{(1)}}(k)+\text{0}\text{.5}{{x}^{(1)}}(k-1)\).

Step 4. Form data matrix B and data vector YN:

\[B=\left[ \begin{matrix} -{{z}^{(1)}}(2) & 1 \\ -{{z}^{(1)}}(3) & 1 \\ -{{z}^{(1)}}(4) & 1 \\\end{matrix} \right],{{y}_{N}}=\left[ \begin{matrix} {{x}^{(0)}}(2) \\ {{x}^{(0)}}(3) \\ {{x}^{(0)}}(4) \\\end{matrix} \right]\tag{9}\]

Step 5. Solve model parameter:

\[\left[ \begin{matrix} a \\ b \\\end{matrix} \right]={{\left( {{B}^{T}}B \right)}^{-1}}{{B}^{T}}{{y}_{N}}\tag{10}\]

Step 6. Form Grey prediction model:

\[{{\hat{x}}^{(1)}}(k+1)=\left( {{x}^{(0)}}(1)-\frac{b}{a} \right){{e}^{-ak}}+\frac{b}{a}\tag{11}\]
\[{{\hat{x}}^{(0)}}(k+1)={{\hat{x}}^{(1)}}(k+1)-{{\hat{x}}^{(1)}}(k)\tag{12}\]

Step 7. Restore the demand prediction value:

\[{{\hat{X}}^{(0)}}(k+1)=(1-{{e}^{a}})\left[ {{X}^{(0)}}(1)-\frac{b}{a} \right]{{e}^{-ak}}\tag{13}\]

where ^ denotes a Grey prediction value.

III. System Design

RFID System Design

RFID is a non-contact automatic identification system. A RFID reader with 2.4 GHz frequency and active tags are used in this study. Figure 5 shows the curve of measured signal strength versus distance of the RFID system. The measured data are illustrated as circles. A curve fitting Equation (14) is shown in solid line as follows:

\[0.0002{{x}^{2}}-0.2052x+194.9023-RSS=0.\tag{14}\]

To solve Equation (14):

\[x=570-\frac{\sqrt{0.0421-0.0008\times (194.9023-RSS)}}{0.0004}.\tag{15}\]

This Equation (15) is the relation of signal strength and distance in the program.

Navigation System Design

Due to the environment and the limitation of RFID, the signal strength of RFID will be affected. In undertaking our experiment, we proposed three rules based on signal strength data for analysis:

Rule 1: Signal strength changes suddenly: When the slope of the curve is larger, i.e., the signal strength rate is higher, and the signal strength should be averaged, we will take the mean of the past five data as the referred signal strength.

Rule 2: Signal strength decreases dramatically: When the signal strength decreases dramatically, the robot may go astray. The system should be restarted for a new route.

Rule 3: Signal strength increases dramatically: When the signal strength increases dramatically, it implies that the robot is approaching the target destination. It should stop rotating. The mechanism is as follows in Figure 6.

Grey Prediction Controller Design

A Grey prediction controller will assist the robot to optimize its navigation rout and shorten its path to the target. The robot’s steps of movement are shown in Table 1, and its navigation diagram is shown in Figure 7. The signal strength and distance conversion are calculated by Equation (15). The explanation is as follows:

Step 1: From start point, robot’s initial coordinate is \(({{x}_{0}},{{y}_{0}})\) with measured signal strength RSS0. Let the rotation angle be \({{\varphi }_{0}}=0\). The robot doesn’t rotate, and the assumed target is \(({{a}_{1}},{{b}_{1}})\). Robot will move a distance S.

Step 2: The robot is at a new location \(({{x}_{1}},{{y}_{1}})\), with measured signal strength RSS1. With RSS0, RSS1, and S, the new target \(({{a}_{2}},{{b}_{2}})\) can be calculated by the cosine theorem. It is solved to get \(({{r}_{1}},{{\varphi }_{1}})\) of \(({{x}_{1}},{{y}_{1}})\) to \(({{a}_{2}},{{b}_{2}})\). The robot will rotate \({{\varphi }_{1}}\) angle and move S distance to location \(({{x}_{2}},{{y}_{2}})\).

Step 3: The robot is at new location \(({{x}_{2}},{{y}_{2}})\), with measured signal strength RSS2. With RSS0, RSS1, RSS2, and S, the new target \(({{a}_{3}},{{b}_{3}})\) can be calculated. It is solved to get \(({{r}_{2}},{{\varphi }_{2}})\) from \(({{x}_{2}},{{y}_{2}})\) to \(({{a}_{3}},{{b}_{3}})\). The robot will rotate angle and move S distance to location \(({{x}_{3}},{{y}_{3}})\).

Step 4: The robot is at new location \(({{x}_{3}},{{y}_{3}})\), with measured signal strength RSS3. With RSS1, RSS2, RSS3, and S, the new target \(({{a}_{4}},{{b}_{4}})\) can be calculated. It is solved to get \(({{r}_{3}},{{\varphi }_{3}})\) from \(({{x}_{3}},{{y}_{3}})\) to \(({{a}_{4}},{{b}_{4}})\). From this step, the algorithm will check the condition \(RSS\text{ }0\) < \(RSS\text{ }1\) < \(RSS\text{ }2\) < \(RSS\text{ }3\), which means the robot is on the right track toward the target, to start the Grey prediction mechanism. If the conditions are met, the Grey prediction mechanism will be started.

When \(RSS\text{ }0\) < \(RSS\text{ }1\) < \(RSS\text{ }2\) < \(RSS\text{ }3\), the program will calculate the next point \(({{{x}'}_{4}},{{{y}'}_{4}})\) from \(({{x}_{3}},{{y}_{3}})\) and \({{\varphi }_{3}}\). However, the Grey controller will predict the next angle \({{{\varphi }'}_{4}}\) according to the inputs of \({{\varphi }_{0}}\), \({{\varphi }_{1}}\), \({{\varphi }_{2}}\) and \({{\varphi }_{3}}\). With the predicted angle \({{{\varphi }'}_{4}}\) and location \(({{{x}'}_{4}},{{{y}'}_{4}})\), the next point \(({{{x}'}_{5}},{{{y}'}_{5}})\) can be obtained. If the robot moves from \(({{x}_{3}},{{y}_{3}})\) to \(({{{x}'}_{5}},{{{y}'}_{5}})\) with adjusted angle \({{\varphi }_{3}}+{{{{{\varphi }'}}_{4}}}/{2}\;\), it will reduce the robot’s unnecessary rotating. The Grey controller will repeat Step 4 as long as the signal strength continually increased. Otherwise, it will follow the RSS algorithm to guide the robot to the target.

IV. Simulation and Results

The simulation program with GUI was developed in Windows API (Application Programming Interface) and VB 6.0 to evaluate the performance of the traditional RSS navigation algorithm and novel IGRNS algorithm.

In the simulation, the RSS value was the real signal strength (160) with random disturbance with tolerance ±1, ±2, and ±3. The unit stroke of robot was 10 cm in the simulation experiment. From the GUI, the RSS/IGRNS mode, target location, and disturbance level could easily be selected or entered (see Figures 8 and 9).

Figures 8 and 9 show the simulation results of RSS and IGRNS algorithms with target distance 400 cm and 60° angle. The robot took 29 steps to reach the target with RSS algorithm, using 16 steps to adjust its direction. On the other hand, the robot only took 22 steps to reach the target with IGRNS algorithm. Table 2 shows the experimental results of RSS algorithm and IGRNS algorithm with different rotation angles and disturbance level. It indicates that performance of IGRNS is superior to that of the RSS.

V. Conclusion

A novel IGRNS algorithm was presented in this paper. The simulation results show that the proposed IGRNS algorithm can eliminate the cumulative error of optical encoder-based navigation. With the intelligence of Grey prediction, the IGRNS can reduce a robot’s unnecessary rotation in order to locate the target destination. With IGRNS, the mobile robot takes fewer steps to reach a target quickly. The performance of IGRNS is better than that of RSS navigation system by 1.70%, 3.11%, and 9.27% under disturbance level of ±1, ±2, and ±3 respectively.

Acknowledgement

The authors thank National Science Council for partial support under the Grant no. (NSC-100-2221-E-327-007).

References

  1. C. T. Yu, "Obstacle avoiding device for car-like mobile robot with fuzzy theorem realized by digital signal processors," M.S. Thesis, Institute of Automatic Control Engineering, Feng Chia University, Taichung, Taiwan, 2005.
  2. J. H. Cheng, "Spatial path tracking system design for an omnidirectional platform using optical flow sensors," M.S. Thesis, Institute of Electrical Control Engineering, National Chiao Tung University, Hsinchu, Taiwan, 2006.
  3. P. Bahl and V. N. Padmanabhan, "Radar: An in-building RF-based user location and tracking system," in Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2000), Tel Aviv, Israel, 2000, pp. 775 -784 vol.772-775 -784 vol.772.
    doi: 10.1109/INFCOM.2000.832252
  4. L. M. Ni, Y. Liu, Y. C. Lau, and A. P. Patil, "LANDMARC: Indoor location sensing using active RFID," Wireless Networks, vol. 10, no. 6, pp. 701-710, 2004.
    doi: 10.1023/B:WINE.0000044029.06344.dd
  5. E. E. L. Lau and W. Y. Chung, "Enhanced RSSI-based real-time user location tracking system for indoor and outdoor environments," in International Conference on Convergence Information Technology, Gyeongju, Korea, 2007, pp. 1213-1218.
    doi: 10.1109/ICCIT.2007.253
  6. J. L. Deng, "Introduction to grey system theory," The Journal of Grey System, vol. 1, no. 1, pp. 1-24, 1989.

Refbacks

  • There are currently no refbacks.


Copyright © 2011-2017  AUSMT   ISSN: 2223-9766