Mapping robot

Projects General Guidance
1

I want to make a robot that drives around a room or a maze and maps out a 2d floor plan. My plan is essentially to put a high quality proximity sensor that is rotatable by a servo on a small robot. The proximity sensor (or maybe sensors, if I need an extra) will be the only sensor on the robot. The robot will scan the room, and attempt to autonomously get a good angle on all points of the wall. I think the best way to do this is have the robot detect spots on its "map" (which I am thinking will be a sort of 2d matrix plot) that are jagged and discontinuous, then drive around and try to get a better angle on those spots, which should smooth out the map. The robot will know where it is by comparing distances and angles from the proximity sensor and servo with its current map, and by very roughly estimating distance traveled using travel time. I would also like to get this robot to do its job quickly as I am hoping this, when finished, will be able to do more advanced things.

So, is this possible, and does anyone have any advice or ideas?

Also, can anyone suggest a proximity sensor? I suppose it needs to have decent range, be very accurate, and take measurements very quickly. I'm also open to using something instead of a sensor on a servo, but I don't know what else I could use.

Thanks!

2

I don't know how you'd represent your map, but if it's just a 2D grid of occupied/clear cells then you're going to need large amounts of data to get anything worth while. Are you planning to put it on an SD card, or something?

Calculating position by dead reckoning is not going to be very accurate and trying to use the previously-discovered map results to tell you where you are I think would actually be very hard to do effectively.

If any of the obstructions in the room/maze are moving/moveable, all bets are off.

3

PeterH:
I don't know how you'd represent your map, but if it's just a 2D grid of occupied/clear cells then you're going to need large amounts of data to get anything worth while. Are you planning to put it on an SD card, or something?

Calculating position by dead reckoning is not going to be very accurate and trying to use the previously-discovered map results to tell you where you are I think would actually be very hard to do effectively.

If any of the obstructions in the room/maze are moving/moveable, all bets are off.

I'm thinking a 2D matrix of booleans or integers. It wouldn't have to be very detailed. I'd say a point on the matrix could represent a 1cm x 1cm space, or maybe something different depending on how much area the robot needed to cover.

Yeah, I definitely think using the previously discovered map will be a challenge. But there are a few reasons I see for doing this. If I were to use encoders on the wheels, and those encoders got thrown off slightly, then the entire map would get messed up unless I added a feature equally complex. I can also attach two servo-sensor pairs to the robot, one used for getting map data and another used primarily for locating where the robot is. Whenever the robot is sure it knows where it is, it now has an extra sensor to use towards its main task. Using only proximity sensors is also probably more interesting and gives the robot more flexibility. For example if it is placed on an already known map it can determine where it is on the map.

4

I'm thinking a 2D matrix of booleans or integers

Or better still, bits.

5

If you use one bit per square cm (something is here; nothing is here), the 2000 bytes of memory allow you to map 16000 square cm.

You'll need some known starting point for the map, and you'll need to know exactly where the robot is relative to the map's coordinate system at all times. This is not a trivial thing to know. IR sensors and ultrasonic sensors don't have that great a resolution. Assuming no slippage of the wheels is not realistic, so encoders of some sort that don't slip (probably another unreasonable assumption) will be necessary.

6

If you are able to put a couple of beacons in the room, you bot would have some way to determine its position and orientation. The problem would be rather easier to solve if you can do that.

7

I was thinking of doing something where not all map data was stored in memory, only the map data that might need to be available for the robot. Like maybe all data that the robot has in sight, or even only points that are within 30 cm. Then just store the rest of the map on the flash.

And unfortunately this would have to be without beacons.

Right now I am leaning towards using two sensor-servo pairs, one for the front 180 degrees and one for the back 180 degrees. But there are other things I could do. Anyone have an idea as to what would be the most efficient setup?

Also, anyone have any ultrasonic sensor suggestions? It needs to be fast, accurate, and be able to measure up close. But not sure if it's even possible to get all that in one package.

8

What you are wanting to do is doable, but it is not a trivial problem to solve; in fact, it's not a problem that's been completely solved yet - so good luck with the project!

If you are serious about pursuing this to the fullest measure, though, I suggest you look into a couple of things.

The first, of course, is SLAM (Simultaneous Localization and Mapping):

That is what you are trying to do. It isn't simple, there's a ton of math involved - you need to understand linear algebra and probability, among other things. But there are tons of resources out there to help and help guide you, so do your research.

The other thing you may be interested in is the following self-paced course:

http://www.udacity.com/overview/Course/cs373/CourseRev/apr2012

It's Udacity's CS373 "Programming A Robotic Car" course, being taught by Professor Sebastian Thrun from Stanford; with a tagline of "Learn how to program all the major systems of a robotic car from the leader of Google and Stanford's autonomous driving teams", believe me, it's exactly what you are wanting. Then again, I am kinda biased; I am currently taking this course (on Unit 3 this week). It isn't easy, but it is fun!

