Hi, I need an algorithm suggestion for a school project...

This topic is 4830 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hi (Sorry for the double post in this forum, I just wasn't sure which page this message should go on... :) ) Anyway, I am looking for an algorithm for a robot I am building as a final project at school. I need the robot to be able to go through a maze (without an ending) from a beginning spot and enter each room it encounters on it's way... Rooms can be on the left or right side of the robot and can be told apart from corridor entrances. It should only enter each room once and should check all the rooms without missing any of them. It can turn around abd go back on it's tracks but only when really necessary (like where there is no where else to proceed - a dead end :) ). Now, I already know an algorithm to do what I need but, it uses some previous knowledge of the maze's turns and rooms whereabouts before even beginning to run in the maze. I am looking for an algorithm which will be able to run in any maze without having previous knowledge of how it's built. Thanks in advance for all of the help... :) I tried to think of such an algorithm but couldn't find any...

Share on other sites
First of all, we're really not supposed to do homework assignments, but I'm gonna hurry up and post before someone calls you out on it.

Second of all, take a stroll through the AI forums, you'll see a lot that might help you there, A* (A star) in peticular.

Goodluck.

Share on other sites
Have a search for SLAM (Simulataneous Localization and Mapping) algorithms, although they seem a little bit advanced for a school project (unless this is at university level). There's a lot you need to do if you don't have the map to begin with. Work on perfecting SLAM is still at the Ph.D. level though, so this is tricky stuff and mightn't work perfectly for your project. Also, have a look at particle systems and the Kalman filter.

I can probably give you some more specific help if you explain the problem to me in a bit more detail. What sort of sensors does your robot have to detect the maze? Are there some sort of cheats or tricks you can use to get an accurate map of the maze?

P.S. The universities that use British spelling (like mine) spell out SLAM as "Simulataneous Localisation and Mapping", so you might need to do two Google searches. I think the American spelling is more prevalent.

Share on other sites
If you always, turn left if you can, go straight if you can't turn left and can go straight and otherwise go right you will hit all rooms only once. Stupid but it works(on some mazes) lol.

Edit: I guess it depends on what you mean by a maze.

Share on other sites
Well, actually, you have described two different problems here:

1. Finding your way through a maze as you go (that is, you explore the maze). This cannot be solved under the conditions that you stated. Consider for instance the three situations below:

       A-D              A-\               A-----\        |                | |               |     |  -> --+-B         -> --+-B          -> --+-B-D |       | |              |                 |     |          C-/              C-D               C-----/

For a robot that just entered the maze, all these situations are identical. However, no matter what path (to A, B, or C) he chooses, there is a situation in which the move is fatal and prevents completion. (Choosing A is fatal in the first, because you get stuck if you go to D afterwards - no going again through A! - or can't access D anymore if you go back).

Therefore I don't think this is the problem you have to solve.

1b. If you also assume that each room only has one entrance, then the problem becomes solvable as long as you can tell if you've been someplace before (by having access to your coordinates, or to room/corridor numbers). And Depth-First search is your friend.

2. Given the preliminary knowledge of a maze, planning the optimal walk through that maze under said conditions. This problem is solvable (if only by testing all possible walks, which are in finite number), and from your original post I can guess you already solved it.

Share on other sites
Thanks for the help everyone.

I thought of solving it just like you said in 1b ToohrVyk. Like you thought, you can be sure that each room has only one entrance and you can try to save coordinates in memory. The problem is that I am using Assembly to program the robot with so it might be a bit hard and useless to implement for just a school's project :).
About the SLAM algorithm... I might look into that later, thank you Trapper Zoid.
Well, I have also thought of the "wall following" way to solve the problem but, just that algorithm by itself wouldn't solve my problem. Thanks anyway O_o :).
Thank you too ciroknight for directing me to a message that might help me solve the problem.

Anyway, in the end my friend (whom I am building the robot with) and I have decided to take the known structure method but, make an escape road that would let us easily change the structure in the robot's memory in case we had to change it in the last minute...

Thanks again everyone for all of your help :)

Share on other sites
You may try a simple fill algorithm. (recursive or backtracking)

1. 1
Rutin
49
2. 2
3. 3
4. 4
5. 5

• 10
• 28
• 20
• 9
• 20
• Forum Statistics

• Total Topics
633409
• Total Posts
3011722
• Who's Online (See full list)

There are no registered users currently online

×