Localization & Location-Based Services with Particle Filters 2010

By Ahsen Jaffer

Description

Visitors to large building such as museums, university / college campuses, libraries, bookstores, office buildings etc. usually require assistance in navigating through the large and sometimes complicated maze of building structures. This assistance is mostly provided by pocket size maps, large printed maps displayed at several different locations and sometimes by help-desk kiosks.

Related work

Following is a list of some of the currently existing solutions to this problem.

1. pocket sized maps Small pocket sized maps are provided to the visitors, who can carry these around while they move about the building. These maps contain useful information regarding what facilities are available in different areas.

Pros

• Easy to use, as they can be carried around with the user.

Cons

• There is recurring cost for the printing of the material
• These maps do not have a way to tell the visitor their current location, the visitor will have to deduce that it self.

2. Printed maps displayed at several locations Large printed maps are put up at several easily visible locations. The visitors can walk up to these maps and can find out their current location, use the guide on these maps to figure out the directions of how to reach their desired destination. Usually this is a self-help process, but sometimes there can be a help-desk employee available to answer questions or help figure out the path.

Pros

• Compared to hiring people, this is a relatively cheap solution. This has a fixed, up front cost, but al most negligible monthly maintenance cost.Visitors do not need to have any special equipment to be able to view the information being displayed.

Cons

• Requires a lot of effort and money to update information.
• A good amount of effort has to be spend in choosing good locations for such maps. The locations have to be visible enough, in order to provide the desired benefit.
• Can not provide dynamic information.

3. Manned help-desk kiosks Help desk employees sometimes are walking around and in other situations will be located in an island where the visitor may approach them for directions. Pros

• Quick means of answering visitor's queries.
• Most of the people prefer face to face conversations, this provides a good way for the visitors to get their queries answered.

Cons

• Relatively expensive, in terms of the monthly cost for keeping a workforce.
• Can be in-effective if the ratio of number of visitors that need help to the help-desk work force is very large.
• The locations have to be chosen carefully to provide the best visibility, furthermore there is a cost limit to the number of kiosks as it gets more expensive with the size of the help-desk workforce.

Emerging solutions

Following lists some of the new ideas that researchers have been working on to solve this problem.

ClickAndGo Way Finding Maps from Intouch Graphics

ClickAndGo Wayfinding Maps is an accessible narrative mapping service for the blind and deafblind. This free service provides maps for public facilities such as schools, airports and hotels. This service is available by telephone or by using their website. http://www.clickandgomaps.com

Pros

• Free service
• provides detailed step by step directions prepared by specialists, including cues to landmarks.

Cons

• The visitor needs to know its current location, in order to use this service.
• This service is specialized for the blind and deafblind, the instructions are detailed with specialized terminology, recommendations exclusively intended to assist blind visitors. The instructions might not be feasible for visitors who are not accustomed to these specialized terminologies.
• Service is for public facilities only, it does not cover private buildings such as office buildings or conference halls.
• Data is prepared by specialists. Comparatively with automated techniques, this can be more time consuming.

LAIR (Location Awareness Information Representation)

LAIR generates descriptive walking directions for indoor facilities. It models the geographical relationships between spaces as well as the functional purpose of a given space to produce walking directions comparable to given by a person.

Pros

• provides walking directions which are comparable to given by a person.

Cons

• Not able to provide with information relevant to user's current location.

Handheld Campus Tour Guide

This is a senior year project by a University of Virginia student. The idea is to provide the visitors a means of a self-guided tour of the university campus. The design goal was that this device will determine the user's location up to an accuracy of five meters indoors and ten meters outdoors. Another goal of this system was to provide visual representation to the user of its current location. http://www.cs.virginia.edu/~mwb7w/union/tour_guide/

Pros

• Provides the visitors a hand-held device, capable of determining their location.
• the hand held device can provide detailed walking directions.

Cons

• Although this project describes work which is very similar to my intended idea, it is not clear if the project met its intended goal.

SafeLink

SafeLink is a wireless geo-location system that uses existing commercial broadcast signals as position references. It is able to provide an equivalent horizontal position accuracy a better altitude accuracy than a GPS device. http://www.safe-link.com/

Pros

• Provides accuracy of three to ten meters both indoors and outdoors in both horizontal and vertical planes.
• Uses the free broadcast signal infrastructure.

Cons

• It is a commercial service.
• Uses proprietary devices.

'LUCAS', Limerick University Computerized Assistive System

It is an autonomous library assistant robot that is used to assist individuals within the library environment.

Pros

• Provides assistance to users to fetch a specific book.
• Able to find its current location and calculate a path to its destination.

Cons

• Needs specialized hardware.
• The time taken by the user to reach its destination is a factor of the time taken by the robot to navigate around obstacles.
• creates possibility for extra work, i.e to make the robot socially acceptable, as compared to using already acceptable devices such as hand held smart-phones.

My Solution

