Building a robot(UPDATED)

[thermalpaste]

I have a project coming up in a few months time and this is what I have to build.......




"In this contest the contestant or team of contestants design and build small self-contained robots (micromice) to negotiate a maze in the shortest possible time.

Micromouse is an autonomous vehicle designed to get to the centre of a maze in the shortest possible time. A micromouse is a device with a chassis; a drive motor or motors to move it; a steering and turning method, sensors to detect the presence or absence of maze walls; sensors or control logic to oversee the action of the rest and keep the vehicle 'on track' or to solve the maze; batteries to provide power. "


DOES ANYBODY HAVE USEFUL LINKS/IDEAS ABOUT IMAGE capturing a maze into the memory of the microcontroller and then solving the maze using the captured image? Which microcontroller to use? I have used Atmel AT89S52, so is there any other microcontroller that is as easy to use as the ATmel and yet very powerful. (please do not suggest me an intel pxa255, its a waste of money and besides intel has priced it like a wh()re.).

 

[Lynx516]

What are the rules?

Maze finding algorithm depends massivly on what the rules are.

proximity sensors , IR prox sensors are pretty good unless you want to do something realy clever which I would not advise.

On the Micro controller it depends on how far you want to go. I would recomend an AVR (made by atmel) if you need more power than that (serioulsy doubt so) I would use a Motorola 68k variant

 

[rgwalt]

I don't know how much money you have available, or how big/small the maze will be, but Lego Mindstorms wouldn't be a bad option for the microcontroller. They may have some suggestions of what to use for a proximity sensor (you may want 4 sensors, one on each side of the vehicle). As far as maze solving algorithms, I suggest Google. Good luck!

R

 

[Matthias99]

Originally posted by: rgwalt
I don't know how much money you have available, or how big/small the maze will be, but Lego Mindstorms wouldn't be a bad option for the microcontroller. They may have some suggestions of what to use for a proximity sensor (you may want 4 sensors, one on each side of the vehicle). As far as maze solving algorithms, I suggest Google. Good luck!

R

I second this. These things rock, programming them is easy, and it's very easy to build and modify different designs. The weak point is the drivetrains, though; LEGO Technic gears slip too much for really accurate steering and distance measurements, although feedback-based mechanisms work pretty well. They make both IR and pressure sensors that you can use for checking for walls, etc.

The simplest maze-solving algorithm I know of is the 'left-wall' (or 'right-wall', I guess ) algorithm -- just follow one wall until you reach the exit. Your worst-case solution time *blows*, but it doesn't require any memory, and very little processing power. It has the advantage of being extremely robust, however. Beyond that things get more complicated, and I suggest doing some research.

 

[Sahakiel]

I sure hope this isn't your homework cause I do know the local college here offers this as a year-round course.

 

[TuxDave]

Originally posted by: Sahakiel
I sure hope this isn't your homework cause I do know the local college here offers this as a year-round course.

Which college do you go to? I know that there is a micromouse competition between universities and I also know that MIT decided to stop competing since they won too many times. Supposedly they shifted their focus of making micromice machines towards teaching others how to do it.

 

[Cattlegod]

A real easy maze solving algorithm is this - > stay on the right wall at all times. you only need a forward sensor and a right sensor.



If ( wall present in front and wall present on right) then turnleft()

else if ( wall present in front and wall !present on right) then turnright()

else moveforward()


that algorithm will solve any maze so long as the maze exit is not on an "island" in the middle of the maze ( i.e. not connected to any walls).

 

[rgwalt]

Originally posted by: Matthias99

Originally posted by: rgwalt
I don't know how much money you have available, or how big/small the maze will be, but Lego Mindstorms wouldn't be a bad option for the microcontroller. They may have some suggestions of what to use for a proximity sensor (you may want 4 sensors, one on each side of the vehicle). As far as maze solving algorithms, I suggest Google. Good luck!

R

I second this. These things rock, programming them is easy, and it's very easy to build and modify different designs. The weak point is the drivetrains, though; LEGO Technic gears slip too much for really accurate steering and distance measurements, although feedback-based mechanisms work pretty well. They make both IR and pressure sensors that you can use for checking for walls, etc.

The simplest maze-solving algorithm I know of is the 'left-wall' (or 'right-wall', I guess ) algorithm -- just follow one wall until you reach the exit. Your worst-case solution time *blows*, but it doesn't require any memory, and very little processing power. It has the advantage of being extremely robust, however. Beyond that things get more complicated, and I suggest doing some research.

I've used the mind storms set to set up a pH control system. For us, gear slippage was not a problem as we used a feedback system to tell the computer to turn off the motor when the gear was in the right position (based on a potentiometer reading) instead of turning of the motor after a certain rotational period. The mind storms systems are very easy to program. You simly write a program on your computer in a language called NQC (not quite C), compile it, and download it to the RCX microcontroller. One thing to be aware of is that the RCX is an integer processor only. It doesn't not do computations in floating point and will truncate all fractional math.

Ryan

 

[eigen]

The problem of the maze is that of finding a specific vertex in a random graph. I dont know off the top of my head but I will ask tommorrow what the best/worst case is and some heurisitics.

I just googled this and I cant find any results

 

[Sahakiel]

Originally posted by: TuxDave

Originally posted by: Sahakiel
I sure hope this isn't your homework cause I do know the local college here offers this as a year-round course.

Which college do you go to? I know that there is a micromouse competition between universities and I also know that MIT decided to stop competing since they won too many times. Supposedly they shifted their focus of making micromice machines towards teaching others how to do it.

