Wich datastructures for this introductional AI project

The best way to learn about AI techniques is of course to read a book and build some examples and those would give you suggestions about how to represent things like paths and the like.

None the less, there is also a lot to be said for just wading in and hacking around on something that you find interesting and seeing what you can build without any particular guidance other than your own muse.

If you fall into the latter category I could make some suggestions about what I think would be fun to play with.

First of all, let your world be a bitmap. This is of course just a 2D grid as you suggested filled with cells, but the cells just have a single rgb color instead of a more complicate structure. You can still make very conventional large scale discrete features, like this is a road, this is grass, this is water, this is ice, this is sand by simply assigning different colors to represent those features. But by working at this tiny pixel scale, you introduce several advantages 1) you can use any paint program to generate any kind of world map that you want. You can even just clip photos from the web and they make world maps as well and 2) you get noise for free.

What I mean by that is, if you define black pixels to be pavement, with a nice high coefficient of friction (easy to drive on) and white pixels to be ice (very slippery) you can interpret greyscale or even dithering (intermixed black and white) as noise. On pure black the car corners well, on pure white is corners less well, on grey, well, it is somewhere in between. I am assuming that you will do some kind of physical modeling of how the car moves on top of different colors.

Furthermore, you can do the same with your sensor modeling. Yor car's eyes, which are looking at the road ahead, look a few pixels ahead of the car (how far ahead, how many, you decide). If you want your work to mean anything useful, you must assume that the sensors are noisy. For example if you see a blade of grass on the freeway, does that mean the the coefficient of friction suddenly drops and you must slow down? A good model will average in the readings of several sensors to deal with noise. And is a system where you can air brush in noise, you can model the noise directly into the world map rather than spending your time solving suspiciously clean problems.

In a model like this it is also easy to model other types of sensor failure, for example, the further you move a pixel vision sensor from the car (the car is looking way ahead) you can have the colors start to wash out. Or they just get more random noise added. The notion is that your sensors basically return colors, what they see and your car must react to the colors that it sees ahead of it whereas the car's motion depends upon the colors that are under it.

Lastly, in keeping with the current fashion in robotics, I recommend that you look into the locally reactive models rather than the global planning models.

What this means is that your car works on learning that when it is looking a smooth hard black top in front of it, it can step on the gas and when it is looking at ice or water it needs to slow down or turn. You should be able to build a car model that can, using just local methods, follow a road, a reasonable width mostly black line.

Global behavior - and goals - can get represented at a higher level. For example you can divide the low level bit=map environment into larger order cells of say 10 by 10 blocks. As your little robot car wanders over the low level grid, it can be keeping track of strategies (like orientation and speed) that it used to cross from one cell into another and thus when asked to get from the cell in the top left corner to the cell in the bottom right, it can pull up the cell map, and start working out a course of action to try to get from where it is to where it wants to go. By tracking where it is at any moment (which cell it is in) it can keep refining the route if necessary to make progress toward the goal.

You can think of the goal behavior as nothing other that the cars attempt to solve a bunch of min-problems like: How can I as rapidly as possible get from Cell(i,j) to Cell(i,j+1). What I am suggesting is that the car can pretty much just wander at random, cacheing what it was doing when it went from one cell to the next and then trying to replay those moves when it has been given a goal that requires it to move from one cell to the next. Will the moves work - maybe yes maybe no. But if you get stuck then thrash and if you end up somewhere unexpected - realign to your goals from there.

I have specifically made no suggestion as to whther you use genetic algorithms, neural nets, support vector machines, hidden Markov models, or any of the dozens of other learning methods that you will need at some point when you get down to training your car to drive. I just wanted to outline some ideas that you could use for building your 2D world and for possibly representing your car's Map of that world.

One last thing. These general guidelines should be sufficient to code up a little high school level project that you can have fun with for a few weeks, or by working a little harder, like for 7 years, it could be a PhD thesis topic. The difference between the two of these is not the problem, it is the amount of effor that you choose to put into exploring the possible solutions.

If that wasn't clear consider the following. You could build a nice complicated physical model of the car motion based on coefficients of friction and newtonian forces. Or you could just let the car move freely on white cells and is unable to move on or cross black cells. Now you could restirct yoursles to maps that are standard mazes (find a picture on the web) white floors black walls. Your local learning model is random walk roomba style, just walk in a straight line till you hit something then turn randomly and do it again. Your global cell map grows to be a map of the maze. When you are done, you have done practically no learning, no physical modeling, and have essentially writen a maze solving program. By choosing a very general starting structure you can either choose to work on fairly simple problems or on hard ones.

Enjoy!

marlin314a at 2007-7-16 1:13:27 >