# Wireless Sensor Network and RFID Fusion Approach for Mobile Robot Navigation

Authors: Guillermo Enriquez; Sunhong Park; Shuji Hashimoto
Journal: ISRN Sensor Networks
 (2013)

---

## Abstract

There are numerous applications for mobile robots that require relatively high levels of speed and precision. For many systems, these two properties are a tradeoff, as oftentimes increasing the movement speed can mean failing to detect some sensors. This research attempts to create a useful and practical system by combining a wireless sensor network with a passive
radio frequency identification system. The sensor network provides fast general navigation in open areas and the radio frequency identification system provides precision navigation near static obstacles. By fusing the data from both systems, we are able to provide fast and accurate navigation for a mobile robot. Additionally, with WSN nodes and passive RFID tag mats, the system infrastructure can be easily installed in existing environments.


---

## Body

## 1. Introduction

In ubiquitous robotics, there are several applications for mobile robots that require relatively high levels of precision. In this research, we developed a system that balances the trade-off of speed and precision for mobile robot navigation around static obstacles. The system uses higher speeds when the area is free of obstacles, via a wireless-sensor-network-based (WSN) navigation approach. Around obstacles, or when a specific path or pose is required, the system incorporates a Radio Frequency IDentification (RFID) system, for precise navigation. By fusing the data from both systems using a simple, vector-based approach, we are able to provide fast and accurate navigation for a mobile robot. RFID tag mats were also developed which, along with easily installed wireless sensor nodes, make for quickly deployed system infrastructure. This system focuses on using this fusion approach for indoor mobile robot navigation with static obstacle avoidance. While the avoidance of dynamic obstacles is also key for ubiquitous robotics, there is still room for improvement in static obstacle avoidance. Moreover, the vast majority of applications for indoor robot navigation have a large static obstacle component to them. It is for this reason that we chose to focus first on this aspect.A simple taxonomy for robot sensors (pertaining to navigation) could be listed as such: vision (cameras, etc.), range-finding (laser, sonar, etc.), inertial (encoders, etc.), active beacons (active RFID, WSN, etc.), and passive beacons (passive RFID, magnetic strips, etc.). All of these systems have their advantages and disadvantages. For instance, range-finding can suffer from inaccuracy when there are few reflective surfaces and vision systems often have a high computational cost and can suffer from reliability problems due to poor lighting. Ideally, when fusing two sensors, they would have complementary properties. For this system, we chose to focus on combining active and passive radio systems. Active beacons generally broadcast their own radio signals independently. Usable anywhere the signal can be read, the robot can travel at higher speeds. A drawback however is that radio waves suffer from instability, due to attenuation and environmental factors. Passive systems on the other hand give high levels of precision, assuming the tag location is known. However, robot speed must be restricted, as tags can be missed at high speeds. Both are well used independently, but there is limited use of them combined. For instance, in [1] a WSN only navigation approach for mobile robots is proposed. This system allowed the robot to navigate without additional obstacle avoidance techniques and at relatively high speeds. However, it suffered from a lack of precision. Conversely, in [2] an RFID only approach was presented. Though precise, the robot was required to move at relatively low speeds to ensure tag reading. In [3] a system combining both was proposed. That system showed a reduction of nodes required, particularly of passive nodes. With their short range, most passive-only approaches require the installation of a large number of tags throughout the navigable area, but with the active nodes the same area can be covered with drastically fewer nodes. The system proposed here also combines WSN and RFID for mobile robot navigation, able to navigate using the WSN in wide open areas and use RFID tags only in areas that required high precision.Originally, WSNs were designed to interface with a variety of sensors while using the network for data collection over a large area or when wired sensing solutions were impractical. RFID technology was initially envisioned as a method to detect the presence of tagged objects/people and provide their location. Although both WSNs and RFID were initially designed for different application domains, their integration can be indispensable in Ubiquitous/Pervasive Computing, as both technologies can be used for coupling the physical and the virtual world. While the combination of WSNs and RFID is not yet common, in some research, such as by [4, 5], it has been predicted that eventually it will be.While not yet prevalent, the fusion of WSN and RFID has been used for several applications. For example, in [6], a system was proposed to support group-tour guiding services. In this system, only the guide carries an WSN node and the guests carry RFID tags. Essentially, the WSN node is used to calculate directions toward guests. Our system uses the existence of tags to modify the direction of the robot. Examples that are not related to navigation also exist. CoBIs RFID tags integrated tags with wireless sensor nodes, [7], were developed to monitor ambient conditions and provide alerts. Similarly, [8] combined WSN and RFID to perform automated asset tracking and inventory management. In more commercially angled research, [9, 10] proposed a global network infrastructure using WSNs and RFID to realize an EPC tracking system. These systems show a potential for using WSN/RFID fusion systems in logistics tracking. If these systems were to be implemented in a warehouse for example, then it would not be difficult to extend the system to enable mobile robots to utilize part of the network to navigate around the warehouse.This paper is organized as follows. In Section2, we will discuss the wireless sensor network, and how it can be used for mobile robot navigation. In Section 3, we will discuss the RFID system, and how we utilize it for our fusion approach, which is discussed in detail in Section 4. Additionally in Section 4, we will explain how the speed of the robot is adjusted in relation to obstacles. In Section 5, we will present the experiments we conducted to test the efficacy of our system and the results of said experiment. Finally in Section 6 we will discuss our conclusions and ideas for future works.


## 2. Wireless Sensor Network

Wireless sensor networks (WSN) are a technology originally developed for autonomous sensor data collection. Their ad-hoc, scalable nature allows for easy extension of the sensible area of a robot simply by adding more nodes. Moreover, while WSNs were not specifically designed for use in robot navigation systems, they possess abilities which make them very useful to such a system. For this research we chose Crossbow Technology MICAz MPR2400 Motes for the nodes of our WSN field. MICAz Motes operate in the 2400 MHz to 2483.5 MHz band and utilize the Chipcon CC2420, IEEE 802.15.4 compliant, transceiver with an integrated Atmega128L microcontroller.


