Encoder Front Page
SRS Home | Front Page | Monthly Issue | Index
Google
Search WWW Search seattlerobotics.org

Navigational Model

Parcet, fparcet@visto.com

2000

Introduction

Problem solving is one of the most important areas of Robotics. Pythagoras is an attempt to create a system to solve a generic problem: go from one point to another avoiding obstacle of unknown location and remembering their position for later use. This is very similar, if not the same, as mapping the environment surrounding the robot.

There are several things to keep in mind when facing the mention problem, among them one can mention:

Even though there are others, the problems mentioned above are of critical importance. Local minima are a problem many robotists have faced. It consists of a partial solution to the problem, which is only the minimum for a section of the curve and not the general solution. The sensor limitations must be considered because the sensors are the connection between the world and the brain, so depending on the kind of sensors that are used is how the robot "sees" the world; therefore, depending on the sensors is how the general problem must be approached. On the other end of the system lies the synchronization between machine and brain.

An example of this last 2 problems can be seen on SETERO (1997, PArcet), where the light sensing used to triangulate the position of the goal was not accurate enough, and the traction of the wheels was so poor that the output instructions given by the brain were not properly accomplished.

Pythagoras is another attempt to solve a similar problem – traveling from one point to another avoiding unknown obstacles and remembering their position, also know as mapping-. In this case the orientation will be controlled internally by the calculation of vector fields on the surroundings of the robot (in SELERO it was external, triangulation using a light source and a array if light sensors). The memory and experience will be the parameters for the vector fields, unlike SELERO, that used a database.

Environments

When developing a navigational system is important to keep in mind the environment it will have to perform in. Environments can be arranged according to their degrees of organization. Laboratory conditions - where all the variables applicable are under control – is the environment with the most organization. Battle fields are considers the least organized environments for a navigational system to perform.

Environments where the organization is low will result in a lower performance of the navigational system. This lower performance is due mostly to the mixed signals and noise present in an uncontrolled performance environment.

Even though the development of any prototype is made in laboratory conditions is a must to keep as a goal the scaling of the system, in such way that it will perform acceptably in uncontrolled conditions. Often, in order to keep the level of performance, adjustments must be made, calibration is a transcendental part of the development of a system. Also, the incorporation of new inputs is a way to maintain the performance; these inputs are fused with the information from the navigational system to create a more accurate image of the situation. Inputs like vision can be added, the visual information can be used to recognize landmarks that can be used to double check the position of the robot (one of the most important variables involved in navigation). Other input that could be added to double check position are radio transmitters used to triangulate position.

One of the main tasks of a navigational system is the calculation of the position of the robot. Once the goal-position is set, is the task of the navigational system to calculate the direction required to approach the goal, this is called orientation. Depending on mechanical and practical factors, the accuracy of the calculation can be affected, as mentioned before there are other inputs that can be added to improve the performance of a navigational system in uncontrolled environments, like the ones created by inaccurate hardware.

In the case of highly accurate hardware, navigational system can be self-contained; meaning that all the information necessary for the robot to navigate comes from the navigational system itself. When inaccuracies are added to the problem external data is necessary. The most common external data used to increase the accuracy of a navigational system are beacons. Beacons are landmarks that can be uniquely identified, either by their arrangement or by the intrinsic characteristics. Using beacons the robots are able to correct errors on location caused by the inaccuracy of the hardware or by unplanned movements caused by environmental variables (e.i. someone moving the robot by hand).

General explanation

