Could you comment on my line maze algorithm article please???

RoboticsProfessor

I am developing a comprehensive article about how to solve a line maze. It includes the problem, photos, videos of fast maze solvers and details of the line maze algorithms. You can see it at:

www.richardvannoy.info/line-maze.php

I am choosing to use pseudocode so that hobyists can use it with BOE-Bot, 3PI or any other microcontroller/robot combination. Eventually, I will post BOE-Bot and 3PI source code.

I would appreciate any comments or suggestions that you may have that will help me make this the best line maze algorithm article it can be. Thank you.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Richard Vannoy

Programming and Electronics Instructor
www.RichardVannoy.info
·

SRLM

I found that there was quite a bit of 'middle' layer stuff. I didn't notice any one line that said exactly what was going to happen. Something like this would work:

The robot makes two passes over the maze; it uses the first pass to develop a map of the best possible route, and the second pass to quickly navigate along the stored shortest route.

Some more detail on implementation would be nice. How exactly do you store the path? Do you use something like a stack, queue, or graph? Do you make a matrix? If this is for a computer science course, that's something I'd expect to see (along with discussions on time complexity...)

What sort of errors or problems does your current procedure have? Are there hardware conflicts such as reaching a maximum speed or losing traction? Are there software issues like too much to do and not enough time? Also, how well does the algorithm that you've developed translate to a different maze? Is the robot's average speed lower, higher, the same? Does it expose deficiencies in your procedure?

If this is intended as a formal introduction (along the lines of a paper), the some circuit diagrams, charts, and graphs would be good too.

kwinn

Interesting, the line following maze looks to be much easier to set up than the physical maze made with 1x3 wood I entered years ago.

What happens if the robot is traveling fast enough to put all the sensors beyond the lines?

It looked like the two robots I saw were "left hand rule" followers. What happens to them if a line goes to the right, turns left 90, and turns left 90?

Jessica Uelmen

Hi Richard,

Ironically enough, last week's Project of the Week was Boe-Bot Maze Navigation with QTIs, which is a line following maze application.· It's much simpler than your article, as it was written to simply introduce the reader to maze navigation logic, but please feel free to look through it and use any of the included code as psuedo-code for your article.

You look like you're off to a great start!· I agree with SLRM's comments, and a bit more information about the hardware design of the actual robot will help readers·better·understand the logic of the code.· Adding a Problems and Challenges section might also let the reader know just how complicated maze navigation can be.

Happy Developing!

Jessica

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Jessica Uelmen
Education Department
Parallax, Inc.

Post Edited (Jessica Uelmen (Parallax)) : 4/14/2009 10:57:05 PM GMT

SRLM

I spent some time working on an algorithm just now, and have a few more comments:

I think I saw that your maze algorithm is for mazes that are acyclic. This seems like a flaw: you're limiting the application to very specific circumstances.

