Let's Make Robots!

Universal recharge, navigation and mapping system

WARNING! this blog is just my thoughts on the subject and may be prone to rambling, monologs and contradictions.

I want to develop a universal navigation system for my robots. By universal I mean that the same code should work on almost any robot with only minor modification to allow for I/O pins used and number / type of sensors. This code is being written for the Arduino but I will document the code well enough that it can be easily adapted for other processors.

 

Theory Stage:

Think of your robot as a blind person. The range finder be it LIDAR, sonar or IR is like a white cane allowing you robot to detect an object without colliding. Most robots on LMR are at this point now but that's where they end. I want to go to the next level.

Once a blind person learns where things are in a room then he has a mental map and can plan his moves. Now that person navigates by dead reckoning and can move about more quickly. The white cane becomes a backup system that provides correction if they drift off coarse and a means of detecting changes such as a chair being moved to a different position.

This ability to map a room and navigate by dead reckoning is the "next level" I wish to develop. I think it is necessary if you want your robot to become useful in the home.

In the case of "Mr. Tidy" I want the robot to wander a room looking for cups / bottles o the floor. The robot should know where to take these things once it has found them and through experience, map of locations where empty cups and bottles are likely to be found so that it can find them more quickly in the future.

In the case of a "pet" robot then you might want it to run to the door and make a barking noise when it hears someone knocking on the door. You don't want the robot to take so long finding the door that the person knocking has already sat down and is having a cup of coffee.

As this will be a "dead reckoning" navigation system it will not rely on compass modules, GPS or any other complex (expensive) sensors. It will be self contained with no wireless links to PC's.

The only exception to the rule of "self contained" I have allowed is a simple/cheap docking station with a single IR LED that will plug into a power point. After all, if I take a robot to friends house or on a business trip then I still need to recharge the batteries.

The docking station will cosist of a panel with the IR LED in the center. A large brass plate on either side of the LED will provide a positive and negative terminal. The robot has two springs or antenna that make contact with the terminials to recharge the batteries. The docking station will become a reference point at the center of the robots map.

When the robot is taken to a new house or if the docking station is moved to a new room in the same house then the robot will soon realise that it is in a new location and begin making a new map. If the robot has enough memory then it may create several maps.

I will be testing this on 6 different robots.

  • Mr. General - 2x contiuous rotation servos - no encoders
  • Mr. Tidy - 2x DC motors - 2x simple encoders
  • Rover 5 with treads - 2x DC motors - 2x quadrature encoders
  • Rover 5 with mecanum wheels - 4x DC motor - 4x quadrature encoder
  • QuadBot chassis - 4x legs / 8x servos - no encoders
  • Chopsticks - 8x legs / 24x servos - no encoders

This covers a wide range of locomotion systems, some with encoders and some without. The maps will be stored in the Arduino's EEPROM or an SD card.

As some of the test robots I am using do not have encoders I was thinking that instead of mapping the rooms by distance I would try mapping the room by time taken to travel from one point to another at a given speed.

Robots that do have encoders can then measure their exact speed for more accurate navigation.

 


 

08-07-2011

Ro-Bot-X found a good link about mapping that describes my aproach better. I did not know the correct terminology as I had not read about it before.

My system is based on "Topological" mapping. Junctions and objects will in future be refered to as "Nodes". The X - Y co-ordinates of these nodes relative to the docking station will be measured in different units depending on the robots design.

Robots such as Mr. General that use continuous rotation servos for locomotion with no encoders will use units of time to measure the distance assuming a given speed.

Robots Such as Mr. Tidy and Rover 5 that use encoders can use time as a unit of measure as well with the encoders being used to precisely control the speed of the motors to reduce error. Alternatively they can measure the distance travelled based on the number of rotations of the wheels.

Robots that walk using legs such as QuadBot or Chopsticks can use their steps as a unit of measure. This is a method often used by blind people.

Lost or a new map?
When your robot cannot find things in expected locations it must determine is it lost, perhaps due to a mischeivous owner picking it up and turning it around or is it in a new location.  

NOTE: Doors must be differentiated in the map somehow otherwise the robot will think there are walls in funny places, decide it is in a new location and start re-mapping.

If the robot has just been turned around or just turned on then it will have no idea where it is. At this point it must wander using obstacle avoidance mode until it finds the docking station so it can orientate itself.