### 2.1. Field Navigation Concept

The base of our navigation system utilizes a number of WSN nodes arranged around the navigable area. The layout and number of nodes required varies depending on the size and shape of the navigable area. The layout is decided by an expert user, but the directions suggested by each node are calculated by the system as described in the following subsection. In general, nodes are placed at critical points such as corners, along walls, and long straights. These nodes are used by the system to create a virtual potential field, Figure1, in which each node suggests the best direction in which to proceed. The benefit of this system is that the suggested directions provide local directions around large, static obstacles. The positions of the field motes are programmed into a map of the area, which serves two purposes, firstly, so that a human can select the desired destination by clicking on the map via a touch screen, and secondly, so that the directions can be calculated once a goal is determined. In most cases it is recommended to use a node as a goal, but this is not a requirement. This map is a part of the system, however the robot does not access it to plan a path or estimate its location. Its output to the robot is a database of the suggested directions from each node to the goal.Figure 1
WSN-based only field navigation concept.


### 2.2. WSN Node Angles

While the directional imperative will vary based on the robot’s location within the field, the directions suggested by field nodes are constant given an unchanging goal. The suggested directions are calculated by an approach commonly used in graphics programming called ray-tracing. In this system it is used to determine if a ray from a node, representing the radio wave emitted on a given vector, intersects a wall before reaching the goal, as illustrated in Figure2. Assuming there is no obstacle between a node and the goal, then the node points in a straight line toward the goal (horizontal solid line). However, in the event ray-tracing shows an intersection with a wall before reaching the goal (dotted line), it implies that the robot would also be directed to navigate into that wall. To avoid this, the direction is set to point to a “safety” point (vertical solid line), but still in the direction of the goal. In general, safety points are placed at the center of junctions, such as hallway intersections or any placewhere there is a constricted section the robot may need to pass through. These directions can be recalculated at any time if a new goal is desired.Figure 2
WSN field map calculation method.


### 2.3. WSN Navigation

The underlying concept of the WSN navigation subsystem relies on some perception of the robot’s distance relative to each field node. In this system we utilize the radio signal strength intensity (RSSI) of each node to determine how much influence a given node’s suggested direction has on the directional imperative supplied to the robot. In triangulation type approaches accuracy depends on the estimated distance; however, in our system the exact distance is not needed, as node imperatives are averaged to provide a general direction the robot should move in. Therefore, we developed [1, 3] a filter to eliminate RSSI readings determined to be erroneous. Each node in the field transmits a message roughly twice per second, which are read by the robot, and used to update a running average for each node. This running average is calculated over a set of values representing the last ten viable signals received from that node. Here, viable means signals that pass a filter based on the deviation of the values in that nodes set. First, (1) and (2) are used to calculate the deviation of the running averages with and without the newest RSSI value added in, respectively. Here, s represents the set of recent, viable RSSI values for a given node. Thusly, s′ represents the same set with the most recently read RSSI included. Also, i is the summation iterator, avg the average of the set. Then we take their difference and comparing that against the deviation threshold f, as shown by (3). Our system uses this filter to reduce noise in the RSSI readings. If a new incoming RSSI is determined to be drastically different from the values in the running set, it is thought to be inaccurate, and is discarded. It should be noted that before the system can be started, the field must run for a few moments so that initial running averages can be calculated. However, the filter in [1, 3], while efficacious, was not sufficient in handling more realistic environments as compared to the simulated navigable areas demonstrated in that paper. A common problem was that when a sensor was occluded (either by static or dynamic obstacles) the running average would remain unchanged, even after new signals began to arrive. This was caused by new signals being sufficiently different from the running average as to cause the filter to determine all new incoming RSSI erroneous. This was corrected by developing a timestamping test, which determines if the most recently included RSSI is older than some given threshold. If a new signal arrives and the running average is older than this threshold, the priming sequence is started again, and the next nine signals are included to create a new running average:
(1)devpre=∑n=i10(si-avgs)210,(2)devpost=∑n=i11(si′-avgs′)211,(3)f≥devpost-devpre.The nodes are sorted by their respective RSSI (running averages) and the suggested directions of the two strongest nodes are combined in a weighted sum, (4). The WSN node ranking in terms of signal strength is n, and with s representing RSSI, sn is the RSSI (running average) for node n. Finally, d→n is the suggested direction of node n. The strongest node’s RSSI is used to adjust the other RSSI to create a weight, which scales the magnitude of a vector, representing the suggested directions. The vectors are added via vector addition, giving us the directional imperative, V→wsn, for that moment. In normal, indoor settings, there is a possibility for sensors to be occluded by walls or other obstacles, causing a situation where even though some occluded nodes are physically closer, nodes that are further away may have stronger RSSI. A more stable path can be attained by only utilizing the closest sensors. As described in previous sections, it is ideal to have a node as the goal. In the event that the goal node or node closest to the goal is one of the two nodes with the strongest RSSI, then the top three nodes are used as can be seen in (5), because goal nodes can not suggest a direction to the robot:
(4)V→wsn=∑n=12‍sns1d→n,(5)V→wsn=∑n=13‍sns1d→n.


## 2.1. Field Navigation Concept

The base of our navigation system utilizes a number of WSN nodes arranged around the navigable area. The layout and number of nodes required varies depending on the size and shape of the navigable area. The layout is decided by an expert user, but the directions suggested by each node are calculated by the system as described in the following subsection. In general, nodes are placed at critical points such as corners, along walls, and long straights. These nodes are used by the system to create a virtual potential field, Figure1, in which each node suggests the best direction in which to proceed. The benefit of this system is that the suggested directions provide local directions around large, static obstacles. The positions of the field motes are programmed into a map of the area, which serves two purposes, firstly, so that a human can select the desired destination by clicking on the map via a touch screen, and secondly, so that the directions can be calculated once a goal is determined. In most cases it is recommended to use a node as a goal, but this is not a requirement. This map is a part of the system, however the robot does not access it to plan a path or estimate its location. Its output to the robot is a database of the suggested directions from each node to the goal.Figure 1
WSN-based only field navigation concept.


