DPRG
DPRG List  



[DPRG] Spring Outdoor Contests #3 and #4: obstacle avoidance

Subject: [DPRG] Spring Outdoor Contests #3 and #4: obstacle avoidance
From: dpa dpa at io.isem.smu.edu
Date: Tue Feb 12 17:09:49 CST 2008

Howdy

The DPRG outdoor robot contest consists of 4 navigation
challenges, the first two of which were discussed in
previous posts.  The 3rd challenge adds obstacle avoidance
to the navigation tasks, and the 4th challenge moves robot
navigation and obstacle avoidance into the "real world."

Here's some thoughts on a simple obstacle avoidance behavior,
and how the 3rd and 4th challenges might be accomplished.

1.  Obstacle avoidance.

The term "obstacle avoidance" is a bit misleading in this
context because the robot is really reacting to sensor
detections, not obstacles.  An "obstacle" is a higher-level
abstraction that suggests that multiple sensor detections
can be grouped together as all belonging to the same
conceptual "object."  That is a difficult and philosophical
distinction and, fortunately, not one we need to make in
order to guarantee robust avoidance behavior.  But it's
useful to remember in this context that the robot has
a "concept" of sensor detections but not the higher-level
concept of the objects which those detections represent,
even though that seems so instinctively obvious to us humans.

2. Obstacle sensing hardware.

There are many different techniques for a robot to sense
obstacles.  For this example I'll use the IR light sensors
of the SR04 indoor robot, and the SONAR array of the jBot
outdoor robot.   In both cases the hardware is arranged to
give the robots two slightly overlapping lobes of detection
in front of the robot, left and right, and that is the key.

   a. IR

SR04 uses IR emitters/detectors to make two lobes of obstacle
detection directly ahead of the robot (ASCII ART requires
monospaced font to make sense):


                     _ - | - _
                   /     |     \
                  /      |      \
                  |  L   |  R   |
                  |      |      |
                  \      |      /
                   \     |     /
                    \    |    /
                    ===========
                    ||       ||
          L wheel  <||  SR04 ||>  R wheel
                    ||_______||
                      \_____/
                         |
                         V
                     tail wheel

                 SR04 robot, top view.

For SR04 the two lobes are formed with a pair of modulated
IR LEDs and a pair of IR detectors from Radio shack.  The
LEDs are aimed off-axis from the detectors to produce the
shape of the lobes.  

Here's a couple of pictures of the installation:
<http://www.geology.smu.edu/~dpa-www/robots/sr04/image49.jpg>
<http://www.geology.smu.edu/~dpa-www/robots/sr04/image46.jpg>

And here's a link to a Seattle Robotics article on IR:
<http://www.seattlerobotics.org/guide/infrared.html>

IR detection range for left (L) and right (R) lobes is slightly
wider than the robot, from the front bumper out to about
3 robot lengths, depending on the IR reflectivity of the
obstacle.

The lobe range is shaded so as not to overlap the edges of the
robot left and right, so that the robot can go through narrow
openings without generating detections.  

The sensors are also masked off so as not to detect reflections
from the floor.  These detectors can "see" out to about 18 inches,
which fits the small scale and low speed of the SR04 robot.

   b. SONAR

SR04 and jBot use SONAR for obstacle detection.  SR04 has a
stereo pair and jBot has an array of 4 SONAR detectors that
can also be used, among other things, to create the two lobes
of detection directly ahead of the robot.
      
Here is a cartoon of jBot showing the arrangement of sensors
and the truncated range of sonar detections used for obstacle
avoidance (ASCII ART monospaced font):


  |----------------- 60 degrees -----------|

  \         \         |         /         /
   \         \--------|--------/         / <--- 8 feet
     \        \   L1  |  R1   /        /
       \       \      |      /       /
         \      \     |     /      /
           \-----\    |    /-----/         <--- 2 feet
             \ L2 \   |   / R2 /
               \   \  |  /   /
                 \  \ | /  /
                ||\__\|/__/||
                ||         ||
                    jBot
                ||_________||
                ||         ||

                ||_________||
                ||         ||

            jBot robot, top view.

Each SONAR has a beam width of about 15 degrees and they are
mounted angled at 15 degree intervals, for a total frontal
coverage of 60 degrees. They are also angled upwards about
10 degrees, to minimize reflections from the ground.

