How To Get A Robot To Exit ANY Room It Has Explored

Sup Dudes! I'm just posting a question on a robotics project I'll be starting fairly soon. The project will be getting two robots to work together to find an object randomly placed in a room. The Arduino based robot will locate the object and message a Mindstorms robot over Bluetooth to pick it up. My problem is: How to get the 'bots out of the room again? I could place nodes around the room, but I want the robots to be able to navigate any room the enter without changing the room, and infra-red is used by the object to be collected by the robots so they can locate it and tell the difference between it and an obstacle, so would this muck up any other infra-red nodes?

The way I was thinking of achieving this would be to get the Arduino to drive in steps; i.e, instead of continuous forward until it sees an object, it goes forward in steps of about 100 - 200 milliseconds, and the same with turning. I could get the robot to save in the EEPROM whether it went forward, backward,left or right (1,2,3,4), and after the object has been collected the robot can count these backwards to exit the room.

I know this method isn't perfect, because of traction on different surfaces and the like, but it should get the robot close enough to the door that it can exit using sensor readings, right? Another problem I have is that I would have no idea as to how to setup a similar program in the Mindstorms graphical programming language/interface thingy. The way I was thinking of solving this was to send the saved path to Mindstorms so it could follow it too. (Problems could be made here by the difference in speeds and sizes between the 'bots...?) Would that work well enough to bring the robot close enough to the door to exit under sensor readings? I have never used EEPROM before, but I have made the common obstacle avoiding robot (Works pretty darn well too, to blow my own over- used trumpet! XD) so the hardware and driving isn't new to me. Would it be possible to save the path using a bunch of variables so that I don't have to use up the limited life of the EEPROM? I don't have any code yet, but if you ask I could write a small sketch of what I'm thinking of doing. Can anyone help me? Thanks! :)

Would going stupid brute force (Go to a wall, turn left, follow the wall. When it finds a break, it will go through it. Maze following behavior) instead of trying to be smart and memorize a route, be an approach?

It might, but there would be problems. The original plan was to have the robots draw a line on a plastic sheet on the floor to follow to get back out, but I scrappd this idea because it meant the room had to be prepped for the robits, i want them to just go into any room, even one full of obstacles, like my sitting room, it would be hard for the robot to detect and avoid certain pieces of furniture, making the robot unreliable, the point of this project is to show how adaptable co operative robots can be, like mine (hopefully ... :/ )Is there really no way I can do this?

GeekyD00d: Is there really no way I can do this?

It can be done - but probably only in a very limited way with an Arduino or a Mindstorms robot; it would be a challenge to try.

The overall method to do this is known as "SLAM" - Simultaneous Localization and Mapping. The core concept is fairly easy to understand; it's the implementation that can be very difficult:

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

Read that article over carefully, and make sure you check out the links (especially the "SLAM for Dummies" part); also do some research. Expect most of it to go over your head (unless you already have a lot of experience with probability mathematics and linear algebra).

The basic gist, though, is to imagine yourself as the robot - and you are blind. All you have are your hands, and someone has plopped you down in the middle of the room. How do you find your way around the room? How do you find the exit (assume an opening in the wall)?

Well - first you "take a measurement" - feel around with your hands - did they hit anything? Ok, in that direction lies something, so you know with a certain probability that you are near something.

Now - move in a random direction (keeping track of where you were and where you expect to be). Then feel around again. Maybe you moved closer to what you touched before, or maybe you moved further away? Whatever - feel around, and update the probabilities of "stuff" in that location.

Do this often enough - and you eventually will build up a "map" of things in a room, and know with a certain level of probability (never 100 percent, though!) where you are at in the room, where the walls are, where objects are, etc. Oh - and where there is a gap in the wall - ie, the door!

Once you have an idea where stuff is in your map, you can then use some form of route planning (such as A* or Wavefront - among many) to find your way from one point to the other (hopefully without running into anything).

Again - it's the implementation that's the hard part. On an Arduino (even a Mega), it would take some real work; I would simplify the map to a grid (a 2D array of bytes would be ok), and just fill in the grid with values to indicate probability something is there (0 = low probability, 255 = high probability). Keep track of how far you have travelled using wheel encoders (and how much you have turned). For the measurement sensor, use ultrasonic or even bump sensors. Size the grid coordinates to the size of the robot body (or larger, if that proves to take up too much memory). Because your "map" will already be a grid, running a route planner on it will be simplified.

Oh - and if you want to have a much better understanding of all of this (and again, you feel your math skills are adequate) - check out the Udacity CS373 course:

https://www.udacity.com/course/cs373

Good luck - hope this gives you some ideas, if nothing else!

If the robot enters the room through the door could it be programmed to memorize its course so it can retrace its route?

A complex improvement would be to program it to return by a shorter route by ignoring minor twists and turns needed to locate the target.

...R

You could put a very loud air-horn on the robot that is triggered when the room is fully explored, at which point your mother/wife/other domestic authority will enter, pick it up and put it in your bedroom/workshop/garage/compost bin. :D

