To Introduction -
To Background
Sensor Processing
The most basic segment of the reactive system is the sensor processing
that occurs within the navigation module. The navigation module is
the primary communicator with the Mage interface, and processes most
of the sensory data used by the rest of the reactive system. A
utility within Mage_Util.c queries state variables filled directly by
the Mage interface. These variables contain the most current data
from the sonar, IR, and tactile sensors. The data from the bump
sensors is placed directly into internal data structures that are
examined by the bump scheme, discussed below. Each of the IR and
sonar sensors return a value corresponding to the distance of the
closest object in that sensor's range. A low reading means the
distance to the nearest object is small . For the 16 pairs of IR and
sonar sensors, the minimum reading from the two is computed, taking
into account a threshold for IR accuracy. A sonar sensor that does
not sense something within its range returns a value of 8000, meaning
that it did not receive the echo from its ping. The sonars get
unreliable at distances of about 25 centimeters, and can return
readings of 8000 even if an object is very close. The IR sensors are
more accurate at short range, but return a nonsense reading at values
above about 28 centimeters, giving random values between 400 and 500
mm. A simple minimum can't be taken between the sonar and IR
readings, as the sonar reading of 800 mm might be accurate, and the
reading of 450 mm from the IR sensor might be just nonsense. Thus,
there is an IR threshold parameter within the sensor processing
portion of the navigation module that can be altered by the
application dependent on the goals of the behavior. If an IR sensor
reading is beneath this threshold, and the IR sensor reading is less
than the sonar reading, then the IR reading becomes the minimum
reading for that pair. Otherwise, the sonar reading becomes the
minimum.
Different behaviors may wish to alter this value. A
behavior which does not plan to be operating in close proximity to
walls may want to set an IR threshold at around 18 to 20 centimeters,
as sonar readings tend to be a little more accurate in ranges above
about 23 centimeters. A behavior designed for operation at close
quarters to obstacles might want to set the IR threshold to 25
centimeters, as IR sensors are better at detecting corners and other
highly textured surfaces.
Back To Top
Obstacle Avoidance
Obstacle avoidance is integrated into the navigation module, as it was
difficult to imagine a scenario in which some flavor of obstacle
avoidance would not be desired. But the obstacle avoidance system
could be parameterized in a such a way as to effectively turn it off,
or even have obstacles exert an attractive force. Obstacle avoidance
is implemented in a reactive potential fields approach as described in
the background section.
Obstacles in front of the robot push the robot backwards, objects to
the left push the robot right; left objects exert a rightward force,
and objects behind the robot push it forwards. As the sensors are
arranged equidistantly around the robot, what constitutes the front of
the robot becomes a bit unclear. For the purposes of this paper, front is defined as
the direction the camera is pointed in its initial configuration,
which also lines up with the wheels. This means that there is a
single sensor pair pointed directly at the front, two other sensor
pairs pointed at the front at slight angle, two more sensor pairs at a
slightly more extreme angle, and so on. As the goal of obstacle
avoidance is not to hit anything, we want to include as many sensors
as possible in the calculation of vectors, but not so many that the
robot's progress through tight spaces is limited. So the current
scheme involves a variable weighting of the sonars for each direction,
where the most important sonars gets the highest weightings for the
force computation in each direction. The exact importance of the
weightings is discussed below.
There are a number of parameters which can be altered to
effect change in obstacle avoidance behavior. The first set of
parameters have been dubbed care values. The care
values specify the value under which a sonar reading should begin to
cause a repulsive force. The range of the sonars is about 3 meters,
but there are few applications where we want the agent to be shying
away from obstacles 250 centimeters away. If we are moving through
relatively unobstructed space, we may want the robot to start reacting
to obstacles at 150 centimeters, but for behaviors operating in tight
spaces, in hallways or doors, we may want the robot to ignore
obstacles as close as 60 centimeters. Care values allow us to
specify exactly what measurement should be reacted to. There is a
care value for each of the four directions.
In a potential fields approach, obstacles exert a force along
a distance gradient. This means that we want obstacles very close to
the robot to exert a stronger repulsive force on the robot than
obstacles farther away. In this implementation, there is a linear
relationship between the distance of an object and the repulsive force
it exerts. The IR minimum range, about 10 centimeters, and the
care value for a particular direction form the range for the
force; sensor readings below 10 centimeters will give a force of 1,
and readings above the care value will give a force of 0. The sensor
weightings for each direction are used in transforming the sensor
values to an actual number representing the command to be passed to
the motors. Every sensor pair that has a non-zero weighting in a
particular direction has its reading passed to a function which scales
the reading between 0 and 1. The scaled number is then multiplied by
the direction-dependent weighting for that sensor pair. A sensor
reading of 1 from a sensor pair that has a weighting of .3 will result
in a scaled, weighted value of .3. Finally, the highest scaled,
weighted value is selected for that particular direction. This system
of sensor processing guarantees that readings from the most important
sensors in a particular direction will be more important than readings
from less important sensors, and will result in higher pushes; still,
a less important sensor pair with an especially low reading will still
result in a repulsive push even if the more important sensors don't
detect anything. As the sensors are undependable, this kind of system
seems the most appropriate for this application.
After the weighting, scaling, and selection a number between 0
and 1 has been computed, but is not yet in units that make sense as
motor commands. Another set of parameters influences this conversion:
max values. The scaled value is multiplied by the max value for that
direction, giving a number corresponding to the desired robot speed in
mm/sec. They are called max values because they are the maximum
obstacle-avoidance push in each direction, as they will always be
multiplied by a value between 0 and 1. By this process each direction
recommends a number, scaled between 0 and max , to be summed into the
final rotate or trans values. The rotation
recommendation for the obstacle avoidance scheme is the sum of left and
the right directional recommendations, and the translational
recommendation is the sum of the forward and backward recommendations.
After obstacles avoidance recommendations have been computed, and the
rest of the schemes make their recommendations, the translation and rotation
recommendations from all of the schema are summed and passed to the motors as
the commands for that time step. In this manner all the schema,
including obstacle avoidance, have their action values for the time
step summed into the motor commands of the robot. The details of all
the non-obstacle avoidance schema are discussed below.
Back To Top
Schema Overview
As discussed in the introduction and background sections, motor
schema monitor incoming sensory information and produce a movement
vector based on that sensory information. In this implementation,
each motor scheme gives two recommendations: a translation
recommendation and a rotation recommendation, though some schema will
ever only have a non-zero recommendation for one of the two.
Behaviors, discussed in more depth in the Behavior section, can
turn schema on or off as they choose by setting a bit of a scheme_on
array to 1. Every time step a function processes the scheme_on array,
calling a scheme function if the corresponding bit is set to 1. Each
called scheme function examines part of the sensory data and makes
translational and rotation recommendations, which are collected in an
array. Finally, a function goes through and sums the recommendations.
These numbers are then placed in a store which can be read by the
navigation module. During the operation of the navigation module, it
sums the total output of the schema with the recommendations of
the navigation-situated object avoidance schema. All of the schema
outputs summed together form the motor commands that the robot will
execute in that time cycle.
Every effort has been made to fully generalize and
parameterize these scheme functions to keep them as broadly useful as
possible. By altering parameters associated with a scheme, the
function of the scheme can change pronouncedly, allowing behaviors to
tailor the schemes on a highly individualized basis. Thus most
applications should be able to use these schema for any task that
requires a scheme of that variety.
The following section describe the inner workings of the
schema: how they examine sensor data to produce action vectors, and
the parameters that can be altered to adapt the function of the schema
to many different behaviors.
Back To Top
Bump Scheme
The first, and perhaps simplest schema is the bump schema, a
scheme that monitors the bump sensors and responds if a bump sensor is
depressed. The only parameter that can be set is bump_force, which is
the amount that the robot will respond if a bump sensor is depressed.
When a bumper is depressed, it will report that it has been pressed
for about 4 or 5 step cycles. Currently, depressing the front three
sensors will push the robot backwards the amount of bump_force, and
pushing the back three sensor will push the robot forward the amount
of bump_force. The other right and left sensors each rotate the
robot away from the depressed bump sensor the amount of bump_force.
Bump_force is parameterized because different behaviors might
want to react differently or in different magnitudes to the depression
of the bump sensors. A behavior moving through open space might want
to react much more violently than a behavior designed for operating in
close quarters to objects, where the robot tends to brush against
things and a strong bump push could send the robot crashing into
another obstacle. Finally, in an application that wanted the robot
the robot to push open doors or push obstacles across the floor, a low
or even negative value could be given for bump_force, which would
actually cause the robot to largely ignore or even push into something
when a bump sensor was depressed.
Back To Top
Goal Scheme
The goal scheme is probably the most important schema given
that the ultimate objective of this schema system is attaining goal
points. The goal scheme examines the current (x,y, theta) position of
the robot and the (x,y) position of the goal and computes a heading
using the atan2 function. If the robot is pointed directly at the
goal point, then the goal scheme will give a 0 for rotation
recommendation, or if the robot is not pointed directly at the goal
will give a recommendation which will rotate the robot towards the
goal. Translation recommendations are kept at a constant positive
value, as we want to keep the robot moving forwards unless actively
prevented from doing so.
A number of parameters affect the functioning of the goal
scheme. The constant translation recommendation can be set, as this
value will in large part govern the speed at which the robot moves
through the world. The rotation recommendation is a bit more
complicated. The angle of the robot to the goal point is kept in
thousandths of radians, scaled between -3141 and 3141 where 0 is
straight ahead. Three parameters control the conversion of this angle
value into the rotation recommendation for the goal scheme. The
computed angle to the goal, a range parameter max_angle, and a range parameter min angle
are passed to a function which linearly scales the angle with respect
to max_angle. This function will return 1 if the absolute value of
the angle is greater than max_angle, 0 if the angle value is less than
min_angle, or a scaled value between 0 and 1 if min_angle <
goal angle <
max_angle. The scaled value is then multiplied by another parameter
max_rotate_val which is the magnitude of the maximum rotation push
that can be recommended by the goal scheme. This scaled value, once
multiplied by max_rotate_val, which will be number between 0 and
max_rotate_val. It is then given the appropriate sign and returned as
the rotation recommendation from the goal scheme.
The workings of these three parameters can be a bit confusing.
Max_angle and min_angle work to allow a range of types of goal pushes.
Some applications might want to move very directly towards a goal,
where moving away from an exact heading towards that goal is to be
strictly avoided. This application would want to achieve a maximum
rotation push very quickly, which would mean a low max_angle, and a
low or zero min_angle. Another application might want to give the
robot more latitude in moving in non-goal directions, which could be
achieved by setting a high max_angle and a high min_angle. The
max_rotate_val can be used to make the goal scheme more or less
influential in relation to other schema. A high max_rotate_val can
cause the goal scheme to dwarf other schema, and a low value can
lessen its importance.
Finally, the ability to simulate wall-following behavior has
been implemented in the goal scheme. Suppose that the robot is in the
bottom of an inverted standard U-shaped curve, with a goal point
directly beyond the cup of the U. It moves toward the goal until it
gets stuck in a local minimum created by the cup of the U, and the
stuck scheme turns it to the right. Facing the right side of the U,
it gets stuck again, turns to the right, and begins following the side
of the U. If at any point, its orientation gets more than 180 degrees
in relation to the goal, the goal scheme will promptly reverse the
direction of the push, causing the robot to whip around to the right,
and head straight back into the center of the cup, to begin the
process again. In this case, the more intelligent thing to do is have
the robot continue to push against the right wall until the end of the
U is found. This may mean, however, continuing the leftward push
against the wall even if it leads directly away from a goal.
The goal scheme has a mode that can create this behavior. If
goal_follow is set to 1, then the goal scheme will recommend rotations
that will cause the robot to follow walls. If the goal_follow
variable is set to 1, an goal angle value above max_angle will cause the
goal_following variable to be set to 1. When this happens, the
goal_max_rotate will the appropriate sign is assigned to
goal_follow_push. The goal scheme will continue to recommend this
value until one of two conditions occur. If the goal_follow value is
set to 0 by the behavior, then the goal scheme will revert to
non-follow performance. Additionally, any time the absolute value of
the angle to the goal drops below max_angle, goal_following will be
set to 0 and the rotation recommendation will be computed as normal.
Thus following just extends the maximum rotation push in a certain
direction from (max_angle to 180 degrees) to (max_angle to (360
degrees - max_angle)). This goal_scheme behavior expands the
situations in which the merely reactive behavior can attain a
goal point that would not otherwise be attainable.
Back To Top
Local Minima Avoidance: Stuck and
Fluct
One of the biggest problems associated with potential fields type
navigation are local minima: what does the robot due when all the
forces impacting it sum to 0? There are scenarios where both the
translation and rotation vectors will sum to zero, resulting in a
complete standstill. For instance, the robot might be headed directly
towards a goal point, with no walls to either side, resulting in a
zero rotation vector. If the robot hits a wall straight ahead, then
the basic goal-oriented forward push can balance the obstacle
avoidance backward push, giving a zero translation vector. The robot
can remain indefinitely in this position unless some kind of force can
push the robot away from these local minima.
In the present configuration there are two schema implemented
to try to avoid local minima. The first, the stuck scheme, monitors
the total summed translation and rotation vectors and senses when
several consecutive cycles pass with low totaled recommendations.
Consecutive low recommendations often indicate the robot is in a local
minimum. The stuck scheme then recommends a short burst of high
intensity rotations in a consistent direction, designed to turn the
robot away from an obstacle in front of it and break the deadlock.
There is also a scheme implemented that gives a consistent level of
variability to the translation and rotation recommendations, to keep
the robot away from local minima in the first place . The fluctuation
scheme recommends a smoothly varying value for both translation and
rotation. This value is tied to a time-based sin function, giving a
smooth and constantly changing value to be factored into the final
recommendations. This gives a noise-like variability to the vectors
which will not cause the jerky behavior associated with true random
noise functions. The particulars of each of the functions are
discussed below.
Back To Top
Stuck Scheme
The first set of parameters governing the function of the stuck
scheme designate what final translation and rotation values constitute
a local minimum. If the total summed translation and rotation values
from the previous cycle are respectively less than stuck_trans and
stuck_rotate, then a counter is incremented. If the translation value
from the last cycle is greater than stuck_trans, or the rotation value
is greater than stuck_rotate, then the counter is reset to 0. Thus
initialization of stuck behavior requires consecutive low-translation,
low-rotation cycles. The number of consecutive low_trans, low_rotate
cycles necessary to initiate the response of the stuck scheme is set
by another parameter, stuck_consec. If the counter discussed in the
previous paragraph is greater than stuck_consec, then the stuck scheme
begins recommending rotation values designed to get the robot unstuck.
Once the stuck scheme has decided that the robot is stuck,
another group of parameters governs the nature of rotation
recommendations. The intensity of the rotational push is specified by
stuck_intensity, and the direction in which to push is set by
stuck_direction. The stuck scheme decides how many cycles to
recommend a rotation in two ways. The first way is simply to
recommend a push for a number of cycles specified by stuck_duration.
But say for instance that the robot is at a corner in a local minimum.
The stuck scheme recommends a push of ten cycles, in the direction of
the other wall in the corner. The stuck push ends, and the robot is
briefly out of the local minimum, but the repulsive force of the other
wall then comes into play and pushes the robot right back into the
local minimum. To avoid this type of cycle, the stuck scheme can be
parameterized to continue the push until there is no obstacle in front
of the robot for a certain distance. This insures that the robot will
be able to move forward at least a little when the stuck scheme ends,
which generally moves the robot permanently away from a local minimum.
Stuck parameters must be set very carefully, as there are
situations when turning away too quickly can be counter-productive to
attaning a goal point. Specifically, the robot may appear to be in a
local minimum in especially difficult positions, such as facing a door
trying to go through it, which is a surprisingly difficult situation
which will be discussed at length later in this paper. If the stuck
scheme decides the robot is stuck when it really just needs more time
to situation itself to get through the door, then the robot may turn
away from a door that leads it to its goal. Also, for the stuck
scheme to be really effective it requires that the stuck_intensity be
set high relative to the goal scheme rotation maximum and the
left-right obstacle avoidance max values. Otherwise, the robot may
remain in a local minimum even after the stuck scheme begins pushing
the robot. But even with a relatively high stuck_intensity, one may
encounter problems. Say the robot is facing a wall which blocks its
progress to a goal point, and another wall is to the robot's right.
Eventually, the stuck scheme begins pushing the robot's rotation to
the right 550 units. But the goal push pushes the rotation back left
300 units, and the wall to the right results in a leftward push of
250. Even with the stuck scheme recommending strong pushes, the robot
can remain in a local minimum.
Back To Top
Fluctuation Scheme
Many local minima can be effectively avoided by using the stuck
scheme as describe above. But there are situations in which the robot
can become stuck despite the efforts of the stuck scheme. Thus there
is another minima avoidance scheme, dubbed the fluctuation
scheme. Some approaches to motor schema use a noise scheme to try to
avoid local minima. A random value is added to the translation or the
rotation values in the hopes that this will provide enough variation
to get the robot out of local minima. I experimented with this
approach, and decided is was not that effective. The main reason for
the lack of effectiveness seems to involve real-world aspects of the
motors. When the motor receive a command, they must accelerate or
decelerate to achieve the desired speed. This acceleration takes
time, and certainly more time than the a single cycle of the 10 or so
cycles per second the robot evaluates its environment. If a random
value of 40 is picked at one cycle, and the next cycle gives a random
value of -40, then the motors will effectively not move at all. For a
noise scheme to effectively dislodge the robot the pushes would have
to be of such a great intensity that they might cause the robot to run
into a wall or do something similarly misguided.
After experimenting with the noise scheme, I decided to try to
implement a variant of the noise function. Instead of picking a
random value every cycle though, I decided to try to make the scheme
vary smoothly with time, to avoid the jerkiness associated with a
straight noise push. The fluctuation scheme has three parameters.
The first parameter is called fluct_period. Fluct_period sets the
periodicity of the sin function that I am using to give a smoothly
varying function. In addition, there are two range values, one for
each translation and rotation. Say, for instance, that fluct_period
is set to 10 seconds, and fluct_rotate is set to 75. The fluctuation
scheme will then smoothly vary from a recommendation of -75 at
number of seconds mod 10 = 0 time, to recommending 75 at 5 seconds, to
recommending 0 at 7.5 seconds, and back to -75 at 10 seconds. With
this scheme on, the robot looks as if it is doing a "waggle", moving
slowly from side to side.
As it turns out, the combination of the fluctuation scheme with
the stuck scheme means that the robot rarely gets stuck. With just
the fluctuation scheme running, there are situations in which the
fluctuation scheme will just leave the robot fluctuating out of a
local minimum without ever actually getting it out of it. But with
both the stuck scheme and the fluctuation scheme running, minima are
generally completely avoided. Additionally, the fluctuation scheme
and "waggling" more generally have additionally helpful
characteristics for the attaining of goal points. This is discussed
fully later in this paper.
Back To Top - To Introduction -
To Background
All material on these pages was created by Gil Jones, Swarthmore
College, January 2001
Questions or Comments?
gil@sccs.swarthmore.edu
Shameless self-promotion