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.

from November 1998 UK Time ...

What is an ARP ?

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.

What is 'Link & Node' Data ?

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.

LINKMAN material updated in 2008 ...

LINKMAN facility in GPSS

LINKMAN history ...

See below the picture for details of LINKMAN use.

LINKMAN display ...

"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 use ...

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:

• [N or L] left clicks on map move the destination and right clicks move the car.
• [+NODE] left clicks on the map add a node to NODES.TXT based on the mouse position.
• [+LINK] left clicks specify the start of a link, and right clicks the end of a link. Each right click results in an update to LINKS.TXT with the links being added. Note: at present all roads are assumed two-way, and so for each right click, two links are added, for each direction between the two nodes.

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:
51.396730 -000.660303,J

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
,2,R,another road
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:

e.g.

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.
28
54
1,51.396730 -000.660303,J
2,51.396730 -000.660121,J
etc,etc.
27,51.397580 -000.660126,J
28,51.397580 -000.659266,J
1,1,3,2,R,0.013,another road
2,1,2,2,R,0.013,another road
etc,etc.
53,27,18,2,R,0.013,another road
54,28,26,2,R,0.013,another road
1
3
5
etc,etc.
53
54

[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
e.g.
3,10,15,2,R,0.032,Armitage Court
4,15,10,2,R,0.032,Armitage Court

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

recent notes from 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.
e.g.
51.397020 -000.660078,50,82,30,RGI$S.WAV,RGI$S
keep straight on
51.396960 -000.659827,50,111,30,RGI$TL.WAV,RGI$TL
turn left
51.397030 -000.659766,50,29,30,RGI$S.WAV,RGI$S
keep straight on
51.397320 -000.659776,50,359,30,RGI$TL.WAV,RGI$TL
turn left
51.397350 -000.660049,50,281,30,RGI$S.WAV,RGI$S
keep straight on
51.397370 -000.660203,50,282,30,RGI$TL.WAV,RGI$TL
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:
e.g.
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
etc, etc
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
etc, etc
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
etc, etc
Node 28 from node 26 via link 62 at cost of 110
testing links...
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.