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
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)
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
NavigationSystem (This document).
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
Arduino serial lines are assigned as:
2: Tx: Estimated state;
Rx: Desired course
Rx: $GPRMC,… typically 68 characters
$GPGGA,… typically 68 characters
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
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.