Line maze solver

Forum 2005-2010 (read only) General Exhibition
1

This project doesn't involve an Arduino, but it is driven by a mega168 that I programmed using the Arduino IDE and Orangutan Arduino Libraries, and I was sufficiently happy with the outcome that I thought others might find it interesting:

The above link is to a youtube video of a Pololu 3pi robot (which has a programmable mega168) solving a line maze. This was my first attempt at making a maze solver and I wrote the code from scratch the night before our last local robotics competition, so there's plenty of room for improvment (for example, it would be cool if it could handle mazes with loops or irregular intersections). It would also be cool if it could have similar performance with higher robustness (changing conditions such as harsh shadows or dusty tires can really throw it off at the moment).

It uses PID control to follow the lines and it makes pre-programmed, timing-based turns once it has identified which way it wants to go at a given intersection. Because of this, it's kind of at the limit of what it can do with current programming; if I push it much further it starts to miss intersections or think the ending circle is an intersection, at which point it turns left and drives around the outside of the circle. As it is now, it's so finely tuned that it only functions with clean tires. In the video, on the fast run, you can see it start to fishtail on some of the turns just from the dust the tires picked up on the learning run (normally I use some rubbing alcohol to clean the tires before every run, but I figured that would be pretty boring to put in the video).

I have one other video of this robot, this one from the actual competition, in which multiple 3pi robots are following a line at the same time. My robot is the one that gets knocked off the line last. I posted it in another thread a few weeks ago, but I'll post it here as well:

Here's an picture of a prototype:

  • Ben

Edit: allow me to apologize for the poor aspect ratio of the video. The camera used takes the video as widescreen, but the only software I have to get it onto the computer didn't seem so good at dealing with this.

2

That's amazing. Too bad there's no Robothon this year.

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.

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 :slight_smile:

When the 3pi hits the market will source code for things like this be available. And any idea how the price will compare to the LV168+Tamiya gear kit+wheels+chassis?

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.

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.

3

wow, i'm amazed at how fast it goes, while keeping very accurate. During the maze video, it just made every trun perfect, and just everything flowed so smoothley. I couldent believe the accuracy and speed you got out of it. Please make it a kit online, i would buy this in a heartbeat! ( ofcourse if the price was right ) And that racing video is also impressive. Good job, you make the robot building community proud!

4

wow, they do run really fast, good stuff

5

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 :slight_smile:

I appreciate your saying this :slight_smile:

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!

  • Ben
6

wow, i'm amazed at how fast it goes, while keeping very accurate. During the maze video, it just made every trun perfect, and just everything flowed so smoothley. I couldent believe the accuracy and speed you got out of it. Please make it a kit online, i would buy this in a heartbeat! ( ofcourse if the price was right ) And that racing video is also impressive. Good job, you make the robot building community proud!

Thanks for the compliments! This will be available as a kit soon.

  • Ben
7

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.

That's much simpler and smarter than what I was trying to do. I was also taking a much more general case where the algorithm allowed any intersection to be reached from any other.

My algorithm would have handled loops in the maze though, but I never got to test it since I never had a way to read in the maze (the robot never actually got past the paper design stage).

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.

I'm really looking forward to reading that.

It's true, the 3pi has almost all of its I/O lines devoted to onboard hardware, which limits its general-purpose usefulness.

I was thinking more of having the standalone orangutan module to use in other projects while not playing with the 3pi.

But as far as what you did say, did you consider using port extenders for things like the reflective sensors to leave some general IO free?

8

That's much simpler and smarter than what I was trying to do. I was also taking a much more general case where the algorithm allowed any intersection to be reached from any other.

I definitely want to make a more advanced, general-case version that can handle loops. It doesn't have encoders, which might make mapping difficult, but it can move at a very constant speed so I might be able to get by with raw timing. This was just my first stab at a maze solver that I didn't have time to start until the night before the competition, so instead of generalizing the algorithm I worked on (a) figuring out the non-looped solving algorithm and then (b) optimizing the performance.

But as far as what you did say, did you consider using port extenders for things like the reflective sensors to leave some general IO free?

Unfortunately we're not familiar with any devices that would meet our design requirements of bidirectionality with resolution of a few microseconds. The pulse lengths we'd be trying to measure from the reflectance sensors will typically range from 50 - 500 us, and we would like to be able to measure them with decent resolution. Do you happen to know of anything that would meet those criteria?

  • Ben
9

Not sure if this would quite do the trick or not, but I am using the DG408 MUX to allow multiple inputs on a project of mine, and it is working quite well. The data sheet says that the switching time is TYP 180 ns, which should be well below your requirements. See http://search.digikey.com/scripts/DkSearch/dksus.dll?Detail?name=DG408DJZ-ND for a datasheet. From the datasheet, it appears to allow bi-directional communication: "The analog switches are bilateral, equally matched for AC or
bidirectional signals."

In my experience, the limiting factor has been the ADC time of the Arduino itself, and not the MUX switching time at all.