First off, thanks for the quick replies guys!

cr0sh, I have heard of SLAM before, but I think it’d be a bit beyond me at this point, plus I think I read somewhere that the UNO doesn’t have the power to do something like that, and I don’t want to buy another board, so that isn’t really gonna work to well. As regards to the Mindstorms, the two robots would work like this: The two 'bots would start at the door of the room. The Arduino one would drive into the room, avoiding obstacles, saving the path it takes, and looking for an object that emits infra-red light (the target). It then sends the Mindstorms robot the path it took over Bluetooth to bring the Mindstorms close enough to the object that it can find it and pick it up. Once the Mindstorms 'bot has picked up the object, it messages the Arduino which then follows its saved path back out of the room. Once its out of the room, it sends its path to the Mindstorms again. Robin2, that’s exactly what I want to do.

This is the kind of code I was thinking of using, this is adapted from my mobile obstacle avoiding robot.

#include <Servo.h>
#include <EEPROM.h>

Servo steer;
const int trigPin = 7;
const int echoPin = 10;
long int duration, distanceCm, cm;
int limitCm = 30;
const int dir = 12;
Number = 0

void setup(){
  pinMode(dir,OUTPUT);
  pinMode(echoPin, INPUT); // the input from my ultrasonic sensor
  pinMode(trigPin, OUTPUT);//the pulse output for my ultrasonic sensor
  pinMode(9,OUTPUT);
  steer.attach(4);
  steer.write(45);
  delay(7000); //delay to allow me to set up the bot before it starts up
  digitalWrite(9, LOW); //disengage the brakes
}

void loop(){
 analogWrite(3, 255); //full power 
 digitalWrite(dir, HIGH); //I'm using the motor shield, this means forward
  delay(150);
  digitalWrite(9, HIGH); //turn on the brakes
EEPROM.write(2, number);
number = number + 1 // this will stop me from continually saving in the same place, it keeps getting bigger
  digitalWrite(trigPin, LOW); 
  delayMicroseconds(2);
  digitalWrite(trigPin, HIGH); 
  delayMicroseconds(5);
  digitalWrite(trigPin, LOW);
  
  duration = pulseIn(echoPin, HIGH);
  
  cm = microsecondsToCentimeters(duration);
  
if(cm < limitCm && cm > 0){
 steer.write(55); //very small steering angle
 EEPROM.write (1, number) ;
number = number + 1;
delay(150);
 steer.write(45); //straight again
} 
delay(100);
}

long microsecondsToCentimeters(long microseconds)
{
  return microseconds / 29 / 2;
}

And for the part where it reads the saved path:

void loop(){
EEPROM.read(number)
number = number - 1 //this lowers the variable, bringing the read back down the saved path, reading it backwards
if(number = 1){ //if the saved number is equal to 1, (the number I used to indicate a right turn) then turn left.
steer.write(35); //turn left a tiny bit (the steering has to be reversed)
delay(150);
} else {
digitalWrite (dir, HIGH); //go forwards if the number is a 2
delay(150);
digitalWrite(9, HIGH);
}

That’s what I was thinkin’. It’s certainly less complicated to set up than SLAM… I hope. :confused:
I don’t know how to integrate the two of those, though. Could I set it up so that when the mindstorms tells the Arduino it has the object, the Arduino sets a variable to 1, and while the variable is a 1, it reads the EEPROM to get out? If I can help it, I don’t want to go down the SLAM route. Again, I don’t want to put nodes all over the room either, and use triangulation or anything, because the whole idea of this project is to show the versatility of co-operative and swarm robots, so I don’t want to change their running environment (currently my house) by putting in nodes. The only change will be the infra-red emitting target/goal that they have to bring out of the room.

I know I’m being a bit picky here, but room mapping is fairly complex and probably a bit beyond me at this stage, I haven’t made many Arduino sketches yet. (Well, that’s not strictly true, there is a LOT of them, but they are all for different versions of the same robot or debugging sketches)
Thanks for your advice anyway!

GeekyD00d.

I guess a small RPG to blow a hole in the nearest detected wall as an exit might be a little disruptive 8)

Just a little bit, CrossRoads... :) Though that might work to bust me out of prison if I get caught trying to get my robot to take over the world... Thanks for the idea! XD

GeekyD00d: Just a little bit, CrossRoads... :) Though that might work to bust me out of prison if I get caught trying to get my robot to take over the world... Thanks for the idea! XD

There's no fun in an RPG, go for a big drill! (Ocean 13 style :), nothing beats an earthquake machine.)

I haven't studied your code in detail but it looks like it is focusing on saving data in Eeprom and retrieving it. That's the easy part - though maybe you should use an SD card.

The complicated bit is what information to store and how to use it when retracing the route. For example is there any risk of wheel slippage which would make distances or turn angles doubtful. And is it possible to integrate the movement information to establish the location of the door relative to where the robot happens to be?

