Maze Solver

Hey, recently i saw this maze problem,

"build a bot to solve a maze with black walls & white floor in least amount of time"

I've seen many algorithms but the problem is not that, my problem is how do we detect those black walls? The floor is white.....

I suppose we cant use IR Sensors here....please suggest something....

the are loads of types of distance sensor, IR, ultrasonic, laser, pick one.

The maze will be illuminated, presumably, so ordinary light sensors should work.

thanxs for the replies everyone.... well i was thinking of something low cost, sharp or ultrasonics are gonna shoot up the budget.

And I guess I cant use IR for black walls....as black will absorb all IR, so no feedback whether there is something or not, it works only with white wall i guess...

anything else, specific?

See my previous post!

It doesn't matter if the maze is illuminated, in fact it probably would be better dark, less ambient light to throw off light sensor readings. You can't just stick a light sensor in a lit room and figure out if there are walls.

Hmm - you might actually think about approaching this problem as a machine vision problem.

If you have a white floor and black walls, it is a perfect high-contrast situation. You would need to image the path in front of you (so, in a 2D perspective, it would look like a "thin triangle") - paths left and right would appear as thin lines leading left and right. A T-junction would look like a T, etc...

Basically, with the right coding, you would be able to tell that a certain path might lead to a dead-end without having to run down the path; you could give a particular branch node point probabilities that the branch leads to a dead end. At such nodes, the robot would scan and look at all directions and give weights to the paths it hasn't visited (and keep track of ones it has or has passed).

I would think approaching it in this manner might give a faster solution to a random maze, rather than what would essentially be a "blind maze runner" with "bump sensors".

The issue then would be to find a means of interfacing a camera to the Arduino - not an easy task. I think for this I would look into interfacing either a CMUCam (or similar camera with on-board processing to reduce the data load to the Arduino), or maybe use a small, low-res camera device like that on an optical mouse. You don't need to store the image data, just start and end points for each scan line (after simple filtering for contrast and noise) to determine the floor layout...

:)