Navigation Techniques

Sandgroper

Hi,

Can anyone point me in the right direction (no pun intended) on information relating to robotic navigation?· What I'm particularly interested in is the principles, techniques and tactics of navigation rather than the specifics.·

I'm building an indoor·domestic robot.· The task is simply to navigate from point A in one room to point B in another.· This is over level floors (no steps).· The environment has the usual challenges associated with domestic applications, e.g. open or closed doors, soft furnishings, skinny chair legs, restrictive spaces, object relocation, ambient IR, etc.

Currently I'm doing this with a mixture of wall following and ded. reckoning, with the occasional reference to·easily identified landmarks·as well as IR beacons.· The robot uses an array of four PINGs·for obstacle avoidance / acquisition, has skid steering,·optical encoders for ascertaining distances, an IR block for beacon detection, an RF block calling the robot, load detection, and low power detection.· No compass as yet, though I haven't ruled out the possibility of using one.· I understand that they can be affected by environmental variables, e.g. domestic appliances.· I also considered GPS, but I understand this isn't suitable for indoor use or high precision work.· The chip set is fairly basic - a BS2-e master chip for the PING, IR,·RF·and navigation routines,·a smaller slave chip for the motor commands, and an H Bridge for the motor control.·

The approach I'm using is to start the robot from a known origin, have it orientate itself to a local object,·and follow a wall in "right hand" or "left hand" mode until an event trigger occurs (e.g. achieving a certain distance or finding an open doorway).··It then switches to the next routine (i.e. "waypoint") and continues its journey.· After completing the set of waypoints it reaches its destination.· It then saves the·"destination" as the·"origin", ready for·the next·command set.· This reduces the errors inherent in ded. reckoning alone.

The robot·uses a variety of tactics to avoid or escape the inevitable navigation traps.· These include switching from open roam mode, left hand wall following, right hand following, reverse and pivot, wall acquisition, parallel or perpendicular orientation, etc.·

Beacon navigation is of limited use because of line-of-sight restrictions.· So too is use of barcodes, line following, etc.· More information on PID control would be great.·

If anyone has other ideas or information on practical methods of domestic navigation, I'd love to hear them!

W9GFO

Magnetic tape on the floor and a hall sensor? Or, something that I'd like to try is inserting small (1/8" dia) high power magnets under the carpeting every few inches to make a breadcrumb like trail. Although those two ideas are similar to line following.

There is also "celestial" navigation by way of a camera looking straight up at a constellation of IR beacons on the ceiling.

Rich H

Sandgroper

Good ideas, but the·robot has to be capable of operating in different houses without undue modification of its environment, and·it has to be able to handle a variety of different surfaces (e.g. concrete,·ceramic tiles, carpet, wood).··Sub-floor tracking systems aren't an option in this case.· Overhead beacons are a possibility, but there are problems with ambient IR,·access, recharging, and aesthetic appeal.· I'd only intended using the beacons·for locating a specific destination when there are no other significant landmarks.· This keeps the number of beacons required to an absolute minimum.
·

Prettybird

I am toying with something similar with my first mini monster boe bot. It grew to over 2 lbs. Sharp IR sensors set up as a simple on off (ajustable level using a LM339 comparitor) is great for fine tuning. Think they work better then the ping so far. Had to add a front bumper switch for table legs and stuff. It roamed 2 hrs without getting stuck. I am just a newbe with the programming and it still needs work. Reading posts in the forum, GPS is not very practicle, especially when not moving. When ready I may add the compas. Of coarse aa simple RC push button control is written in and works great when it does get stuck. Sometimes it get stuck in a loop. That is the software part. I suggest some kind of tank treads. Works sort of OK outdoors on concrete but the servos have no power to really climb anything. Learning by experience.

SRLM

One of the best sources for this sort of information are papers from acedemics. Just do a google search with your keywords ("indoor robot navigation") and the suffix ( "filetype: pdf") and you get a very helpful list. Repeat with other keywords. It also helps if you're an IEEE member or a student, so that you can get into IEEE xplore.

edit: put into code brackets due to the idiotic highlighting of : p as a smily face...
edit: more formatting...

Post Edited (SRLM) : 7/13/2009 5:23:39 AM GMT

Timmoore

As a followup to SRLM suggestion, search for papers by Johann Borenstein, he has done a lot of work on robot navigation.

Sandgroper