An automated assistant in the form of an application that can be installed on to the visitors' smartphone / mobile computing device. The visitors will be able to use this automated assistant application while walking around the building. This automated assistant application will know its current location and also be able to give instructions to navigate them through the building.

Why is this a good idea?

This solution combines the advantages of the current practices: pocket map, large printed displayed maps and help-desk kiosks.

This application has the following advantages: can be carried around knows its current location can give navigation instructions through the building has dynamic content, content changes do not incur huge costs, as there are for re-printing large printed maps. does not require a proprietary hardware, it can run on the current smartphone that the visitors may already have.

This application has the following disadvantage: Visitors need to have a smartphone / mobile computing device in order to use this solution.

Algorithms

There are two problems that need to be solved: Localization and Path finding. This project is going to attempt the Localization part only.

Localization

The topic of indoor localization is very well researched and has many different solutions. The following table lists the characteristics of some of the selected solutions:

Using the radio signal strength of the WiFi Access Points (AP) seems like a growing trend in the research community. WiFi technology is a good choice for indoor global localization systems, it has the following advantages:

• its coverage is quickly growing, as there are WiFi Access Points (APs) in most public buildings like hospitals, libraries, universities, museums, etc. Furthermore, measuring the WiFi signal level is free even for private WiFi networks.
• It is an efficient method for global localization since access points are uniquely identifiable
• No modifications to the environment are required, existing infrastructure is good enough
• Completely passive localization is possible by "sniffing" wireless traffic
• WiFi signals do not require line-of-sight. As such, they can be used even in the presence of obstructions that would block laser range-finders or cameras.

WiFi Localization Technique This type of localization technique is based on measuring the signal strength of received WiFi packets.

There are two phases: training phase and estimation phase. In the training phase, a wireless-map is created. While in the estimation phase, based on the received signal strength, a best match is calculated as an estimate of the location of the robot.

The signal strength is a function of distance and the obstacles that might be in between the robot and the origin of these signals i.e. the Access Points (APs) One obvious solution could be triangulation of the signal strengths from multiple Access Points (APs). But unfortunately the signal strength is a complex function of distance, because there is a lot of noise on the wireless channel in indoor environments and the radio frequency (RF) signal can suffer from reflection, diffraction and multipath effect. To overcome this issue, a radio map can be created, which captures the signatures of each Access Point (AP) at certain points in the area of interest.

Training Phase There are different ways that this step can be accomplished.

A. This can be done manually by measuring the RSSI at every grid point in the floor plan. This method is accurate, but is expensive and time consuming. This has the disadvantage of requiring re-calibration if there is a major change in the propagation environment (e.g. new walls, furniture, AP moved, amount of human traffic has changed significantly etc.)

B. Use indoor propagation models to predict the fingerprints.

   B.1 Empirical Models
   B.2 Deterministic Models

I chose the option A, I manually measured the RSSI for 4 locations:

Drexel's Hagerty Library's 2nd floor Drexel's Computer Science Department's Corridor. Inside of my house Outside of my house.

Localization Phase I tested my implementation in the following locations.

Drexel's Hagerty Library's 2nd Floor

   I measured RSSI at 8 states: one, two, three, four, five, six, seven.  The figure below shows a screen shot of localization, where black circle signifies the actual location of the robot, and the red circles signify the Particle locations.  The size of the circle signifies the number of particles at each state.

The chart in the Figure 2 shows the result visually. This shows that 100% of the particles were in the correct state while being in the states 'three' and 'five' and 50% of the particles were in the neighbor states while being in the states 'four' and 'eight' The particle filter failed to produce any particles for the rest of the states.

This is the video of the Particle filter in action. Media:Library.mov

Drexel's Computer Science Department's Corridor

   I measured RSSI at the following states :Entry, Bathroom, Corridor1, Corridor2, Corridor3, Corridor4, Corridor5, Corridor6, Room145.  Figure 2 below shows a screen shot of localization in action.  Black and Red circles signify actual and particle locations as discussed above.

   The chart in the figure below shows that the Particle Filter did not work very well in the Corridor area.  It gave 50% particles in the correct state while at the location 'Corridor3' and the rest 50% particles were in the neighbor states.  While being at the locations 'Corridor6' and 'Bathroom' the particle filter gave 100% particles in the neighbor states.  All other locations did not generate any particles.

This is the video of the Particle filter in action. Media:CSDept.swf

Inside my house

   I measured RSSI at the following states: K, L1, L2, C, O, B.  Figure 3 shows a screen shot of localization in action.

   The chart in the figure below shows the result visually.  While in the K, L1, L4 states 100% of the particles were in the correct states, while being in B,C states 50% of the particles were in the neighbor states, for the rest of the states the particle filter did not produce any particles.

This is the video of the Particle filter in action. Media:House.swf

Outside my house

   I measured RSSI at the following states: Garden1, Garden2, Patio1, Patio2.  Figure 4 shows a screen shot of localization in action.