## 2.2. WSN Node Angles

While the directional imperative will vary based on the robot’s location within the field, the directions suggested by field nodes are constant given an unchanging goal. The suggested directions are calculated by an approach commonly used in graphics programming called ray-tracing. In this system it is used to determine if a ray from a node, representing the radio wave emitted on a given vector, intersects a wall before reaching the goal, as illustrated in Figure2. Assuming there is no obstacle between a node and the goal, then the node points in a straight line toward the goal (horizontal solid line). However, in the event ray-tracing shows an intersection with a wall before reaching the goal (dotted line), it implies that the robot would also be directed to navigate into that wall. To avoid this, the direction is set to point to a “safety” point (vertical solid line), but still in the direction of the goal. In general, safety points are placed at the center of junctions, such as hallway intersections or any placewhere there is a constricted section the robot may need to pass through. These directions can be recalculated at any time if a new goal is desired.Figure 2
WSN field map calculation method.


## 2.3. WSN Navigation

The underlying concept of the WSN navigation subsystem relies on some perception of the robot’s distance relative to each field node. In this system we utilize the radio signal strength intensity (RSSI) of each node to determine how much influence a given node’s suggested direction has on the directional imperative supplied to the robot. In triangulation type approaches accuracy depends on the estimated distance; however, in our system the exact distance is not needed, as node imperatives are averaged to provide a general direction the robot should move in. Therefore, we developed [1, 3] a filter to eliminate RSSI readings determined to be erroneous. Each node in the field transmits a message roughly twice per second, which are read by the robot, and used to update a running average for each node. This running average is calculated over a set of values representing the last ten viable signals received from that node. Here, viable means signals that pass a filter based on the deviation of the values in that nodes set. First, (1) and (2) are used to calculate the deviation of the running averages with and without the newest RSSI value added in, respectively. Here, s represents the set of recent, viable RSSI values for a given node. Thusly, s′ represents the same set with the most recently read RSSI included. Also, i is the summation iterator, avg the average of the set. Then we take their difference and comparing that against the deviation threshold f, as shown by (3). Our system uses this filter to reduce noise in the RSSI readings. If a new incoming RSSI is determined to be drastically different from the values in the running set, it is thought to be inaccurate, and is discarded. It should be noted that before the system can be started, the field must run for a few moments so that initial running averages can be calculated. However, the filter in [1, 3], while efficacious, was not sufficient in handling more realistic environments as compared to the simulated navigable areas demonstrated in that paper. A common problem was that when a sensor was occluded (either by static or dynamic obstacles) the running average would remain unchanged, even after new signals began to arrive. This was caused by new signals being sufficiently different from the running average as to cause the filter to determine all new incoming RSSI erroneous. This was corrected by developing a timestamping test, which determines if the most recently included RSSI is older than some given threshold. If a new signal arrives and the running average is older than this threshold, the priming sequence is started again, and the next nine signals are included to create a new running average:
(1)devpre=∑n=i10(si-avgs)210,(2)devpost=∑n=i11(si′-avgs′)211,(3)f≥devpost-devpre.The nodes are sorted by their respective RSSI (running averages) and the suggested directions of the two strongest nodes are combined in a weighted sum, (4). The WSN node ranking in terms of signal strength is n, and with s representing RSSI, sn is the RSSI (running average) for node n. Finally, d→n is the suggested direction of node n. The strongest node’s RSSI is used to adjust the other RSSI to create a weight, which scales the magnitude of a vector, representing the suggested directions. The vectors are added via vector addition, giving us the directional imperative, V→wsn, for that moment. In normal, indoor settings, there is a possibility for sensors to be occluded by walls or other obstacles, causing a situation where even though some occluded nodes are physically closer, nodes that are further away may have stronger RSSI. A more stable path can be attained by only utilizing the closest sensors. As described in previous sections, it is ideal to have a node as the goal. In the event that the goal node or node closest to the goal is one of the two nodes with the strongest RSSI, then the top three nodes are used as can be seen in (5), because goal nodes can not suggest a direction to the robot:
(4)V→wsn=∑n=12‍sns1d→n,(5)V→wsn=∑n=13‍sns1d→n.


## 3. RFID System

Radio Frequency IDentification (RFID) systems are well developed and widely used in robot applications, for navigation as well as interfacing with the environment. RFID systems generally consist of a reader, an antenna, and a number of tags. For our system, we utilized the Midrange Reader Module made by Texas Instruments which operates at a frequency of 13.56 MHz. It has an anticollision function that makes it capable of reading multiple RFID tags simultaneously. Our antenna is circular and capable of reading RFID tags reliably within 5 cm, vertically, and within around 10 cm, horizontally from the center, of the antenna. While most RFID-based navigation systems involve distributing tags through the navigable area in a variety of arrangements, we place passive RFID tags on the floor in key areas where a collision is likely or otherwise a high level of precision is required. As the tags are placed on the floor, we attached the antenna to the underside of the mobile base, keeping the distance from the antenna to the floor at approximately 4 cm.


### 3.1. RFID Tag Arrangements

In RFID systems, there has been extensive research done in how different arrangements affect the ultimate system [11–13]. We wanted to focus on ease of installment. To this end, we wanted to reduce the number of tags used to a minimum. Through previous experiments [14], we developed two generic arrangements that can be used when coupled with our WSN navigation system; strips and radials. The strip arrangement, Figure 3, is used anytime the robot is required to navigate a long, narrow straight. In this research, we focused on the use of the radial arrangement, Figure 4, which can be used to help guide the robot through openings, and around corners.Figure 3
Strips Layout.Figure 4
Radial layout.


### 3.2. RFID Tag Angles