Thanks for all you replies - much appreciated.··I trawled the internet prior to·my initial post, but I couldn't find what I was looking for.· Most of the info concerned industrial applications or highly specialised areas.··(I'll go back and·check for the papers by Borenstein).·

I suppose what I'm really interested in are any of those "light bulb" moments where people have managed to solve navigation problems in ingenious, low tech, common sense ways.· You know, the type of techniques that people invent out of sheer necessity that aren't written in any standard texts.·

As an example, I have one program that allows the robot to detect the type of surface it's moving over by checking the rolling resistance.· When I ran it, I was surprised to see that it was so sensitive it would actually detect the nap of the carpet, as well as any hollow spots and slopes·in what otherwise appears to be·a level, tiled concrete floor.· That allows the robot to make asssumptions about its location and direction using nothing but a speed checking routine.· It's fairly basic and straightforward, yet I've never read anything about·using rolling resistance·as a navigation aid.·

Nor have I read anything about using a velocity check to distinguish between fixed objects (e.g. walls) and movable objects.· The same applies to techniques such as using speed sensing·or load sensing as an alternative to bumper switches and whiskers.·

There must be thousands of ideas like that out there somewhere!··

erco

Full Borenstein book PDF download at http://www-personal.umich.edu/~johannb/Papers/pos96rep.pdf . Looks to be very useful stuff. Thanks for the lead, Timmoore.

Sandgroper, sounds like you're well into the art of robot navigation. That rolling resistance program of yours sounds pretty impressive. I·put·some simple encoders on a Scribbler robot to go straight and make calibrated turns, but that's as far as I've gone. Please keep us advised on your progress, you have big goals and I'm sure Forum members will be interested to learn of your findings.

erco

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·"If you build it, they will come."

Sandgroper

Thanks Timmore and erco.· After looking at the link I remembered that I had actually read a lot of it some time ago!· It's certainly worth reading again.· And erco, I think you're right - robotic navigation is definitely an "art".

The rolling resistance program is far simpler than it sounds.· All I did was clock the average velocity over different surfaces for a given load at a set speed.· The idea was to use the variation in speed as one method of identifying the surface type and therefore the approximate location.· The surprise was finding that some surfaces had consistent variations in certain directions and / or locations.·

You can check for carpet nap with nothing more than encoders.· Run the robot forward for a set distance.· Then reverse straight back for the same distance.· If there is any nap in the carpet, the robot will either overshoot or undershoot the starting point.· I found it was possible to orientate the robot according to the direction of the nap.· The robot I used had front wheel drive / rear wheel steering.· I'm not sure how easy it would be·with skid steering.

erco

Nice work. I'm a huge fan of odometry & dead reckoning, my "big" robot project is using those pretty well. Accuracy and repeatability depend so much depends on specific chassis design. Differential drive will yield different results than a robot using 4-wheels (Ackerman steering) or a tricycle design. Also, whether you are putting encoders on your driven wheels (which can slip), or non-driven wheels. Wheel diameter, width, rubber, and·tread are more variables. Mechanical build quality (chassis flex, transmission efficiency & backlash, wheel concentricity &·trueness, etc) is critical to repeatability, yet usually overlooked. IMHO, being a good machinist/builder is at least as important as being a good electronics/software person. From my experience, all the processing power in the world can't compensate for chassis which is·fundamentally flawed chassis either through conceptual layout or final execution.

See http://www.seattlerobotics.org/encoder/200108/using_a_pid.html·for very useful info on using PID in a real-world robot in a contest setting.

Our own Forum guru PhiPi·wrote a thoroughly wonderful piece on using encoders in the BoE-Bot: http://www.parallax.com/dl/docs/prod/datast/ApplyEncoder.pdf

I have an older·CYE robot that set the standard for odometry accuracy in its day. No sensors at all except two motor encoders. A simple but high-accuracy diff-drive robot that would periodically square itself against a wall or corner to zero out accumulated errors. It came with some slick GUI software called "Map & Zap" that was well-done and·fun to use. Well worth a look to see the process: http://www.personalrobots.com/home.html·One guy pretty much did the whole project, I chatted with him on the phone years ago. Found him at that website, SMART tech guy. He·could be·a valuable resource for you.

Getting from A to B to C is definitely possible in a laboratory·setting. But the real-world variables (wheel slip and random obstacles that must be detoured around) assure that the whole-house navigation problem is not in danger of being solved easily or immediately!

erco

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·"If you build it, they will come."

Post Edited (erco) : 7/16/2009 9:39:25 PM GMT