Here are a couple of pictures of the installation:
<http://geology.heroy.smu.edu/~dpa-www/jpeg/sonar_01c.jpg>
<http://geology.heroy.smu.edu/~dpa-www/jpeg/sonar_02c.jpg>

The outer-most sonar (L2,R2) are mounted pointing out over
the front two wheels, just high enough so that the wheels
cannot be seen by the sonar beams when the suspension is
fully compressed.  The inner pair (L1,R1) are mounted 7.5
degrees off axis from the center line and tilted upward
10 degrees.  

Here is a picture showing the coverage:
<http://geology.heroy.smu.edu/~dpa-www/jpeg/sonar_03c.jpg>

The sonar are mounted on the radius of a 10 inch circle,
itself mounted 10 inches from the center of the robot.  Sonar
readings are offset by 10 inches so that all measurements
reference the center of the robot, same as the odometry or
position calculations.  This also means that the sonar are
mounted about 6 inches back from the front of the robot and,
consequently, can detect objects right up to the front
bumper.

The sonar sensors can see out to about 32 feet, and the array is
used for several different kinds of navigation.  For simple
obstacle avoidance the robot ignores all returns from the outer
two sonar (L2,R2) that are greater than about 2 feet, and all
returns from the center two sonar (L1,R1) that are greater than
about 8 feet, as illustrated above in the ASCII ART cartoon.

Here is a good tutorial on the SensComp sonar:
<http://www.acroname.com/robotics/info/articles/sonar/sonar.html>

   c.  Optical. 

There are a variety of methods for sensing obstacles using
optical means like laser range finders and video cameras using
parallax, stereo imaging, structured light, and so forth.  

These methods can be used in the same fashion as the IR and
SONAR examples above, by dividing the area directly in front
of the robot into left and right zones and testing for the
presence of "detections" within those zones.  Those detections
are then passed as inputs to the obstacle avoidance software.


3. The Avoidance algorithm

The avoidance algorithm for both robots is very similar, and
looks something like this:

    if (detection == LEFT)  slow to half speed and turn right.
    if (detection == RIGHT) slow to half speed and turn left.
    if (detection == BOTH)  slow to 0 and continue turning.

This algorithm works for a differentially steered platform with
zero turning radius.  Obstacles detected by one sensor or the
other cause the robot to slow and turn away.  Obstacles detected
by both sensors cause the robot to drive the speed toward 0 and
rotate away.  For Ackerman steered platforms, the robot needs to
monitor for that condition and perform it's Ackerman-specific
jack-knife turning maneuver at that point.  

Which way should the robot turn if an obstacle is seen by both
detectors?  There are several different common ways of dealing
with this situation, from random number generators to complex
histories of where the robot has been and where it is going.

A very effective technique in this situation is to continue
turning whatever way the robot is already turning.  

This is easily detected on an Ackerman steered robot, and on
a differentially steered robot one can just test which wheel
is going slower based on its current encoder counts.  

4.  The Avoidance behavior in 'C'

Here's the behavior for a differentially steered platform.
The inputs are the sonar readings L1, L2, R1, and R2.  The
outputs are obstacle_flag, obstacle_speed, and obstacle_turn
for the subsumption arbitrater.

void obstacle_avoid()
{
    int extern obstacle_flag, obstacle_speed, obstacle_turn;
    int detect = 0;

    // set sonar detect bits, 1 = left, 2 = right 3 = both
    if ((L2 < TWO_FEET) || (L1 < EIGHT_FEET)) detect = 1;
    if ((R2 < TWO_FEET) || (R1 < EIGHT_FEET)) detect |= 2;

    if (detect) {
        obstacle_flag = TRUE;

        if (detect == 1) {
                obstacle_speed = top_speed/2;
                obstacle_turn = OBSTACLE_TURN;
        } else
        if (detect == 2) {
                obstacle_speed = top_speed/2;
                obstacle_turn = -OBSTACLE_TURN;
        } else {
                obstacle_speed = 0;
                if (left_encoder > right_encoder)
                        obstacle_turn = -OBSTACLE_TURN;
                else    obstacle_turn = OBSTACLE_TURN;
        }
   } else {
           obstacle_flag = FALSE;
   }
}


Top_speed is a variable set by the user.  OBSTACLE_TURN
is a constant that the builder has tweaked to produce
smooth turns or jerky turns, whatever you prefer.

The obstacle_flag signals the arbitrater that this behavior
wants control of the robot at this time. For a more detailed
description of the subsumption arbitrater see the previous post.

