Watching the DARPA Car Race

It is almost 3 in the morning here in Bangalore as I type this. I've been watching the webcast of the DARPA Car Race. This years challenge was for the autonomous ( == no human control) robot cars to accomplish three sub-missions in an urban environment, following all traffic laws (obeying traffic signs, recognizing and conceding right of way etc). This task is a magnitude tougher than finishing a 130 mile autonomous drive in the desert, with zero human control, which was the goal of the DARPA 2005 car race.

Stanford's entry, Junior, just pulled in to the finishing area. While it isn't yet clear who won (because this is not a first past the post race), I'd put my money on Junior. (His (its? :-) ) predecessor Stanley won the 2005 Grand Challenge. This is history being made before our eyes.

The sight of the cars driving themselves, with the steering visible through the windows turning with no human hand at the controls is .. exhilarating... exalting... too cool for words. This is **REAL** programming in action. The people who made this happen are just incredible. Congratulations to all!

How lucky does one have to be to live in these times?

Now to drag myself off to bed (and dream of autonomous vehicles).

To "learn AI"

first learn basic mathematics.

I keep getting asked this question and I keep saying the same thing - to three people in the last week, for e.g, two of whom were working through (or planning to work through) AIMA - so I thought I'd put this down here (and point anyone who asks the same question to this entry in the future).

Learning AI (or any deep comp.sci for that matter) is not like learning J2EE or ruby "dsl"s or whatever the fad du jour in the enterprise software world is - read a few chapters of the latest bestselling "pragmatic" book, write some crappy web site and hey presto you are the expert.

"Real" comp sci doesn't quite work like that.

To understand a standard 3 layer feed forward neural network, for example, you need to have a solid grip on

• vector spaces
• basis vectors and change of bases
• eigen vectors and eigen values
• Basic matrix operations like inversion
• multi dimensional performance surfaces
• Quadratic functions and finding their global maxima within Newton's method and Conjugate gradients
• performance measures and steepest descent
• partial differentiation of vector values
• numerical stability of algorithms

