[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]

Because mazes are completely random, so this is the solution!

[Guest]

I do agree this is the best solution so far, but I wouldn't go so far as to say this is "the" solution. I can not offer a better one. The probability is practically, as you say, 100%. So I guess I would say this solution is practical, if not practicable. As you say, we have to assume we are given "as much time as needed", in addition to a robot with a practically infintite power supply and never breaks down.

[Guest]

Yup. And since mazes confuse by really not being orderly, I'm not sure if there is, in fact, a way to program exactly what to do besides random. But if you come up with better answer, Post it!

[Guest]

How do people solve mazes? Go a direction, if it doesn't work, go back. Perhaps we could program it to do that? Wait no can't do memory....

[Guest]

Ok, this assumes that we're using a maze that only has one solution. Here is an example of a maze that my solution can't solve.

##########

#S#.........#

#..#..#F#..#

#..#..###..#

#.............#

##########

loop start if left side is empty turn left, then go forward, then return else if front side is a wall, then turn right, then return else move forward return

That should get you to the end eventually.

Is that useful?

Edited July 21, 2010 by Lailoken

[Guest]

oops too late to edit more, i didn't check out the spoiler part. It seems to have erased my carriage returns. Just add one after the word return anywhere you find it to make it ore readable.

[Guest]

Do that, except left, have it randomized between left and right.

[Guest]

You should check out this site: http://www.astrolog.org/labyrnth/algrithm.htm

Without making more assumptions about the maze or allowing more capability in the robot, I don't think there is any algorithm which would guarantee escape. The maze below is a good example of when wall-following wouldn't necessarily work, but any maze with loops can be susceptible to this problem. The "pledge" algorithm would work for even mazes with loops, provided the maze exit is on the outside of the maze and even then the robot has to keep some information about it's internal state. Given a completely dumb robot and no maze specifications, there really is no way to guarantee escape, but moving randomly as some have suggested will give close to 100% success as the number of moves approaches infinity.

█████████ █

█       █ █

█       █ █

█  █ █  █ █

█  █☺█  █ █

█  █ █  █ █

█       █ █

█         █

███████████

☺ = Robot

[Guest]

simple.

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

yes.

if you favor the right or left hand rule for 2D mazes then then answer for any maze that moves in more dimensions than 2 is that you have to keep track of a number of walls that is 1 less than the number of dimensions you are moving through. assuming it's cubicle in nature. If you are moving in a 3D maze then you could keep track of the right wall and the floor. if you turn left or right then it's like a 2D maze but if you move up or down then the walls you are watching would change to the left wall and the ceiling. In a 4D maze you'd have to keep track of 3 surfaces and so on and so forth. Building and programing a robot should be easier after figuring this out.

[Guest]

Assuming that you do not start within the maze but must traverse the maze from a start and a stop that are the only openings in maze walls you can use a touch sensor to always follow either the left or right wall. In this situation i believe you will always find the exit.

[Guest]

yes.

if you favor the right or left hand rule for 2D mazes then then answer for any maze that moves in more dimensions than 2 is that you have to keep track of a number of walls that is 1 less than the number of dimensions you are moving through. assuming it's cubicle in nature. If you are moving in a 3D maze then you could keep track of the right wall and the floor. if you turn left or right then it's like a 2D maze but if you move up or down then the walls you are watching would change to the left wall and the ceiling. In a 4D maze you'd have to keep track of 3 surfaces and so on and so forth. Building and programing a robot should be easier after figuring this out.

Wouldn't "keeping track" require memory?

[Guest]

Assuming that you do not start within the maze but must traverse the maze from a start and a stop that are the only openings in maze walls you can use a touch sensor to always follow either the left or right wall. In this situation i believe you will always find the exit.

See some of the example mazes posted. Doesn't always work.

[Guest]

See some of the example mazes posted. Doesn't always work.

It does work if you don't start within the maze but start outside the maze at an opening in the exterior wall and end at an opening in the exterior wall.

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

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

What about this one?