Much like the WSN nodes, each tag in the navigable area has a suggested direction, which when combined using the fusion algorithm described in Section4, is used to refine the path produced by the WSN navigation algorithm. The angle of each tag is simply a normal to the obstacle which the tag is surrounding. When the tags are near a corner, the radial arrangement is used and the tags point away from the corner. In the event the tag is along a wall, then the strip arrangement is used and the tag angles are simply normal to the wall. An example of each is shown in Figures 3 and 4, where the arrow emitting from the tags, small squares, represents the angle for that tag.


## 3.1. RFID Tag Arrangements

In RFID systems, there has been extensive research done in how different arrangements affect the ultimate system [11–13]. We wanted to focus on ease of installment. To this end, we wanted to reduce the number of tags used to a minimum. Through previous experiments [14], we developed two generic arrangements that can be used when coupled with our WSN navigation system; strips and radials. The strip arrangement, Figure 3, is used anytime the robot is required to navigate a long, narrow straight. In this research, we focused on the use of the radial arrangement, Figure 4, which can be used to help guide the robot through openings, and around corners.Figure 3
Strips Layout.Figure 4
Radial layout.


## 3.2. RFID Tag Angles

Much like the WSN nodes, each tag in the navigable area has a suggested direction, which when combined using the fusion algorithm described in Section4, is used to refine the path produced by the WSN navigation algorithm. The angle of each tag is simply a normal to the obstacle which the tag is surrounding. When the tags are near a corner, the radial arrangement is used and the tags point away from the corner. In the event the tag is along a wall, then the strip arrangement is used and the tag angles are simply normal to the wall. An example of each is shown in Figures 3 and 4, where the arrow emitting from the tags, small squares, represents the angle for that tag.


## 4. Path and Speed Refinement

The goal of this research was to capitalize on the advantages of WSN and passive RFID systems, while minimizing the weaknesses. When no tag is being read, we navigate using the WSN system only. As part of this, we control the robot's speed based on its relative distance to obstacles. When tags are read, we use our fusion algorithm to evaluate the read tag’s direction relative to the WSN's imperative, then calculate the appropriate direction in which to move.


### 4.1. Speed Adjustment

As the robot navigates, if the RSSI of the strongest field node is low, we assume that we are relatively far from any static obstacle, and can consequently run at high speeds. As the RSSI increases, we likewise assume that we are approaching a critical area, and should therefore begin to reduce speed. A simple linear function, (6), is used to adjust the speed of the robot. Here, rssicurrent is the RSSI of the currently strongest field node, spdmax and spdmin represent the maximum and minimum speeds we want the robot to move at, rssimax is the maximum signal strength expected from the field sensors, and spdfinal is the output speed that will be sent to the robot. There are cut-offs such that even if the RSSI increases or decreases beyond high and low thresholds, the speed will not go above or below spdmax and spdmin. Regardless of the RSSI, in the event a tag is read, the speed is set to minimum, as we know we are near a critical area. In order to determine the maximum and minimum speeds at which the WSN and RFID systems could be read by the robot, we tested both by running the robot in a straight line toward the node/tag at different speeds. It is important to note that the time it takes for RFID readers to recognize that a tag is present varies by make and model. We determined through our experiments that the robot could always read the WSN anywhere up to approximately 42 cm/s, its maximum speed with the current payload. Conversely, while the RFID system could occasionally read the tag even at the maximum robot speed, it was only able to consistently read tags at speeds lower than approximately 17 cm/s. Additionally, it was observed that even at speeds near 17 cm/s, the turning rate of the robot could occasionally be insufficient to avoid collisions. And so, based on these experimentally determined values and observations, and in the interest of ensuring tag reading, we set the maximum speed of the robot to 34 cm/s and the minimum (when reading a tag) to 8 cm/s:
(6)spdfinal=(rssicurrent*-spdmax-spdminrssimax)+spdmax.


### 4.2. WSN/RFID Navigation Algorithm

The fusion algorithm we developed consists of two parts. When a tag is read, first we evaluate it's direction relative to the WSN's imperative. In the event that more than one tag is being read simultaneously, we take the average of all the tag angles, and use that for comparison. If the tag direction is within±90° of the WSN direction, we classify this as a “similar” direction. Otherwise, we classify the tag direction as “opposing”. To state this numerically, for example, if the WSN angle is 0° and the tag angle is 45°, then it is “similar”. Conversely if the tag angle were 125°, then it would be considered “opposing”. The purpose of this classification is to determine whether the robot is moving toward an obstacle, and therefore requiring dramatic redirection, or if the robot is already moving away from an obstacle and we simply need to encourage that avoidance. These classifications are of course dynamic. Having determined which type of tag direction we are reading, the second step is to apply the appropriate fusion approach for that type.For similar directions, we can assume that the robot is either skirting an obstacle or has just passed an obstacle. In either case, the chances of colliding with the obstacle are relatively low, as the robot is already moving in the desirable direction. Thus, we simply bisect the WSN and tag angles, and return the result as the direction to be taken by the robot, (7). Here, V→fusion represents the resulting direction from our fusion algorithm. As before, V→wsn represents the WSN directional imperative and V→tag represents the direction from the tag (or tags) being read. Conversely, when the directions are opposing, we can assume that the robot is approaching an obstacle, and may require drastic redirection. This is why the normal to the obstacle is used as the tag angle. When the tag direction is opposing, we calculate the two angles orthogonal to the tag angle, and return the one closest to the WSN angle as the direction to be taken by the robot. This is easily visualized with angles. In (8) through (11), Awsn and Atag are the angle representations of V→wsn and V→tag, respectively. If Awsn passes test equation (8), then we use (9). Otherwise, that is, Awsn passes (10), then we use (11). In the event a failure occurs and an RFID tag is not read, the system continues navigation using the WSN alone. This can cause potential for a collision, which is why the speed reduction explained in the previous subsection is critical. Consider
(7)V→fusion=V→wsn+V→tag,(8)Atag<Awsn≤Atag+180°,(9)Afusion=Atag+90°,(10)Atag≥Awsn>Atag-180°,(11)Afusion=Atag-90°.


## 4.1. Speed Adjustment