5.  The subsumption loop

The previous post developed a control loop for a simple navigation
behavior.  We can now add the avoidance behavior to that loop

void subsumption()
{
    while (1) {
        cruise();
        navigate();
        waypoint();
        obstacle_avoid();
        arbitrate();

        tsleep(TDELAY);
}

and be capable of running DPRG Outdoor Challenge #3. 

The robot begins its run at the origin (0,0), pointed toward
the first target 100 feet away at (0,1200) using coordinates
in inches, with some obstacles (probably idle DPRG members)
in the way.

The navigate() behavior requests full speed straight ahead and
the robot's PID controller accelerates the robot toward the
target.

Note that in the "continuous message" form of subsumption that a
stream of commands is required from the navigate() behavior to the
motor control subsystem to change the motion of the platform.  A
single detection might cause a temporary blip but won't be able
to effect the robot's path substantially.  This acts as a noise
filter and also smooths the control response.

Somewhere along the way to the target the obstacle detection
sensors will see the obstacle and, depending on whether the left
detector or the right detector sees the obstacle first, it will
issue a command to turn the robot.  The obstacle_avoid() behavior
has higher priority than navigate() so the arbitrater passes it's
commands along to the motor control, and the robot begins to turn,
let us say left for this example.

Immediately the navigate() behavior begins to issue commands to
turn back to the right, toward the target.  But these commands are
ignored as long as the obstacle_avoid() behavior is still detecting
the obstacle(s) and "subsuming" the navigation behavior.  

At some point the robot has turned far enough to no longer see any
detections from the obstacle, and so sets it's behavior flag back
to FALSE.  At that point the arbitrater begins to pass navigate()
commands to the motor control, and the robot begins steering back
towards the target.  This pattern is repeated for each obstacle
encountered, with the navigate() behavior pulling the robot toward
the target waypoint and the obstacle_avoid() behavior pushing the
robot away from intervening obstacles.

6. Examples.

Here are some examples as mpeg videos that may make the above
behavior descriptions more obvious.  

    a.  IR avoidance behavior

First is SR04 running a 10 foot Borenstein UMBMark, with no
obstacles (6.2 Mb)

<http://www.geology.smu.edu/~dpa-www/robots/mpeg/sr04_outdoor_sq_001x.mpg>

Note that the robot decelerates as it approaches each waypoint, as
described in the previous post.  At each waypoint, it performs two
behaviors: it rings a little electronic bell, and it rotates to face
the next waypoint.  Using a quarter as a fiduciary reference, SR04
has about 15 inches of error on this run.

Now here is the SR04 robot running that same 10 foot square, this
time with obstacles in between some of the waypoints (7.6 Mb):

<http://www.geology.smu.edu/~dpa-www/robots/mpeg/sr04_sq_001x.mpg>

Note that this obstacle avoidance and navigation technique combined
can deal with both static and dynamic, i.e., moving, obstacles.

Finally, here is SR04 running a 24 foot out-and-back task, identical
to the DPRG Outdoor Challenge #1 100 foot task, in the attic of the
SMU Heroy building strewn with old furniture and equipment.

<http://www.geology.smu.edu/~dpa-www/robots/mpeg/sr04_ob3.mpg>

The SR04 robot has a pair of red LEDs mounted on the left and right
side of the robot just above the wheels.  These LEDS are turned on
when the obstacle avoidance behavior senses a detection.  By watching
these as the robot navigates through the attic, it is possible to
tell when the robot's turning is controlled by obstacle_avoid()
(LEDs on) and when it is controlled by the navigate() behavior,
(LEDs off).

    b. SONAR avoidance behavior

jBot uses it's SONAR array for several different tasks.  In addition
to obstacle avoidance it also uses the SONAR readings for wall
following and for escape maneuvers.  In the following videos those
behaviors are disabled, and the robot's control regime is very
similar to the SR04 robot examples above.

First here is jBot running a 20 foot version of challenge #1, out-and-
back, over broken ground.  The robot has a slight mod of the waypoint
navigation algorithm described previously in that it can reload the
waypoint list at the end of the run, in order to run the same sequence
repeatedly.  That what's happening here, as jBot drives back and forth
between two way points and tries to maintain it's location and
orientation.  Note that in this case the robot does not slow to a stop
or take other actions at the waypoints (5 Mb):

<http://www.geology.smu.edu/~dpa-www/robo/jbot/jbot_rough_01.mpg>

Here is the same out-and-back pattern repeatedly, this time for 100
feet as in the DPRG Outdoor Challenge #1 and #3, but with many
obstacles in between the two waypoints (12 Mb):

<http://www.geology.smu.edu/~dpa-www/robo/jbot/jbot_gardenx.mpg>

Here's a similar challenge in the Colorado Rockies, where the robot
navigates 500 feet through the forest and back (9.3 Mb):

<http://www.geology.smu.edu/~dpa-www/robo/jbot/jbot2/jbot_rock2a.mpg>

And in this final video, the robot navigates 500 feet through the
woods at Lake Dallas, avoiding trees and trashcans and picnic tables,
and returns within inches of the origin, all without GPS (21 Mb):

<http://www.geology.smu.edu/~dpa-www/robo/jbot/jbot_hatrick2_2.mpg>

7. Challenge #4

Challenge #4 is seek to a distant waypoint and back on the
grounds at FairPark.  At this stage the robots will probably
need some shepherding by human handlers to keep them out
of the ponds and away from delicate flower beds (jBot has
already transgressed in this particular area and it wasn't
a pretty sight.)  However, if the robots have good obstacle
avoidance behaviors, this is just a matter of chasing them
away from difficulties.  It's our assumption that as the
robots improve and advance they will require less and less
shepherding.  But it's allowed at this time, and even
encouraged.

A couple of other behaviors might also be required for
successful completion of challenge #4.  One is an escape()
behavior that can sense and respond appropriately when the
robot collides with an obstacle or becomes physically stuck,
high centered, etc.  This must be a high priority behavior.  

Another is a behavior that can monitor for and recover from
the concave "singularity" obstacle trap discussed in a
previous post.

jBot switches into a perimeter following mode using its
SONAR array looking out to about 20 feet, in order to deal
with large concave geometries.  That behavior has an
intermediate priority between the target seeking and obstacle
avoidance behaviors.  The whole thing might look like this:


void subsumption()
{
   while (1) {
       cruise();
       navigate();
       waypoint();
       perimeter_follow()
       obstacle_avoid();
       collision_recovery()
       arbitrate();

       msleep(DELAY);
   }
}


The navigate() target seeking behavior can be subsumed by perimeter
or wall-following behavior if it determines that the robot is
trapped in a concave space.  That behavior is in turn subsumed
by the obstacle avoidance if any obstacles are encountered, and
both are subsumed by the collision recovery behavior if it is
determined that the robot is physically stuck or has had a
collision.  More detail on these behaviors are available on
jBot's webpage.

8. Grand Adventuring

Once your robot is able to complete challenge #3 and #4, navigating
to a waypoint and back with obstacles in between, it's time to
turn it loose and see how it survives in the real world.  If the
out-and-back or Borenstein UMBMark sequences have been hard-coded
into the robot, you can set your robot down at any arbitrary
location and send it off adventuring.  This is where it really
gets to be interesting.  And fun.

I often find myself giving the robot purposefully difficult tasks,
like seeking a waypoint behind a big pile of old pipes and broken
concrete, just to see how well the robot can handle it.   The
world is your playground.

Another nifty little function allows jBot to mark the GPS location
of the car when I take the robot out to play.  Then at the end of
the day when I'm tired and the robot has become unaccountably
heavy, it can seek back to the car on its own, without me having
to carry it.  I only have to follow along behind.  It even finds
the car for me if I've forgotten where we parked.

Those builders interested in pursuing the Seattle Robotics Society
Robomagellan Contest at this point only need to add some means
 -- like a CMUCam -- of identifying and acquiring an orange
traffic cone when the robot arrives at the waypoints, and add
that behavior to the subsumption control loop.

In fact, some experiments I've run with jBot suggest that traffic
cones can be recognized by their shape with SONAR alone.  This is
somewhat similar to the way that SR04 recognizes soda cans with
SONAR alone for the DPRG CanCan contest:

<http://www.geology.smu.edu/~dpa-www/robots/mpeg/cancan.mpg>

which also required the addition of a single subsumption behavior.

At any rate, once your robot can do these four exercises you
will hopefully have a robust enough platform to be suitable for
all sorts of sensors, cameras, grippers, and grand adventures
in outdoor robotry.

Happy Roboting!
dpa

More information about the DPRG mailing list