Imperial College, London
information systems engineering year 2:
Surprise 1997
Imperial College Crest

Mobile Robot Navigation
Global Reference Navigation for Mobile Robots: Issues in Practical Implementation
Jonathan Dixon
27 May 1997

Contents

  • Abstract
  • Introduction
  • Ground Based RF Beacons
  • Overview
  • International Systems
  • Motorola Mini-Ranger Falcon
  • Harris Infogeometric System
    •
  • Differential GPS
  • Overview
  • Differential Correction Providers
  • DGPS Receivers
  • Phase Tracking Systems
  • Problems with DGPS
    •
  • The Global Reference
  • Conclusion
  • Bibliography
  • References
    •

    Abstract

    This document describes and reviews methods for navigating mobile robots, using commercially available systems, over medium sized areas. This will be carried out with a view toward practical mobile robot requirements, such as accuracy and reliability, and implementation constraints, such as size and power consumption.

    This document accompanies "An Overview of Global Mobile Robot Navigation: Global Positioning" (from here on referred to as Article 1), however, where that document focused on truly global techniques - which could operate at any point on the planet without previous preparation - this one will study global referenced navigating, with the possibility of being limited to a defined area.

    Introduction

    Industrial and commercial Automatic Guided Vehicles have been employed in warehouses and yards for years [Dowling, 1995]. Early mechanical systems rode on tracks, requiring major construction to install or alter routes. By the 1950s, electronic AGVs were following signal wires buried under the floor, which improved matters. In the 1980s microprocessors made possible autonomous AGVs with long-range sensors navigated by sparse arrays of beacons. This made them slightly less reliable to their predecessors. Although marginally cheaper than buried wires, these still required a specialist to reprogram for new routes.

    Debate is open about where the commercial robot market will move next; the two main areas of research are improving the local reference systems using processor intensive visual techniques, and refining the beacon based system, working on a global reference navigation system.

    This article will study the latter of these two, and attempt to trace where the current trends are leading. For the purposes of comparison, we will be assuming a medium size (order of 1 meter dimensions) autonomous robot requires navigation about a medium sized outdoor area such as a field (order of 10 km dimensions).

    Ground Based RF Beacons

    Overview

    Navigation using active beacons has been with us for many centuries. Using the stars for navigation is one of the oldest examples of global referenced navigation; technology has brought forward many other systems, such as lighthouses and, more recently, radio navigation.

    Beacon systems can be viewed as global reference systems. Although they can only immediately present a user with positioning information relative to that of the beacon system, if this point is known as a global location (i.e. it is a surveyed location), the global position of the user can easily be determined.

    As well as Radio Frequency (RF) beacons, laser and ultra-sonic (amongst others) beacons exist. We will only consider RF beacon systems here, however, as others tend to have greater line-of-sight requirements. Those restrictions imposed by RF (where a low amount of concealment between beacon and user is acceptable) are tolerable for our intended purposes - any greater restrictions are deemed too limiting (however, other beacons are considered for localised navigation [Henlich, 1997]).

    One disadvantage of RF systems, however, is that they are generally unsuitable for indoor use [Borenstein et al., 1996]. This is due to a combination of attenuation of signals by obstacles, and the multipath introduced by multiple reflections of RF off of walls and other surfaces.

    There are two basic types which RF beacons can be separated into: continuous broadcast beacons and interrogation response beacons. With the former type of system the user constructs hyperbolic line-of-positions using the difference in phase of signals received from two pairs of continuously broadcasting transmitters [Tetley, 1991]. With the second the round trip propagation delay time from user to beacon and back to user (or vice-versa; generally in position monitoring rather than navigation situations) is measured - analogously to radar operation - to determine range.

    International Systems

    As introduced in Article 1, there are several well established international RF navigation systems in use today; all of them using a continuous broadcast hyperbola method; Loran-C is an example of these. Loran-C was introduced in the early '80s to replace Loran-A (an older, lower power system). It was originally designed for naval applications, and today the best coverage is in coastal areas; near to transmitters, accuracy of around 100 m is achievable. There are several problems with this system with respect to out chosen application; As a result, this system can not really be viewed as a viable basis for current and future robot navigation. However, the principles of the Loran system can be employed in more specialised systems which might be more suitable for our purposes.

    Motorola Mini-Ranger Falcon

    A proprietary commercial positioning system available is the Mini-Ranger Falcon series produced by Motorola, Inc. This operates using a radar like approach, where a number of transmitter sites are interrogated by a user, measuring round trip delays, and hence calculating their range from each. The separation distance, or range, R, is calculated by

    R = ((tr - tt - tp).c) / 2,

    where

    tt = time of transmitted interrogation,

    tr = time reply received,

    tp = internal propagation delay of beacon (found empirically),

    c = speed of light.

    Example Beacon geometry with (a) two beacons, (b) three beacons.Figure 1: Possible user positions at the intersect of circles when range to (a) two, and (b) three, transmitters is known.

    The range to any given transmitter maps out a circular loci of possible positions of user around the site; the interception of two or more of these loci gives the position of the user. Figure 1 shows how increasing the number of transmitters increases the assurance of position fix. Up to 16 beacon ranges can be used in determining position; due to random errors introduced, they will not all coincide exactly on a single point, hence the least squares method is used to reduce combined differences to a minimum. The system must be calibrated by measuring the turn-around delay for each beacon from a number of known locations, which future position fixes will be relative to. If these positions are known in global co-ordinates, then this becomes a global referenced system as required.

    This system quotes an attainable accuracy of 2 m, over ranges up to 75 km. The system can be time shared by up to 20 mobile users, each obtaining position fixes at a 1 Hz update rate. Possible problems which this system might introduce when employed in mobile robotics are:

    Also there is the issue of surveying the global reference calibration points for the system, discussed below.

    Harris Infogeometric System

    This is another commercially system, developed by Harris Technologies, Inc. [Borenstein et al., 1996]. This system provides both navigation positioning information to each user, and data communications between users. Positioning is provided by a number of stationary beacons, continuously transmitting a time-stamped signal according to an internal highly accurate clock. The mobile users employ code-division multiple-access (CDMA) spread-spectrum modulation which allows simultaneous inter-user communications so that each device has a full image of all others on the network.

    Precision positioning is provided by range trilateration from the beacons, using a technique similar to GPS. With the Harris system, however, each mobile user carries a high precision clock, synchronised to that in the beacons, so that the difference in time between a signal being transmitted and received equates directly to the distance between them. As with the Motorola system, at least three beacons should be accessible for optimal two dimensional positioning .

    The accuracy of the system is enhanced by automatic use of the mutual data communications for time synchronisation and range correction purposes. Each mobile user can correct their own internal clock according to the user or beacon closest (least propagation distance) to them. Given random motion of users over time, and careful processing of clock corrections, this can facilitate the complete synchronisation of clocks to a central reference. In addition, access to measurement of range errors made by fixed stations allows other users to perform additional corrections. Using these techniques reported accuracy is improved from a number of meters to a fraction of a meter [Borenstein et al., 1996]. Power requirements of the system are low, with 100 mW peak power transmitters providing position fixes in ranges up to 500 m.

    Again, the major disadvantage of the system is the requirement for a number of precision sites, contributing towards costs considerably; the cost of a minimum system specification system is around US$ 30 000.

    Differential GPS

    Overview

    Under Simple Positioning Service (SPS), the US Navstar Global Positioning System (GPS) does not provide enough accuracy to be individually useful for mobile robot navigation, as discussed in Article 1. However, when augmented by the benefits of Differential techniques, GPS does become a viable method for global reference navigation.

    DGPS operate by receiving the satellite broadcast GPS signal at a known site, and then transmitting a correction according to the error in received signal, to mobile GPS users. So long as the mobile user is in the proximity of the stationary site, they will experience similar errors, and hence require similar corrections. Typical DGPS accuracy is around 4 to 6 m, with better performance seen as the distance between user and beacon site decreases.

    Differential Correction Providers

    DGPS availability is constantly increasing, through a number of different means. In the US, as well as several other countries, the National Coast Guard is implementing DGPS around the coast lines and in particular in major harbours, with an expected accuracy of 1 m. There are several schemes world-wide in progress to provide DGPS corrections over FM links to paying users. The FAA WAAS (using INMARSAT) and LAAS (localised to airports) schemes will provide increased DGPS coverage, primarily for aviation users, globally and locally to airports respectively.

    If necessary, it would also be possible to set up a private localised system. The cost of a commercial reference station is somewhere between US$ 10 000 and US$ 20 000, however, there are only a few requirements for a minimal site suitable for navigation:

    In mobile robotics a data link to the robot is often already present for other purposes; surveying a position is discussed later. The resultant system has a lower marginal cost, up to about US$ 5 000.

    DGPS Receivers

    A great number of modern commercial GPS receivers and OEM development modules come with differential correction capability, of which almost all follow the RTCM-104 standard for interfacing with the DGPS receiver and network [RTCM, 1994]. This allows a GPS receiver to be used according to requirements, and DGPS correction signals from any appropriate source to be used by connecting the relevant DGPS receiver.

    An example of a commercial DGPS receiver is the Communication System International CSI SBX-1. This is a so called OEM module, designed to be integrated into another manufacturers system: ideal for mobile robot construction. It is rated at less than 1 W at 5 VDC, and measures a mere 10 cm2. Coupled with a suitable GPS receiver (typically having somewhat high requirements; e.g. 10 W, 20 cm2) this would provide a good ground for mobile position fixes.

    Phase Tracking Systems

    One area of DGPS development that has a bearing on mobile robot navigation is its use in surveying. In the past this has mostly been static in nature, with a great deal of GPS data being processed off site after the event (post-processing). This is changing, however, as new methods are developed using high precision tracking of the phase information of GPS signal (rather than the data transmitted in the code). With complex algorithms becoming available in firmware on receivers, this processing can be carried out in real-time, allowing moving - or kinematic - surveying. Technology suitable for high precision real-time surveying is also very applicable to many forms of mobile navigation [Linkwitz, 1989], including of robots.

    The L1 frequency, 1575.42 MHz, corresponds to a wavelength of about 20 cm. By measuring the phase changes in this signal, and also those on the L2 frequency on a number of modern receivers, the movement of the user can be calculated to an accuracy in the order of cm. The use of the L2 frequency is possible, albeit very complex, without knowledge of the (DoD encrypted) PRN code used on it [Cosentino, 1996]. By using both frequencies, a lock on the difference of the wavelengths (known as the wide lane), can be obtained much more quickly; making this useful for mobile navigation.

    These techniques still rely strongly on DGPS (generally), as the phase information can only indicate changes in position of the user relevant to the satellites; not absolute (global reference) position. Hence the starting position must be accurately known - this can be found, in part, by the DGPS methods described previously.

    Problems with DGPS

    The following GPS problems still exist when differential methods are employed, and must be overcome by other techniques,

    The Global Reference

    One area that has been assumed in the previous chapters is obtaining the fixed global reference of the beacons employed in the various systems. The aim is to obtain highly accurate global reference for stationary site, from which to compose the global position of mobile users. This is basically a small baseline static survey.

    One of the simplest methods is to use static GPS, Wide area DGPS, or Local Area DGPS (depending on availability), into which a great deal of experimentation has been carried out [Beutler, 1989][King, 1989]. The primary factors in achieving high precision results were found to be,

    The long tracking time helps increase accuracy in a number of ways. Advanced GPS receivers can average out variations in position fix location - as any variance must be due to errors (particularly selective availability), which tend to average to zero over time. Also, as satellites pass by with time, Doppler theory can be applied to the received signal's frequency variations to improve accuracy.

    Conclusion

    When considering positioning systems for mobile robots, there are a large number of variables that must be considered, including With the current high growth in GPS technology and the GPS market as a whole, GPS - especially with differential corrections - looks set to become an ever more viable option for mobile robotics.

    On price DGPS is hard to beat, due to the massive investment already sunk by the US Government into the project, resulting in minimal user outlay requirements. With the enhancements described, its accuracy can be made to match many other systems. At the time of writing, indications [IoN Newsletter, Winter 1996] are that the L2 frequency is due to become publicly accessibly early next century, resulting in higher accuracy achievable in even smaller packages.

    Bibliography

    References

    Borenstein, J., Everett, H. R., Feng, L., 1996. Navigating Mobile Robots: Systems and Techniques. A K Peters, Wellesley, MA..

    Cosentino, R. J., Diggle, D. W., 1996. Differential GPS. Understanding GPS.

    DoD/DoT, 1995. 1994 Federal Radionavigation Plan. Spring-field, VA, National Technical Information Service.

    Dowling, K., 1995. History of the MRL. The Mobile Robot Laboratory, Carnegie Mellon University.

    Institute of Navigation, Winter 1996. ION Newsletter. http://www.ion.org/

    Kaplan, Elliott D. (Ed.), 1996. Understanding GPS - Principles and Applications. Artch House Publishers.

    Linkwitz, K., Hangleiter, U. (Eds.), 1989. High Precision Navigation. Integration of Navigational and Geodetic Methods. Springer-Verlag.

    Linkwitz, K., Wolfgang, M., 1989. Navigational Methods of Measurement in Geodetic Surveying. High Precision Navigation: Proceedings of an International Workshop, Stuttgart and Altersteig May 1988.

    Radio Technical Commission for Maritime Services Special Committee No. 104. RTCM Recommended Standards for Differential NAVSTAR GPS Service, Version 2.1. RTCM, Washington DC, 1994.

    Tetley, L., Calcutt D., 1991. Electronic Aids to Navigation: Position Fixing. Edward Arnold.

    Titterton, D. H., Weston, J. L., 1997. Strapdown Inertia Navigation Technology. Peter Peregrinus for the Institution of Electrical Engineers.