Pythagoras (PT) is a robotic system that will intent solve the mapping problem. In order for it to orientate itself, PT will be provided with the initial location of the goal (Xg,YG) and its initial position(X,Y). Based on that it will calculate a vector field centered on the goal, this vector field will have a constant magnitude over the whole plane, and in order to guide PT to the goal, it will be attractive. Once PT is traveling -guided by the vector field- every point where it corrects its direction will be stored in a list (LPO = list of points and obstacles) in such a manner that the trajectory will be the connection of all those points. The trajectory will be the center of another vector field. In this case the vector field will be repellent, and its magnitude will be discussed in depth later. As PT advances it will encounter obstacles, as this obstacles will force PT to change direction, the position of the obstacles will be stored in the LPO, but this time there will be a "flag" in the list indication that this point is a obstacle. PT does this because the obstacles will be the center of a third kind of vector field. This vector field will be also repellent, and the magnitude will be discussed later as well.

The idea behind the calculation of all those vector field is that after every unit of displacement or when in contact with and obstacle, PT will recalculate the sum of all those vector field in order to determine where to go; where the goal is and what is the best path. As will be shown in the next part of this presentation, the magnitudes of the vector field centered on the trajectory and the obstacles are neglectable when far enough; therefore every time the calculations are done, only the vector field for relevant points will be calculated, optimizing the time of reaction.

Definitions

In the rest of the presentation some term are used, and they will defined now.

One characteristic of the vector field is their magnitude. Since the magnitude of a vector field can change with the position where it is calculated the term Graduality (GF) can be defined. Graduality is the rate of change of the magnitude of the vector field respect to the distance from the center of the field. In the case where the center is no a point, the perpendicular distance will be used.

In other words

Another term used is the Strength of a vector field, it will be defined as a unitless magnitude of the vector at a determined position. This number only makes sense when it's used to compare vector fields at the same point; in such away that one field can be "stronger" than other.

Description of the fields involved

As mentioned before, there are 3 different kinds of vector field involved in this project. Here is the detail explanation of each one of them.

FG(x,y) – Goal Field

The vector field centered on the goal is defined as a vector field with constant magnitude and attractive properties. In order for it to have the desired characteristics it must look like:

where K is a constant that determines the magnitude of the field at any point.

A graphic appearance will be like:

 

If the magnitude of the field is calculated be have

One can see that the magnitude is constantly K, for any point in the plane. Since , the Graduality will be 0. Meaning that there will be no change of magnitude for any displacement on the plane.

T(x,y) – Trajectory Field

The vector field centered on the trajectory is defined as a vector field with its magnitude inversely proportional to the f power of the distance.

Since the trajectory will be a set of interconnected lines, the vector fields will be centered on those segments instead of a point.

The robot should avoid visited places in order to solve the local minima problem. But given the situation that it is needed that the robot crosses over the line; the field cannot go to infinity (stronger than FG) at the center –unlike the obstacle vector field where the solution to the vector fields can’t go over the obstacle-. All those characteristics lead to define the trajectory field as:

where , A and f are constants (q is the angle between the x-axis and the segment).

The terms (mx+n-y) and (y-mx-n) determine the inclination of the vector field, given by the segment. The coefficients k and l are defined to make the vectors perpendicular to the segment; without them, the vectors point parallel to either the y-axis or the x-axis.

As mentioned the field must be "crossable", meaning that the robot can define a path that goes over the old trajectory. That is the reason for the constant A. This constant determines a maximum value to the vector field when positioned over the line. The terms in the denominator are to the f power because f determines the Graduality of T(x,y). The greater the f the greater the Graduality; therefore the field gets weaker at a smaller distance when f gets bigger. The final value of f must be determined based on the hardware and experimental world.

Sample of vector field T(x,y)

R(x,y) – obstacle Field

A third kind of vector field centered on the obstacles, is defined as an "uncrossable" field with repellent properties. It’s needed that the robot never plans to go over an obstacle. In order for the vector field to be uncrossable the value of the field must be greater than the final value of the calculated path, meaning that the sum of the vector a any point must never be greater and opposite to the vector field generated by the obstacle. That kind of behavior is ensured if the

vector field is define using a inverse to-the-g-power relationship. Given all this the field will look like:

, where (xi,yi) is the position of the i-obstacle and g is a constant.

 

