Reactive Systems: The Schema

Navigation Module


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?
Shameless self-promotion