Regarding ultrasonic sensor suggestions: One of the best ultrasonic sensors you can buy is the SensComp (http://www.senscomp.com/) 6500 series; it combines long distance with a fairly narrow beam-width. They aren't cheap though - at least buying them new. However, an almost identical sensor can be had for much less if you are willing to hack an old Polaroid camera (specifically the Sun 660 and Spectra models, but there are others). You can find these cameras in thrift stores and other similar outlets, for $5.00 or so.

Other possibilities would be sensors from MaxBotix (http://www.maxbotix.com/) and Hexamite (http://www.hexamite.com/)...

9

cr0sh:
What you are wanting to do is doable, but it is not a trivial problem to solve; in fact, it's not a problem that's been completely solved yet - so good luck with the project!

If you are serious about pursuing this to the fullest measure, though, I suggest you look into a couple of things.

The first, of course, is SLAM (Simultaneous Localization and Mapping):

Simultaneous localization and mapping - Wikipedia

That is what you are trying to do. It isn't simple, there's a ton of math involved - you need to understand linear algebra and probability, among other things. But there are tons of resources out there to help and help guide you, so do your research.

The other thing you may be interested in is the following self-paced course:

Learn the Latest Tech Skills; Advance Your Career | Udacity

It's Udacity's CS373 "Programming A Robotic Car" course, being taught by Professor Sebastian Thrun from Stanford; with a tagline of "Learn how to program all the major systems of a robotic car from the leader of Google and Stanford's autonomous driving teams", believe me, it's exactly what you are wanting. Then again, I am kinda biased; I am currently taking this course (on Unit 3 this week). It isn't easy, but it is fun!

Regarding ultrasonic sensor suggestions: One of the best ultrasonic sensors you can buy is the SensComp (http://www.senscomp.com/) 6500 series; it combines long distance with a fairly narrow beam-width. They aren't cheap though - at least buying them new. However, an almost identical sensor can be had for much less if you are willing to hack an old Polaroid camera (specifically the Sun 660 and Spectra models, but there are others). You can find these cameras in thrift stores and other similar outlets, for $5.00 or so.

Other possibilities would be sensors from MaxBotix (http://www.maxbotix.com/) and Hexamite (http://www.hexamite.com/)...

Thanks! I never realized how much academic interest this topic has. I'm going to watch the course, it seems fun.

So far the best option seems to be the maxbotix sensors, even though they aren't cheap. All the other ones aren't close range enough. I have also decided I am not going to use servos, and just keep the sensors stationary, as it simplifies everything a great deal. Maybe get 4 sensors and place them all facing to the sides or front of the robot, or maybe have an extra facing straight back.

I have also thought about using IR sensors. They seem to be cheaper, but larger and have less range. Are there any you would recommend, or should I focus on sonar?

10

sug15:
Thanks! I never realized how much academic interest this topic has. I'm going to watch the course, it seems fun.

There's been probably close to 50 years worth of research on the topic; plenty of stuff out there...

sug15:
So far the best option seems to be the maxbotix sensors, even though they aren't cheap. All the other ones aren't close range enough. I have also decided I am not

Well, you can only get measure so close with an ultrasonic sensor anyhow, due to reflection and cross-talk issues.

sug15:
going to use servos, and just keep the sensors stationary, as it simplifies everything a great deal. Maybe get 4 sensors and place them all facing to the sides or front of the robot, or maybe have an extra facing straight back.

If you look around at some of the older robots out there (check out Cybernetic Zoo, for instance: http://cyberneticzoo.com/), you'll notice that more than a few from the 1980's used the Polaroid sensors, and would typically use 8-16 or more; you fire them off sequentially, and wait until you get the return from one before moving on to the next. That can get expensive, though, but if you really want to do SLAM with ultrasonics, you need as much "resolution" as you can get (and you can only use so many before the "cones" overlap; then again, I've often wondered if you couldn't do some form of interferometry using ultrasonics - I'm sure that's been studied, too).

sug15:
I have also thought about using IR sensors. They seem to be cheaper, but larger and have less range. Are there any you would recommend, or should I focus on sonar?

Something to keep in mind with robotics, SLAM, etc: You can't rely on any one sensor; you need to take a range of readings from multiple sources, and integrate everything into a singular whole. In regards to them, the "standard" Sharp IR sensors are probably best; they come in a variety of "ranges", so you can pick the one that best suits your needs.

If you really wanted to get fancy, and money wasn't a huge issue, you could try to find a "broken/dead" Neato XV-11 on Ebay, then gut it for its built-in 2D LIDAR sensor (it's been hacked, so you can figure out how to use it fairly easily).

11

Thanks. That Neato sensor is amazing, but I haven't found a broken/old robot on ebay or anything yet, which is too bad. The sensor also may be too big for my needs, but maybe I can shrink it down by changing the spinning mechanism.