3 Navigation

This chapter deals with mathematical solutions for the execution of a flight plan. Solutions for the calculation of the flight path are presented. It is assumed that the navigational system is build on top of a system for attitude stabilization, which is separately treated.

3.1 Reference Systems

The global positioning system GPS is based on a geodetic reference system. A GPS position consists of geographical degree of latitude (Latitude, λ), degree of longitude (Longitude, φ) and height over sea level (Altitude, h).

Figure 3: geodetic and local reference system

A GPS position valid for Germany is e.g. 50°27' N, 12°33' E, 310 m. The position is to be picked out e.g. from the NMEA data record GGA:

Calculation with these data is possible, however it is somewhat difficult. Therefore a local reference system (LR) is introduced, based on an orthogonal coordinate system. The origin of the local reference system is specified as the starting point of the route of the autonomous robot; the x axis corresponds to a straight line from west to east, the y axis to a straight line from south to north, and the Z-axis of a virtual line of earth center through the origin. Figure 3 shows the relationship of the systems to each other.

In order to convert a GPS position into coordinates of the LR, first the GPS position of the starting point (origin, O) must be known. Further a conversion factor f is needed for the conversion of degrees to meters. This can be determined from the earth radius; it with 111200 m/grad is in the following set. The computation is then as follows:

For the described purpose this conversion is quite sufficient, however one should be conscious that it is not accurate, since it does not consider the flattening of the globe among other things. It is further not suitable for large distances, with those earth's curvature has an increasing influence and / or in areas close of the North and South Pole.

A further simplification of formula 1 is the use of cosφ0 in place of cosφP. Here is assumed the maximum distance of a position P of the origin amounts to only few kilometers, which on the angle difference of φ has only very small influence and can be neglected. Thus only uniquely onr trigonometric function must be implemented, what saves arithmetic performance.

3.2 Fundamental Terms

3.2.1 Position

As anticipated already, a position is characterized in the local reference system by its x, y, and z coordinates. Mathematically seen, it is a three-dimensional vector.

3.2.2 Attitude

The attitude can be represented likewise as vector. It points from the current position to the direction of the current movement. It is meaningful to standardize the attitude vector so that it becomes independent of the speed factor v. To a straight, homogeneous movement therefore applies:

With GPS data as only basis there are two possibilities of determining the attitude. On the one hand the difference of the position of two temporally successively lying measurements can be calculated; on the other hand the heading or track value can be picked out directly.

Conversion angle to vector:

The track value can be read for example from the NMEA data record VTG. It is the first value after the identification sentence:

It indicates the angle in the clockwise direction beginning from north. However our geometrical coordinate system refers to the x axis and runs against the clockwise direction (see Figure 4). The conversion happens as follows:

For the transformation of an azimuth angle into a direction vector the sine and cosine function are used

Figure 4: track and geometrical angle

Contrariwise the arc tangent can be used

Note that the x-portion of the vector may not be 0. If x = 0 is, the vector runs parallel to the y axis, thus the angle is, dependent on y, 90° or 270°. Some programming languages offer special functions, which have x and y as parameters. In Java for example the method Math.atan2(double y, double x) can be used.

3.3 2D Maneuvers

3.3.1 Heading for a given point

We assume an airplane is at a certain time at the point A and moves in a straight non accelerated way. It now gets the instruction to head for point C. Therefore it must change its attitude, i.e. fly a curve. As simplification this curve can be regarded as a segment of a circle, which begins in point A and ends in point B. After point B is reached, the flight path changes again into a straight line.

Figure 5: Approach one point

For the computation of the flight path now the point B is looked at. It can be regarded geometrically as a tangent contact point, which touches the circular path that represents the curve.

Figure 6: Representation of B as tangent contact point

Figure 6 shows a circle with the radius r and center M, which serves for the curve representation. It is evident that there are two possible tangents for the circle, which go through point C. In the case shown the point Bl is looked for.

But first we must compute the center point M. In addition it must be decided whether a right or a left curve is flown.

Right or Left?

The question about a left or a right curve can be attributed to the question, on which side of attitude vector A the point C is located. Thus whether the angle between A and AC has positive or negative direction of rotation. This can be done simply with the determinant:

To the case from Figure 6 applies:

Orthogonal vectors

We now know that our airplane must fly a left turn. Thus also the center of the curve must be on the left side. Since the airplane begins immediately with the circulation (simplification, as seen above), we regard the direction vector as tangent at the circular path. In this case the radius of the circular path stands perpendicularly on the direction vector. In order to find the center M, we must detect a vector orthogonal to a, which has the length of the turning radius r.

Therefore we implement a rotation around 90° on a. Since a is standardized, i.e. the length is 1, the vector must be multiplied by r. Formula 7 shows the derivation with the rotation matrix. The resulting solution is shown in formula 9.

Thus the center of the circular path can be determined, which lies left of point A. In the case that M lies to the right, a right curve is thus flown, acts it itself around in a negative direction of rotation, and the angle A = -90°. In this case only a change to the sign occurs as to be seen in formula 10.

In order to generalize formula 9 and 10, we introduce the parameter s, which indicates the direction of rotation of the curve. s can only take the values -1 ^= right and +1 ^= left.

