Friday, April 18, 2008

News coverage of our senior project

KSL, the local TV station, wrote up an article about our senior project last week. They also did a TV segment on it, which you can watch here:

(If the embedded video player doesn't work for you, try the watching the video on KSL's page.)

Monday, April 14, 2008

Robot obedience training

Over the weekend, Nick (one of my my senior project teammates) came in and worked on our robot for a few hours. Here are the results:

If you're interested in the technical details of how our robot works, take a look at our team web site.

Friday, April 11, 2008

My disobedient robot

My senior project this semester has been to build an autonomous robot racer with a team of four other people. Translated into English, that means that we take a remote control toy monster truck, stick a computer and camera on it, and make it drive around all by itself. It's been a lot of fun—and a lot of work. We had our final competition yesterday and fared horribly.

The goal of the project was to get our robot to use computer vision to drive a race course all by itself. The course was a bunch of orange and green pool noodles (we call them "pylons" to sound sophisticated) that were set up vertically and spaced out on the floor. Orange meant that the robot had to pass them on the right and then turn to the left; green meant the opposite. The robot was supposed to use its camera to find a noodle, drive to it, make a turn, and repeat until it had finished the course.

That was the idea, anyway. None of the five teams that competed in the project were completely successful. Our team fared the worst.

There are several components to a system that can autonomously control a racer:
  • A color segmenter that can identify areas in the image that are the specific shade of green or orange that we're looking for.
  • A feature extractor that can take those areas and identify the precise position of the pylon.
  • A vision-guided control system that uses the data from the feature extractor to control the robot's steering and throttle to drive toward pylons.
  • A dead reckoning control system that "drives blind" to control the robot while pylons are out of view.
  • A "mission control" computer program that runs on a desktop computer that communicates wirelessly with the robot. This program doesn't control the robot; it's just used to monitor its state, fine-tune parameters, and send an emergency stop command if the robot gets out of control.
Our robot could (mostly) successfully drive toward pylons, but it had a really hard time correctly executing turns. We got it working a week ago on a simple two-pylon course, but that's about the most advanced thing it could do. It was pretty disobedient, and our competition yesterday was an embarrassment.

What went wrong? A lot of things. Most of it boils down to poor planning and a rushed schedule.
  • We optimized prematurely. We tried to implement our feature extractor in hardware (VHDL) because we wanted it to run fast. Developing hardware is a lot trickier than developing software, and we spent three weeks trying to get it to work. We finally decided to cut our losses, and I wrote the object extractor in C and had it working in two hours. In hindsight, I should have written it in C to begin with, and only converted it to hardware if it was too slow. As it turns out, the software, running at 100MHz, was plenty fast enough to process images at the camera's full 35 fps frame rate.
  • We added too much complexity too quickly. When we finally got our feature extractor working a couple of weeks ago, we tried to throw everything else into the pot all at once. When you add a lot of complexity all at the same time, it's hard to tell where to look when something doesn't work. Instead, we should have tested each feature independently. When we were confident that a feature was working by itself, we could add it to the rest of the system and make sure that it works when integrated. That way it's a lot easier to isolate problems.
  • We didn't have a consistent schedule. With a semester-long project like this, it's easy to put it off and work on more pressing assignments for other classes. That hurt us in the long run, though. There were also several times when one person was assigned to complete an important part of the project by a certain day, and they didn't have it done. That then delayed everyone else who couldn't make progress until that part was in place.
  • It was hard to work in parallel. We had only a single development computer, so only one or two people could work on the project at once. That wasn't an issue for most of the semester, but when it was crunch time, it would have been really helpful to have two or three workstations.
  • Attitude. Most school project are very well-defined and self-contained. This project was different: it was very open ended, both in approach and schedule. This type of project requires more discipline and more creativity than typical school projects. It also requires a different attitude. When something doesn't work—and it seems that nothing works on the first try—you can either give up and say "I tried", or you can buckle down, try a different approach, do research, talk to others, and make things happen, even though the problem is hard. Some members of our team were better than others at taking the reins and making things happen. That's not mean to bash my team members, though; I feel like everyone contributed to meaningfully to the project.
I feel like with another day or two of work, we could have our racer driving courses pretty well. It's a shame that we didn't finish in time. However, I think that everyone on our team learned a lot, and the project was definitely worth doing. We accomplished in the last three weeks what took the other teams most of a semester to accomplish. I think that we have about 90% of the functionality of most other teams, but that last 10% is key to having a working robot.

