Navigation System

Elcano Navigation System

The Elcano robot design is built on several communicating microprocessors, including modules for path planning, localization, piloting and vehicle control. There is no central computer in the system. Localization is done by the Navigation system, which consists of a microcontroller and sensors to determine the position of a mobile robot. Elcano is designed for outdoor use, but could also be used indoors. Elcano assumes that it has a map of its environment, and uses landmarks on the map and the intended trajectory to refine the position estimate provided by the instruments of the Navigation System. All code is written in the C++ dialect supported by Arduino.

The Navigation System as currently implemented consists of

  • GPS system

  • Sonar sensors for landmark or obstacle detection.

  • Hall effect odometer

  • Kalman fiter to include dead reckoning and sensor integration.

The Navigation System is expandable to include

  • Inertial Measurement Unit (IMU) aka Inertial Navigation Unit (INU)

  • Digital compass

  • Visual odometry from an optical mouse or camera

Other sensors, such as a camera for landmark recognition, would not be part of the Navigation System, but would be handled by the microprocessor reading the map. The Navigation System exports a serial string giving the robot position and velocity, as well as object range and bearings found from the sonars.

The Navigation System is currently implemented on an Arduino Mega. Hardware is documented in Elcan_BOM. The base GPS system is about $150. Documentation and software are on http://sourceforge.net/projects/urbanchallenge

Documentation:

NavigationSystem (This document).

Wiring_C6Mega.xls

Navigation sheet of Elcano_BOM .

Copy the following software files to an Elcano_C6_Navigator directory:

Elcano_C6_Navigator.ino; add new tabs with the following names and copy contents

C6_IO.h

GPS.cpp

GPS.h

KalmanFilter.cpp

Matrix.cpp

Matrix.h

Arduino serial lines are assigned as:

0: Monitor

1: INU

2: Tx: Estimated state;

$ESTIM,<east_mm>,<north_mm>,<speed_mmPs>,<bearing>,<time_ms><positionStndDev_mm>*CKSUM

$OBSTCL,<number>,<obstacle1_range_mm>,<obstacle1_bearing>, …*CKSUM

Rx: Desired course

3: GPS

Rx: $GPRMC,… typically 68 characters

$GPGSA,…

$GPGGA,… typically 68 characters

Tx: $PSRF103,…

Sensed navigation information is passed to C3/C4, which use preexisting or SLAM

digital maps, landmarks and intended path to refine the estimated position.

C3/C4 may use a particle filter.

C3/C4 may also receive lateral lane deviation from a camera (C7).

The odometry sensor is one dimensional and gives the position along the

intended path. Lane deviation is also one dimensional and gives position

normal to the intended path. Odometry, lane following and a digital map

should be sufficient for localization. An odometer will drift. This drift

can be nulled out by landmark recognition or GPS.

An alternative to the Kalman Filter (KF) is fuzzy numbers.

The position estimate from most sensors is a pair of fuzzy numbers.

[Milan Mares, Computation Over Fuzzy Quantities, CRC Press.]

A fuzzy number can be thought of as a triangle whose center point

is the crisp position and whose limits are the tolerances to which

the position is known.

GPS provides a pyramid aligned north-south and east-west, in contrast to

odometry / lane deviation, which is a pyramid oriented in the direction of

vehicle motion. The intersection of two fuzzy sets is their minimum.

By taking the minima of all position estimate pyramids, we get a surface

describing the possible positions of the vehicle, which can be used by a

particle filter.

The Navigation System is an independent unit that does not require a PC or other microprocessors. It can be used to collect the digital maps used by Elcano. A self-contained Navigation System can be carried over the preferred routes. It will log the positions and range to obstacles at points on this route. The information is written to an SD card in a file named for the current date and time. The text is comma separated values (.csv). The SD card can be placed in a laptop and read by a spreadsheet to analyze data and generate graphics. The data can then be processed by software to generate a map of the area in which Elcano will be operating. Elcano avoids simultaneous localization and mapping (SLAM). Most areas of the world are mapped, and Elcano assumes that it has access to a good map.

The Navigation System is designed for Arduino, on which both a float and a double have about 6 digits of accuracy. Latitudes and longitudes are represented as decimal numbers, and would require 9 digits of precision. Thus, latitudes and longitudes are represented as long integers, with 6 digits following the virtual decimal place. We assume that the earth is flat in the region of interest, and define an origin. Latitude is converted to a distance north of the origin in millimeters; longitude is the distance east of the origin in millimeters. If the robot travels more than 2000 km, it will need to redefine the origin.

NavigationSystem_html_m7c072186

Open Source Autonomy