Let's assume I am using Mr. Tidy to move cups it finds randomly around the house to a specific location. If I just pick him up and turn him around then once he has relocated the docking station he will find all the nodes are where they should be (allowing for a small percentage of error) and he can continue as normal.

If I move his docking station or take him to a new house then even when he knows where the docking station is, few if any nodes in his memory will be where they are supposed to be. Depending how much memory you have then Mr. Tidy can either start a new map or rewrite the old map.

A way to teach your robot different areas of a house would be to use a TV remote. As the robot will use an IR receiver to locate and align with the docking station it can also recognise signals from a TV remote. When the robot is in a specific area press a button on the remote (for example use the numbers 0-9 to define 10 different rooms in the house. Upon receiving the signal the robot can store it's present location.

Lets say your programming your robot to go to the door and bark like a dog when it hears a knock at the door. You might use your TV remote to designate the front door as node 1 by pressing the number 1 button on the TV remote. After that, whenever the robot hears a knock on the door it could start barking like a dog and go to node 1 in it's map.

 


Planning stage:

 

Below is a very crude layout of my appartment as the robot would see it. Pale yellow objects are furniture without legs. Pale green circles are table legs and chair legs etc. Red lines are doors that could be open or closed at different times of day.

The light blue circle is the docking station. The orange circle represents an area where the robot is most likely to find cups and empty bottle to be collected. The green circle is where empty bottles should go for recycling. The purple circle is where empty cups can be taken. The pink circle is where socks should be taken.

The first thing I see is that my topological map really nees to have zones as well as nodes. A zone will basically be a room or an area within a room. In my map above I would want the robot to recognise the table and chair legs as a zone within the dining room to be avoided. Probably the best way to map a zone is as two nodes that represent diagonally opposite corners of a rectangular area.

 

1st step in mapping:
In this diagram you can see the path my robot would take when mapping the appartment for the first time using a typical "follow the right hand wall" search pattern. Each arrow represents a point where the robot had to change direction.

It should be noted that this process of gathering raw data by following a wall has the added advantage that it can be used for robot calibration. Most walls are pretty straight and most houses have the walls at right angles. As the robot tries to maintain a set distance from the wall the left/right motor speeds can be calibrated for traveling in a straight line and making 90 degree turns.

This first stage of mapping will not work with every home. If for an example there is a corridor surrounding a room or group of rooms then the robot will not find the surrounded group by following a wall. As this mapping idea will be self updating you could just wait until the robot stumbles across the missing rooms while traveling from A to B.

Another solution is for the robot to recognise unusually large empty areas as an area to cut through the middle of once it has finished following a wall.

There are about 64 of these points. In my case I am programming my robot to only go into large areas (at least the width of a small door frame). This prevents the robot getting into tight corners and forces the robot to group table and chair legs that are close together into a single object.

Initially I would have my robot store these points where it had to change direction as 3 byte nodes (9 bit X co-ordinate, 9 bit Y co-ordinate and 6 bits description). This would only take up 192 bytes of data. Unfortunately this "Raw" data is not very easy to work with. We need to process it to make a useful map.

At this point we should define what information is considered useful. The robot should know what room it is in where it needs to go and roughly how to get there. This does not require the dimensions and shape of the rooms. The robot needs to know what room it's in and what doors it needs to pass through to get to the required location.

As long as it knows roughly what direction to travel in then the robots standard obstacle advoidance routines should be able to handle minor problems like the family pet lying in the middle of the room.

A bigger obstacle will be finding a door closed. If the robot cannot find an alternative route then it must signal for assistance or wait patiently until the door is opened.

Other information that is necessary would be noteworthy objects or locations. In my map I've marked some locations where the robot should place objects it has picked up depending on the size, weight and colour of the object.

One location that the robot should be able to determine for itself is the location where it is most likely to find empty cups or bottles. This may vary from time to time so the robot may need to store multiple locations and even delete locations that have not been active for an extended period of time.

Creating a map from the raw data:
In the map below I have circled the doorways. These are crucial to the map. If you think of the rooms and objects as cities on a map then the doorways represent the highways linking these cities.

 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I want to write the code for the worst robot, the robot that has no encoders and does not drive straight. The rest can just use their addition sensors to do the job better.

All of the range finders can be used to keep the robot within a set distance from the wall, even my simple compound eye can do this as long as the wall is a uniform colour. In my map I am assuming a relatively short distance of 200mm (8 inches).

As most homes do have straight walls this means that the mapping process will be fairly accurate and can actually be used for calibrating left and right motor speeds, turning times etc.

The end result is that the mapping routine would also double as a calibration routine and any time the robot gets lost (perhaps as a result of poor calibration or flat batteries) the process of finding it's way back to the docking station would result in a quick tune up.

What will happen if the appartment (or region) to be mapped can't be mapped with the "follow right hand" rule?
I once was living in such an appartment some years ago.

Basile.

True there are situations where this search pattern will not work. In that case a fill pattern is one option but it would be very slow and time consuming. I will discuss a better solution in the next update.

A problem I have given some thought to as well. I have not yet come up with a solution, so I shall be watching eagerly for your solution to the mapping problem.

My robot, which I have now decided to name Schrödinger, has 512K of i²c add-on memory, so he has plenty of room for mapping. (Although I also thought I might eventually work on a visual recognition system which will eat memory, I do have room for more i²c memory, if I need it.)  Schrödinger's biggest problem is how to orient the map or orient himself to the map.  He could be in a slightly different spot or different orientation and not recognise any of his previously stored map.  Likewise, he may be in a totally new environment which may (or may not) eventually link up to his existing map. Consequently, I need to save the existing map and start building the new memory map in a different place in memory.

ADD: Of course he can move the map to elsewhere in memory easy enough by reading in a block and writing it out to another location, but the i²c access process takes too long when moving large quantities of memory here and there.

EDITED: He needs to be able to move blocks of memory, so he can rotate the existing map to different angles to try and match what he is seeing in his surroundings, or if he determines he is in a new place entirely, he should probably move the old map to a "safe storage" for later retrieval.  (Even if he does start in exactly the same spot, when he makes turns which are not exact angles, he may eventually not be able to match the map to his sensor readings. He needs to be able to use a "fuzzy logic" to say, "My readings are close to what the map says, so I must be right. I will just turn the map slightly to make it fit where I am." --or he might make an occasional turn that simply serves the purpose of reorienting himself to the stored memory map.) Due to the maths needed for the proper calculations in rotating the map or even just to make the comparisons, I may need a more advanced processor...  (I have a couple DS5000s laying around here as well as a 6800, 6502, 6509E, and others but they also need more complex board layouts and support chips that would make it too much like real work...)

Anyway, I look forward to your solution.

 

 

I think your missing the point Dan. If I used a conventional grid map then yes you would need lots of memory and shift blocks. As I mentioned previously, the docking station provides an initial point of reference including orientation. To save memory and allow for quicker processing I am trying a new approach to mapping where only objects and points of interest are memorized. The location and type of object/location is stored as 3 bytes of data. The idea is to stop thinking like a person who can see and start thinking like a robot that only has the equivalent of a white cane to find it's way around.

Yes, in this case I am designing a system based on the topological mapping aproach because it can use less memory and is better suited for mapping areas that are of different shapes.

Oh, no, I did not miss your point.  I was saying these were the way I was thinking of going with MY robot and that I am not pleased with my various choices.

I know there must be a simpler solution if I could wrap my mind around it. (--as the younger set says.)  That is why I said I would be watching your solution with great interest to see how you handled the mapping problem. --how this works out.  It does sound feasible.

 

 

Exactly that what makes a robot more independent, especially the auto-map mode in a new location.

Will see if i can help with ideas since I am also trying to keep the things easy and cheap ;-)

As this must work on a wide range of robots including start here bots the data to be stored (height, width, colour, etc) will be up to the user. The library will simply let you store whatever information is relevant at that location on the map. The timing error should not be an issue for robots with encoders. Robots with the ability to measure their battery voltage could do as you suggest. I was thinking of a system of self correction. If the robot reaches a junction earlier or later than expected by a small amount then adjust the map scale factor to compensate. If it is out by a large amount then the robot must go into an error checking mode where it must determine if an object has been moved or if the robot is in a new location. Battery charging is entirely up to the user. For a simple robot with no voltage monitoring ability then a simple timing system should work. The robot would time how long since it last recharged to guess when the battery is getting low. Another timer is used to determine a safe charge time.