Surprise 97

Mobile Robot Navigation

An Overview of Global Mobile Robot Navigation: Global Positioning

Jonathan Dixon

20 May 1997


Contents

  • Abstract
  • Introduction
  • Positioning Fixing
  • Overview
  • Radio Navigation
  • GPS
  • Differential GPS
  • Future of Position Fixing
  • GPS Developments
  • Other Developments
  • Between Position Fixes: Dead-Reckoning (DR)
  • Inertial Navigation Systems (INS)
  • INS Integration with GPS
  • Conclusions
  • References
  • Bibliography
  • Other WWW Sites

  • Abstract

    The aim of this document is to give an overview of and investigate into the methods available, using current and future technologies, of globally navigating a mobile robot (or Autonomous Guided Vehicle - AGV). In this context global refers to the ability to discover ones position when placed in any unknown location on the planet (position fix), and update that knowledge while moving to fulfil some other objective (e.g. follow way-points of a map).

    The partner document to this one (An Overview of Local Robot Navigation) deals with local issues - sensing position relative to local (and non-mapped) land marks for appropriate response (e.g. collision avoidance).


    Introduction

    In 1973 the American Defence Navigation Satellite System was formed, as a joint service between the US Navy and Air Force, along with other departments including the Department of Transport, with the aim of developing a highly precise satellite based navigation system - the Global Positioning System. In the 24 years since conception GPS has established itself firmly into many military and civilian uses across the world, here it will be considered in the context of a device for Navigation of mobile robots.

    When GPS was released by the US DoD (Department of Defence), it superseded several other systems, however it was designed to have limited accuracy available to non-military (US) users. Several methods of improving the performance, which have been developed as a result of this, will be discussed which greatly increase the usefulness of the system for AGVs.

    Alternatives to GPS will also be considered, along with ways of integrating either of them into a more complete navigation system.


    Positioning Fixing

    Overview

    The basis of Global Navigation for an AGV is reliably gaining a co-ordinate of vector describing where the vehicle is in relation to a fixed point on the globe. This point is generally taken to be the intersection of the Greenwich meridian and the equator line of latitude, at sea level - in accordance with standard geographical practice. Using this position information, with reference to a map or otherwise, a list of way-points can be generated and followed to allow the vehicle to navigate between end points of a journey.

    Toward the end of this document (Between Position Fixes: Dead-Reckoning) there is discussion of methods for navigating when a continuous or regular position fix is not available, and any movement in the mean time must be estimated if the global position information is to be kept up to date.

    Radio Navigation

    There are several land-based radio navigation systems in use around the world, but mostly these have been superseded by GPS, the most commonly used being Loran-C, Omega, and Decca (see US Coast Guard Navigation Center for further information on these systems). Of these, only Omega can claim to have truly global coverage; using a very low frequency carrier which propagates around the world well, from the eight base transmitters. However, this is at the cost of accuracy in resultant position fix - generally an accuracy of only 7 km can be relied upon, although this does improve in areas. Loran-C and Decca both provide more localised coverage, with accuracy approaching 20 m when used near (i.e. within a few km) to transmitters [10]. However globally no guarantees can be made of accuracy, which can drop to several km (Loran-C) before the signal is lost altogether.

    Figure 1: Hyperbolic Paths between master and two slaves (dotted), intersect at the position of the user.

    As the transmitters for these services are mainly centred around coasts, they are primarily useful for maritime purposes - where high precision is required when approaching ports, but lower precision is acceptable when on open seas. This does not make them very useful for the general Mobile Robot, however, as the ideal global position fixing service should provide (near) uniform accuracy globally - in particular on land. Also, with the advent of GPS, the time for which these systems' transmitters will remain active is under question. The 1994 [US] Federal Radionavigation Plan states that Omega transmissions are due to terminate on 30 September 1997, and Loran-C in the year 2000. Hence at the time of writing, support for both these land based radio-navigation systems is being withdrawn - certainly not likely technologies for reliance on for future AGV navigation.

    All of these systems use a hyperbola method of position fixing (Figure 1), where the difference in phase (which is a function of distance) of signals from a number of transmitters are compared, and hence the position of the user determined. The loci of points of equal difference in distance between any two transmitters trace out a hyperbola. The intersection of two such hyperbola - formed from two pairs of transmitters - gives the location of the user. This is an important concept as it is analogous to the method employed by the Navstar GPS system.

    GPS

    Fundamentals

    In the early 1960's the American Navy Navigation Satellite System (NNSS) was developed, using 'Transit' Satellites, to provide a global position fixing system for the US Navy's Polaris submarines. This system became fully operational in 1964, and was made available to the general public in 1967 by Presidential order [8]. The accuracy of position information made from the transit system was not very great, as it relied on the "Doppler" effect of a signal broadcast from a satellite as it passed overhead. As it changed from approaching the user, to receding from them, the frequency of the received signal would change (like the siren of a passing ambulance), hence the position of the user could be estimated. However, the satellites deployed for the system had no orbit correcting facility, and so with time they slowly drifted from there ideal orbits creating large gaps in reception.

    Figure 2: GPS Satellite Constellation.

    The DNSS Global Positioning System was conceived to supersede Transit. Again, to justify the costs involved, it was decided to allow non-military users access to the system.

    The space segment of GPS is 24 satellites (or Space Vehicles - SVs) in orbit about the planet (Figure 2) at a height of approximately 20 200 km, such that generally at least 4 SVs are viewable from the surface of the Earth at any time. This allows the instantaneous user position to be determined, at any time, by measuring the time delay in a radio signal broadcast from each satellite, and using this and the speed of propagation to calculate the distance to the satellite (the pseudo-range). As a 'rule-of-thumb', one individual satellite needs to be received for each dimension of the user's position that needs to be calculated. This suggests 3 satellites are necessary for a position fix of the general user (for the x, y, and z dimensions of the receiver's position), however, the user rarely knows the exact time which they are receiving at - hence 4 satellite pseudo-ranges are required to calculate these 4 unknowns.

    The satellite data is monitored and controlled by the GPS ground segment - stations positioned globally to ensure the correct operation of the system.

    Limitations

    When the decision was made to allow civilian use of the GPS network, a facility was included to deny full positioning accuracy. This is known as Selective Availability (SA), and became active on 4 July, 1991. It is implemented by only allowing public access to one of the two pseudo-random noise carriers used in modulating the data sent from each satellite (see Global Positioning System Overview for a further discussion of GPS signal modulation). This Coarse/Acquisition (C/A) code is simply used as a high powered, narrow band signal to lock onto the 3 dB weaker Precision (P) code. However, as the P code is generally encrypted (forming the Y code), civilian users can only access the C/A code. Both codes are transmitted by all satellites on a common frequency (L1), and the P (Y) code is also transmitted independently on a second frequency (L2) restricted for military use.

    The C/A code carries fundamentally the same information as the P code, only under selective availability the satellite orbit data (epsilon) or transmission clock frequency (dither) may have an artificial inaccuracy introduced. This provides a worse case accuracy of 100 m (95 % of the time) to Standard Positioning Service (SPS) users. This can be improved to about 15 m (95 %) for authorised Precision Positioning Service (PPS) users.

    There are other factors which introduce errors, such as timing errors, atmospheric distortion of signals, relativistic effect of fast moving satellites, and receiver noise and signal reflections. However, to the SPS user, SA is the major contributor to inaccuracy [6].

    For Mobile Robot navigation, accuracy of 100 m is generally only useful for a coarse position fix on the locality of the device - it is not exacting enough to allow precise movement through a mapped terrain, only give an indication of what area (e.g. which field) the AGV is in. Hence on its own GPS is not a complete AGV navigation solution.

    However, the benefits of using GPS are great. The accuracy provided is available continouosly 24 hours a day, at no usage cost, and near instantaneously (so long as there is reasonably little obstruction of the signal path, a 5º inclination view of the horizon in all directions is quoted as the ideal).

    Differential GPS

    Known as DGPS, differential GPS is category of methods by which the accuracy of GPS can be greatly improved. The concept is to calculate the current mean error in position fix at a known location, and then transmit a list of corrections which a mobile user can apply at any location at that point in time. It can easily be shown that this will nearly always overcome the errors introduced by Selective Availability, as well as helping to correct other inaccuracys in a given locale. DGPS comes in two main forms, local area and wide area.

    Local Area DGPS (LADGPS)

    Figure 3: A typical LADGPS system

    LADGPS operates by calculating a GPS position fix at a known location (the base station), and transmitting the difference in location data (longitude, latitude, height) to local users. It is important that this is only used when close to the base station as most error sources are spatially dependant, but more importantly as it is entirely dependant on which satellites are used to calculate the position fix, as each satellite has its own errors introduced by SA. If a different set of satellites is used to the base station, and the wrong corrections applied, then the resulting data will be further distorted - possibly producing worse resultants than standalone GPS.

    Wide Area DGPS (WADGPS)

    WADGPS overcomes the problems of Local Area GPS by calculating the errors in pseudo-ranges to each satellite individually. The error in distance to each can then be calculated (as the exact location of satellite and base-station are known), and these can be transmitted individually to mobile users. The user can then apply these correction to satellite delay timings before they calculate their position from this data, what ever satellite set they use and wherever they are on the globe (base-station communication permitting). This does however introduce further complications in correcting for atmospheric interference, as this varies with global position.

    Unlike GPS itself, there is not standard for implementing DGPS, however, most use a wide-area approach. Across the United States, and several other countries, the national Coast Guard have set up DGPS transmitters using already existing radio beacons [US Coast Guard Navigation Center]. Across many countries, including Britain there, is a commercial DGPS service - charging fees for access to the network [3]. The INMARSAT organisation - primarily concerned with maritime communications - are introducing a global DGPS system (part of the US Federal Aviation Administration's Wide Area Augmentation System (FAA WAAS)) relayed via their network of geostationary communications satellites [6].

    Differential GPS Applications

    As shown above, the most active advancements in DGPS service are for marine applications, with coast-line transmitters being installed. The FAA, in addition to WAAS, has a Local Area Augmentation System (LAAS) program under way centred on airports, which intends to provide aircraft landing assistance - due to be gin in 2002 [5]. The drive for commercial DGPS systems is led by the oil-exploration and surveying industries, which continually require high-precision measurements. For surveying purposes a specialised form of LADGPS can be employed, measuring the phase differences between points, to allow very high accuracy measurements (order of cm's).

    Error SourceTypical GPS Error DGPS Error,

    Ref-Remote < 100 km

    SV Clock40
    SV Ephemeris40
    Selective Availability40 0
    Troposphere40
    Ionosphere400
    Pseudo-Range Noise4 4
    Receiver Noise44
    Multipath22
    TOTAL (R.M.S.)606
    Table 1: Typical (estimated) Error Budget. [2]

    With all this development going into the area of DGPS, it forms a vary promising basis for Mobile Robot Navigation. The resolution provided (see Table 1 for a typical situation example), is approaching that required for adequately accurate navigation, and in the near future there could be several services providing a global DGPS.


    Future of Position Fixing

    GPS Developments

    In March 1996 the US President approved new guidelines for the management and use of GPS [4]. The new policy includes termination of the current practice of degrading civilian signals (SA) in the next decade, and to promote GPS as an international system for open peaceful use. As a result of this, the US DoT is looking into providing a second (non-encrypted) frequency for civilian use (dubbed L5); equivalent to the L2 frequency available to authorised users only.

    Beginning in the year 2000, the president will make annual determination on the continuation of SA on the current (Block II and IIA) satellites; the aim being to give the DoD sufficient time to prepare for non-exclusive access to the high precision signal. The second civilian frequency, the feasibility of which is currently being studied, would become active in the next generation (Block IIF) satellites, due for lunch from 2004 - following the current replenishment satellites (Block IIR), which are waiting to be lunched following a set back in January 1997. Current indications [5] are that the L5 frequency will actually be the old military L2 frequency. One reason for this is that many of the surveying techniques adopted actually use the phase information in the current L2 (with out the need to decrypt the restricting information), to provide high accuracy. This places pressure on the DoD not to alter the form of this channel (which it was considering, in increasing its power), hence the amiable solution is for the DoD to release this frequency for full civil use, and find new spectrum for its restricted transmissions

    The result of this will mean civilian users will have simple and reliable access to positioning information with sub 20 m accuracy, is a minimal sized receiver. The current augmentation systems (such as WAAS), will continue to be developed, to provide improved accuracy and system status/ failure redundancy information.

    The co-operation of the DoD and DoT in deciding to move military use away from the L2 frequency affirms the position of GPS with civillian users - in particular high-accuracy systems already using both frequencies.

    This sets to GPS provide a very comprehensive, accurate, and reliable position fixing service into the next century, which will put it in a firm position to be integrated into all forms of Autonomous Navigation systems.

    Other Developments

    The developments in DGPS are set to continue well into the next century, providing increased resolution to target user groups. The FAA's WAAS and LAAS augmentation schemes are set to be carried out in the near future - a White House Commission (12 February 1997) suggests that the completion date should be brought forward from 2012 to 2005 [5]. The aim being to provide high enough accuracy, even before the lifting of SA, to totally modernise the airspace system. In addition, it will provide greater redundancy, enhance the ability for users to cross check GPS accuracy and verify system reliability in critical systems.


    Between Position Fixes: Dead-Reckoning (DR)

    The aim here is to give a brief overview of the methods which can be employed in tracking an AGV's position in areas where only occasional (in the worst case, one) global position fixes are available: for example, in extremely built up areas, of when going underground. These methods rely on what is commonly known as dead-reckoning: given a known starting location, and a sequence of delta offsets (vectors), the position at any subsequent point in time can be calculated.

    Inertial Navigation Systems (INS)

    INS has been in use in aircraft as a primary source of (relative) position fixing since around the 1960s; one of the earliest demonstrations of the method was in the V2 rockets developed by German Scientists in World War II [9]. The principle is to measure any force (hence acceleration) applied to a body, and use the second order integral with respect to time to calculate position, given the initial position and velocity.

    The basic sensors for such a system are accelerometers, which provide a measure of acceleration in a single dimension, and the gyroscope, which provides a measure of rotational motion about an axis. Advances in the early 1970s led to much smaller and more reliable sensors being fitted directly to vehicles (in "strapdown" systems), rather than just accelerometers being used on large inertial platforms. Modern applications of the technology include missile and torpedo guidance, spacecraft and submarine navigation, and guiding underground tunnelling work.

    In principle INS allows, given a single starting co-ordinate (e.g. the airport's location), the vehicle's position at any time in the future to be known; with one limitation. All errors introduced to the acceleration and hence position while navigating are cumulative. That is, the longer the vehicle maintains movement after a position fix, the greater the inaccuray in the calculated position. The accuracy can be modelled as a fraction of the distance travelled, increasing from 0 (given an exact start location), and tending to infinity as the vehicle travels indefinitely.

    INS Integration with GPS

    By combining GPS and INS, defeciancies in both can be overcome. The idea is to have regular absolute position fixes, using GPS, and to track position in the interim using INS. In this situation the GPS provides short term accuracy, while the INS provides long term stabilty - complementing each other well to produce a sustainable navigational position. The outputs of both systems are compared and suitably filtered, and corrections made to either or both systems accordingly. One widely quoted filter for doing this is the Kalman filter, which combines two estimates and provides a weighted mean, using factors chosen to yeild the most probable estimate [6, 9].

    By adding INS capability to a GPS navigaion system, considerable improvemnts have been observed. Of particular interest is experiments reported present at the Instute of Navigation's Forty Ninth Annual Meeting [6], where a GPS/Dead-reckoning system was tested in many major urban areas. When tall buildings reduced satellite availability, the stand-alone GPS would use 3 satellites - assuming constant height from previous readings. This produced large inconsistencies where hills where encountered as well. However, the INS based GPS/DR system overcame this by only taking GPS fixes when full accuracy was attainable (i.e. 4 satellites in view). In between, the DR kept a very good estimate of position.


    Conclusions

    GPS on its own does not currently offer a sufficient navigation resolution to allow it to be used as a standalone global navigation method for mobile robots. A robot would typically work on a scale of 1 m ("human" scale device), whereas the reliable accuracy for GPS is only 100 m. This only allows GPS to act as a coarse position fixing aid, and then some other more localised method has to be used, with reference to landmarks or otherwise, to get an adequate position fix.

    However, there are several enhancements to GPS, both current and future, which may allow it to be more seriously considered in AGV navigation.


    References

    Bibliography

    1. Bock, Y., Leppard, N. (Eds.), 1990. Global Positioning System: An Overview. International Association of Geadesy Symposia. Springer-Verlag.
    2. Dana, P. H., 1995. Global Positioning System Overview. http://www.utexas.edu/
    3. Gray, T. GPS & DGPS Explained. Communication Systems International Inc. http://www.csi-dgps.com/
    4. Institute of Navigation, Summer 1996. ION Newsletter. http://www.ion.org/
    5. Institute of Navigation, Winter 1996. ION Newsletter. http://www.ion.org/
    6. Kaplan, Elliott D. (Ed.), 1996. Understanding GPS - Principles and Applications. Artch House Publishers.
    7. Linkwitz, K., Hangleiter, U. (Eds.), 1989. High Precision Navigation. Integration of Navigational and Geodetic Methods. Springer-Verlag.
    8. Tetley, L., Calcutt D., 1991. Electronic Aids to Navigation: Position Fixing. Edward Arnold.
    9. Titterton, D. H., Weston, J. L., 1997. Strapdown Inertia Navigation Technology. Peter Peregrinus for the Institution of Electrical Engineers.
    10. Toft, Hans, 1987. GPS Satellite Navigation. Shipmate Marine Electronics.

    Other WWW Sites