Author Topic: 3pi Line Maze Solver  (Read 9963 times)

0 Members and 1 Guest are viewing this topic.

Offline bensTopic starter

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 331
  • Helpful? 3
3pi Line Maze Solver
« on: June 10, 2008, 06:12:45 PM »
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

Offline emmannuel

  • Full Member
  • ***
  • Posts: 87
  • Helpful? 0
Re: 3pi Line Maze Solver
« Reply #1 on: June 16, 2008, 12:59:32 AM »
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?

Offline bensTopic starter

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 331
  • Helpful? 3
Re: 3pi Line Maze Solver
« Reply #2 on: June 16, 2008, 02:06:14 PM »
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

Offline emmannuel

  • Full Member
  • ***
  • Posts: 87
  • Helpful? 0
Re: 3pi Line Maze Solver
« Reply #3 on: June 16, 2008, 04:44:17 PM »
Ah that is super clever, and efficient! :D

Offline Admin

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,632
  • Helpful? 169
    • Society of Robots
Re: 3pi Line Maze Solver
« Reply #4 on: June 21, 2008, 01:31:30 PM »
nice and fast! glad to see im not the only one who has an autocalibrate feature :D

Quote
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 :P

Offline newbie

  • Jr. Member
  • **
  • Posts: 36
  • Helpful? 0
Re: 3pi Line Maze Solver
« Reply #5 on: August 11, 2008, 03:03:52 AM »
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!!!!!!!
 ;) ;) :D :D

Offline Admin

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,632
  • Helpful? 169
    • Society of Robots
Re: 3pi Line Maze Solver
« Reply #6 on: August 11, 2008, 04:46:12 AM »
the code on my irobot create mapping robot will work on the arduino without modification:
http://www.societyofrobots.com/programming_wavefront.shtml

Offline newbie

  • Jr. Member
  • **
  • Posts: 36
  • Helpful? 0
Re: 3pi Line Maze Solver
« Reply #7 on: August 13, 2008, 09:52:53 AM »
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!

Offline vidam

  • Supreme Robot
  • *****
  • Posts: 423
  • Helpful? 1
  • Robotronics.org
Re: 3pi Line Maze Solver
« Reply #8 on: August 13, 2008, 10:29:34 AM »
Am not able to view Ben's 3pi line maze solver video either in IE or Firefox!?  :-\

Offline Ro-Bot-X

  • Contest Winner
  • Supreme Robot
  • ****
  • Posts: 1,431
  • Helpful? 25
  • Store: RoBotXDesigns.ca
Re: 3pi Line Maze Solver
« Reply #9 on: August 13, 2008, 07:02:41 PM »
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!
Check out the uBotino robot controller!

Offline Spartan001

  • Beginner
  • *
  • Posts: 1
  • Helpful? 0
Re: 3pi Line Maze Solver
« Reply #10 on: March 08, 2010, 08:31:01 AM »
Could you post the code for the maze-solving?

Offline GWER57

  • Full Member
  • ***
  • Posts: 65
  • Helpful? 2
Re: 3pi Line Maze Solver
« Reply #11 on: March 08, 2010, 08:50:19 AM »
I'm pretty sure that the code is on Pololu's website ;D.
GTW

Offline CraftMaster25

  • Jr. Member
  • **
  • Posts: 11
  • Helpful? 0
Re: 3pi Line Maze Solver
« Reply #12 on: April 11, 2010, 07:39:05 AM »
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  ;D

 


Get Your Ad Here

data_list