[Guest]

How can you program a robot to find his way out of a 2D maze WITHOUT using a memory? the maze has only horizantal and vertical walls and the lengths are in integer units (as in a wall can't be 2.34522345784 meters long, it can be 1m, 2m, 3m...etc)

The robot cannot record anything or modify anything or leave anything behind, though going back over paths you crossed is permitted...

Edited July 21, 2010 by Anza Power

[Guest]

simple.

use the left hand (or alternatively the right hand) rule.

basically the robot follows the left hand wall until it reaches the end of the maze.

now here's a real question. can it be generalized to multiple dimensions in any way?

[Guest]

Always get it to turn right when it meets a wall? Eventually it will escape.

[Guest]

now here's a real question. can it be generalized to multiple dimensions in any way?

Yes, depends how big the maze is. You could say randomize the turns, but heavily favour the left flat turn, but occasional instead of doing a flat turn do a vertical turn instead (just drive straight up the wall). So instead of truing just drive up the wall and start turning left again once you meet the next wall, repeat....There are probably more elegant solutions.

Edited July 21, 2010 by David31337

[Guest]

Ha this reminds me of my lego NXT camp. Heres what we would've done;

Just put a touch sensor and program it to go left every time.

You said two dimensional maze, meaning flat. We had a sensor in front of robot, and whenever it detected a certain color, you could've programmed it to turn left or right. Do something like that.

Funny story about my robocamp: the theme of all the missions was Terraforming, or preparing a planet for human habitation. We were supposed to deactivate this space station, made out of legos (Our robots were lego NXT) You deactivated space station by sliding out a brick from the space station. Most people made like a probe of sorts, almost a single long finger. My partner and I thought that was boring, so we took all the legos we had and built a giant hammer. We named robot Thor and hammer Mjolnir, and we had it smash the space station. That space station was DEFINITELY deactivated.

[Guest]

Oh wait 2D meaning u dont go up and down. I get it now! Saw that you said vertical/horizontal walls. Lets see, programming should involve the 1m, 2m, 3m thing I think.

[Guest]

If said robot is R2D2, then it just uses rocket jet things to go OVER the walls. Or sends out probes to scout out maze for it

Okay here's my real ansswer: Program it to go in a random direction every one meter. It should eventually find its way out of the maze.

[Guest]

I say

Program it like

:Loop

Move Forward 1m

// Attempt right turn

Turn 90 degrees right

IF can move forward 1m

THEN move forward 1m

ELSE turn 90 degrees left and move forward 1m.

Goto loop.

Or...

Activate Plasma Cutter

While not EndOfMaze; Move forward 1m.

then

Edited July 21, 2010 by mabus

[Guest]

The left(right) hand rule will not work all the time. If you start in the maze,as opposed to the edge, you might find the wall to your left(right) wall is an island and you can circle it all day and still be no closer to the exit

[Guest]

You guys think I got right answer?

[Guest]

I have a small issue with

random directions, but, sticking with one direction will always work. Even if you start in the center of the maze.. you will do assloads of backtracking, but will eventually get out.

However, I would make this change to my last "program"

Program it like

:Loop

// Check right

IF right is movable THEN turn 90 degrees right

// Check forward

ELSE IF can move forward, THEN move forward 1m

//Check left

ELSE IF left is movable, THEN turn 90 degrees left

/If all 3 conditions fail, pull a u-turn

ELSE turn 180 degrees right

Goto loop.

Edited July 21, 2010 by mabus

[Guest]

I have a small issue with

random directions, but, sticking with one direction will always work. Even if you start in the center of the maze.. you will do assloads of backtracking, but will eventually get out.

However, I would make this change to my last "program"

Program it like

:Loop

// Check right

IF right is movable THEN turn 90 degrees right

// Check forward

ELSE IF can move forward, THEN move forward 1m

//Check left

ELSE IF left is movable, THEN turn 90 degrees left

/If all 3 conditions fail, pull a u-turn

ELSE turn 180 degrees right

Goto loop.

One direction wouldnt always work. For examples:

_____________

|xxxxxxxxxxxxx

|xxxx|x|

|xxxx|x|

|xxxx|x|

|xxxx|S|

Turn left into that, u wont get out. left every m would end up u going into circle.

Had to put x's because spaces were gotten rid of. S represents start.

Edited July 21, 2010 by NickFleming

[Guest]

One direction wouldnt always work. For examples:

_____________

|xxxxxxxxxxxxx

|xxxx|x|

|xxxx|x|

|xxxx|x|

|xxxx|S|

Turn left into that, u wont get out. left every m would end up u going into circle.

Never get stuck!

This assumes spinning in place is okay,

but you have to give preference to one direction, but be flexible.

I wrote my stuff to

1 Try right, if that fails, then

2 Try forward, if that also fails,

3 Try left, if that also fails, the you are at a dead end, so

4 Turn around and start over

Edited July 21, 2010 by mabus

[Guest]

I was talking about when you said "Sticking with one direction will always work." In that case, it wouldn't. And each x represents space robot would take up, so then it would just keep going left, and go around in circles.

Edited July 21, 2010 by NickFleming

[Guest]

Never get stuck!

This assumes spinning in place is okay,

but you have to give preference to one direction, but be flexible.

I wrote my stuff to

1 Try right, if that fails, then

2 Try forward, if that also fails,

3 Try left, if that also fails, the you are at a dead end, so

4 Turn around and start over

That wouldn't work either, because first thing you do is always right. So you could get trapped in mirror image of thing I showed earlier.

[Guest]

The attached bitmap is a simple maze in which going left(right for mirror image) or forward is always possible but the robot will never get out.

maze.bmpmaze.bmp

[Guest]

The attached bitmap is a simple maze in which going left(right for mirror image) or forward is always possible but the robot will never get out.

maze.bmpmaze.bmp

Where's exit?

[Guest]

And why did I see people's avatars if I pressed next image?

[Guest]

If said robot is R2D2, then it just uses rocket jet things to go OVER the walls. Or sends out probes to scout out maze for it

Okay here's my real ansswer: Program it to go in a random direction every one meter. It should eventually find its way out of the maze.

Real answer on this one would still work.

[Guest]

You guys think I got right answer?

me likee

[Guest]

Can't explain the avatars. i only loaded 1 image. Which one is your "real answer"?

[Guest]

Random direction one. After the face.

[Guest]

With random direction, there is a high probability of success, but it is not a certainty.

[Quantum.Mechanic]

Random walk

[Guest]

With random direction, there is a high probability of success, but it is not a certainty.

I know, but, given as much time as needed, the probability would be so high it would be practically, word practically being used in proper sense, 100%, even with a very large maze. The probability of it not reaching the end after billions of years? Almost 0.

[Guest]

Random walk

See, thats what I said!