As the robot navigates, if the RSSI of the strongest field node is low, we assume that we are relatively far from any static obstacle, and can consequently run at high speeds. As the RSSI increases, we likewise assume that we are approaching a critical area, and should therefore begin to reduce speed. A simple linear function, (6), is used to adjust the speed of the robot. Here, rssicurrent is the RSSI of the currently strongest field node, spdmax and spdmin represent the maximum and minimum speeds we want the robot to move at, rssimax is the maximum signal strength expected from the field sensors, and spdfinal is the output speed that will be sent to the robot. There are cut-offs such that even if the RSSI increases or decreases beyond high and low thresholds, the speed will not go above or below spdmax and spdmin. Regardless of the RSSI, in the event a tag is read, the speed is set to minimum, as we know we are near a critical area. In order to determine the maximum and minimum speeds at which the WSN and RFID systems could be read by the robot, we tested both by running the robot in a straight line toward the node/tag at different speeds. It is important to note that the time it takes for RFID readers to recognize that a tag is present varies by make and model. We determined through our experiments that the robot could always read the WSN anywhere up to approximately 42 cm/s, its maximum speed with the current payload. Conversely, while the RFID system could occasionally read the tag even at the maximum robot speed, it was only able to consistently read tags at speeds lower than approximately 17 cm/s. Additionally, it was observed that even at speeds near 17 cm/s, the turning rate of the robot could occasionally be insufficient to avoid collisions. And so, based on these experimentally determined values and observations, and in the interest of ensuring tag reading, we set the maximum speed of the robot to 34 cm/s and the minimum (when reading a tag) to 8 cm/s:
(6)spdfinal=(rssicurrent*-spdmax-spdminrssimax)+spdmax.


## 4.2. WSN/RFID Navigation Algorithm

The fusion algorithm we developed consists of two parts. When a tag is read, first we evaluate it's direction relative to the WSN's imperative. In the event that more than one tag is being read simultaneously, we take the average of all the tag angles, and use that for comparison. If the tag direction is within±90° of the WSN direction, we classify this as a “similar” direction. Otherwise, we classify the tag direction as “opposing”. To state this numerically, for example, if the WSN angle is 0° and the tag angle is 45°, then it is “similar”. Conversely if the tag angle were 125°, then it would be considered “opposing”. The purpose of this classification is to determine whether the robot is moving toward an obstacle, and therefore requiring dramatic redirection, or if the robot is already moving away from an obstacle and we simply need to encourage that avoidance. These classifications are of course dynamic. Having determined which type of tag direction we are reading, the second step is to apply the appropriate fusion approach for that type.For similar directions, we can assume that the robot is either skirting an obstacle or has just passed an obstacle. In either case, the chances of colliding with the obstacle are relatively low, as the robot is already moving in the desirable direction. Thus, we simply bisect the WSN and tag angles, and return the result as the direction to be taken by the robot, (7). Here, V→fusion represents the resulting direction from our fusion algorithm. As before, V→wsn represents the WSN directional imperative and V→tag represents the direction from the tag (or tags) being read. Conversely, when the directions are opposing, we can assume that the robot is approaching an obstacle, and may require drastic redirection. This is why the normal to the obstacle is used as the tag angle. When the tag direction is opposing, we calculate the two angles orthogonal to the tag angle, and return the one closest to the WSN angle as the direction to be taken by the robot. This is easily visualized with angles. In (8) through (11), Awsn and Atag are the angle representations of V→wsn and V→tag, respectively. If Awsn passes test equation (8), then we use (9). Otherwise, that is, Awsn passes (10), then we use (11). In the event a failure occurs and an RFID tag is not read, the system continues navigation using the WSN alone. This can cause potential for a collision, which is why the speed reduction explained in the previous subsection is critical. Consider
(7)V→fusion=V→wsn+V→tag,(8)Atag<Awsn≤Atag+180°,(9)Afusion=Atag+90°,(10)Atag≥Awsn>Atag-180°,(11)Afusion=Atag-90°.


## 5. Experimental Results

In order to test our system, we developed two experiments. In the first experiment, the layout creates a situation where the robot must decelerate for one obstacle and accelerate again on the way to the next. WSN nodes and tags were arranged in a way to facilitate this, while keeping their numbers to a minimum. The focus of this experiment was to highlight the speed adjustment capabilities of the system. The second experiment was conducted in an actual hallway, where the user steps off the elevator and finds the robot waiting. The user indicates where they would like to go via a touch panel displaying a map of the area. To increase the reality of the experiment, the tags have been packaged into a mat, which allows for easy installation. The focus of this experiment was to highlight the path refinement provided by the RFID tags. For both experiments we used a mobile robot mounted with a WSN node to interface with the network and an RFID reader with an antenna attached to the underside of robot.


### 5.1. Mobile Robot: Chamuko

For our speed tests and experiments we used a robot called Chamuko, Figure5. It’s base is a MobileRobots Pioneer 3-DX, a differential drive platform, measuring 40 cm × 50 cm. Along its exterior are eight ultrasonic transducers (sonar sensors), though they are not utilized. In fact, in order to emphasize the effectiveness of the system, apart from the WSN and RFID systems, Chamuko performs no collision detection. Internally mounted is the RFID reader, with an antenna attached to the underside of the chassis. Mounted on the front bumper is a WSN node for interacting with the field. The robot's pose estimation is handled internally via on-board sensors.Figure 5
Chamuko, the robot used for experiments.


### 5.2. Speed Experiment Environment