Hope this helps

Cheers

10

Thanks for the link. I did some searching for digital multiplexers since the QTR sensors on the 3pi are controlled and read using digital I/Os and found some that are even cheaper, but I'm not convinced the added complexity and cost are justified when the reward is freeing up two I/O lines (since there are five sensors, all three multiplexer inputs would be required.

It seems like the best way to get more I/O lines is to use an AVR in a package that natively provides more I/O lines (e.g. the mega644). The increased cost would be comparable to that of using a mux or port expander, but the performance would be much higher and the circuit complexity would be much lower.

If your design to expand the 3pi robot requires more than three digital I/Os and two analog inputs (or two digital I/Os and three analog inputs), the solution we envision is to turn the base into a serially controlled slave device driven by a secondary microcontroller such as an Arduino.

We intend the 3pi to be the first of a line of programmable robots that provide a quality mechanical platform for your software and custom electronics. We're already tossing around an idea for a larger robot based on the mega644 (64k flash, 4k SRAM, 2k EEPROM, 32 digital I/Os, 8 analog inputs). As far as programming goes, the mega644 is very similar to the mega168, and there would be plenty of I/O lines and prototyping space available for custom electronics.

  • Ben
11

like i said if the price is fair, i'll buy this in a second! this is really impressive...

pm me, or let my know when this becomes available.. or post back here, ill check this thread from time to time

12

I'll make some sort of announcement when they are available. It will hopefully be some time in July.

  • Ben
13

I'll make some sort of announcement when they are available. It will hopefully be some time in July.

  • Ben

I'm sure there will be an announcement. I'm not normally the sort to eagerly await a product release, but you've got my attention here :slight_smile:

14

To Ben -

Count me in among the folks interested in the 3Pi. Like some of the others have mentioned above, I'd to use the 3Pi as a expandable base. One of the comments you made earlier has me intrigued:

...you have the option of using LCD pins for I/O if you remove the LCD.

Judging by the 3Pi picture and the data sheet for the 8X2 display, it looks like you're using 11 pins?

I'm thinking:

Remove the LCD, and add some additional sensors to the base
Add a second platform with another AVR & the previously removed LCD
And maybe an xbee radio.
Instead of using the serial pins, utilize the 3Pi as an SPI Slave.

I look forward to checking out the schematics as soon as they're posted, to determine approximately how much power the 3Pi is using, and how much might be left over.

Any thoughts?

15

I have posted an answer to this here:

http://forum.pololu.com/viewtopic.php?f=2&t=983&p=4309#p4308

in response to your post on the Pololu forums.

  • Ben
16

I'm sure there will be an announcement. I'm not normally the sort to eagerly await a product release, but you've got my attention here :slight_smile:

I thought I'd post an update here. We have started putting information about the 3pi up on our website and have made it available for preorder. We hope to begin shipping orders sometime next week, at which point I'll make a more formal announcement. Documentation is a little light at the moment, but rest assured that work on a detailed user's guide and sample programs (including line-following and maze-solving code) is under way. We already have a 3pi library written (one version is compatible with the Arduino environment and another is intended for use with AVR Studio), but we need to finish up the documentation on that as well.

If you have any questions, comments, or suggestions, please feel free to post them to our new 3pi forum!

  • Ben
17

That's really good news. The price seems quite low too. Basically for $100, we get a $60 robot controller, $32 worth of motors, and the whole rest of the robot as well as libraries to help program it.

By the way, what is the diameter of the robot? For some reason I had the impression it was around 6" after viewing the videos. But now looking at the picture, based on the LCD and batteries, it looks closer to 4".

18

It's 3.7 inches (3pi centimeters) in diameter weighs 2.9 ounces without the batteries, so it's fairly compact.

One of my favorite features of the 3pi is that the motors are driven off of a regulated 9.25 V, so your robot's performance doesn't change as the batteries discharge. This means that you avoid the common problem of finely tuning your robot with fully charged batteries only to see its performance change drastically when the batteries are low. The performance consistency also means you can even do limited dead reckoning by using simple timing. This is how my maze solver performed its 90 and 180° turns (I figured out how long to drive the motors at a given speed to achieve the desired turn, and no matter what the battery charge the turn is always the same), and it is also how I was able to drive faster on long maze segments while still slowing down before reaching the next turn.

  • Ben

Oh, and here's a fun shot of one following a line in the dark:

19

how this robot can save the road? i mean how it can recognise the road at the second run?

any programming source code u can provide for that function?
i really hope to learn that!

thankz. :wink:

20

how this robot can save the road? i mean how it can recognise the road at the second run?

At its simplist all you need is tree data structure where you have a node for each intersection. Each node will have 3 pointer to the node for the next intersection if you go left, right, or straight. That will only work if the maze has no loops though.

From that point, there's many ways you can find the optimal path. You can have links back to the parent nodes in your data structure, or you can apply Dijkstra's shortest path algorithm to it, just as a couple of example.