Sample of an obstacle centered on the origin

There may be many obstacles; therefore, an index is needed to organize their location, i. Using the g power allows to control the Graduality of the vector field, it must be determine once working with the hardware.

To understand why and how this vector field determines the path to be taken by the robot, the magnitude of the vector field will be intersected with a common perpendicular plane, where the z-axis represents the magnitude of the field. a dimensional graph can be seen.

The vector fields F(x,y) and R(x,y) have magnitudes |F(x,y)| and |G(x,y)|. The 3D graph of these magnitudes can be intersected with any plane perpendicular to the XY-plane. But in order to have a consistent view of the magnitudes of T(x,y), the intersecting plane must be perpendicular to the XY-plane as well as perpendicular to the segment of T(x,y) lying on the XY-plane. That's why the calculations shown below start with T(x,y) instead of following the previous order.

For R(x,y) the calculations are as follows

And for the goal:

Summarizing:

As it can be seen all the magnitudes are define as functions of constants, this constants must be defined based on the characteristics of the hardware and the experimental world. But the relationship among them can be shown now.

There are characteristics particular to each field. F(x,y) must be constant all over the plane, it's been shown that K is that constant value. f and g are the constants that determine the Graduality of the fields, and several possibilities will be shown below. The value for A will determine the maximum value T(x,y) will take, as well as the value in the extreme points. As it will be seen in the graphics A must be set in such manner that K will be always greater than T(x,y).

Defining a constant's vector C=(K,f,g,A)

 

F(x,y) is represented by the blue curve.

T(x,y) is represented by the green curve.

R(x,y) is represented by the red curve.

It can be seen that for C=(1,2,2,1) the distance between T(x,y) and F(x,y) is quite big, making the visited point not very repellent. With C=(1,2,4,0.3) the Graduality of R(x,y) is quite notorious and T(x,y) and F(x,y) are quite close, always keeping F(x,y) greater than T(x,y).

The values used for C are only a way to represent the relationship between the constants, because only once the hardware is working, the final value can be defined.

Load Reduction

Calculations like the one defined above demand enormous amounts of processing time. In order to reduce the time of processing, a new concept is introduced: Relevance.

The Relevance is a characteristic that will determine to sets of points: Relevant and Neglectable points. Relevant points are the points for which the field centered on them has an important effect on the behavior of the robot. Neglectable points are the points that produce magnitudes of fields that don’t affect (in an important way) the total sum of vectors.

Every point on LPO will be used to evaluate the distance between it and the center of the field. According to that distance a fuzzy decision will be taken, resulting in either a rejection or acceptance of the point. All the accepted points will be used to calculate the VFs that will determinate S(x,y). The rejected points will be discarded and the process begins again with the next point on LPO, until the end of the list is found.

Interaction of the Fields

Now that the fields in used had been defined, the interaction of the fields with the robot can be discussed. The path that the robot will follow (S(x,y)) will be the sum of the vector field, meaning

where n is the total number of records in LPO and m is the total number of obstacles encountered at the time of the calculation.

Calculating the Path

Given some Graduality, the effect of the fields far enough will be neglectable, so in actuality when S(x,y) is calculated, not all the points and obstacles will be used, only the ones that are at a relevant distance will be considered. A point Pi will be considered at a relevant distance if and only if the magnitude of the is less than some constant R. Even though the last definition is correct, it doesn't take away the extra calculations needed to determine the relevance of a point. In order to diminish the load of calculation done for all the points in the LPO, the fuzzy function will be introduced.

where R is the relevance of the point in the list, d is the distance between the actual location and the point Pi, G is the Graduality of the vector field and m is the threshold for the definition. In this way, each point will be tested for relevance before starting the major calculations of the fields. For every point the robot will calculate the distance between the point and the robot's location, if the inverse of this distance to the Graduality power is greater than a certain m, then the point is relevant, and the VFs will be calculates. If this number is less than m, then the point is discarded and the cycle starts again with the next point, until i=n.