...R

Tricky!

You don't have to use the EEPROM to save the path data. If there's RAM available, save it to a string or array. Normally EEPROM is used to save data that you need across resets or power-cycles. Of course, if the path gets really complicated you might run out of space to store it.

The problem with the type of 'dead reckoning' navigation that you are using to retrace the paths is that it is terribly imprecise. If your wheels slip, or the floor is uneven or you run over an obstacle, it gets off course. Plus there is just a certain amount of error in encoders and gear trains. I'm not saying it can't be done, but you have to take the errors into account. To see how big those errors can get, have your bot map a path, and then do it in reverse. It won't end up exactly where it started. You can use the saved path as a general guide on which way to go, but be prepared to do some searching along the way.

One thing you can do, depending on how smart the mindstorms bot is, is to use the obstacles as part of the navigation. "Go forward until you hit something, then turn right." might be more accurate than trying to say "go forward exactly 29 inches, then turn 98 degress". That is if the obstacles don't move.

Sounds like a fun project.

Thanks again for the replies guys!

ckiick, I think you're right, I should use some RAM instead of EEPROM. How would I save the path to a string or array? How would the code work? I could just save numbers, and decode them into directions and stuff. Also, the navigating with objects sounds like a great idea, the only problem being, the robot isn't navigating the room randomly, it is going to be actively searching for an infra red emitting object, so it might end up avoiding the objects all together, and then this kind of navigation would be screwed up. I could make it steer in really small increments though, so that it can still measure its path, and at the same time be able to path towards anywhere in the room. You're also right about wheel slippage and stuff, but I'm hoping the robot will be close enough to the door by the end that it can navigate towards it under sensor readings. Hopefully. :/ So yeah, could someone give me an example of how to use a string or an array to save the path rather than EEPROM? I read the page in the reference section of Arduino.cc, and it only confused me... :astonished:

Thanks Everyone!

Ants lay down a chemical trail. Why not deposit an invisible chemical trail that is fluorescent under UV light? The robot has a UV light and follows the trail back. As long as the chemicals will not damage the floor surface it could work.

Prompted by the chemical trail idea this is a very wild idea …

If it’s possible to place an anchor (a heavy weight or anything that won’t move) just outside the door and if the robot unrolled a string attached to that anchor as it went along then when it is time to return it could wind up all the slack in the string and use the string as a line-following robot would follow a line?

No possible damage to the floor.

…R

Don't ants get into problems with circular death-marches, where a path gets over-reinforced?

Don't ants get into problems with circular death-marches, where a path gets over-reinforced?

That can happen if they go anti - clockwise.

Thanks for the replies!

radman, I think there could be problems from that, good idea, but if the robot is in the same room twice, the path will get muddled up. Also, it would be hard to find a chemical that's cheap, easy to clean and non harmful towards carpets, floors and generic house-going life forms... :/ And Robin2 (I notice you keep comin' back...Thanks!) The anchor idea would be hard to implement because the string could get caught around objects in the room, and then it'd be hard to follow it back out as well, because it would either have to be released from the robot to be followed as a line, or wound up at the same pace the robot is following it to keep it going on the right path. AWOL, I think you're right. I think that it would be more practical for it to remember its path in its program, than having to rely on lines etc. on the floor. Does anyone know how I could save the path to the RAM? In an array or a string or something? Could you give me some example code or point me in the right direction?

Thanks guys!

Reading and writing from an SD card would reduce restrictions on the amount of path data you could store. There is a library for doing this; http://arduino.cc/en/Reference/SD

Just remembering the path is a good idea, but you may need some kind of adjustment algorithm to compensate for slippage and movement inaccuracy.

new to robotics, so maybe I am off base here. But wouldn't it be possible to view the room as a grid? The robot doesn't have to map the room, just know where it is in relation to where it started. Assuming the robot isn't randomly moving around of course.

For example, lets assume the robot will either move 1 foot forward, rotate 90 degrees to the right, or 90 degrees to the left. At any point, those are the only 3 actions it can perform. Any other action is a combination of those 3 (for example, turning around is two actions of a 90 degree turn). Based on the action performed, we should be able to pay attention to the heading of the robot and how far it has moved from 0,0. If we have three variables, X, Y, and heading. We should be able to plot our current location and heading in reference to where we started. If we move two "steps" forward, turn 90 degrees to the left, move two steps forward, we would be at 2,-2 and facing away from door. If we want to get back to 0,0 we should be able to easily solve that issue, even if we don't take the same path back. We just need to know our last location and heading and calculate any new value for the next step. We don't need any more history than that. No matter how big the room is, the robot would not run out of memory storing its location because that information never gets any bigger. When placing the robot into the room, you could have a button to reset your 0,0 and heading values. It it can make 45 degree turns, it gets a bit more complicated because 1 unit forward at 45 degrees isn't a whole grid step. Instead of 12 inches it has to move approx 17 inches to get to the next grid value.