Tell me more ×
Electrical Engineering Stack Exchange is a question and answer site for electronics and electrical engineering professionals, students, and enthusiasts. It's 100% free, no registration required.
up vote 1 down vote favorite

I want to build a robot that will navigate over every spot it can in a room. But i thought some kind of a laser to map the room would be best or maybe a ultra sonic sensor. Could anyone guide me in a direction to learn how to do this or is there a better way to do this?

share|improve this question
@user: You give no reason why a random walk wouldn't work, despite the new requirement that this be a vacuum cleaner. Just saying so doesn't make it so. I think random walk would solve this problem quite well, and is certainly easier to implement and doesn't require fancy sensors or nanosecond timing. – Olin Lathrop Jun 10 '12 at 11:37
@Olin - user...whatever (doesn't he have a name?) is right. You may cover 50% of the room in 15 minutes, 90% in 2 hours, 98% in 10 hours, ... – stevenvh Jun 10 '12 at 11:42
@stevenvh: Right, and how does this violate any specs? Let it run whenever you're not there or don't mind it bumping around. Eventually it will get everywhere with a high enough confidence level. Compared to a human deliberately vaccuming once a week (and then possibly missing some spots, humans aren't perfect either), I think it would do a reasonable job. Sometimes dumb and simple works. – Olin Lathrop Jun 10 '12 at 12:06
@Olin - Hey, I've got nothing against the random walk, that's how I do it too. :-) But mine has "visual feedback" to clean up that last bit of lint, before my guests are comming. – stevenvh Jun 10 '12 at 12:10
Pure robotics questions were considered off topic a long time ago but since the robotics sights were stuck in arguments and failed to form it might be worth discussing on meta adding back robotics as a tag and a section of the site. We had never attracted robotics experts at the time we removed it and the robotics community felt everyone jumping in with over simplified electronics answers to serious robotics question(which was happening and quite discouraging to robotics users) was prohibitive to growing the community here. – Kortuk♦ Jun 11 '12 at 4:23

closed as off topic by Kellenjb, Kortuk♦ Jun 11 '12 at 4:21

Questions on Electrical Engineering Stack Exchange are expected to relate to electronics design within the scope defined in the FAQ. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about closed questions here.

1 Answer

up vote 1 down vote accepted

I would walk along the walls to get a contour. Roomba seems to measure reflection time of its IR sensors for this, though this requires high accuracy: a signal sent from 15cm from the wall returns in 1ns.

When you have the contours you can use a floodfill algorithm to walk the room. This will account for any obstacles or concave contour of the room.

A recursive floodfill isn't very difficult to write if you have a bitmap representation of the room: You call Floodfill(Pt), where Pt is for instance the topleft corner. Floodfill moves you there, and checks if you've been there. If you have, finish. Otherwise, set a flag that you've been at that location and recursively call Floodfill() for all 8 adjacent points. That's all.

If your first direction is east that will walk the robot east until it hits the wall, upon which it goes back and tries the second direction, e.g. south. There it tries east again, as its first direction, and so will walk again from the west wall to the east wall on the next row.

Notice that this is somewhat less efficient than an electronic floodfill, like used by GPUs, because when backtracking the robot has to physically move to its previous point.

share|improve this answer
thanks, thats a much better way to do it – user1361852 Jun 10 '12 at 11:31

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