Tag Archives: particle filter

Cell phone tracking, Processing, and computational thinking

I gave a survey to my students recently. My lowest score on any of the questions was 'What I learn in this class will help me in real life.' I've given this question before, and am used to getting less than optimal responses. I even think I probably had a higher score on this question than I have received previously, but it still bothers me that we are having this discussion. Despite my efforts to include more problem solving, modeling, and focusing on conceptual understanding related tasks over boring algorithmic lessons, the fact that I am still getting lower scores on this question compared to others convinces me that I have a long way to go.

I came up with this activity in response. It combines some of the ideas I learned in my Udacity course on robotic cars with the fact that nearly all my students carry cell phones. While I know many cell phones have GPS, it is my understanding that phones have used cell towers for a while to help with the process of locating phones. It always amazes me, for example, how my cell service immediately switches to roaming immediately when driving across the US-Canada border, even when I had a non-GPS capable phone.

My students know how to find distance using the distance formula and sets of coordinates, but they were intrigued by the idea of going backwards - if you know your distance from known locations, can you figure out your own location? The idea of figuring this out isn't complicated. It can most easily be done by identifying intersections of circles as shown below:

One of my students recalled this method of solving the problem from what he saw in the movie Taken 2 , and was quickly able to solve the problem this way graphically in Geogebra. Most students didn't follow this method though - the general trend was to take a guess and adjust the guess to reduce the overall error until the distances were as close to the given distances as possible.

I got them to also look at other situations - if only two measurements to known locations are known, where could the cell phone be located? They played around to find that there were two locations in this case. I again pointed out that they were following an algorithm that could easily be taught to a computer.

I then showed them a Processing sketch that went through this process. It is not a true particle filter that goes through resampling to improve the guessed location over time, but it does use the idea of making a number of guesses and highlighting the ones with the lowest error. The idea of making 300,000 random guesses and choosing the ones that are closest to the set of distances is something that computers are clearly better at than humans are. There are analytical ways of solving this problem, but this is a good way of using the computational power of the computer to make a brute force calculation to get an approximate answer to the question.

You can look at the activity we did in class here:
Using Cell Phones to Track Location