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.