I'm not quite sure what sort of data structure you're using, but I'd use a graph. It would work like follows:
1. Map and label each junction of 3 or 4 openings. (on the first run)
2. Create a graph with each junction as a node, then the cost to each node is the number of 'squares' from the adjacent nodes.
3. Use a single-source shortest path algorithm (like Dijkstra's) to figure out which route to take. That way, you get the guaranteed shortest path.

Despite any fancy programming tricks, it still seems like a hardware problem. Namely, how fast can you get the robot to turn and accelerate. I think that could use some significant discussion.

RoboticsProfessor

>>The robot makes two passes over the maze; it uses the first pass to develop a map of the best possible route, and the second pass to quickly navigate along the stored shortest route.

Thanks. I'll do this.

>>Some more detail on implementation would be nice. How exactly do you store the path? Do you use something like a stack, queue, or graph?

Thats the next part of the article. What it will say is...

The storage is an array. In BS2, I use 4 bit nibbles because of the limited memory. In 3PI a byte is OK. At each turn, a single character is stored:

R = Right turn

L = Left turn

S = Straight

B = Back or U-turn

Any time a "B" is stored that means a wrong turn was made. So at the next intersection, record the turn, then unwind. By unwind, I mean replace the three bad letters with the correct turn.

LBL means the robot took a left, had to turn around and then took a left at the same intersection. So, the first time, the robot needed to actually take a right. So the rule is "Examine the last three bytes. If "B" is the next to last character then replace the last three with the correct turn. So...

Replace LBL with R

Replace SBL with R

Replace SBL with R

and so on...

·

>>Also, how well does the algorithm that you've developed translate to a different maze? Is the robot's average speed lower, higher, the same? Does it expose deficiencies in your procedure?

I've tried·successfully on three different mazes (two ways each, starting at the start and at the end, so six total) and it works fine.

With BOE-Bot, it's speed it too slow to matter. I'm always travelling at top speed. 3PI is a whole different problem. The trick is to speed up to just before control is lost.

>>If this is intended as a formal introduction (along the lines of a paper), the some circuit diagrams, charts, and graphs would be good too.

I'm thinking a BOE-Bot supplement and a 3PI supplement so that I can address the specifics of each bot.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Richard Vannoy

Programming and Electronics Instructor
www.RichardVannoy.info
·

RoboticsProfessor

Thanks for the comments. What I'm seeing is I started out with an article and if I keep going, it will eventually become a book! (grin) But that's OK. As a teacher, I have as much fun writing the documentation as I do making the robot work.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Richard Vannoy

Programming and Electronics Instructor
www.RichardVannoy.info
·

SRLM

Do you have a different link? I had to drop out of Chrome open up IE (ugh!) to view the file. Even so, it was pretty large and took a long time to open. Perhaps break it into two or three parts (preferably not a .mht)?

Okay, you call a dead end 'intersection' but not a corner (slide 21)? How does a dead end qualify as "Intersection: A point in the maze where the robot has more than one choice of directions to proceed."

Nitpicking, but I think some of the capital 'shouts' are distracting.

Overall, a very good presentation. I'd still like to see a solution for loops in the maze, but as it stands I think it's pretty informative.

On a side note, I went to a mm competition a few weeks ago, and thought some about the problem. Eventually, you'll get to a speed where it's not just raw distance that matters, but speed too. So, you'll want to find a path with the fewest turns, and so you can burn it out on the resultant straight aways. If you want your mazes to be similar to the IEEE version, you'll have to allow loops and 'center finding'. I haven't really been around long enough to be sure, but it appears that the IEEE mm competitions are more or less the 'standard' at the University level (at least U of California).

W9GFO

I pretty much agree with all that SRLM said. It was informative and thorough. I'd really like to see the flood/fill strategy explained with the same detail.

Why does your link have the extension .mht? I had to go to your homepage and follow the link to get to the ppt file. Powerpoint slideshows are about my least favorite way to get information. Would much prefer a pdf but that is just me.

Here's a working link www.richardvannoy.info/line-maze-algorithm.ppt

I hope you'll continue to write more about maze solving, there isn't a lot out there that I've found. I'm hoping to put together something to enter in the line maze and/or micromouse competition this fall at Robothon.

Rich H

RoboticsProfessor

I uploaded the .ppt, .mht and the .htm versions to see about size and loading times. I think I'll dump them all and go with .PDF.

Agree. By my definition, dead-end is not an intersection. I'll revise that.

So, far, to keep it simple for my students, I've avoided loops and center finding, but I'll check out iEEE and see what they do. I have more white mboards, so it would be an easy task to just make another maze and add one level of complexity.

SRLM said...
Do you have a different link? I had to drop out of Chrome open up IE (ugh!) to view the file. Even so, it was pretty large and took a long time to open. Perhaps break it into two or three parts (preferably not a .mht)?

Okay, you call a dead end 'intersection' but not a corner (slide 21)? How does a dead end qualify as "Intersection: A point in the maze where the robot has more than one choice of directions to proceed."

Nitpicking, but I think some of the capital 'shouts' are distracting.

Overall, a very good presentation. I'd still like to see a solution for loops in the maze, but as it stands I think it's pretty informative.

On a side note, I went to a mm competition a few weeks ago, and thought some about the problem. Eventually, you'll get to a speed where it's not just raw distance that matters, but speed too. So, you'll want to find a path with the fewest turns, and so you can burn it out on the resultant straight aways. If you want your mazes to be similar to the IEEE version, you'll have to allow loops and 'center finding'. I haven't really been around long enough to be sure, but it appears that the IEEE mm competitions are more or less the 'standard' at the University level (at least U of California).

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Richard Vannoy

Programming and Electronics Instructor
www.RichardVannoy.info
·

RoboticsProfessor

Most robots check the sensors 20-50 times a second, so I haven't seen this problem much. Our fastest robot, the 3PI, can miss a turn at full speed, though, so one student found success by measuring the length of the straightaway and going full speed until about 6 inches from the intersection, then slowing down.

"Right - Left 90 - left 90" with no other possibilities at each turn is treated as "not intersections" so are ignored by the program. Robot only has one way out so extra 90 degree turns can be ignored.

kwinn said...
Interesting, the line following maze looks to be much easier to set up than the physical maze made with 1x3 wood I entered years ago.

What happens if the robot is traveling fast enough to put all the sensors beyond the lines?

It looked like the two robots I saw were "left hand rule" followers. What happens to them if a line goes to the right, turns left 90, and turns left 90?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Richard Vannoy

Programming and Electronics Instructor
www.RichardVannoy.info
·

RoboticsProfessor

The data structure I use is a string with L, R, S or U stored for each possible turn. With a simple, no loop, maze, there is no need for more complicated storage.

On the maze shown on my web site, www.richardvannoy.info, a BOE-Bot takes about 3·minutes to traverse the maze.·The 3PI with the program from their website cannot successfully get through the maze, but with considerable tweaking of the code can get impressive speeds.·Last semester the top two competetors made the multi-turn, 27 foot course in 16 and·13 seconds. Mostly it was done by optimizing turns and by speeding up considerably on the straightaways.·I've attached a photo of the exact maze and the winning team.

SRLM said...
I spent some time working on an algorithm just now, and have a few more comments:

I think I saw that your maze algorithm is for mazes that are acyclic. This seems like a flaw: you're limiting the application to very specific circumstances.

I'm not quite sure what sort of data structure you're using, but I'd use a graph. It would work like follows:
1. Map and label each junction of 3 or 4 openings. (on the first run)
2. Create a graph with each junction as a node, then the cost to each node is the number of 'squares' from the adjacent nodes.
3. Use a single-source shortest path algorithm (like Dijkstra's) to figure out which route to take. That way, you get the guaranteed shortest path.

Despite any fancy programming tricks, it still seems like a hardware problem. Namely, how fast can you get the robot to turn and accelerate. I think that could use some significant discussion.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Richard Vannoy

Programming and Electronics Instructor
www.RichardVannoy.info

JohnB

It was a pleasure to read your ppt on building a maze algorithmn.
Thank you, for sharing it with us.
John

RoboticsProfessor

I've made some suggested corrections and as requested, changed my line maze article to .PDF format at:

http://www.richardvannoy.info/line-maze-algorithm.pdf

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Richard Vannoy

Programming and Electronics Instructor
www.RichardVannoy.info
·

NikosG

Hi Richard,

You have made a great job about line mazes!·I' ve already added your web pages·in my favorites.

I am working on wall mazes this period. I’ m trying to develop a new software that creates random mazes and also I’m trying to make it able to generate automatically code for the boe bot to solve the maze.

http://www.youtube.com/user/ngyt40

http://3lyk-patras.ach.sch.gr/nickpage.htm·

Nikos Giannakopoulos

RoboticsProfessor said...
I am developing a comprehensive article about how to solve a line maze. It includes the problem, photos, videos of fast maze solvers and details of the line maze algorithms. You can see it at:

www.richardvannoy.info/line-maze.php

I am choosing to use pseudocode so that hobyists can use it with BOE-Bot, 3PI or any other microcontroller/robot combination. Eventually, I will post BOE-Bot and 3PI source code.

I would appreciate any comments or suggestions that you may have that will help me make this the best line maze algorithm article it can be. Thank you.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