Maze-Navigating Robot

[andrew.]

Hey guys,

I need some hints regarding navigating a maze. Basically, for one of our labs, we must program a Lego Mindstorm robot to navigate a "maze" of black lines. The problem is not that we don't know how to make the robot follow the line, but we'd like some hints on what kind of algorithms we should use for this. It doesn't have to be optimized or fast; we were just thinking of taking every left path and counting the number of forks until we hit a wall, then we go to the last fork and go right, and keep doing that. However, we'd like something a little more robust than that, and we're kind of stuck. It would be nice if you guys could offer some opinions, ideas, or concepts.

Thanks a lot!

[Zren]

The mazy is a 2d grid with 90degree turns right? Just wanting to clarify.

Edit: and each "cell" of aprroximatily the same size.

[andrew.]

No, it's not only 90 degrees. The lines can be curvy or anything. But I just looked at the map, and it's mostly linear. Each fork on has two branches, and there's a grey area there so we can detect the fork. It looks similar to a tree where only two branches sprout from one branch.

[Sur_real]

Hmmm...I don't know how complex the maze is but can't you implement a DFS type of algorithm (like using stack)

[Zren]

There's no intersecting nodes right? As in two paths don't join up later.

[andrew.]

No, two paths never meet. Imagine a tree where it could only branch off to two at a time.

[Insectoid]

Are you using the standard Mindstorm software or something else (ie RobotC)?

I dunno how you'd do this with the Mindstorm software, but I'd keep a list of all forks the robot hit and the direction it took. Then have the robot take the left (or right, as long as it's consistent) path every time. If it hits the end of a branch but doesn't find the finish line, back up to the last fork. If you've only visited it once (ie the last direction was left), take the fork right. If you've visited it twice (ie last direction was right), back up the the previous node.

Note that you only should check the direction of a node when you're backing up. If you're moving forward it doesn't matter, 'cause you can only move forward to a node you've never been to.

Hey look, a fantastic real-life example of recursion. Right after I authored a thread about not enough examples of recursion.

[andrew.]

@insectoid: We're creating software services in C#. Basically, we subscribe to and handle events from the Mindstorm.

Also, that's what our group was going to do. I tried to describe it briefly in my first post. Is there a better way to do it though?

[Zren]

andrew. @ Thu Mar 03, 2011 9:19 pm wrote:

No, two paths never meet. Imagine a tree where it could only branch off to two at a time.

Ya, I figured as much. If they did, you would be forced to know your coordinated in worldspace, so as to know you've reached this point already. So long as the end is extenal (the outer wall), then you could eliminate all the nodes in the current node.

If you know either the general area of the exit, you could take your position in world space, and try to make a beeline for it using the smaller delta angle from the exit.
Fig A is if you don't know.
Fig B is if you do know.
These two are what you can assume when going into the maze.
C and D is just the logic of my suggestion.


If you don't know where the exit is, or have the ability to observe clues toward the edge of the maze (bounding box/area) in order to make a guess at where it is, then left hand rule is pretty much the only way I know of. The only suggestion is that if both you and the teacher knows this, and you know he'd also assume right hand rule as well. Uou could try to randomly choosing when meeting new nodes, keeping the stack of nodes you haven't visited, versus the nodes you still need to take.

[andrew.]

Okay, thanks for the help. We're probably going to end up going left all the way and keeping track of the nodes.