I'm really happy with the work that everyone on our team did. I'm also really happy that I'll be able to get a little sleep again. :)

Tuesday, April 08, 2008

The internet is broken

My passage of a small milestone today points to a not-so-small problem with the internet at large. That image over there isn't a joke: I really passed the 50,000-message mark in my Gmail spam box this morning. Gmail deletes spam messages after 30 days, so that means that I have received 50,000 new spam messages since March 10.

Let's look at a few stats on my spam:
  • Spam conversations in the last 30 days: 50,000
  • Other conversations in the same timeframe: 745
  • Percent of conversations that are spam: 98.53%
  • Percent of conversations that are legit: 1.47%
  • Average time between spam messages: 51.8 seconds
I should note that my email setup is a little different than most people's, since I relay mail through before forwarding it on to Gmail. However, even with my somewhat unique configuration, 50,000 spam messages in 30 days is ridiculous!

I'm glad that Google has such an amazing spam filtering system, or else email would be completely unusable for me. (As an aside, I'm taking a class on machine learning right now, and it's cool that Google uses advanced machine learning techniques to implement their spam filtering. All of that nerdy computer science stuff I'm learning about is quite useful in real life.)

How did we get to this point? After all, back when I started using the internet in 1995, Spam was almost unheard of; today I have received 37 spam messages since I started writing this blog post. It all boils down to two things: motives and methods.


For spammers to be successful, they need a market of people who will buy their products. If no one ever clicked on a link in a spam message, it seems pretty obvious that it wouldn't be worth it for spammers to continue. However, there is unfortunately some small, clueless proportion of the population who are in the market for "Male enhancement", "New collection of Swi$$ R0lex", or "Mic.rosoft Win.dows Vista U1timate" and think that responding to spam is a good way to get what they want. I have yet to meet one of these clueless people in real life, but they must be out there, or I wouldn't be receiving spam. It's simple economics.

So what has changed since 1995?
  • More people use the internet now, so it's a larger, more attractive target to potential spammers.
  • The average internet user is less computer-savvy (and maybe less everything-savvy) now than in 1995.
Back in 1995, the only people who used the internet were scientists, professionals, and nerdy early adopters like me. Everyone who was on the internet spoke computerese pretty fluently. Also, most of them were pretty smart people who recognized that there were better ways to lose weight or get a discount mortgage than by responding to some spammer scammer's email.

These days, your grandma, Joe Sixpack, my baby brother, and everyone else in the developed world is on the internet. Now, instead of marketing to a group of scientists and engineers, spammers are marketing to a pretty broad cross section of the population. Both the size and the gullibility of the potential market have increased.

Let's do a little cost-benefit analysis to look at the economic incentives for sending spam. Let's estimate how much the bandwidth to send all of that spam might cost. We'll focus only on the top 3 web mail providers (Yahoo!, Microsoft, and Google), ignoring the vast number of other email accounts out there.
  • There are about 600 million web mail accounts in the world.
  • If every one of them receives spam at the same rate that I do (which I admit is probably a little high), that's about 30 trillion messages per month, or an average of about 11 million spam messages per second.
  • If each spam is about 1KB in size (seems about average, looking through my spam box), then that's about 85 gigabits of spam per second.
  • A quick internet search found a site that lists wholesale internet connection lease rates. They charge $15,000/month for a 622Mbps OC-12 line.
  • Even if we assume a 50% discount on line lease rates since the spammers would be using such massive amounts of bandwidth, that still comes out to 138 OC-12 lines, which would cost $1 million/month.
Let's estimate that it costs another $1 million/month to maintain the network equipment and servers to send all of that spam. Finally, let's assume that spammers make only $1 for every message that someone responds to. What response rate do they need to break even?

1 message in 15 million.

In other words, if one person in 600 responds to one of their 50000 spam messages a month, they provide an economic incentive for spammers to keep spamming.


Even if spammers have an incentive to do their thing, they still need a way to do it. They won't be able to walk up to most respectable internet providers and say "I'd like to flood the internet with 30 trillion messages a month. Can I buy a little bandwidth from you?". So how do they send spam without being blocked?

They use your computer.

A large percent of spam is sent by organized crime groups. They realize that they can't just go out and buy bandwidth to send spam—after all, who would sell to them? Besides, if they bought bandwidth from one place, it would be pretty easy to block that one place and stop the flow of spam. They would also have to buy millions of dollars of computer equipment to handle sending all of that spam.