Graduality versus m

Once the perimeter of relevance has been determined the calculations start. For every point accepted by the fuzzy decision a vector field will be generated, using the point as a center.

As mentioned, the trajectory is a compendium of segments. Each segment is the line that joins Pi with Pi-1. The vector field for the point Pi is actually the vector field centered on the mentioned line. Because of this another decision must be taken. Once the point has been accepted, the vector field calculations start, but depending on the nature of the point is the kind of vector field it will generate. For the points representing an obstacle a R(x,y) will be calculated, for the trajectory points, a T(x,y).

Once all the relevant points have been processed S(x,y) will be the final vector field. S(x,y) will be a compendium of all relevant fields around the robot. The following figure shows a hypothetical S(x,y) using a goal and one obstacle.

Vector field with goal and obstacle

Noise

Until now the hypothetical situations analyzed on this project are not considering random imperfections on the world where the experiments are been done.

The next figure shows a situation where stalling may occur. This stalling is the result of locating the robot exactly in the line that joins the goal and obstacle. The addition of nothing but the vector field created by the goal, the obstacle and the trajectory has a recursibly closed set of solutions; therefore, the robot will stall in this area set.

The previous situation, and the existence of non-perfect experimental worlds, can be solved by introducing Noise. Noise will be understood as a random set of vector distributed evenly all over the plane. The magnitude of this vector will be pre-set in such a way that the noise by it self cannot override the attraction of the goal, by itself.

Noise will be defined as a magnitude-fixed vector with random direction, changed every p time steps.

In other words,

where np is the predefined magnitude and z is a random angle.

An example of a pure Noise field follows

Random Noise VF picture here

The final path of the robot will be the sum of S(x,y) and n(x,y).

Here are some examples of the path that the robot could take in different situations.

Vf with obstacles and goal and lines from flow.

 

 

 

 

Safety and Efficiency

The system described above creates path that will certainly direct the robot to the goal.
The path created by adding the vector field on the plane may result in a non-efficient path, meaning that the path is not close to the shortest possible. An example of this can be seen next

vector field with non-efficient path.

Optimization.

Once PT has experienced the world successfully, it will know the location of the obstacles, at least of some of them. A rect line connecting the goal and the initial position can be created. This line will be represented by the vector field NPP(x,y) (new potential path)

where N is a constant.

This vector field is attractive and with a high Graduality. It’s defined in this way to incentive the robot to stay in the center of the field.

vector field of NPP

As well as the trajectory, the NPP is approximated to a collection of rect lines. In this way the NPP is stored as a set of points.

Once the shortest path has been determined, it’s operated with all the obstacles known to be at a relevant distance of the path. This in done to ensure that the NPP is not an attempt to cross over an obstacle.

In order to make the robot move through the NPP is it operated with goal field F(x,y). This will create an attractive field inside the "weak" zone of the NPP, This is

where m’ is the total number of obstacles in the way of the path.

Since the constants involved in F(x,y) and R(x,y) are already defined, only the constants for NPP can be adjusted in order to get a path "wide" enough for the robot. The "size" of and obstacle –in the robot’s eyes- depends on the Graduality of it. Again, the relevant distance must be taken into account. The distance between the center of NPP and limit for neglectable points for the obstacle must be greater, but close, to the radius the area of the robot.

In this way the navigational solution made by the system is the flow created by the sum of the vector fields and their interaction with the robot’s position.

Conclusion

The use of vector field in the development of robots allows us to work with a navigational system that is reliable and self contained; meaning, it does not need of external beacons to know where it is, and where to go. The use of vector fields is also an approach to solve issues like local minima. This system was developed in laboratory conditions; therefore the addition of other inputs would be necessary if the system where to be scaled to an uncontrolled environment use.

This system is energy-time efficient, since the final optimized path is the best choice given a determined environment.