LINKMAN for Automatic Route Planning work
last updated 1630 Wednesday 9th April 2008
Hi Folks ! This page is for use by those working with me on work related to putting Automatic Route Planning (ARP) and Turn By Turn Guidance (TBTG) into GPSS and GPSS for the Pocket PC.
The big pictures below are taken from the GPSS.EXE that I am working on, with an updated LINKMAN tool. LINKMAN enables us to prepare small test files, of link and node data (see explanation further below), for countries where we do not have suitable data yet available. The data is made by clicking on a detailed map of the test area - typically near your home or office.
LINKMAN is also being used as a test harness to check out ARP/TBTG algorithms with both small samples of test data, and data from professional sources. i.e. much bigger files of real data - such as the free USA street mapping (see bottom picture).
Much of the explanatory information at the start is based on the very old ARP page. See also the Open letter to digital map data suppliers.
I'll start with the very old, explanatory information from 10 years ago, then finish with the latest information on LINKMAN and current ARP work.
A good example of an Automatic Route Planner (ARP) is Microsoft's Autoroute. Other examples include Route66. These programs are normally run 'on the desk' to plan the best route to take on a journey. The user enters his Start and End destination, and the program calculates the optimum route, based normally on minimum time or distance travelled.
This type of facility has been included within Car Navigation systems for several years, but availability of suitable map data has delayed widespread use outside Japan.
For an ARP to be of practical use in car navigation, it needs to have far more detailed data than that normally found with products such as Autoroute. i.e. it is not sufficient to hold major roads and junctions between towns: it needs to hold every street that the car might need to use within a large city. This is a large quantity of data. Provision of this data, for a particular country or city, is far more difficult than provision of suitable ARP software. Also, the ARP software must be designed to hold the required data in a form suitable to process it quickly.
The data needed to support an ARP is often described as 'link & node' data. This is because it simplifies the mapping of a country or city into a list of 'nodes' (locations of junctions between roads) and a list of 'links' (sections of road).
The important information about a node is its position (e.g. latitude & longitude). Other information held might include the type of feature (e.g. crossroads).
The important information about a link is the two nodes it connects. Note that most roads are two-way, and so there are two links. Other information might include the length of the section of road, and it's category - used to calculate the speed that can be travelled along it. The ARP will use this data when calculating the optimum route between two nodes.
See below the picture for details of LINKMAN use.
"Total cost to a node from the start node" are shown in red, below the node. Cost is in metres if "distance" is selected, or tenths of seconds if "time" selected.
Visited links and nodes are shown in cyan (light blue). If the ARP algorithm fails to visit nodes, they are shown in yellow.
Calculated Turn-By-Turn-Guidance is shown at each node. e.g. "turn left".
LINKMAN FOR USE BY THOSE IN DIRECT CONTACT WITH ROBIN.
LINKMAN is a very simple and austere means of creating Link and Node data by clicking on detailed maps.
Before creating your own local maps for LINKMAN use, or your own sample link and node data, it is reccomented that you download and add the test data from ARPDATA.EXE and familiarize yourself with how LINKMAN behaves - and misbahaves - with this data.
For local work in your own country, you will need at least one detailed GPSS map, for the (small) area in which you will be making link and node data.
The map should preferably be of the same bitmap size as the screen you are using for GPSS. e.g. 1024x768. This is because the old logic to display the links and nodes will only appear briefly if the sizes are different.
Run GPSS, select the required background map, and start LINKMAN by clicking the [LINKMAN] button on the Ctrl-C experimental page.
A small form will appear similar to that in the low right corner of the picture below.
The [N or L] button, when clicked, cycles between three states:
The button [INDEX] should be left as it is. When clicked it switches between [INDEX] and [VALUE] effecting the file saved by [OUTPUT].
To create nodes, simply click on the map (with [+NODE] selected).
If you wish to label the node
with a category such as JR=roundabout from GPSS.CAT, change J to JR
before you click. Clicking on the map will append lines of data into NODES.TXT
in the following format:
to create links between nodes, first switch over to 'Link Entry Mode' by
clicking on the +NODE button to select [+LINK]. The text field
J will switch to
This means 2 = two way road, R = road from GPSS.CAT, name of road.
To create a link, first choose the start point by pointing at a node, then
clicking with the left mouse button. Then point to the end node and click
with the right mouse button. Link data will be added to file LINKS.TXT:
51.396730 -000.660303,51.396770 -000.660519,2,R,Armitage Court
- link from 51.396730 -000.660303 to 51.396770 -000.660519, 2-way, road, named "Armitage Court".
You can change the default "another road" to the road name if you wish. (e.g. "Armitage Court") before you click on the map to add the link.
[OUTPUT] outputs the data within NODES.TXT and LINKS.TXT to NODELINK.TXT which is the file to be imported into experimental ARP logic. The data is saved into LINKNODE.TXT in a different format (lat/lon values instead of node numbers) if the earlier button is [VALUE] - not reccomended or supported.
LINKMAN sorts nodes into ascending values of latitiude, and nodes into ascending start node number before output to NODELINK.TXT which is used by the experimental ARP algorithm under the [PLAN] button.
NODELINK.TXT starts with explanatory text, followed by data:
NODELINK.TXT of 12:17:28 on 01-16-2008 holds 28 nodes (NNODES) and 54 links (NLINKS).
After NNODES and NLINKS there is the list of nodes, sorted by latitude. N,LOC,CAT.
Next the list of links for 1..NLINKS: N, NODEFROM, NODETO, CAT, DIST, NAME. Sorted by NODEFROM.
Next for 1..NNODES the first link for that node. NODE, FIRSTLINK.
[SHOW] shows the raw data in NODES.TXT and LINKS.TXT
[5. Street] sequences through link types, which effect speed along the link (if used). It is used when creating LINKS.TXT to specify the type of road.
1. Motorway(70)..... 10. Slow path(1). The number in brackets is typical speed in mph.
[OUTPUT] process scans the nodes in NODES.TXT
to replace the lat/lon by a node number, for saving into NODELINK.TXT
[PLOT] plots the contents of NODES,TXT, LINKS.TXT and NODELINK.TXT onto the map. It also looks for the nearest nodes to GPS (car) and Destination positions.
[PLAN] runs the experimental ARP (Automatic Route Planning) code presently being tested*
* At the time of writing this I am working an ARP algoritm based upon that used many years ago on the Barossa Project.
* LINKMAN is only for use by those working closely with Robin.
By April 2008 the ARP algorithm in LINKMAN was working well with sample data for New York,USA and the whole island of Corfu, Greece. At the time of writing this, Corfu tests of TBTG on Pocket PC are in progress. Recent buttons added include [DoALL}, [toRGD] and [PlotRGD], all related of making data for use by GPSSppc.
The default files used are NODES.TXT,LINKS.TXT and NODELINK.TXT but now you can switch between different sets of data with the [>] button.
This will sequence from NODES.TXT, NODES1.TXT.... NODES9.TXT and back to NODES.TXT.
I've added sample data for NODES1.TXT and NODES2.TXT (more around Sunninghill area), NODES3.TXT (small sample for New York, USA), and NODES4.TXT - a larger sample of 10km x 10km near New York holding 7923 nodes and 23200 links.
If you are creating your own local samples, I suggest you start in NODES9.TXT and work downward.
When the [>] button is used, and files are found, it will move the car to NODES.TXT line 9 and the destination to line 13. Note these are NOT nodes 9 and 13 in NODELINK.TXT.
[SHOW] plots the raw data in NODES.TXT and LINKS.TXT
[OUTPUT] creates NODELINK.TXT
It also attempts to remove errors such as unused nodes.
[PLOT] plots NODELINK.TXT
[PLAN] runs the experimental ARP - with bugs of course :-)
It also makes PLAN.RGI with Route Guidance Instructions for Turn-By-Turn-Guidance.
keep straight on
keep straight on
keep straight on
turn left 51.397290 -000.660168,50,165,30,RGI$S.WAV,RGI$S
keep straight on
[MAKE] makes a sample of link and node data from USA street mapping VEC files.
You can now select "minimum distance" or "minimum time" for the ARP under [PLAN]
Checkbox "Trace" makes the ARP pause at each step - so you can see where it went wrong :-)
Checkbox "slow" makes the ARP run slowly, so you can see the pattern of (wrong) processing :-)
Checkbox "labels" allows you to switch on or off display of node and link numbers, costs, etc.
The [PLAN] button now outputs ARPDUMP.TXT to assist post mortems on
errors remaining in the ARP algorithm - or in data samples.
Typical contents are:
ARPDUMP.TXT output at 18:24:05 on 02-17-2008
Using NODELNK1.TXT with 28 nodes and 66 links.
Node 1 from node 2 via link 4 at cost of 67
Node 2 from node 5 via link 8 at cost of 54
Node 3 from node 1 via link 1 at cost of 83
Node 9 from node 10 via link 20 at cost of 20
Node 10 from node 14 via link 32 at cost of 0 NODE NEAR GPS
Node 11 from node 12 via link 28 at cost of 42
Node 21 from node 20 via link 47 at cost of 107
Node 22 from node 26 via link 63 at cost of 119 NODE NEAR DESTINATION
Node 23 from node 17 via link 40 at cost of 78
Node 28 from node 26 via link 62 at cost of 110
OK - all links were visited.
The latest Beta GPSS.EXE with LINKMAN is on the OLDNEW page, which also has the test data download.
Speak to Robin for the latest information.