Mapping System

The Sensor Hub has a low-definition digital map of its operating area. That map is a directed graph of intersections. The files system on the SD card is organized at the original PC MS-DOS system: file names of up to 8 characters, a dot, and an extension of up to three characters.

Master File

The master file is named MAP_DEFS.TXT It may look like this:

47.758949, -122.190746, UWB_CAMP.TXT

47.6213 , -122.3509 , SEATTCEN.TXT

47.662 , -122.115 , MARYMOOE.TXT

47.660 , -122.185 , BRIDLETR.TXT

47.760854, -122.190033, UWB_SCCR.TXT

49, 8, CARLA.TXT

The first two numbers are the latitude and longitude of the origin of the map file. The third item is the name of the file. When the robot powers up, it will acquire a GPS fix for its present position. It will find the closest latitude and longitude to its position and load that file.

Local Maps

For instance, the first few entries of MARYMOOE.TXT are

 -775855,  -78948, 1 ,  END,  END,  END,  1, 1, 1, 1
 -598367,   16679, 0 ,   2 ,  END,  END,  1, 1, 1, 1
 -426121,  137882, 3 ,   17,   19,  END,  1, 1, 1, 1
 -345240,  149001, 4 ,   18,  END,  END,  1, 1, 1, 1
 -216431,  154561, 18,   15,    5,  END,  1, 1, 1, 1
 -34449,   174576, 4 ,   6 ,   14,  END,  1, 1, 1, 1
 89118,    116792, 5 ,   7 ,   13,  END,  1, 1, 1, 1
 148281,   165680, 6 ,   8 ,   12,  END,  1, 1, 1, 1

Each line corresponds to one of the numbered intersections (nodes) in the figure, starting at 0 and increasing by 1. The fist number is the distance north from the origin in millimeters (or distance south for a negative number). The second number is the distance east in mm if positive or distance west if negative. The third, forth, fifth and sixth numbers are the nodes connected to the present node, or "END" if none. An intersection of more than four ways can be handled by introducing a helper node at the same location.

Distances are given in mm so that they can be stored in a 32-bit integer and will not overflow until the distance is over 2147 km. Arithmetic in integers is much faster than floating point, especially on micro-controllers that do not have hardware floating point.

The last four numbers are the relative costs of the paths linking the nodes. Path planning is done with A*, which makes the assumption that the distance between nodes is Euclidean. If this is not the case, due to road curvature or speed restriction, the multiplier should be modified.

The vehicle will find a path that goes from node to node until it reaches the destination that was entered. To do so, it finds the closest road (where roads are the lines connecting nodes and takes the shortest path to that road. It then follows the road network from node to node until it gets close to the destination. If the destination is not on a road, the vehicle will follow a path to the origin that is perpendicular to the nearest road.

The map should be laid out to give preferred robot paths that do not contain any fixed obstacles. Nodes should be provided to approximate road curvature.

Enhanced Mapping

This basic map structure should be augmented by a secondary file that describes the road. This supplemental file may include road curvature, number of lanes, lane width, lane markings, and speed.

The SD card has a simple files system where only one file can be open at a time. After MAP_DEFS.TXT is read, that file is closed, and the file for the directed graph is read into memory and then closed. A road supplemental file could be read as needed.

Cubic Splines

The nodes in the directed graph are of class Waypoint. A Waypoint may contain more information than just its location. In the implementation as of August 2020, Waypoints are connected by straight lines, which produces discontinuities where they join. In the original design, Waypoints were connected by cubic splines (Hermite Curves; see James Foley et al. "Introduction to Computer Graphics" for a good summary). Cubics are infinitely differentiable and are widely used to fit smooth curves. The main practical difference between a line segment and a cubic is that the line is specified by its two endpoints, but the Hermite curve also requires the tangents (directions) at the endpoints. The cubic connecting two intersections will be different if one is required to approach from the west or from the south; the line segment would be identical. Bezier curves are similar to Hermite curves. Both have four control points. The Bezier curve has two control points not on the curve that are used to shape it. There is a simple matrix transformation relating the Bezier and Hermite curves.

Latitude and Longitude

Global positions on the earth are given in spherical coordinates:

• Latitude - angle between the north (90) and south (-90) poles
• Longitude - angle east or west of Greenwich.
• Radius of the earth (meters)

Since the Elcano system is designed to operate in a small area, it is not concerned about great circle routes for intercontinental distances. Instead it makes the approximation that the earth is locally flat. It sets an origin for the area in which it operates, and sets up a coordinate system (x,y) where positive x is distance east of the origin and positive y is distance north. Distances are internally stored in mm, and can be easily displayed in meters. The distance represented by one degree of longitude varies from 111 km at the equator to 0 at the poles. The size of a degree of longitude depends on the cosine of the latitude.

Given a (latitude, longitude) its map position as (east_mm, north_mm) is given by

north_mm = (latitude - latitude_of_map_origin) * earth_radius_mm

east_mm = (longitude - longitude_of_map_origin) * cos(latitude_of_map_origin) * earth_radius_mm