Without that background you will be able to use conceive of "class NeuralNetwork" that "has an" instance of "class Node" etc, but you will *not*,(repeat NOT) be able to do anything useful with real world data (writing a XOR classifier doesn't count!).

And, a feed forward neural network is only one type of pattern recognizer (or function approximator). There are many more, each with its own trade offs , and you have to know the math to make the trade offs.

That being said, the best book to start with is AIMA as long as you (1) learn the required math parallely (2) do all the exercises at the end of every chapter.(I can't emphasize this enough). Reading through != "working through".

If one is willing to work hard, there are very few fields as fascinating as the various branches of AI.

Once you start down the rabbit hole, however it may be very hard to continue writing all that heavy lifting enterprise software without hearing the giant sucking sound of your life going down the drain as you write yet another jsp page for the latest leasing system. ;-)

Be warned! :-D.

Anyway the really hard part of "learning AI" is not getting the books or working through them systematically (which is hard enough), but that is for another blog entry.

Post Script - Some book recommendations for beginners.

1. Linear Algebra by Gilbert Strang
2. Calculus by Gilbert Strang
3. Artifcial Intelligence A Modern Approach By Russell and Norvig
4. Machine Learning By Tom Mitchell
5. Neural Networks for Pattern Recognition by Chris Bishop
6. Paradigms of Artificial Intelligence Programming by Peter Norvig (ok, this one is not quite an cutting edge AI book, but imo this is the best book on programming ever written and if you call yourself a programmer you should have it on your book shelf)

Snapshots from my Robot Simulator

I've built a tiny robot simulator for my ongoing research. Like the (absolutely brilliant) Stage Simulator, my simulator enables the simulation of robots in a 2D world. Of course my simulator is much simpler than Stage, primarily because it doesn't try to do as much as Stage does. On the other hand it has a couple of important differences that are important to my research. For e.g. it has a built in sensor and motion error model and (being implemented) a sophisticated Sonar Model.

Anyway, here are some early snapshots of a simple environment.

A simple world for a robot to navigate - The world is 10m X 20m with a resolution of 2 cm. The corridor is 2.5 m wide.

A robot (the little blue dot)stands in the middle of a corridor.

The world overlaid with a quadtree that overlays and recursively decomposes the 2D world and enables efficient ray projection.

The world illuminated with a laser. The illuminated points are rendered in yellow. The scan has a resolution of 1 degree,a "pan" of 360 degrees and a range of 3 m. I was a bit concerned that this would be slow but it takes no appreciable time, even when the angular resolution is 0.1 degree. All hail the quadtree!

Of course the robot sees only the illuminated points, not the complete length of the walls etc.

This is what the robot "sees". There are other sensors simulated (e.g. an odometer) but they are not rendered here. You'll notice that the laser sensor senses the environment "perfectly", i.e the range detected is the actual range to an obstacle that intercepts the laser beam. No real sensor works like that. To simulate this imperfection in a simulator, a probabilistic error model is added to filter the reading so the robot sees an approximation to the real range.

Here we've added a bivariate gaussian error (with a standard deviation of 10 cm) to the laser sensor. If you squint, you can see that the readings now only approximate the wall surface. To see this more clearly, we'll remove the unseen parts of the corridor walls and the overlaid quadtree to get a picture of what the robot sees, with the simple error model in place.

This is what the robot "sees" through the error filter. Note the "scatter" of the readings. Now the robot doesn't know for certain where the walls (or whatever objects obstruct the laser - different parts of the world react differently to different sensors - some surfaces absorb light for e.g returning no readings to the laser sensor) are.

The robot simulator is not the central thrust of my research effort, but it helps to have an environment in which one can plug in various sensor models, motion models and error models and see what the robot would see. I thoroughly enjoyed coding this up.

The next step is to replicate a realistic sonar (vs laser) sensor. There are a few interesting issues to be resolved to get this to work properly. Sonar works differently from lasers - cones of ultrasound have different propagation and reflection characteristics from rays of light. Stage simulates sonar with the same "ray trace" approach as is used for lasers. For my research I need a more accurate model (and hence the need for a custom simulator). Early next week, I will be visiting the Robotics Lab of the DRDO (The Defense Research and Development Organization - For non Indians reading this, they are the local equivalent of DARPA) to talk to some scientists working on similar problems. I have a basic sonar model working already, the key challenge of which was to layer different continuous probability distributions and sample data from them in reasonably efficient fashion, but to describe that would make an already long post longer, so I'll stop now.

To Teach is To Learn Twice ... And More

I am sometimes asked by clients to implement Artificial Intelligence based solutions to problems involving massive datasets, real time requirements etc. A non trivial part of this work is to transfer the knowledge of AI algorithms and the underlying maths to the client's programmers. After doing this a few times, I now have a clearer idea of some of the difficulties involved and some partial solutions for them.

1. Problem 1 : Transferring Mathematical Intuition Using AI effectively often demands a deep understanding of the mathematics underlying whatever AI 'paradigm'/algorithm you use. For e.g. to even think about whether Neural Networks are a good solution for a problem, one needs to understand Linear Algebra at very intuitive level. To many people maths == a set of equations or symbols to be manipulated. And this manipulation and re arrangement of concepts to achieve precise effects is something programmers are naturally good at and so this tendency is even more deeply rooted in good programmers.

   For e.g., a lot of us have learned the equation F = m * a , where 'F' is Force, 'm' is mass and 'a' is acceleration. And to get through our exams we treat this as some kind of pluggable system in which two quantities are known (or can be derived from the given data) and the third has to be derived. This looks fairly simple. To check whether you understand the reality underlying the equation ask yourself this - "Does Force cause acceleration? Or Vice versa? Or both? Why? When?".

   The use of equations to *calculate* a quantity is different from being able to think effectively in terms of the concepts underlying the equation. To use mathematics effectively one has to constantly translate between the world of mathematics and the domain of the problem. Very few people(including mathematicians) feel the need to acquire this skill. People who use mathematics to get work done (e.g. Physicists/ Astronomers/ Race Car Designers) acquire this skill out of sheer necessity. Forcing oneself to translate (and asking students to translate) back and forth between English(without using mathemetical terms) and Mathematics is a valuable exercise. (try doing this for a simple differential equation and you will see what i mean)

   Thus, it isn't possible for someone to grab a few equations out of the latest AI/Pattern Recognition/Robotics etc book and apply them straight away to solve real world problems. To even know what is possible takes an understanding of the mathematical undepinnings of the various "families" of AI algorithms and this intuition takes a long time(at least for folks like me) to acquire. If programmers are just shown some algorithms or mathematical proofs, it is very unlikely they will be able to program an effective system or even maintain a system to meet changing environments. This is complicated by the fact that intuition may take a few years to acquire but has to be transferred in a week or less.

   While there is no perfect solution to this, I find that one can transfer large "chunks" of intuition through carefully selected (sequences of) motivating examples. In my first "iteration" of teaching, I said (in effect), "o.k. here is the (basic) theory. This is the algorithm in pseudocode. Use this and you will get the results you want". Everyone seemed happy but the whole effort "thrashed " for quite a while before delivering the (astoundingly effective) results.

   So these days, I try to instill an understanding of the theory distinct from the programming effort. More of a "teach how to fish" while giving the student enough "fish" so he doesn't starve till he learns to fend for himself.

   Thus instead of just throwing out the algorithms for (say) prediction and monitoring of data streams using Markov models, I start with real world examples of prediction vs monitoring and slowly feed in the maths (equations first, trivial programs next, then proofs, then real world programs). Given sharp "students" (as most of the programmers I interact with on a daily basis are, (Thank God!)) this works suprisingly well. I sometimes feel I am spinning a rope bridge across yawning chasms but the notion of a "slice" through a system works just as well in mathematics as in agile "story card" based implementation. Once a few cables are thrown across, programmers feel brave enough to explore the abyss a few feet at a time without too much assistance.

2. Problem 2 : Getting beyond "right" and "wrong" Sometimes in spite of my best attempts at simplifying and communicating, my "students" (I think of them as peer programmers rather than as students, hence the quote marks) sometimes misunderstand and "screw up" the concepts and write strange programs or advance baffling arguments. In the beginning my response was "That is NOT what I said! THIS is what you need to do. PLEASE look at the examples/notes/code. Aaaargh!!!! Not Again! ".

   A more effective way is to try to figure out what the student's mental model is, faulty though it be. So now, instead of reacting to a totally off track argument by (mentally) banging my head on the nearest wall, I say to myself "What he says makes sense to him. So what mental/model thought processes has he adopted which causes him to see the world in a fashion that makes this argument logical?". The moment I can identify this precisely I am able to come up with an illuminating example that demonstrates the error. And sometimes it turns out they are on to something important and it is my perceptions that need fixing. "Learn Twice" indeed.

3. Problem 3 : Ability to Do != Ability to Teach Sometimes the "teaching" gets so fatigue-inducing that I think to myself "I could have coded up all this in one tenth the time it taks me to communicate to someone else". My client, (being wiser than I) insisted on the teaching approach. What I have realized that many people (including Yours Truly) know how to do many thngs but are not often able to explain how they do them or teach others to do likewise. When you teach others you have to know each concept in a crystal clear fashion and also grok all the inteconnections between the concepts. Teaching often involves re-arranging concepts in increasing order of complexity and interdependence, seeking real life and programming examples that illustrate each facet of a concept with great clarity and slowly transitioning into complex real world problems and solutions. After teaching others, I understand many things at a much deeper level than I used to.

   That being said, teaching consumes massive amounts of time. I have to work 10 hours or more to prepare for a three hour "lecture". Thus "teaching" conflicts with "doing". For the time being, I'll focus on being a programmer more than a "teacher" type but I wonder how others manage.

There is a lot more I could write but this post is long enough. In another entry I will look into the difference between "Real world" and "Toy" AI.