The navigable environment is arranged as in Figures6 and 7. The total area is 8 m × 5 m. There are two sets of tables, arranged to appear as walls with a doorway. Each doorway has four radial layouts, a left and right layout for inbound and outbound side (these terms are relative, but apply when facing the doorway from either side). These “doorways” measure 90 cm, wide enough to overlap the outermost tags of the two radial patterns for each side. This makes 4 tags redundant, because there is no need to have two tags in exactly the same spot. Additionally, this width is just over twice the width of the robot, requiring the robot to navigate precisely in order to avoid collision. The tags are placed 15 cm apart. There were 5 WSN nodes and, omitting the redundant ones, 84 RFID tags. The angles to be suggested by the WSN were calculated as described in Section 2, and we utilized the radial tag arrangement described in Section 3. The robot was placed as marked in Figure 6, facing vertically (in relation to the diagram), which was done so that the initialization of WSN nodes would be reliable. In the current layout, the robot must start within 1m of the location marked in Figure 6 in order to reach the goal. Ideally, the WSN/RFID tags would be arranged such that the robot could navigate to and from any location; however, we have created this limited map for the purpose of highlighting the speed changes. The environment was designed to cause the robot to slow down as it approaches the first doorway, speed again as it passes it, and then slow once more before reaching the goal.Figure 6
Experiment environment layout.Figure 7
Experiment environment image.


### 5.3. Speed Experiment Results

In Figure8 we see an example path the robot took in one instance of the experiments conducted. The circles mark the position of the robot at a given time. We can see the circles are further apart or closer together depending on the speed of the robot. In Figure 9, we see a corresponding graph representing the speed of the robot. The robot’s path can be broken up into four “zones”. In zone I, the robot is approaching the first obstacle. In zone II, the robot is passing over the tags and through the gap between the two sets of tags of the first doorway. Zones III and IV are similar to the previous two, with the exception that this time the robot is approaching the second obstacle and at the end it stops at the goal. Based on an average of five successful example runs, we estimate the average run time for this experiment using our fusion algorithm at 39 sec. In order to compare this, we estimated how long it would take to run this map with the system described in [2]. By scaling up their results (their experiment was conducted on a smaller navigable area), we estimate the run time using that system would be approximately 110 sec. Even if the RFID system were to take an optimal route, at the speed described for that system, 12.2 cm/s, the run time would still be approximately 67 sec. This would give us a run time reduction of nearly half over an optimal RFID system. Conversely, comparing this system with the WSN only approach described in [1] is difficult, as the system would most likely be unable to navigate precisely enough to reach the goal.Figure 8
Experiment: example path.Figure 9
Experiment: example speed graph.Looking at Figure9, we can see the change in speed. In zone I, there is a tendency to decrease, as would be expected while approaching an obstacle. The graph has a peak about halfway through zone I, which results from the the robot changing direction to aim toward the “doorway”, as can be seen in Figure 8. In zone II, the robot is reading tags, and so mostly maintains minimum speed. The spike in zone II results from the gap in between the sets of tags on either side of the doorway. In zone III, again we see the decreasing trend, with similar spikes as in zone I. Finally, again in zone IV we see a similarity to zone II, as the robot is reading tags and there is a gap between the two sets of tags for the second doorway. This graph illustrates the system’s ability to adjust itself to maximize speed in open areas while still bring the robot to minimum speed when near RFID tags to ensure tag detection. That being said, we feel there is room for improvement in the smoothness of zones I and III. Currently this sudden change in speed is dampened internally by the mobile base’s controller.


### 5.4. Path Refinement Experiment Environment

The second experiment was performed in an actual hallway, Figure10, over an area measuring approximately 5 m × 6.5 m. There is an elevator at one end with several doorways on an opposing wall. This hallway posed a challenge for the system, as it is not possible to take a straight path toward the goal. The walls in the environment are made from a variety of materials such as wood, metal, and glass. An obstacle, a trash can, was placed along the way, but was not included on the map as it is small enough to be moved about and is not a permanent fixture. However, RFID tags were placed around the obstacle. In previous sections, two generic arrangements were presented; strips and radials. For this experiment, we developed a modified radial arrangement to be placed at convex corners where there is a high probability of collision. These tags were mounted to the underside of 270° pie shaped mats with a radius of 50 cm, Figure 11, made of thin rubber flooring material. The tags are arranged in expanding arcs of radii 15 cm, 30 cm, and 45 cm. As in the generic radial layout, the angle of each tag is a vector from the center of the pie shape to said tag, as can be seen in Figure 12. Five mats with 165 RFID tags were used with nine WSN field nodes. Their positioning can be seen in Figure 13.Figure 10
Hallway experiment environment.Figure 11
Tag mat for easy deployment.Figure 12
Diagram of tag angles based on mat center.Figure 13
Hallway experiment environment diagram.


### 5.5. Path Refinement Experiment Results

In Figure14, we can see two example paths taken by the robot on representative runs. Due to the dynamic nature of radio waves, the robot never takes exactly the same path twice, however, the paths are generally similar to the examples. The dotted path represents a path when the system used WSN-only navigation. While tags were read, we did not use the fusion algorithm to modify the WSN navigation. It can be seen that without RFID, the robot collided with the small obstacle not on the map. In fact, even if the obstacle was not there, the robot most likely takes a path that would result in a failure. The dashed line represents a path when the system utilized tag information and the fusion algorithm. It can be seen that the robot touches nearly all the mats. Not only is the robot successful in reaching the goal, it also cleanly avoids the small obstacle, because of the mats located around it. Due to its constant proximity to walls and other obstacles, the robot demonstrated no speed change, and maintained the minimum speed throughout.Figure 14
Example result paths.


### 5.6. Discussion

