Autonomous Robot Localization Using WiFi Fingerprinting

Abstract: 

We are using widely available 802.11 wireless networks to determine the location of autonomous robots. Before a robot can accomplish a simple task such as moving to a specific coordinate, it must accurately know its current location with-in a certain degree of accuracy. Humans often take their eye sight and spatial awareness for granted. For a robot, the computational difficulty of solving the same problem becomes apparent. Our implementation creates a database of wireless signal strengths of a given area and uses the current signal strength reading within the area to find a weighted signal space distance. The “closest” point in the database should also correlate with the current position of the robot. Given the robots correct location we can successfully navigate around any area with sufficient Wi-Fi coverage.

Table of Contents: 

    Introduction

    Existing Global Positioning Systems (GPS) require a line of sight communication with geosynchronous satellites in order to function. This requirement renders GPS usability in indoor environments minimal. However, indoor usability can still be accomplished using multiple techniques. Vision based systems attempt to identify certain known landmarks with-in an area by using image processing algorithms. These are computationally expensive and require significant training. [3] Odometer based localization methods measures distance traveled and orientation changes, but experience increasing error due to imprecise measurements. [1] And radio based methods attempt to measure radio signal delay and signal strength from known sources, but require transmitters to be installed within the indoor environment to function. Thanks to the prevalence of wireless networking, most indoor environments have preexisting infrastructures in place that can be utilized for both communication and localization. We were tasked with using the University of North Texas’s (UNT) existing 802.11n wireless networks to solve the indoor localization problem using four Acroname Garcia Robots. Refer to the photograph of the robots in Figure 1.

    Hardware

    The Acroname Garcia Robot is composed of the following components:

    • Gumstix Verdex-Pro XL6P COM
    • 600mhz Ram
    • USB Port
    • 32MB flash memory (file system)
    • MicroSD expansion (file system)
    • Openembedded Linux Distribution
    • Wifistix 802.11b/g Expansion Board (Marvel 88W8385 Module)
    • Acroname Brainstem Processor
    • Two Maxon 250443 Motors
    • Two HiTech 322HD Servos (camera tilt/rotate)
    • Six Infrared Range Fingers
    • Hokuyo URG-04LX Laser Ranger

    Localization Methods

    After researching existing techniques to accomplish our goal we decided upon wifi fingerprinting. Despite previous work done by others at UNT in way of trilateralization, we quickly realized that they ignored the issue of converting the Received Signal Strength Indicator (RSSI) to distance. Using freespace path loss models, as a basis to solve for real world distances, in indoor environments simply does not work in practice.[2] Indoor environments are subject to shadowing and multipath distortion, which are completely ignored by these models. Most implementations of the trilateralization methods rely on taking signal strength samples and performing a log fit to create a model of the sampled data. The fingerprinting method, however, uses the sampled data directly and correctly accounts for any nonlinear changes in signal strength that are regularly seen with-in a typical indoor environment.

    Fingerprinting

    The fingerprinting method is primarily composed of two phases; a database creation phase and an usage phase. In order to implement the fingerprinting method one must create a wireless signal strength database, also known as a radio map, as a preprocessing step. This is accomplished by physically taking measurements of signal strengths at regular intervals within the desired area at any granularity that achieves the desired results while minimizing the physical effort required to generate the data. After the database is created, software is used to determine the location in real time by searching for the closest matching database signal given the current signal reading. We collected signal samples at approximately one meter intervals in a grid pattern of two separate locations—A common area between the computer science (CS) and electrical engineering (EE) departments and an embedded systems computer lab within the CS  department.

    Design

    After placing tape to mark one meter intervals in the desired location we placed the Acroname Garcia Robot on the markers in a single orientation (facing the positive x axis of generated data and images). We used the linuz iwlist scan command to collect data from the robot which was piped into a plain text files. Multiple samples were taken at each point one to two seconds apart. Originally, we took three samples per reference point and later took ten samples per reference point in one of our two locations. Using standard ANSI C code we wrote programs that created a binary database of the collected text data and used this database to perform various tasks. These tasks included an implementation of the fingerprinting algorithm, generating visual heatmap images of the collected data (robot path finding), and creating programs to inspect the contents of the database. This free and open source code will be available at http://lineofsight.aqeight2009.com along with our collected data. Refer to Figure 2 for this information.

    Access Point Transmit Power

    The University of North Texas uses Aruba AP-125 802.11n antennas which act as terminals that are centrally controlled by a single master controller. As our selected method makes the assumption that wireless signal strength is relatively constant over time, our accuracy is limited by the fluctuation of signal power transmitted by these access points. We requested that UNT enable a constant transmit power and disable any dynamic load balancing or power saving features offered by the aruba network because the settings would be temporary in nature and due to the lead time required to get changes in place, we attempted as best we could to work with the dynamic settings. When collecting our first dataset, the area between the CS and EE departments, the school had a constant transmit power enabled. The first two sets of embedded lab data, however, have the schools normal dynamic settings. We are unaware as to what settings were changed and what these settings are. Refer to Figure 3.

    Results

    Our results varied greatly depending on where the robot was placed. Certain locations returned a perfect match regularly while most areas were within 2-3 meters of the robots actual location. Other areas near walls, between computer desks, or within the embedded lab had results that were off by as much as 5 meters. However, in cases where perfect matches occurred the signal space difference between the sample and the matched location was consistently low, ranging between 0.5 and 1 dBm, for only a single point. In cases where the matches were between 2-3 meters a small subset of points near the robot had similar dBm differences between 0.75 and 2dBm. This allows one to give a rough confidence level of the results received and provide the robot with enough information as to whether or not it should rely on the fingerprint localization coordinate. Assuming worst case results, this still gives the robot a general idea of where it is located within a space when placed randomly. This information when combined with information from other sources, such as laser range fingers and odometer data, can be used to help determine the robots actual location based on other known features identification.

    Conclusions

    The accuracy of wifi fingerprinting depends heavily on the quality of the data collected and the variation of signal strength power. The results given by our matching program can be improved without making any changes to the code itself. Minimizing transmission power variability as well as reducing any inaccuracy that may occur between the true RSSI value and what is recorded by the linux driver can improve our system. Probabilistic methods may also improve the accuracy of fingerprinting at the cost of complexity, but larger gains will be made through the use of hardware that is designed with localization in mind. The Horus method [4] claims results accurate to 1.4 meters 90 percent of the time, however, they made use of custom linux drivers and much more sophisticated, probabilistic, modeling methods. However, customizing drivers and firmware for our purposes would be a huge undertaking in and of itself. Detailed knowledge of the factors influencing the transmit power for the deployed Aruba 802.11 access points would be helpful along with any methods one may use to ensure that there is little to no variation of signal strength over time. Accurate odometer data is crucial to the correct operation of any autonomous system as any small error in direction exacerbates the localization problem.

    References

    [1] R. Havangi, M. Nekoui, and M. Teshnehlab. A multiswarm particle filter for mobile robot localization. IJCSI International Jounal of Computer Science Issues, 7(2), May 2010.

    [2] D. Lymberopoulos, Q. Lindsey, and A Savvides. An empirical characterization of radio signal strength variability in 3-d ieee 802.15.4 networks using monopole antennas. The European Workshop on Wireless Sensor Networks, 2006.

    [3] J. Wolf, W. Burgard, and H. Burkhardt. Robust vision-based localization by combining an image retrieval system with monte carlo localization. IEEE Transactions of Robotics, 21(2), 2005.

    [4] M. Youssef and A. Agrawala. The horus wlan location determination system. Proceedings of the 3rd international conference on Mobile systems, applications, and servies., 2005.

    Figure 1: Photograph of Acroname Garcia Robots

    Figure 2: Algorithm 1: Our original unoptimized matching algorithm

    Figure 3: Signal strength images from access point 00:1A:1E:8B:47:60 displaying signal fluctuation of embedded lab from different scan sets taken roughly two weeks apart