Rather than deal with all of those problems, they use botnets to send spam. A botnet is a network of hacked computers, usually running Windows, that is under centralized control. The person controlling the network can have 1000s of computers all across the internet send out spam for them. This offers a couple of advantages to spammers:
  • It's really difficult to track and block spam from so many different sources.
  • They don't have to pay for bandwidth or servers.
(In reality, many spammers pay a botnet operator for their services, but the general principles are the same.)

If you've ever downloaded and run one of those fun little games someone emailed to you, or if you've ever run a cool screensaver you found on a shady-looking web site, or if you don't run antivirus and firewall software, or if you don't keep your system patched with Windows Update, or maybe even if you do do all of these things, your computer might be part of a botnet and you don't even know it.

The situation is depressing, and there are no really good technological measures for stopping the flood of spam without drastically changing the way that internet email works. At least Google has some good filtering algorithms.

PS—Here's the current count:

Sunday, April 06, 2008

I survived

I'm taking a wilderness survival class at BYU. We had a 2-1/2 day field trip last weekend, from Thursday afternoon to Saturday night. I'm happy to report that I didn't die.

The trip was actually easier than I thought it would be. We got to bring almost everything that I would typically bring on a campout, with the exception of a headlamp, a lighter, and food.

We drove out to the west desert in Utah (near Eureka) and hiked eight miles late on Thursday night. We threw down sleeping bags on the side of the road and slept without any shelter that night. It was about 25ºF that night, so we slept close together for warmth.

On Friday morning we awoke to discover that we each had an orange to eat for the day. I was very thankful for the food, since I had expected that we would have to scavenge for everything we ate. day we passed off several skills with our TAs (starting fires, building traps, etc.).

Late that afternoon our teacher brought several live chickens for us to eat. We killed, skinned, cooked, and ate them. I had helped butcher chickens before (my uncle raised them), but it was a completely new experience for most of the people in the class. Some were visibly squeamish about it, and some really enjoyed it. I think that it made an impression on everyone that the lunchmeat that you buy at the store doesn't just some from a factory: it was once a living animal. We made chicken soup, and the broth and vegetables were really good, but the meat was pretty rubbery.

That night, about an hour before dark, our teacher gave us each two granola bars, a packet of oatmeal, and a packet of hot chocolate, and then our TAs split us up for 24 hours of individual solitude. I brought some live coals from our cooking fire to start a fire in my individual camp, but when I got to my camp I found that the coals had gone cold. "Great", I thought. "I'm going to freeze for the next day." Thankfully, however, I started a fire with flint and steel on my first try (the first time I had ever tried in my life, actually), and soon I had a warm fire. I was very happy that I got it started.

In the short remaining time before it got dark, I collected firewood from the surrounding area and laid out my sleeping bag. Before I went to sleep, I put two large logs on the fire in the hope that I would still have warm coals in the morning so I wouldn't have to start the fire again. The sky was clear, so I didn't bother with a shelter for the night: I slept under the stars. I woke up once during the night to the scratchy sound of snow crystals falling on my sleeping bag.

I awoke at dawn and found that I still had hot coals. I built up the fire and boiled water for my hot chocolate. I savored it, since I wouldn't have much else for the day.

I marked the position of the sun so that I would be able to tell the time during the day, and then I laid back down to sleep. I woke up around 9 a.m. and cooked and ate my oatmeal. I've never tasted anything so good. I spent most of the rest of the morning reading. Around noon I ate a granola bar and fell asleep again. I spent the afternoon alternately sleeping and and reading.

Around 2 p.m. the wind picked up, sustained at about 20 MPH. I started to get cold, and ash from the fire kept blowing all over me, so I built a wind shelter with some branches and a tarp. I put my sleeping bag inside and laid there for the rest of the afternoon.

At 6 p.m. our TAs signaled that it was time for us to pack up and return to the main camp. When we got there, our teacher was cooking a Dutch oven dinner. It was pretty miserably cold waiting around for it, but I was glad to eat. I would have preferred to just go home, though.

Being out by myself, completely alone for 24 hours was a great experience. I had time to think and pray about things without distraction. I also gained a greater appreciation of the companionship of others. It can get kind of boring being by yourself with little to do for that long.

I'm glad I went on the field trip. I grew from the experience. It gave me a much greater appreciation of all of the conveniences that I enjoy. When I'm hungry, I go to the fridge and get food. When I'm cold, I turn up the heat. Can't see? Flip on the lights. Dirty? Take a shower. Wonder about the time? Look at a clock. Living without all of these things made me appreciate more what I have.