While great advancements have been made in mobile robot navigation, there is no one single approach that has proven to be the perfect solution. The most basic solution is dead reckoning, or the use of odometry to estimate how far the robot has traveled and thereby its position. The compounding error that develops does not affect our system, as our system moves based on a suggested direction toward the goal. In fact, no localization is performed at all. Vision systems are also frequently used in mobile robots, as they can be used to handle not only navigation, but object recognition and tracking as well. However, they are susceptible to poor lighting or occlusion of landmarks. For instance, in [15], an omnivision camera is used to detect landmarks, and an insect-homing method is used to compare a snapshot of the robots current position with the desired, “home” position. While this work is a good example of bio-inspired approaches, it is separate from the critical component, landmark recognition. If a significant number of landmarks are occluded, it is possible for the robot to be incapable of returning home. Our system uses a radio-based system and the waves can still be read, even around corners. Furthermore, as the sensor data is aggregated, the problem of possibly occluded landmarks is further lessened. Another good example of vision-based navigation can be seen in [16]. This system takes a ceiling mounted camera to not only localize the robot but also to plan an optimal path to the goal. Aside from the similar problems of occlusion in this approach, there is also a problem of limited navigable area. While there may be an application for such a small area, our system takes advantage of the ad hoc, scalable nature of WSN. If we wish to expand our navigable area, we simply add more nodes. Another popular approach for navigation is the use of laser range finders, which can also suffer from sensor resolution and unusual obstacles. As the distance increases, the resolution between sensor steps decreases, which can affect long-term path planning. This can also lead to loss of detection of objects that have a small “footprint”, such as chairs whose legs are very slim. Our system suffers from neither, as the map treats all objects the same regardless of physical properties. There have been attempts to improve laser range finder reliability. In [17] a method of calibration is presented which involves modeling the error of a given sensor in a given environment and a regional split/least square fitting approach. While this approach improves the performance of the laser range finder, it is likely that the calibration will not hold for other environments or while the robot is in motion. Our system’s calibration time is based only on first populating the running averages for each node with viable signals, which can be done at run-time. In fact, not all node running averages need to be populated before navigation may begin, as they may be initially occluded or out of sensor range. Our approach is more focused on the concept of structuring the robot work environment, which aims to construct an environment that provides a support framework suitable for robots. In our case, the function of the RFID and WSN is to supply information about the environment in order to facilitate simple, easily deployed, and reliable robot navigation.


## 5.1. Mobile Robot: Chamuko

For our speed tests and experiments we used a robot called Chamuko, Figure5. It’s base is a MobileRobots Pioneer 3-DX, a differential drive platform, measuring 40 cm × 50 cm. Along its exterior are eight ultrasonic transducers (sonar sensors), though they are not utilized. In fact, in order to emphasize the effectiveness of the system, apart from the WSN and RFID systems, Chamuko performs no collision detection. Internally mounted is the RFID reader, with an antenna attached to the underside of the chassis. Mounted on the front bumper is a WSN node for interacting with the field. The robot's pose estimation is handled internally via on-board sensors.Figure 5
Chamuko, the robot used for experiments.


## 5.2. Speed Experiment Environment

The navigable environment is arranged as in Figures6 and 7. The total area is 8 m × 5 m. There are two sets of tables, arranged to appear as walls with a doorway. Each doorway has four radial layouts, a left and right layout for inbound and outbound side (these terms are relative, but apply when facing the doorway from either side). These “doorways” measure 90 cm, wide enough to overlap the outermost tags of the two radial patterns for each side. This makes 4 tags redundant, because there is no need to have two tags in exactly the same spot. Additionally, this width is just over twice the width of the robot, requiring the robot to navigate precisely in order to avoid collision. The tags are placed 15 cm apart. There were 5 WSN nodes and, omitting the redundant ones, 84 RFID tags. The angles to be suggested by the WSN were calculated as described in Section 2, and we utilized the radial tag arrangement described in Section 3. The robot was placed as marked in Figure 6, facing vertically (in relation to the diagram), which was done so that the initialization of WSN nodes would be reliable. In the current layout, the robot must start within 1m of the location marked in Figure 6 in order to reach the goal. Ideally, the WSN/RFID tags would be arranged such that the robot could navigate to and from any location; however, we have created this limited map for the purpose of highlighting the speed changes. The environment was designed to cause the robot to slow down as it approaches the first doorway, speed again as it passes it, and then slow once more before reaching the goal.Figure 6
Experiment environment layout.Figure 7
Experiment environment image.


## 5.3. Speed Experiment Results

In Figure8 we see an example path the robot took in one instance of the experiments conducted. The circles mark the position of the robot at a given time. We can see the circles are further apart or closer together depending on the speed of the robot. In Figure 9, we see a corresponding graph representing the speed of the robot. The robot’s path can be broken up into four “zones”. In zone I, the robot is approaching the first obstacle. In zone II, the robot is passing over the tags and through the gap between the two sets of tags of the first doorway. Zones III and IV are similar to the previous two, with the exception that this time the robot is approaching the second obstacle and at the end it stops at the goal. Based on an average of five successful example runs, we estimate the average run time for this experiment using our fusion algorithm at 39 sec. In order to compare this, we estimated how long it would take to run this map with the system described in [2]. By scaling up their results (their experiment was conducted on a smaller navigable area), we estimate the run time using that system would be approximately 110 sec. Even if the RFID system were to take an optimal route, at the speed described for that system, 12.2 cm/s, the run time would still be approximately 67 sec. This would give us a run time reduction of nearly half over an optimal RFID system. Conversely, comparing this system with the WSN only approach described in [1] is difficult, as the system would most likely be unable to navigate precisely enough to reach the goal.Figure 8
Experiment: example path.Figure 9
Experiment: example speed graph.Looking at Figure9, we can see the change in speed. In zone I, there is a tendency to decrease, as would be expected while approaching an obstacle. The graph has a peak about halfway through zone I, which results from the the robot changing direction to aim toward the “doorway”, as can be seen in Figure 8. In zone II, the robot is reading tags, and so mostly maintains minimum speed. The spike in zone II results from the gap in between the sets of tags on either side of the doorway. In zone III, again we see the decreasing trend, with similar spikes as in zone I. Finally, again in zone IV we see a similarity to zone II, as the robot is reading tags and there is a gap between the two sets of tags for the second doorway. This graph illustrates the system’s ability to adjust itself to maximize speed in open areas while still bring the robot to minimum speed when near RFID tags to ensure tag detection. That being said, we feel there is room for improvement in the smoothness of zones I and III. Currently this sudden change in speed is dampened internally by the mobile base’s controller.


## 5.4. Path Refinement Experiment Environment

