Mapping System - Revision history

Tfolsom at 19:45, 6 August 2020

2020-08-06T19:45:02Z

Tfolsom at 19:16, 6 August 2020

2020-08-06T19:16:40Z

Tfolsom at 00:25, 5 August 2020

2020-08-05T00:25:35Z

Tfolsom at 00:19, 5 August 2020

2020-08-05T00:19:31Z

Tfolsom at 00:08, 5 August 2020

2020-08-05T00:08:57Z

Tfolsom at 00:01, 5 August 2020

2020-08-05T00:01:50Z

Tfolsom: Created page with "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 origi..."

2020-08-04T23:50:19Z

Created page with "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 origi..."

New page

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.

The master files 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.

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, END, 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.

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.

@@ Line 52: / Line 52: @@
 ==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 east; the line segment would be identical.
+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.

@@ Line 1: / Line 1: @@
 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.
-The master files is named MAP_DEFS.TXT
+==Master File==
 It may look like this:
@@ Line 18: / Line 19: @@
 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.
 For instance, the first few entries of MARYMOOE.TXT are
@@ Line 35: / Line 38: @@
 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 1000 km. Arithmetic in integers is much faster than floating point, especially on micro-controllers that do not have hardware floating point.
+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.
@@ Line 43: / Line 46: @@
 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.
 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.

← Older revision		Revision as of 00:01, 5 August 2020
Line 34:		Line 34:

	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 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.
		+
		+	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.

@@ Line 25: / Line 25: @@
    -426121,  137882, 3 ,   17,   19,  END,  1, 1, 1, 1
    -345240,  149001, 4 ,   18,  END,  END,  1, 1, 1, 1
-   -216431,  154561, 18,   15,  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
 ,    116792, 5 ,   7 ,   13,  END,  1, 1, 1, 1
 ,   165680, 6 ,   8 ,   12,  END,  1, 1, 1, 1
-[[File:Marymoor.png]]
+[[File:Marymoor.PNG]]
 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.