Tangent

Now the point Bl looked for in Figure 6 can be determined. Three things are known. The length of the distance MC, since points M and C are known. The length of the distance MT, i.e. r, as well as the angle between MT and BC, i.e. 90°. With the help of the Pythagoras now first the length of BC can be determined. For later purposes the factor q is introduced, which indicates the relationship between the lengths of BC and r.

As in formula 12 q is not defined, if the radius is 0 and the distance between M and C is smaller than the radius. Both are graphically easily comprehensible. Further it must be marked that q can actually take two values, i.e. a positive and a negative one. In the connection shown a negative route distance is however not reasonable, that's why the negative value is not used.

Since the distance BC stands perpendicularly on MT with positive direction of rotation, formula 8 can be used:

From this now Bl is deduced:

For right curves the computation is similarly executable with the negated value of q.

Now the question arises whether the calculation of the tangent contact point is really necessary. After all an autonomous airplane can as well determine by frequent measuring of distance and angle whether the movement in the circular path must be continued or not. The advantage of the computation is on the one hand the higher accuracy - the time of the end of the turning flight can more accurately be computed, than the measurement cycles permit (with GPS 1 - 4 cycles per second). On the other hand it is the basis for the computation of the next maneuver, which cannot be exactly steered only by the help of a simple automatic control loop.

3.3.2 Heading for a point from a given direction

For the approach flight it is compellingly necessary that the runway is approached exactly in the angle of its adjustment. During final descending flight before touchdown no more curve should be flown, therefore results the task to approach the point of entrance for final descending flight in the given angle of the runway.

Figure 7: Approach a given by point D from a given direction

In Figure 7 it is to be recognized that for the maneuver two circulations are necessary. The first circulation serves for the approximation to the point of entrance - designated here with D. The second circulation leads finally to the change of direction according to the demand. The change of direction is implemented in such a way that it is exactly terminated in point D. The given direction in point D is named d in the following.

Now the task is to determine the connecting distance BC between the two circular paths. Geometrically regarded, it concerns thereby the tangent between two circles. Dependent on it whether first and the second curve have same direction of rotation or not, is it an outside and / or internal tangent. First thus the direction of rotation of the two curves must be determined.

Direction of rotation of the curves

A simple algorithm for the determination of the direction of rotation of the curves is to use the shortest connection between the points A and D and to compare it in each case with the direction vectors a and a. From the two arising determinants the respective direction of rotation can be determined. As is yet shown later, the procedure leads to errors and / or not optimal solutions under certain conditions.

Figure 8: Determination of the direction of rotation of the curves

Outside Tangents

Mathematically easily to solve is the computation of the outside tangents, thus the connecting distances for two curves with same direction of rotation. If the two curves have the same radius - which we presuppose here - the tangent is parallel to the connecting line of the centers. Therefore it has the same length and forms a rectangle together with the respective radius.

Figure 9: Construction of the outside tangent

The centers M and N can be computed with help of the vectors orthogonal to a and d as already shown. Therefore a and d must be presented normalized:

Now vector b is introduced and normalized.

On the basis of M and N now the points B and C can be calculated over the orthogonal vectors to b with the length r. The direction of rotation is here opposite to that of the curves:

Inside Tangents

For the computation of the internal tangent we determine again first the centers M and N of the two circular paths. Now we introduce the point E as intersection of the distances MN and BC. Hereunder applies

Figure 10: Construction of the inside tangent

Now B is computed as tangent contact point of the tangent through point E.

C is now computed as extension of the distance BE with factor 2.

Problematic cases

As already mentioned, the algorithm for the determination of the direction of rotation of the two curves is not error free. In the following two cases are presented, in which it supplies a wrong solution.

Figure 11: Procedure supplies wrong solution

In figure 11 D lies on the right seen from A. Thus first a right curve could be flown. However, since D can never be approached in this way toward D, first a left curve must be flown and then a right curve.

Figure 12: Procedure supplies unfavorable solution

In figure 12 D lies on the right seen from A. Therefore right would be the first curve. From the inside tangent D shows to the left, therefore the second curve would be a left curve. It is however actually shorter to fly two left curves.

The solution of the problems and a better procedure is yet to be done.

3.4 Notes

3.4.1 Accuracy

The presented solutions can be regarded only as simplification of an actual flight path. In the reality a straight non accelerated movement never changes abruptly into a circulation but a transition takes place. The flight path developing thereby is designated klotoide. For more exact computations thus in the future the klotoide should be included and / or a procedure be supplied, which sufficiently exactly models the transition of straight-line and circulation.

3.4.2 Prospects

The presented solutions are only a small part of what is needed for the controlling of an autonomous airplane. The computation of important waypoints was presented - now solutions are needed, which control the attitude itself. For example the control should constantly compare the current position with the demands during a flight and be able to make appropriate corrections. For the straight flight a correction of the cross-wind is desirable. Further three-dimensional maneuvers were so far omitted, likewise the influence of the airspeed. For the approach flight - which is probably the most difficult maneuver - the influence of all sizes mentioned will play a role, equally also the orbit correction must include the factors position, direction and speed at the same time.