The second experiment was performed in an actual hallway, Figure10, over an area measuring approximately 5 m × 6.5 m. There is an elevator at one end with several doorways on an opposing wall. This hallway posed a challenge for the system, as it is not possible to take a straight path toward the goal. The walls in the environment are made from a variety of materials such as wood, metal, and glass. An obstacle, a trash can, was placed along the way, but was not included on the map as it is small enough to be moved about and is not a permanent fixture. However, RFID tags were placed around the obstacle. In previous sections, two generic arrangements were presented; strips and radials. For this experiment, we developed a modified radial arrangement to be placed at convex corners where there is a high probability of collision. These tags were mounted to the underside of 270° pie shaped mats with a radius of 50 cm, Figure 11, made of thin rubber flooring material. The tags are arranged in expanding arcs of radii 15 cm, 30 cm, and 45 cm. As in the generic radial layout, the angle of each tag is a vector from the center of the pie shape to said tag, as can be seen in Figure 12. Five mats with 165 RFID tags were used with nine WSN field nodes. Their positioning can be seen in Figure 13.Figure 10
Hallway experiment environment.Figure 11
Tag mat for easy deployment.Figure 12
Diagram of tag angles based on mat center.Figure 13
Hallway experiment environment diagram.


## 5.5. Path Refinement Experiment Results

In Figure14, we can see two example paths taken by the robot on representative runs. Due to the dynamic nature of radio waves, the robot never takes exactly the same path twice, however, the paths are generally similar to the examples. The dotted path represents a path when the system used WSN-only navigation. While tags were read, we did not use the fusion algorithm to modify the WSN navigation. It can be seen that without RFID, the robot collided with the small obstacle not on the map. In fact, even if the obstacle was not there, the robot most likely takes a path that would result in a failure. The dashed line represents a path when the system utilized tag information and the fusion algorithm. It can be seen that the robot touches nearly all the mats. Not only is the robot successful in reaching the goal, it also cleanly avoids the small obstacle, because of the mats located around it. Due to its constant proximity to walls and other obstacles, the robot demonstrated no speed change, and maintained the minimum speed throughout.Figure 14
Example result paths.


## 5.6. Discussion

While great advancements have been made in mobile robot navigation, there is no one single approach that has proven to be the perfect solution. The most basic solution is dead reckoning, or the use of odometry to estimate how far the robot has traveled and thereby its position. The compounding error that develops does not affect our system, as our system moves based on a suggested direction toward the goal. In fact, no localization is performed at all. Vision systems are also frequently used in mobile robots, as they can be used to handle not only navigation, but object recognition and tracking as well. However, they are susceptible to poor lighting or occlusion of landmarks. For instance, in [15], an omnivision camera is used to detect landmarks, and an insect-homing method is used to compare a snapshot of the robots current position with the desired, “home” position. While this work is a good example of bio-inspired approaches, it is separate from the critical component, landmark recognition. If a significant number of landmarks are occluded, it is possible for the robot to be incapable of returning home. Our system uses a radio-based system and the waves can still be read, even around corners. Furthermore, as the sensor data is aggregated, the problem of possibly occluded landmarks is further lessened. Another good example of vision-based navigation can be seen in [16]. This system takes a ceiling mounted camera to not only localize the robot but also to plan an optimal path to the goal. Aside from the similar problems of occlusion in this approach, there is also a problem of limited navigable area. While there may be an application for such a small area, our system takes advantage of the ad hoc, scalable nature of WSN. If we wish to expand our navigable area, we simply add more nodes. Another popular approach for navigation is the use of laser range finders, which can also suffer from sensor resolution and unusual obstacles. As the distance increases, the resolution between sensor steps decreases, which can affect long-term path planning. This can also lead to loss of detection of objects that have a small “footprint”, such as chairs whose legs are very slim. Our system suffers from neither, as the map treats all objects the same regardless of physical properties. There have been attempts to improve laser range finder reliability. In [17] a method of calibration is presented which involves modeling the error of a given sensor in a given environment and a regional split/least square fitting approach. While this approach improves the performance of the laser range finder, it is likely that the calibration will not hold for other environments or while the robot is in motion. Our system’s calibration time is based only on first populating the running averages for each node with viable signals, which can be done at run-time. In fact, not all node running averages need to be populated before navigation may begin, as they may be initially occluded or out of sensor range. Our approach is more focused on the concept of structuring the robot work environment, which aims to construct an environment that provides a support framework suitable for robots. In our case, the function of the RFID and WSN is to supply information about the environment in order to facilitate simple, easily deployed, and reliable robot navigation.


## 6. Conclusions and Future Works

The applications for ubiquitous robotics often require high speeds and precision. For many systems, these two requirements are a trade-off. There are a variety of sensors often used for mobile robot navigation; however, these systems are not without their drawbacks. For instance, range-finding sensors are a powerful tool but can suffer from inaccuracy when there are few reflective surfaces in the environment. Vision systems, too, are powerful and often used, but can suffer from poor lighting or occlusion from obstacles. In this paper, we have presented an approach that combines two radio systems with complementing features. A wireless sensor network (WSN) system provides relatively high speed general navigation, while a passive Radio Frequency IDentification (RFID) system is used to provide precision in critical places. Using our simple, vector-based fusion algorithm, we are able to use the WSN in wide open areas, and while near obstacles we incorporate the RFID system's signal to increase the system’s accuracy. We performed two experiments that illustrated the system’s ability to navigate precisely, and also showed that the robot can adjust its speed in relation to its proximity to obstacles. Based on the results of these experiments, we conclude that the system is a viable approach to relatively high speed and precise mobile robot navigation in an indoor static-obstacle environment. Additionally, with the development of RFID tag mats, our system allows for quick installation of system infrastructure. Future works includes the addition of dynamic obstacle avoidance, in a manner that will be incorporated into the fusion algorithm. We also plan to further develop the RFID tag layouts so as to be more generic for scaling and applying to other maps. We are also developing tools for automatically generating the WSN node and RFID tag layouts, based on architectural schematics.



---

*Source: 157409-2013-01-21.xml*