51

I am hacking a vacuum cleaner robot to control it with a microcontroller (Arduino). I want to make it more efficient when cleaning a room. For now, it just go straight and turn when it hits something.

But I have trouble finding the best algorithm or method to use to know its position in the room. I am looking for an idea that stays cheap (less than $100) and not to complex (one that don't require a PhD thesis in computer vision). I can add some discrete markers in the room if necessary.

Right now, my robot has:

  • One webcam
  • Three proximity sensors (around 1 meter range)
  • Compass (no used for now)
  • Wi-Fi
  • Its speed can vary if the battery is full or nearly empty
  • A netbook Eee PC is embedded on the robot

Do you have any idea for doing this? Does any standard method exist for these kind of problems?

Note: if this question belongs on another website, please move it, I couldn't find a better place than Stack Overflow.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Matthieu Napoli
  • 48,448
  • 45
  • 173
  • 261
  • go straight and then turn sounds like a good approach; using a brownian motion is probably just different and perhaps not better. The ultimate solution is to make a map over the room with all items on floor exactly marked and then using a traveling salesman algorithm to move between markers. Think you need to define "better" ... just my 10c :-) – Fredrik Pihl Jun 29 '11 at 12:28
  • (Meta-commentary:) Going off of [Jeff's example here](http://programmers.stackexchange.com/questions/87611/simple-method-for-reliably-detecting-code-in-text) and subsequent justifications, I'm voting to move this to Programmers. – Cody Gray - on strike Jun 29 '11 at 12:31
  • Could you elaborate on the inefficiencies of your current algorithm? You ask for a way to make it "more efficient" but it would be helpful if you mentioned what areas could be improved. – tskuzzy Jun 29 '11 at 12:57
  • @tskuzzy Well it takes up a long time to clean every bit of the floor of the room (given it's random). Additionnaly, i'd love to be able to tell the robot to go to a specific position, but that's not the top priority. – Matthieu Napoli Jun 29 '11 at 15:00
  • Do you need to know its exact position in the room from the start, or do you just need to be able to track where it is (and where walls/obstacles are) relative to its start position? If the latter, couldn't you simply use dead reckoning, based on optical encoders on the wheels? – Nick Johnson Sep 07 '11 at 04:14

10 Answers10

38

The problem of figuring out a robot's position in its environment is called localization. Computer science researchers have been trying to solve this problem for many years, with limited success. One problem is that you need reasonably good sensory input to figure out where you are, and sensory input from webcams (i.e. computer vision) is far from a solved problem.

If that didn't scare you off: one of the approaches to localization that I find easiest to understand is particle filtering. The idea goes something like this:

  1. You keep track of a bunch of particles, each of which represents one possible location in the environment.
  2. Each particle also has an associated probability that tells you how confident you are that the particle really represents your true location in the environment.
  3. When you start off, all of these particles might be distributed uniformly throughout your environment and be given equal probabilities. Here the robot is gray and the particles are green. initial particle filter
  4. When your robot moves, you move each particle. You might also degrade each particle's probability to represent the uncertainty in how the motors actually move the robot. particles after movement
  5. When your robot observes something (e.g. a landmark seen with the webcam, a wifi signal, etc.) you can increase the probability of particles that agree with that observation. particles after observation
  6. You might also want to periodically replace the lowest-probability particles with new particles based on observations.
  7. To decide where the robot actually is, you can either use the particle with the highest probability, the highest-probability cluster, the weighted average of all particles, etc.

If you search around a bit, you'll find plenty of examples: e.g. a video of a robot using particle filtering to determine its location in a small room.

Particle filtering is nice because it's pretty easy to understand. That makes implementing and tweaking it a little less difficult. There are other similar techniques (like Kalman filters) that are arguably more theoretically sound but can be harder to get your head around.

Nate Kohl
  • 35,264
  • 10
  • 43
  • 55
  • +1 for being the only person to suggest an approach that would not get you laughed out of a room full of roboticists. However, OP said he could place markers around the room, if you can uniquely identify images (like QR codes) you would then have an absolute sensor and a particle filter would be overkill, especially considering the hardware limitations. – fairidox Jun 30 '11 at 05:13
  • +1 because of the competence shown and the care in the explanation. However I have doubts this approach can be implemented on an Arduino _efficiently_ (maybe on the Arduino Mega?). I bet an implementation of triangulating between known markers will be more efficient and bore better results. – mac Jul 08 '11 at 22:01
8

QR Code

A QR Code poster in each room would not only make an interesting Modern art piece, but would be relatively easy to spot with the camera!

Peaches491
  • 1,239
  • 15
  • 27
  • 1
    Yes, but this would only tell me in which room I am (or which wall I am facing). It wouldn't help me much for knowing the robot's position in that room. – Matthieu Napoli Jun 30 '11 at 07:29
  • 2
    You can get 3D position from the size and angle of the 2D image (OpenCV can handle that part for you). Put multiple QR codes around the room and handle positioning when one isn't fully in view by doing dead-reckoning since the last one was seen. – jhocking Jun 30 '11 at 11:46
  • 1
    You could also use ultrasonics to sense how far you are from one wall, then turn 90 deg then sense the next wall. That will get you (x, y) relative to one corner of the room – Peaches491 Jun 30 '11 at 15:34
6

If you can place some markers in the room, using the camera could be an option. If 2 known markers have an angular displacement (left to right) then the camera and the markers lie on a circle whose radius is related to the measured angle between the markers. I don't recall the formula right off, but the arc segment (on that circle) between the markers will be twice the angle you see. If you have the markers at known height and the camera is at a fixed angle of inclination, you can compute the distance to the markers. Either of these methods alone can nail down your position given enough markers. Using both will help do it with fewer markers.

Unfortunately, those methods are imperfect due to measurement errors. You get around this by using a Kalman estimator to incorporate multiple noisy measurements to arrive at a good position estimate - you can then feed in some dead reckoning information (which is also imperfect) to refine it further. This part is goes pretty deep into math, but I'd say it's a requirement to do a great job at what you're attempting. You can do OK without it, but if you want an optimal solution (in terms of best position estimate for given input) there is no better way. If you actually want a career in autonomous robotics, this will play large in your future. (

Once you can determine your position you can cover the room in any pattern you'd like. Keep using the bump sensor to help construct a map of obstacles and then you'll need to devise a way to scan incorporating the obstacles.

Not sure if you've got the math background yet, but here is the book: http://books.google.com/books/about/Applied_optimal_estimation.html?id=KlFrn8lpPP0C

phkahler
  • 5,687
  • 1
  • 23
  • 31
  • +1 for marker suggestion, it's really the best option. But that is a really scary book imo, you may want to check out: http://www.probabilistic-robotics.org/ – fairidox Jun 30 '11 at 05:01
  • Very interesting, but I'm not sure I understand fully. You mean if I detect 2 markers on an image of the camera, then I can compute my distance to them using the "on-picture distance" between the 2 markers (knowing the "physical distance" between the markers)? – Matthieu Napoli Jun 30 '11 at 07:36
  • @Matthieu: one way to think of it is that seeing a single marker gives you a distance to that marker, which places you somewhere on a circle around that marker. Seeing two markers gives you two circles that the robot should be on. Hopefully the intersection of those two circles should result in one or two points that the robot could be located at. For example, see pages 40 & 41 of http://www.cs.utexas.edu/users/AustinVilla/legged/2003/AustinVilla03.pdf – Nate Kohl Jun 30 '11 at 11:54
  • @Nate Ok I get it now, though I'm still not sure of how you compute the distance to a single marker: is it according to its size on the camera's picture? (even with the best calibration, is that accurate?) – Matthieu Napoli Jun 30 '11 at 12:51
  • 1
    @Matthieu: you're absolutely correct that distance to a single marker is noisy, especially when you get far away -- 1-pixel differences when you're far away can mean huge differences in position. Page 41 of that tech report I linked to above also describes how to do 3-marker localization, which doesn't use distances and is therefore a little more robust. (Basically, the angle between a pair of markers puts you on a circle, so with 3 markers you can get two circles and look at their intersection, similar to what I described above.) – Nate Kohl Jun 30 '11 at 13:31
  • @Nate thank you for explaining all that, this is really interesting. I was thinking though that in order to locate 3 markers (maybe even 2), you need either 2 webcam or you need to turn the robot around. – Matthieu Napoli Jun 30 '11 at 15:13
  • 1
    @Matthieu: that could work. Maybe every time the robot needs to get a fix on where it is, it spins in a 360 and gets a bunch of angles to markers around it. From those, it might be able to get a good one-time fix on its position. Combine that with dead-reckoning information from the motors, and you might have a good little localization system. – Nate Kohl Jun 30 '11 at 17:36
  • If a marker is a known height above the camera then its vertical position in the image (height above horizon) will be related to its distance. If 2 markers are separated by some angle (measured by horizontal position in image) they lie on a circle containing the camera, whose radius depends on that angle. – phkahler Jul 01 '11 at 19:51
5

This doesn't replace the accepted answer (which is great, thanks!) but I might recommend getting a Kinect and use that instead of your webcam, either through Microsoft's recently released official drivers or using the hacked drivers if your EeePC doesn't have Windows 7 (presumably it does not).

That way the positioning will be improved by the 3D vision. Observing landmarks will now tell you how far away the landmark is, and not just where in the visual field that landmark is located.

Regardless, the accepted answer doesn't really address how to pick out landmarks in the visual field, and simply assumes that you can. While the Kinect drivers may already have feature detection included (I'm not sure) you can also use OpenCV for detecting features in the image.

jhocking
  • 5,527
  • 1
  • 24
  • 38
3

One solution would be to use a strategy similar to "flood fill" (wikipedia). To get the controller to accurately perform sweeps, it needs a sense of distance. You can calibrate your bot using the proximity sensors: e.g. run motor for 1 sec = xx change in proximity. With that info, you can move your bot for an exact distance, and continue sweeping the room using flood fill.

odrm
  • 5,149
  • 1
  • 18
  • 13
3

Assuming you are not looking for a generalised solution, you may actually know the room's shape, size, potential obstacle locations, etc. When the bot exists the factory there is no info about its future operating environment, which kind of forces it to be inefficient from the outset. If that's you case, you can hardcode that info, and then use basic measurements (ie. rotary encoders on wheels + compass) to precisely figure out its location in the room/house. No need for wifi triangulation or crazy sensor setups in my opinion. At least for a start.

tmslnz
  • 1,801
  • 2
  • 15
  • 24
  • +1 for this, because I will indeed add rotary encoders to know my speed (this seems like a basic/cheap way of doing that). I'll try with the map of the room, even though indeed that's not really fun because your robot would not be very smart in an unknown environment. I will maybe try to build a map with the robots sensors. – Matthieu Napoli Jun 30 '11 at 07:28
  • Encoders are a good start, but they must integrate velocity measurements to find position. Due to wheel slippage and sensor error, a position estimate from encoders will quickly drift from ground truth. You should definitely use encoders for short term measurements, but you need an absolute measure of position to eliminate drift; e.g. using a camera to localize yourself w.r.t. known points whenever they are in view. – Michael Koval Jul 04 '11 at 00:54
1

I was thinking about this problem too. But I don't understand why you can't just triangulate? Have two or three beacons (e.g. IR LEDs of different frequencies) and a IR rotating sensor 'eye' on a servo. You could then get an almost constant fix on your position. I expect the accuracy would be in low cm range and it would be cheap. You can then map anything you bump into easily.

Maybe you could also use any interruption in the beacon beams to plot objects that are quite far from the robot too.

user1671687
  • 11
  • 2
  • How would you mesure the distance between the robot and each beacon? You need that for triangulation. And that solution implies to set up the beacons, and have them powered (connected to power). That's not very practical if you want your robot to be able to "work" all day long (i.e. not having to turn on/off the leds manually). – Matthieu Napoli May 22 '13 at 14:51
  • You always know the distance between the two or three beacons so all you need to do is measure the angle between them from your robot.. its the basis of navigation before GPS - how you would fix your position at sea from bearings to known landmarks on the land. You could use passive reflectors of some kind if you don't want to power them.. but they would only need very brief flashes and could run on batteries. – user1671687 May 23 '13 at 11:16
  • 1
    You don't need to know the distance from the robot to the beacon (d), that's what you solve the equation for, knowing the distance between the beacons (L) on the wiki example. Note you can get the coordinates this way too. If you used a laser and reflectors instead of beacons it could be ultra-accurate, only hindered by how accurately you can encode the servo turning the laser - obviously this is how modern surveying equipment works. – user1671687 May 23 '13 at 11:23
  • 1
    my bad! I mixed up with http://en.wikipedia.org/wiki/Trilateration :) which is was GPS actually uses http://en.wikipedia.org/wiki/Global_positioning_system#Basic_concept_of_GPS – Matthieu Napoli May 23 '13 at 13:54
  • Comment to the original answer then: not a bad idea, however I can think of some practical constraints: you need to have a rotating ir sensor/camera (not always easy/simple). And furthermore with a rotating camera, calculating the angle between 2 beacons may not be that simple (but maybe I'm wrong). – Matthieu Napoli May 23 '13 at 13:56
1

Use Ultra Sonic Sensor HC-SR04 or similar. As above told sense the walls distance from robot with sensors and room part with QR code.

When your are near to a wall turn 90 degree and move as width of your robot and again turn 90deg( i.e. 90 deg left turn) and again move your robot I think it will help :)

Ravinder Payal
  • 2,884
  • 31
  • 40
1

You have a camera you said ? Did you consider looking at the ceiling ? There is little chance that two rooms have identical dimensions, so you can identify in which room you are, position in the room can be computed from angular distance to the borders of the ceiling and direction can probably be extracted by the position of doors.

This will require some image processing but the vacuum cleaner moving slowly to be efficiently cleaning will have enough time to compute.

Good luck !

MAC
  • 419
  • 3
  • 9
1

Ever considered GPS? Every position on earth has a unique GPS coordinates - with resolution of 1 to 3 metres, and doing differential GPS you can go down to sub-10 cm range - more info here:

http://en.wikipedia.org/wiki/Global_Positioning_System

And Arduino does have lots of options of GPS-modules:

http://www.arduino.cc/playground/Tutorials/GPS

After you have collected all the key coordinates points of the house, you can then write the routine for the arduino to move the robot from point to point (as collected above) - assuming it will do all those obstacles avoidance stuff.

More information can be found here:

http://www.google.com/search?q=GPS+localization+robots&num=100

And inside the list I found this - specifically for your case: Arduino + GPS + localization:

http://www.youtube.com/watch?v=u7evnfTAVyM

Peter Teoh
  • 6,337
  • 4
  • 42
  • 58
  • As you said, resolution is 1 to 3 meters, can you extend on how you get a resolution around 10cm range? (and btw, the last link is a robot *not* using GPS, check the video title) Thanks – Matthieu Napoli Jul 01 '11 at 07:24
  • 2
    You will not get 10 cm precision without using a very expensive DGPS with very expensive corrections. The robot I worked with that had 10 cm accuracy used a $12,000 DGPS with $2500 / year differential corrections - completely infeasible for this type of project. And even if you did have the money, it would only work outside. – Michael Koval Jul 04 '11 at 00:51