I know UC Davis still does this every year. They also to a NatCar project, which has some similarities. I know Sac State does NatCar.

 

[thermalpaste]

THis competition is going to be held in I.I.T ( indian institute of Technology). They have sternly mentioned everywhere, that we cannot image capture the maze in the memory.
HERE'S THE LINK....

 

[thermalpaste]

Originally posted by: eigen
The problem of the maze is that of finding a specific vertex in a random graph. I dont know off the top of my head but I will ask tommorrow what the best/worst case is and some heurisitics.

I just googled this and I cant find any results

This is precisely one of things I was trying to google out. Besides We are not allowed to use mindstorm or any kit, we have to build it ground up..

 

[thermalpaste]

Originally posted by: Cattlegod
A real easy maze solving algorithm is this - > stay on the right wall at all times. you only need a forward sensor and a right sensor.



If ( wall present in front and wall present on right) then turnleft()

else if ( wall present in front and wall !present on right) then turnright()

else moveforward()


that algorithm will solve any maze so long as the maze exit is not on an "island" in the middle of the maze ( i.e. not connected to any walls).

Thanks a lot. I was thinking of using this algorithm, and I think I may stick to this one. Any other suggestions??

 

[thermalpaste]

Originally posted by: Lynx516
What are the rules?

Maze finding algorithm depends massivly on what the rules are.

proximity sensors , IR prox sensors are pretty good unless you want to do something realy clever which I would not advise.

On the Micro controller it depends on how far you want to go. I would recomend an AVR (made by atmel) if you need more power than that (serioulsy doubt so) I would use a Motorola 68k variant

I think I am going to use the Atmel AVR microconroller. I have used the Atmel AT89S52 umpteen times, and I Swear by Atmel. I shall also consider the 68K series, though I am not exactly familiar with the architecture of this particular microcontroller.

 

[TuxDave]

Originally posted by: thermalpaste

Originally posted by: Cattlegod
A real easy maze solving algorithm is this - > stay on the right wall at all times. you only need a forward sensor and a right sensor.



If ( wall present in front and wall present on right) then turnleft()

else if ( wall present in front and wall !present on right) then turnright()

else moveforward()


that algorithm will solve any maze so long as the maze exit is not on an "island" in the middle of the maze ( i.e. not connected to any walls).

Thanks a lot. I was thinking of using this algorithm, and I think I may stick to this one. Any other suggestions??

You better be careful using this algorithm. The last time I checked the 'exit' was an island in the middle of the maze. That may cause the 'follow the right wall' algorithm to fail.

 

[eigen]

I asked my thesis advisor today (she is a graph theorist) and explaind the situation and she plainly stated the without for knowledge of the maze the best solution is that of the brute force/stay to the right.

 

[blahblah99]

Originally posted by: eigen
I asked my thesis advisor today (she is a graph theorist) and explaind the situation and she plainly stated the without for knowledge of the maze the best solution is that of the brute force/stay to the right.

I wouldn't say its the BEST solution.. its one of the solution, but not the quickest, which is one of the criteria for this contest.

 

[eigen]

So whats your answer?
random walks are dangerous.
Whats a feasible algorithmn.

By best we mean feasbile and implementable.

 

[Shalmanese]

Not neccesarily, graph theory abstracts it too much. Theoretically, you should be able to keep track of your location inside the maze although it's a ah heck to do in practise. A simple heuristic would be to always to take the path that seems to be leading towards the middle. You can prune out a lot of your search tree in that manner.

 

[Sahakiel]

Remember the old adage: "The fastest way to compute is to precompute."
Don't move that mouse till you know exactly where it's going. Last I checked, there was no height limit.

 

[skene]

Originally posted by: thermalpaste
THis competition is going to be held in I.I.T ( indian institute of Technology). They have sternly mentioned everywhere, that we cannot image capture the maze in the memory.
HERE'S THE LINK....

I don't see anything in the link saying that you can not use image captureing of the maze. Since there is no height limit, what's stopping you from having a high camera analyzing the maze from the top? Well, other then the whole image processing algorithms you'd need to write and putting a powerful chip on there to use them that is. Since you've got 25x25 cm to work with, you could put a full out x86 chip on there. Take a look at VIA's mini-itx boards. You can get a decent one for <$150 and basicaly have a linux/windows PC controling the whole thing.

If I'm reading the maze specs right, there are no island in it so the wall following will get you there, but it will probably be quite slow. One thing you might want to look into is for autonomous mapping algorithms. In general terms, they store data of where they have been and try to explore unknown areas. I'm sure you can find one that can be tuned to try to move towards the center of the maze while exploring.

For sensors I'd say look at IR or ultrasonic sensors. Both are pretty cheap and pretty, easy to work with, and don't take much power.

Good luck on this.

 

[klocwerk]

honestly, I'd go with a brute force algorithm, and win it with hardware.
nice grippy little tires and a high torque motor on a well thought-out gearbox would probably win it.

 

[blahblah99]

The problem with this maze is that you have no idea what size the maze is going to be (or at least I don't), so any algorithm involving calculations of distance is not going to work unless you can pre-enter the dimensions beforehand, and have a way for your robot to measure distance traveled.

If you can precompute and allowed to mark your path, I'd go with Tremaux (spelling?) algorithm.


But if that isn't the case, then I'd go with klocwerk and focus more on hardware design than algorithm development. As for microcontroller, any low powered mcu with a C/C++ compiler and an onboard A/D would work.

 

[thermalpaste]

I am planning to use a pentium-II mobile cpu+mb. I was thinking of using a webcam for capturing the image of the maze. Any links? Any suggestions?