AI on your iPod Shuffle

I was browsing Beyond Satire, a site run by Ellen Spertus (one of my summer colleagues on the orkut team), and I happened to hit a link about something called the Martin Shuffle. It turned out to be a name for a way to find a particular song using the "shuffle" and "next" features of the iPod shuffle. I read the article and was both intrigued and amused because it tried to apply some randomized mathematical analysis on iPod Shuffle usage; namely, the writer was analyzing what the optimal policy would be for finding a particular song on the iPod shuffle and how long that would take.

Two elements in the article caught my attention. One, on the right side of the page, there was an image of the Randomized Algorithms textbook that was used in Karger's 6.856 class, a class that I took, enjoyed, thought was consuming my life and causing endless pain, and subsequently dropped. Second, the analysis used the concept of Markov Decision Processes (MDP), a term that I vaguely remembered from Kaelbling's 6.825 class (Techniques in AI).

Quite frankly, this was one of the coolest AI/mathematical/algorithm articles that I've read in some time. For a while, my impression of AI has been that it was too heavyweight and abstract for solving real-world decision problems. AI papers that I've read, AI problem sets that I've done, and AI lectures that I've attended typically dealt with toy problems rather than the more complicated ones that we encounter in real life. Moreover, I had not really built a real-world application that used a major AI technique (we're discounting search in this discussion).

What suprised me the most was that the analysis was elegant and that the author actually provided short Python code to implement a value iteration algorithm for solving MDPs. The code was lightweight, nothing substantial that would've even taken me, a novice in the world of Python, to write. More importantly, it was concrete where the lectures that I had on MDPs were abstract. In short, I was amazed and inspired that the author could take something that I thought to be abstract, i.e. MDPs, and apply it to a fun but still real question. If only 6.825 had used fun examples like this instead of robots trying to vacuum dust from rooms or avoiding monsters, I might actually have found the material more interesting.

It was clear that the article was written by someone with a nerdy sense of humor. Upon checking the URL, I realized that the article was written by none other than Peter Norvig - the author of Artificial Intelligence: A Modern Approach (AIMA) and the Director of Web Search Quality at Google. From skimming his website, I saw that he actually had other pieces of Python code doing practical, lightweight, and intelligible AI. From reading the article, I'm actually inspired to bust out my copy of AIMA, relearn some AI techniques that I had previously thought to be of mainly theoretical value, and see what other neat questions AI can answer.

Thanks Norvig.