3pi Line Maze Solver

[bens]

Here is a video of my Pololu 3pi robot (the same robots as from the Extreme Line Following video) solving a line maze.  Note that the aspect ratio is a little screwed up; the camera used films in widescreen but the current software I have for getting it onto the computer doesn't seem to be on such good terms with widescreen.

[youtube]mJV-KDqHgDQ[/youtube]

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).

- Ben

[emmannuel]

Thats an awesome job. I can't wait till I finish my construction and move more towards the software part of my project.

BTW does it have every square of that maze area mapped in memory?

[bens]

No, it could conceivably create a full map of the maze as it runs (although the mega168 might have some memory issues given it only has 1k of RAM), but this version is designed for non-looped mazes where that's not necessary.  Instead, it builds up a list of intersections it's visited, and if it ever reaches a dead end, it back-tracks, eliminates the false paths from the lists, and modifies its record of which way to turn at the intersections it revisits.  In the end, all I have in memory is a list of what to do at all of the intersections in the direct path from start to finish.

For example, imagine a maze that looks like a plus, where the start is at the bottom and the finish is on the right:

Code: [Select]

  |
-----o finish
  |
start

The robot would hit the first intersection, identify that it is possible to turn left, record an "L" for left, and then turn left.  The intersection string would now read "L".  It would then reach the end of the left branch, note the end of the path, record "B" for back, and turn around.  It would reach the intersection again, turn left, and record an "L".  Once again, it would reach a dead end, record "B", return to the center intersection, record an "L", and turn left.  This would take it to the finish line.  Its intersection string would now read:

LBLBL

If you note that LBL (left-back-left) is equivalent to S (straight), and LBS (left-back-straight) is equivalent to R (right), you get that this reduces to:

(LB(LBL))
(LB(S))
R

As my robot runs the maze, it is performing this type of reduction as it goes to keep the intersection list as trimmed as possible.

- Ben

[emmannuel]

Ah that is super clever, and efficient!

[Admin]

nice and fast! glad to see im not the only one who has an autocalibrate feature

No, it could conceivably create a full map of the maze as it runs (although the mega168 might have some memory issues given it only has 1k of RAM), but this version is designed for non-looped mazes where that's not necessary.

yea, using squares wouldn't work for this . . . I was only able to get a 15x15 grid on my mega168 when doing my wavefront algorithm . . .

but of course, it gets much trickier when the lines are rounded

[newbie]

can ben provide a sample programming source code for this robot?
i am using a arduino,

want to solve a maze (not a line maze but wall maze) too, i will try to modify the programming u provide to suite me, anywhere u r brilliant!!!!!!!
 

[Admin]

the code on my irobot create mapping robot will work on the arduino without modification:
http://www.societyofrobots.com/programming_wavefront.shtml

[newbie]

but i will not know my target place, not like the tutorial. because i want to build a wall maze solving robot that can remember theroad after 1 trail like the 3pi,  can i download the 3pi source code?

i love the 3pi algorithm that LBL=S, how my robot can save this?

if i want to use the admin source code, i should download it to my arduino through the arduino program (usb) or throuh the avr stdio(isp)?

sorry if i have any mistakes....thank u!

[vidam]

Am not able to view Ben's 3pi line maze solver video either in IE or Firefox!? 

[Ro-Bot-X]

No, it could conceivably create a full map of the maze as it runs (although the mega168 might have some memory issues given it only has 1k of RAM), but this version is designed for non-looped mazes where that's not necessary.  Instead, it builds up a list of intersections it's visited, and if it ever reaches a dead end, it back-tracks, eliminates the false paths from the lists, and modifies its record of which way to turn at the intersections it revisits.  In the end, all I have in memory is a list of what to do at all of the intersections in the direct path from start to finish.

For example, imagine a maze that looks like a plus, where the start is at the bottom and the finish is on the right:

Code: [Select]

  |
-----o finish
  |
start

The robot would hit the first intersection, identify that it is possible to turn left, record an "L" for left, and then turn left.  The intersection string would now read "L".  It would then reach the end of the left branch, note the end of the path, record "B" for back, and turn around.  It would reach the intersection again, turn left, and record an "L".  Once again, it would reach a dead end, record "B", return to the center intersection, record an "L", and turn left.  This would take it to the finish line.  Its intersection string would now read:

LBLBL

If you note that LBL (left-back-left) is equivalent to S (straight), and LBS (left-back-straight) is equivalent to R (right), you get that this reduces to:

(LB(LBL))
(LB(S))
R

As my robot runs the maze, it is performing this type of reduction as it goes to keep the intersection list as trimmed as possible.

- Ben

You managed to explain the concept better than me some while ago in this post: http://www.societyofrobots.com/robotforum/index.php?topic=3525.msg27290#msg27290

Congratulations!

[Spartan001]

Could you post the code for the maze-solving?

[GWER57]

I'm pretty sure that the code is on Pololu's website .

[CraftMaster25]

Awesome job on the robot (I didn't notice any of the fishtails). What are you using to program the robot? Could you post the source code? But, GREAT JOB