Tag Archives: localization

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

Bringing robotic cars and Udacity to my classroom

I was really excited to learn about Udacity, a new online education system that premiered two courses on February 20th. That a course on programming a robotic car would appeal to me is probably not surprising to anyone that knows me. I also love having yet one more excuse to continue learning Python, especially one that gets me working with an expert in the field such as Professor Sebastian Thrun. I recall reading about him shortly before his team's successful bid at the DARPA Grand Challenge, and have since seen his name repeated at many key moments along my development as a robotics enthusiast.

The course is structured really well, with short videos introducing concepts, quizzes and programming tasks (with solutions) along the way to check comprehension, and homework assignments. The students love that I have homework.

I am busy, but this was too cool to pass up.

I also have a pretty hard time hiding the things I'm enthusiastic about in my classroom, so the content of the class has been something I've mentioned and shared with students at the start or end of planned activities. The whole classroom gasped at this video from the 25th second onward:

Based on that reaction, I really wanted to give them a sense for the things I was learning to do. The first week centered on learning about localization - a process that uses probability calculations to estimate the location of the car using sensor readings and a map of the surroundings. I did a quick overview of what this meant as a filler activity to break up work during class, but wanted to find a way to do much more.

Today's Algebra 2 class was going to be missing a couple students that are attending a Model UN conference, so I figured it would be a good time to try something different.

We started with the following warm-up problems:

Mr. Weinberg tells you we are guaranteed to have a quiz one of the days between Monday and Friday. He tells you that the probabilities of the quiz happening Monday through Thursday are 0.1, 3/8, 1/16, and 36%. What is the probability that the quiz will be on Friday? On which day is the quiz most likely to occur?

This helped review the total probability principle which is key to understanding the localization algorithm. We also did a review of finding the probability of compound independent events, first with a tree diagram, and then using multiplication and the counting principle.

We then went through the following activity for the rest of the period:
Robot Localization activity

I adapted parts of the course material provided by Udacity, primarily simplifying language, cleaning up diagrams, and adjusting the activities for my students who do not have any programming ability. We did have a Python activity back in October, but installing and running Python was a hassle on the 1-1 Macbooks with OSX since I was trying to do it with Python 3 and IDLE. It was only shortly afterward that I learned that an earlier version of Python was automatically installed. Oops. For this activity, we used http://repl.it/ to do the programming. This worked fantastically well.

The students seemed to do really well with the introductory material and filling things in, and modifying the basic programming went smoothly. They ran into some trouble around problem 7, which I half expected - that was the first part of the activity when I told them to do something without any rationale behind it. Most were generally able to implement the procedure and get to problem 9, but at this point at the end of the day on a Friday afternoon, fatigue started to take over. This was after around 45 minutes of working on the activity.

I added a section on motion for possible use in another class, as I ultimately would like them to be able to throw my own homework solution code into a simulator provided by Udacity user Anna Chiara. I did not deal with any of the sensor probability or move probability. The intuition for understanding how those apply in the algorithm is a bit subtle for the background of my students, and would take more of an investment of time than I think my students have the patience for at this state. I think it would be easier to talk about how these issues exist, and then have them observe what they mean by looking at the output of the program.

All in all, it was a cool, low-key way to share my own learning with students after an exhausting week. I think we all needed a bit of a change.