### Author Topic: Covering a known space by an autonomous robot  (Read 944 times)

0 Members and 1 Guest are viewing this topic.

#### TheDevilnish

• Beginner
• Posts: 2
##### Covering a known space by an autonomous robot
« on: September 18, 2011, 02:10:25 AM »
Hi, i really need some help for the time being...I've got the floor plan of my house and using this info i wanna design a bot to clean my house in a systematic way ie not moving randomly. The problem is how will i save the map in the robots memory ??by the way i' m wanna use the longest path distance transform for coverage. I'm using a pic microcontroller no communication to pc will be used for processing everything needs to be done by the robot only. thx

#### mstacho

• Supreme Robot
• Posts: 376
##### Re: Covering a known space by an autonomous robot
« Reply #1 on: September 18, 2011, 06:40:16 AM »
Well, unless you can figure out a way to compress the data REALLY well (for example, in terms of straight line motor commands and turns, represented as an array, such as:

path = {10, PI/2, 1, PI/2, 10, PI/2, 1, PI/2, x}  where "x" is the number of times you repeat a given sequence (you can pad with zeros for smalller rooms etc).

However, this will make your code look horrifying (although a big enough PIC can probably store enough in its memory to do a back-and-forth sweep of every room in a reasonable sized house this way).

An alternative that I would prefer is to store everything in an SD card, and read it through the PIC (which, IIRC, just needs an SPI interface?  Anyone?)  This way you're not limited in memory unless you want to put in more than a few GB of points :-P

How do you intend to make up the map and then find the minimum distance?  In other words, how are you going to represent the path for the robot to follow?

MIKE
Current project: tactile sensing systems for multifingered robot hands

#### TheDevilnish

• Beginner
• Posts: 2
##### Re: Covering a known space by an autonomous robot
« Reply #2 on: September 18, 2011, 09:00:43 AM »
Thx Mike for ur response..Doing some research i can see that that we can cover the environment using a bousphoredon decomposition(sweeping back and forth), morse decomposition, longest distance transform etc... However we must represent the graph as a grid(occupancy grid) and how to do that i dnt know...I just need an algorithm to represent the graph then do a breadth first search etc..I understand the bfs but how to represent the map in terms of node and edges i dnt know and i really need help...thx

#### mstacho

• Supreme Robot
• Posts: 376
##### Re: Covering a known space by an autonomous robot
« Reply #3 on: September 18, 2011, 10:43:00 AM »
Well...welcome to one of the most fascinating problems in robotics :-P Properly representing space in a way that's efficient has been solved in a number of ways. Now, you're dealing with a PIC, so you have unique problems that limit what you can do (But I'll ignore those because it's easier :-P ).

Let's work on a single room, because the house is just a whole bunch of rooms.  The easiest (ha!) way to represent the house, then, is as a whole bunch of graphs (the rooms) that are connected at only one or two edges (the doors).

First, probably the simplest (but not nearly the most efficient) way of doing this is to represent every point you have to turn as a node in the graph.  Two nodes are linked by an edge if they are adjacent in terms of when you turn.  That is, if you turn at node A, then drive to node B, then turn again, this means that nodes A and B have an edge between them.  The cost associated with each edge is the distance you have to travel. (in theory, it's possible to optimize how far you go, but in your case, driving back and forth, the solution to that problem is just to visit the nodes in sequence, since you don't so much have a graph as a line :-P ).

But what happens if you want it to go around complex obstacles?  Well, then the easiest way is to divide space into a quad-tree (I'm assuming it's a floor, not a 3D robot :-P ).  Basically, take your space, and divide it into 4 equal sections.  Any of those four sections that have lots of obstacles in them get divided again into four.  And so on for however much resolution you want.  This way, the robot has an efficient way of representing empty space (since if one quadrant has no obstacles it's left alone, so one node on the tree contains like 50% of the area of the room), while you get to change how much resolution you want to deal with for obstacle-rich sections.  Each node, then, is a section of the room without any obstacles in it.

Going the quad-tree route makes your life harder to begin with, because you have to do the measuring yourself.  But then all you need is a cheap "TURN-MOVE-TURN" algorithm that makes the path online for the robot, given as input whichever node in the quad-tree you're in.

Since this is a forum post, it's sort of hard to go into more detail, but that's the general idea :-P The two options basically work like this: option 1 makes the robot think the least, since the spatial representation IS the path to follow.  But it's memory heavy.  Option 2 makes the robot think the most, since it has to recompute the path for each node, but it's memory lean on average (but in a cluttered room, not so much).

Any thoughts, anyone else?

MIKE

ps: this is tip of the iceberg stuff...it gets more sophisticated from here.
Current project: tactile sensing systems for multifingered robot hands