The chart in the figure below shows the result visually. While in the 'Garden' states, 100% of the particles were in the correct state, but while in the 'Patio' states, 50% of the particles were in the correct state.

This is the video of the Particle filter in action. Media:OutSide.swf

Software

The source code can be downloaded from here: Media:VirtualGuide.zip

I made minor changes to the aima core library. One example of a minor change was to stop looping infinitely, when there were not enough particles found. <aima-core-test-changed.jar> <aima-core-changed.jar>

The NetStumbler wifi scan files are available here: Media:scans.zip

Implementation Details

For collecting RSSI for each state I used NetStumbler with custom script. Each state's RSSI is collected in individual files. Each file has the following information:

State's Name State's neighboring states State's x-y location for drawing on the screen.

For capturing the RSSI I wrote a VB Script that is run by NetStumbler. The output file generated by this script looks something like the following snippet:

#Scan[1] 001A1E8EE421|-71 001A1E8ED4C3|-78 001A1E85A361|-52 001A1E8ED4C1|-78 001A1E8EBE20|-85 001A1E8EE2A1|-57

For each scan the line starts with '#Scan[]' The number inside the square bracket indicates the number of scans performed.

I then manually add the following information for each file:

#State:Corridor6[Corridor5,Room145][680,300]

From the above example, the state's name is 'Corridor6', its neighbors are 'Corridor5' and 'Room145', its x,y location on the screen is 680,300.

The NetStumbler script is available here Media:stateScan.txt

Regular Expressions

I use regular expressions to read the relevant information from the state files, e.g to get state's name, neighboring states, and x,y location:

Pattern p = Pattern.compile("\\#State\\:(.*)\\[(.*)\\]\\[(.*),(.*)\\]");

Particle Filtering

I used open source implementation from Aima-Java. This version of the implementation requires the client to create a Transition-model and a Sensor-model.

Transition Model

For the transition model, I created a graph of the states, with each state connected to its neighboring states. I then used the open source project annas to traverse the graph in a breadth-first manner. Using breadth-first traversal I am able to give higher transition probabilities to the closer states, and gradually assign lower transition probabilities to farther states.

Note: The above diagram shows a uni-directional graph. In my implementation I created bi-directional graph.

Sensor Model

For calculating the sensor model I considered the combination of the AP's MAC Address + Received Signal Strength as the perception, e.g. following shows a list of perceptions:

001A1E8EE421|-71 001A1E8ED4C3|-78 001A1E85A361|-52 001A1E8ED4C1|-78 001A1E8EBE20|-85 001A1E8EE2A1|-57

I then calculated the likelihood of the above said combination for each state, by dividing the number of times this combination was observed (in a particular state) by the total number of times this combination was observed (in the whole system.)

Filtering Noise

While creating the sensor model, I observed that sometimes the received signal strengths from a some Access Points had a large spectrum from a low to high signal strength. I filtered out such Access Points. Another filtering technique I used was to only consider the top strongest Access Points, this helped increase the performance of the algorithm.

Problems

NetStubmler on Mac OS X

I am using Mac OS X. I installed KisMac, which is able to give NetStumbler compatible log files. But I was not able to find a way to add script. I decided to use Windows (as a VM) and use the NetStumbler software with my custom VBScript to generate the output file as was discussed above.

Sensor Model

Creating a good sensor model is challenging. I tried with a couple of different models, and there are still a lot of different ways the sensor model can be created.

Discoveries

Filtering on strongest AP

The algorithm gives different results when the number of top Access points to use for the sensor model is changed. The number that gives best results is different for each location I tested. The reason this is different is because each location is unique, i.e. the number of Access points visible, the environment e.g. number of walls, ceiling height, things as such play a role on how the signal strength dissipates.

Environment Matters

Although looking at the chart for the Drexel's Computer Science Department's Corridor, it can be deduced that the Particle Filter algorithm did not give very good results. But upon viewing the attached video sequence, one can see that the particles are not far behind, or are in the corridor's vicinity. The problem here is the environment, since the thin long Corridors can propagate the Signals easily, that can cause the signal's strength to stay unchanged or change by a very little amount.

Future Work

Movement model Maybe a movement model can be incorporated with the particle filters. This model can keep track of the user's speed and direction, and can be used to refine the particles. This can be done by keeping in consideration that if a person is walking in one direction, it is more probable that this person keeps walking in the same direction, rather than turn back suddenly.

Physical walls, barriers model We can take into consideration the fact that people can not walk through walls or other physical barriers. We can use this fact to refine the results given by the particle filters.

Resources

I used the following resources:

aima-java Java implementation of algorithms from Norvig And Russell's "Artificial Intelligence - A Modern Approach 3rd Edition." http://code.google.com/p/aima-java/

annas Graph implementation and algorithm package http://code.google.com/p/annas/