I've tried to make a line solving robot in the past. It's easy enough to do in theory (trivial implementation of Dijkstra's algorithm), but where I always got caught up was converting the robot's observations into a map of the maze. I'm also very impressed that you implemented the algorithm on such a tiny processor. As I recall, it's space is O(n^2) on the number of edges and you've only got a few hundred bytes to play with.
I devoted a 200-byte array to storing the intersections, and since I only really need two bits to encode the four possible intersection options (left, straight, right, or back), I could optimize the code to make that 200-byte array capable of storing 800 intersections. I devoted another 200-byte array to storing the lengths of all the line segments between intersections so I could later determine which ones were long enough for me to safely run at higher speeds. The robot prunes its intersection list as it runs (i.e. as it reaches a dead end and backtracks, it eliminates those dead-end intersections from the list), so it never stores the entire maze. This is sufficient because the maze doesn't contain any loops. In the end, what's left is the shortest path from start to finish.
For what it's worth, it's fair to all it an Arduino design if you used the IDE and an ATMEGA168, and even if it weren't, you know I'd be in favour of calling the Orangutan an honourary Arduino clone :)
I appreciate your saying this :)
When the 3pi hits the market will source code for things like this be available.
We plan on releasing sample line-following and line-maze-solving code for the 3pi robot. The maze code will most likely be a simplified version of what you see in the video so that it's
a) more robust, and hence more likely to function well on courses that use different materials than the one I've optimized mine for
b) easier to read and understand (ideally people will be able to see how it works and will feel comfortable enough to start improving it for themselves)
c) something people have room to improve upon and make their own
I'd also like to make a line-following tutorial that explains how to use closed-loop PID control and a maze-solving tutorial that explains a basic algorithm for exploring a non-looped maze and for obtaining the best path solution in the process.
And any idea how the price will compare to the LV168+Tamiya gear kit+wheels+chassis?
It will be a little more expensive than the above list of parts, but not too much more. However, it comes with higher quality motors than the Tamiya gear boxes, and it has built into the PCB five QTR reflectance sensors. Plus the 3pi has some extra features that I think people are going to really like.
It's a pretty little thing, but it looks like I don't get a standalone Orangutan out of the deal which is a bit disappointing.
It's true, the 3pi has almost all of its I/O lines devoted to onboard hardware, which limits its general-purpose usefulness. The only truly unused I/O lines are the UART's RX and TX lines (arduino pins 0 and 1). Analog inputs 5, 6, and 7 are connected to onboard hardware via shorting blocks, so these can be used for extra sensors if those shorting blocks are removed, and you have the option of using LCD pins for I/O if you remove the LCD. As far as expanding the system, our thought is that a second level could possibly be added in the future. To this second level you could add the microcontroller board of your choice and use it to control the lower level via serial commands to the 3pi's UART. The 3pi's mega168 could have a default program that accepts serial commands and in response drives the motors, plays the buzzer, returns sensor readings, etc. This would greatly increase its configurability and make it a more general-purpose platform, but that's an upgrade for the future. At the moment we're just focused on getting it released! Note that the 3pi will be entirely code compatible with the LV-168, so programs you write for one will work on the other (assuming they share the same hardware connections).
Edit: I just watched to maze video, from your description I was picturing something a lot more sluggish. That easily rivals the best I've seen in robot competitions and it's from something that will be a general robot platform kit. You've really outdone yourself.
Thank you very much for the compliment!