1
$\begingroup$

I want to know if there is best algorithm and technique to implement self learning maze solving robot in 8 bit limited resource micro-controller? I was looking for some well optimized algorithm and/or technique. Maze can be of any type. Of-course first time it has to walk all the way and keep tracking obstacles it found.

I think best technique would be neural networks but is it possible to do this in such a short resources of 8bit? Any example online with similar kind of problem?

My wall detection is based on units, well, I have counted the wheel turns and it is almost 95% accurate in integers. For sensing the walls Ultrasonic range finding is used. Wheel can remeber its current position in let say, 3 feet staight, 2 feet right, etc.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Frankly, this question shows a remarkable lack of research. $\endgroup$
    – Josh Vander Hook
    Mar 14, 2013 at 0:45
  • $\begingroup$ The answers to this question will vary wildly based on the specifics of your problem. Are you in a well-defined grid space (all movements are integer units), or a physical space (movements in decimal units)? What is your method of sensing the walls, and how accurate is it? How will your vehicle determine its position? Do your vehicle's attempted movements result in success 100% of the time? $\endgroup$
    – Ian
    Mar 14, 2013 at 19:18
  • $\begingroup$ Welcome to Robotics Abdul, as on all Stack Exchange sites, questions work better if you ask practical, answerable questions based on actual problems that you face. If you could tell us more about what your robot currently does, why you are limited to an 8 bit micro-controller and what algorithms you have tried before, we may be able to help more. My suspicion is that trying to do this with a neural net would be interesting. $\endgroup$
    – Mark Booth
    Mar 15, 2013 at 19:38
  • $\begingroup$ Also, it is better to add information requested in comments by editing your question, that way the comments can be tidied up (deleted) and stop distracting people from the question. $\endgroup$
    – Mark Booth
    Mar 15, 2013 at 19:41

4 Answers 4

Reset to default
5
$\begingroup$

Perhaps the best way to get started on this kind of problem is to take relevant coursework(either online or in real life) or to read an introductory book on this topic.

A good introductory book on motion planning and SLAM is Principles of Robotic Motion.

A good course on SLAM/Mobile Robots: Control of Mobile Robots

Improve this answer
$\endgroup$
4
$\begingroup$

My understanding of your problem is that you would like to discover and navigate a 2D maze of irregular obstacles with a non-holonomic robot using a single forward-looking ultrasonic range sensor and wheel odometry. This is a hard problem.

"Best" solution

Although a "best" or "optimal" solution to this problem possibly could be implemented on an 8-bit microcontroller, it is made up of 3 problems -- each nontrivial and frequently left to full-fledged computing systems:

  1. Enhancing your ultrasonic sensor to be able to differentiate between walls and corners, because echoes from a maze-like environment can confuse your sensor.
  2. Exploring and mapping the space, typically done with a SLAM algorithm. (This will assume that you get near-perfect localization information from your odometry approach to navigation.)
  3. Using your map, compute a solution using a maze-solving algorithm

Achievable Solutions

Since the "best" solution is a tall order for an 8-bit microcontroller, focus on a "dumb" solution that actually works: use whisker sensors and the right-hand rule.enter image description here

Going further, you could add a compass/accelerometer for navigation, use infrared sensors to detect obstacles, and use a regular 2D grid with large gird squares. That would be similar to the Micromouse competition (for example, this one), which also uses microcontrollers for maze solving. Micromouse competition Micromouse robot

Improve this answer
$\endgroup$
3
$\begingroup$

You might want to have a look at my maze solving robot solution (http://www.benaxelrod.com/robots/maze/index.html). I used a Lego RCX which is more powerful than an 8bit microcontroller, but is still pretty resource constrained. I abstracted away most of the hardware problems to focus on the algorithm. It uses a flood-fill or A* type algorithm.

Improve this answer
$\endgroup$
1
1
$\begingroup$

Neural networks are not the best by a loooong shot. Neural networks are not AI, they are a way to do regression and classification. If you don't know what those things are, then you have no business working with Neural Networks.

What you have described is a mapping problem. You need two things from a good algorithm in this case:

  1. Coverage. You need to ensure that the robot can reach every part of the maze. If it cannot, then it might not find the exit / entrance.

  2. Mapping. You need to ensure that you can keep track of all the obstacles.

Without more information about the type of maze, type of robot, and type of obstacles, I'm afraid this problem is under-determined.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.